Re: SHA1 collisions found

[Linus Torvalds <torvalds@linux-foundation.org>]

On Tue, Feb 28, 2017 at 11:52 AM, Shawn Pearce <spearce@spearce.org> wrote:
>
>> 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