Re: SHA1 collisions found

On Tue, Feb 28, 2017 at 11:34 AM, Linus Torvalds
[off-list ref] wrote:

On Tue, Feb 28, 2017 at 11:07 AM, Junio C Hamano [off-list ref] wrote:

quoted

In a way similar to 8415558f55 ("sha1dc: avoid c99
declaration-after-statement", 2017-02-24), we would want this on
top.

There's a few other simplifications that could be done:

Yes, I found and did a number of these when I ported sha1dc to Java
for JGit[1], and it helped recover some of the lost throughput.

[1] https://git.eclipse.org/r/#/c/91852/

 (1) make the symbols static that aren't used.

     The sha1.h header ends up declaring several things that shouldn't
have been exported.

     I suspect the code may have had some debug mode that got stripped
out from it before making it public (or that was never there, and was
just something the generating code could add).

 (2) get rid of the "safe mode" support.

     That one is meant for non-checking replacements where it
generates a *different* hash for input with the collision fingerpring,
but that's pointless for the git use when we abort on a collision
fingerprint.

I think the first one will show that the sha1_compression() function
isn't actually used, and with the removal of safe-mode I think
sha1_compression_W() also is unused.

Correct.

Finally, only states 58 and 65 (out of all 80 states) are actually
used,

Yes, at present only states 58 and 65 are used. I cut out support for
other states.

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:

  for (i = 0; sha1_dvs[i].dvType != 0; ++i)
  {
    if ((0 == ctx->ubc_check) || (((uint32_t)(1) << sha1_dvs[i].maskb)
& ubc_dv_mask[sha1_dvs[i].maski]))

Its a loop over all 32 bits looking for which bits are set. Most of
the time few bits if any are set for most message blocks. Changing
this code to find the lowest 1 bit set in ubc_dv_mask[0] provided a
significant improvement in throughput.

The sha1_dvs array is indexed by maskb, so the code can be reduced to:

  while (ubcDvMask != 0) {
    int b = numberOfTrailingZeros(lowestOneBit(ubcDvMask));
    UbcCheck.DvInfo dv = UbcCheck.DV[b];

Or something.