Sebastian MorrJust out of curiosity: Do you know of any attempts to construct a tree object that contains itself, that is, references it's own SHA-1?
Sebastian
threads / discuss / 29089
Yo dawg, I heard you like trees...
Subject: Yo dawg, I heard you like trees...
Sebastian Morr
Andrew ArdillRe: Yo dawg, I heard you like trees...
The difficulty in doing this is essentially the same as breaking SHA-1, so I doubt anyone has seriously tried to do it.
Regards,
Andrew Ardill
On 6 December 2011 10:57, Sebastian Morr <sebastian@morr.cc> wrote:
Show 9 quoted lines
> Just out of curiosity: Do you know of any attempts to construct a tree > object that contains itself, that is, references it's own SHA-1? > > Sebastian > -- > To unsubscribe from this list: send the line "unsubscribe git" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html >
Sebastian MorrRe: Yo dawg, I heard you like trees...
> Git uses a DAG. The A stands for "acyclic". Loops are not allowed.
I'm aware of that. It's acyclic by design, but is this actually enforced by the code? Or does it simply trust that no loops will ever occur, because it's so improbable?
After Andrew's response I investigated a bit, and it seems I overvalued the attempts to "break" SHA-1. Wikipedia quotes a 2008 attack, that can create a collision with 2^51 hash function calls.
Which, of course, is still way to much. Good for you! :-)
Jeff KingRe: Yo dawg, I heard you like trees...
On Wed, Dec 07, 2011 at 04:54:11PM +0100, Sebastian Morr wrote:
Show 5 quoted lines
> > Git uses a DAG. The A stands for "acyclic". Loops are not allowed. > > I'm aware of that. It's acyclic by design, but is this actually enforced > by the code? Or does it simply trust that no loops will ever occur, > because it's so improbable?
The latter. And not just "improbable", but "so improbable that trying to do it on purpose should still take billions of years".
Assuming sha1 isn't totally broken, of course.
> After Andrew's response I investigated a bit, and it seems I > overvalued the attempts to "break" SHA-1. Wikipedia quotes a 2008 > attack, that can create a collision with 2^51 hash function calls.
According to wikipedia, it _may_ produce collisions in 2^51 to 2^57.
Worrisome numbers, certainly, but 2^51 is probably within our ability to compute if a big project is undertaken. Yet to my knowledge nobody has actually created such a collision. So the attack is still theoretical at this point, and there's no good way to create a loop within the git DAG (or within a tree).
-Peff