Re: Hash algorithm analysis

On Mon, Jun 11, 2018 at 12:29 PM Jonathan Nieder <jrnieder@gmail.com> wrote:

Yeah, I really think that it's a mistake to switch to something that has the same problem SHA1 had.

That doesn't necessarily mean SHA3, but it does mean "bigger intermediate hash state" (so no length extension attack), which could be SHA3, but also SHA-512/256 or K12.

Honestly, git has effectively already moved from SHA1 to SHA1DC.

So the actual known attack and weakness of SHA1 should simply not be part of the discussion for the next hash. You can basically say "we're _already_ on the second hash, we just picked one that was so compatible with SHA1 that nobody even really noticed.

The reason to switch is

 (a) 160 bits may not be enough

 (b) maybe there are other weaknesses in SHA1 that SHA1DC doesn't catch.

 (c) others?

Obviously all of the choices address (a).

But at least for me, (b) makes me go "well, SHA2 has the exact same weak inter-block state attack, so if there are unknown weaknesses in SHA1, then what about unknown weaknesses in SHA2"?

And no, I'm not a cryptographer. But honestly, length extension attacks were how both md5 and sha1 were broken in practice, so I'm just going "why would we go with a crypto choice that has that known weakness? That's just crazy".

From a performance standpoint, I have to say (once more) that crypto performance actually mattered a lot less than I originally thought it would. Yes, there are phases that do care, but they are rare.

For example, I think SHA1 performance has probably mattered most for the index and pack-file, where it's really only used as a fancy CRC. For most individual object cases, it is almost never an issue.

From a performance angle, I think the whole "256-bit hashes are bigger" is going to be the more noticeable performance issue, just because things like delta compression and zlib - both of which are very *real* and present performance issues - will have more data that they need to work on. The performance difference between different hashing functions is likely not all that noticeable in most common cases as long as we're not talking orders of magnitude.

And yes, I guess we're in the "approaching an order of magnitude" performance difference, but we should actually compare not to OpenSSL SHA1, but to SHA1DC. See above.

Personally, the fact that the Keccak people would suggest K12 makes me think that should be a front-runner, but whatever. I don't think the 128-bit preimage case is an issue, since 128 bits is the brute-force cost for any 256-bit hash.

But hey, I picked sha1 to begin with, so take any input from me with that historical pinch of salt in mind ;)

                Linus