Re: SHA1 collisions found

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Feb 28, 2017, 22:56 UTC
Message-ID: <CA+55aFxG_5KU54KXZdTMC0p0EF5ixmv0C6ccjnYcPUeN_kDREA@mail.gmail.com>
In-Reply-To: <CAJo=hJuB9JkTZSRbhN2DX0gBqpjddU=Sk8iRV9++TYRv4xKA6Q@mail.gmail.com>

On Tue, Feb 28, 2017 at 11:52 AM, Shawn Pearce <spearce@spearce.org> wrote:

Show 5 quoted lines

>
>> and from what I can tell, the 'maski' value is always 0, so the
>> looping over 80 state masks is really just a loop over two.
>
> Actually, look closer at that loop:

No, sorry, I wasn't clear and took some shortcuts in writing that made that sentence not parse right.

There's two issues going on. This loop:

>   for (i = 0; sha1_dvs[i].dvType != 0; ++i)

loops over all the dvs - and then inside it has that useless "maski" thing as part of the test that is always zero.

But the "80 state masks" was not that "maski' value, but the "ctx->states[5][80]" thing.

So we have 80 of those 5-word state values, but only two of them are actually used: iterations 58 and 65). You can see how the code actually optimizes away (by hand) the SHA1_STORE_STATE() thing by using DOSTORESTATE58 and DOSTORESTATE65, but it does actually generate the code for all of them.

You can see the "only two steps" part in this:

  (sha1_recompression_step[sha1_dvs[i].testt])(...)

if you notice how there are only those two different cases for "testt".

So there is code generated for 80 different recompression step functions in that array, but there are only two different functions that are actually ever used.

Those are not small functions, either. When I check the build, they generate about 3.5kB of code each. So it's literally about 250kB of completely wasted space in the binary.

See what I'm saying? Two different issues. One is that the code generates tons of (fairly big) functions, and only uses two of them, the rest are useless and lying around. The other is that it uses a variable that is only ever zero.

So I think that loop would actually be better not as a loop at all, but as a "generated code expanded from the dv_data". It would have been more obvious. Right now it loads values from the array, and it's not obvious that some of the values it loads are very very limited (to the point of one of them just being the constant "0").

Anyway, Dan Shumow already answered and addressed both issues (and the smaller stylistic ones).

               Linus