Re: SHA1 collisions found

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

On Tue, Feb 28, 2017 at 2:50 PM, Marc Stevens <marc.stevens@cwi.nl> wrote:
>
> Because we only have 32 disturbance vectors to check, we have DVMASKSIZE
> equal to 1 and maski always 0.
> In the more general case when we add disturbance vectors this will not
> remain the case.

Ok, I didn't get why that happened, but it makes sense to me now.

> Of course for dedicated code this can be simplified, and some parts
> could be further optimized.

So I'd be worried about changing your tested code too much, since the
only test-cases we have are the two pdf files. If we screw up too
much, those will no longer show as collisions, but we could get tons
of false positives that we wouldn't see, so..

I'm wondering that since the disturbance vector cases themselves are a
fairly limited number, perhaps the code that generates this could be
changed to actually just generate the static calls rather than the
loop over the sha1_dvs[] array.

IOW, instead of generating this:

        for (i = 0; sha1_dvs[i].dvType != 0; ++i) {
                .. use sha1_dvs[i] values as indexes into function arrays etc..
        }

maybe you could just make the generator generate that loop statically,
and have 32 function calls with the masks as constant arguments.

.. together with only generating the SHA1_RECOMPRESS() functions for
the cases that are actually used.

So it would still be entirely generated, but it would generate a
little bit more explicit code.

Of course, we could just edit out all the SHA_RECOMPRESS(x) cases by
hand, and only leave the two that are actually used.

As it is, the lib/sha1.c code generates about 250kB of code that is
never used if I read the code correctly (that's just the sha1.c code -
entirely ignoring all the avx2 etc versions that I haven't looked at,
and that I don't think git would use)

> Regarding the recompression functions, the ones needed are given in the
> sha1_dvs table,
> but also via preprocessor defines that are used to actually only store
> needed internal states:
> #define DOSTORESTATE58
> #define DOSTORESTATE65

Yeah, I guess we could use those #define's to cull the code "automatically".

But I think you could do it at the generation phase easily too, so
that we don't then introduce unnecessary differences when we try to
get rid of the extra fat ;)


> Note that as each disturbance vector has its own unique message differences
> (leading to different values for ctx->m2), our code does not loop over
> just 2 items.
> It loops over 32 distinct computations which have either of the 2
> starting points.

Yes, I already had to clarify my badly expressed writing on the git
list. My concerns were about the (very much not obvious) limited
values in the dvs array.

So the code superficially *looks* like it uses all those functions you
generate (and the maski value _looked_ like it was interesting), but
when looking closer it turns out that there's just a two different
function calls that it loops over (but it loops over them multiple
times, I agree).

                           Linus