Re: SHA1 collisions found

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Feb 28, 2017, 23:11 UTC
Message-ID: <CA+55aFwjzbhYyFm_MqL=cDZZeKbSjqd-jSeb0yW_bJ_WQTzEpA@mail.gmail.com>
In-Reply-To: <259cc328-13f7-2d2d-c86f-8b4fc7da8e34@cwi.nl>

On Tue, Feb 28, 2017 at 2:50 PM, Marc Stevens <marc.stevens@cwi.nl> wrote:

Show 5 quoted lines

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

Show 6 quoted lines

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

Show 5 quoted lines

> 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