Re: SHA1 collisions found

[Morten Welinder <mwelinder@gmail.com>]

The attack seems to generate two 64-bytes blocks, one quarter of which
is repeated data.  (Table-1 in the paper.)

Assuming the result of that is evenly distributed and that bytes are
independent, we can estimate the chances that the result is NUL-free
as (255/256)^192 = 47% and the probability that the result is NUL and
newline free as (254/256)^192 = 22%.  Clearly one should not rely of
NULs or newlines to save the day.  On  the other hand, the chances of
an ascii result is something like (95/256)^192 = 10^-83.

The actual collision in the paper has no newline, but it does have a NUL.

M.




On Thu, Feb 23, 2017 at 1:31 PM, Joey Hess <id@joeyh.name> wrote:
> Joey Hess wrote:
>> Linus Torvalds wrote:
>> > What you describe pretty much already requires a pre-image attack,
>> > which the new attack is _not_.
>> >
>> > It's not clear that the "good" object can be anything sane.
>>
>> Generate a regular commit object; use the entire commit object + NUL as the
>> chosen prefix, and use the identical-prefix collision attack to generate
>> the colliding good/bad objects.
>>
>> (The size in git's object header is a minor complication. Set the size
>> field to something sufficiently large, and then pad out the colliding
>> objects to that size once they're generated.)
>
> Sorry! While that would work, it's a useless attack because the good and bad
> commit objects still point to the same tree.
>
> It would be interesting to have such colliding objects, to see what beaks,
> but probably not worth $75k to generate them.
>
> --
> see shy jo