{"thread":{"id":"29089","subject":"Yo dawg, I heard you like trees...","startedAt":"2011-12-05T23:57:41Z","lastAt":"2011-12-07T22:12:02Z","messageCount":4,"participants":["Sebastian Morr","Andrew Ardill","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"180324","messageId":"20111205235740.GB27318@thinkpad","threadId":"29089","inReplyTo":null,"subject":"Yo dawg, I heard you like trees...","fromName":"Sebastian Morr","fromEmail":"sebastian@morr.cc","sentAt":"2011-12-05T23:57:41Z","receivedAt":"2011-12-05T23:57:41Z","isPatch":false,"sender":{"key":"sebastian@morr.cc","avatar":"https://avatars.githubusercontent.com/u/81277?v=4"},"body":"Just out of curiosity: Do you know of any attempts to construct a tree\nobject that contains itself, that is, references it's own SHA-1?\n\nSebastian\n"},{"id":"180326","messageId":"CAH5451nfXe_W7QA-WFP-_-q7OryMzNgSrO4EWpqaP97YrspyKQ@mail.gmail.com","threadId":"29089","inReplyTo":"20111205235740.GB27318@thinkpad","subject":"Re: Yo dawg, I heard you like trees...","fromName":"Andrew Ardill","fromEmail":"andrew.ardill@gmail.com","sentAt":"2011-12-06T00:04:45Z","receivedAt":"2011-12-06T00:04:45Z","isPatch":false,"sender":{"key":"andrew.ardill@gmail.com","avatar":"https://gravatar.com/avatar/da14cb7c091dd44dc6c63a4d3361b149acaf25226dc78eb4131a17b93d9b0993?d=mp&s=160"},"body":"The difficulty in doing this is essentially the same as breaking\nSHA-1, so I doubt anyone has seriously tried to do it.\n\nRegards,\n\nAndrew Ardill\n\n\n\nOn 6 December 2011 10:57, Sebastian Morr <sebastian@morr.cc> wrote:\n> Just out of curiosity: Do you know of any attempts to construct a tree\n> object that contains itself, that is, references it's own SHA-1?\n>\n> Sebastian\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n>\n"},{"id":"180491","messageId":"20111207155411.GB2003@thinkpad","threadId":"29089","inReplyTo":"CABURp0rBkGtGfU=od2XeuhD6otUWUfL2ASqo1XBckra18WKy7w@mail.gmail.com","subject":"Re: Yo dawg, I heard you like trees...","fromName":"Sebastian Morr","fromEmail":"sebastian@morr.cc","sentAt":"2011-12-07T15:54:11Z","receivedAt":"2011-12-07T15:54:11Z","isPatch":false,"sender":{"key":"sebastian@morr.cc","avatar":"https://avatars.githubusercontent.com/u/81277?v=4"},"body":"> Git uses a DAG. The A stands for \"acyclic\". Loops are not allowed.\n\nI'm aware of that. It's acyclic by design, but is this actually enforced\nby the code? Or does it simply trust that no loops will ever occur,\nbecause it's so improbable?\n\nAfter Andrew's response I investigated a bit, and it seems I\novervalued the attempts to \"break\" SHA-1. Wikipedia quotes a 2008\nattack, that can create a collision with 2^51 hash function calls.\n\nWhich, of course, is still way to much. Good for you! :-)\n"},{"id":"180533","messageId":"20111207221202.GB21596@sigill.intra.peff.net","threadId":"29089","inReplyTo":"20111207155411.GB2003@thinkpad","subject":"Re: Yo dawg, I heard you like trees...","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-07T22:12:02Z","receivedAt":"2011-12-07T22:12:02Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 07, 2011 at 04:54:11PM +0100, Sebastian Morr wrote:\n\n> > Git uses a DAG. The A stands for \"acyclic\". Loops are not allowed.\n> \n> I'm aware of that. It's acyclic by design, but is this actually enforced\n> by the code? Or does it simply trust that no loops will ever occur,\n> because it's so improbable?\n\nThe latter. And not just \"improbable\", but \"so improbable that trying to\ndo it on purpose should still take billions of years\".\n\nAssuming sha1 isn't totally broken, of course.\n\n> After Andrew's response I investigated a bit, and it seems I\n> overvalued the attempts to \"break\" SHA-1. Wikipedia quotes a 2008\n> attack, that can create a collision with 2^51 hash function calls.\n\nAccording to wikipedia, it _may_ produce collisions in 2^51 to 2^57.\n\nWorrisome numbers, certainly, but 2^51 is probably within our ability to\ncompute if a big project is undertaken. Yet to my knowledge nobody has\nactually created such a collision. So the attack is still theoretical at\nthis point, and there's no good way to create a loop within the git DAG\n(or within a tree).\n\n-Peff\n"}]}