Yo dawg, I heard you like trees...

Yo dawg, I heard you like trees...

[Sebastian Morr]

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

Re: Yo dawg, I heard you like trees...

[Andrew Ardill]

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:
> 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
>

Re: Yo dawg, I heard you like trees...

[Sebastian Morr]

> 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! :-)

Re: Yo dawg, I heard you like trees...

[Jeff King]

On Wed, Dec 07, 2011 at 04:54:11PM +0100, Sebastian Morr wrote:

> > 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