Justus Winter justus@sequoia-pgp.org writes:
I think hashing should be fallible. If a collision attack is detected, no digest should be produced, because the digest has none of the properties that we usually associate with a hash digest.
I disagree; a hash function is a well defined function (in the mathematical sense) regardless of attacks on some of its assumed cryptographic properties.
Also, if we add a return value indicating success or failure, I would expect that applications either ignore it anyway (there's currently no circumstances when nettle's sha256_digest function could sensibly fail, so why add code to check for that?), or attempt to handle errors, resulting in code clutter and error "handling" code with no test coverage.
If we come up with a new API anyway, we should make all hash functions fallible, because sooner or later, any algorithm may fall.
In my view, the proposed "counter cryptanalysis" feature is specific to known attacks on MD5, SHA1 and hash functions with similar structure. And once we see a second-preimage attack (rather than a collision attack) on a hash function, that kind of detection will be less useful.
I've had a quick look at the paper, https://marc-stevens.nl/research/papers/C13-S.pdf, and I think it makes some sense to add to Nettle. It's neat that the detection will trigger when processing either one of the two colliding messages, and I can see a real benefit in checking for that as part of verification of old sha1 signatures.
If you want to move forward with this, I would suggest to
* Select a new name, preferably less unwieldy than "sha1_collision_detection". Just sha1_cd might do, but I'm also happy with something sligthly longer.
* Only do detection, no builtin substitution. An application that wants to, e.g., replace suspicious hash values with a truncated sha256 or sha3 hash or the like, can do its own hashing of the message itself in parallel with sha1. Exactly what digest output to produce on failure, I'm not sure. Maybe produce the regular sha1 digest. Maybe leave the output area unchanged, similar to how rsa_sec_decrypt handles failure. Then one mode of using it would be to unconditionally initialize the digest area with a truncated sha256 hash, then call sha1_cd_digest, and ignore the return value.
* See if it needs it's own context struct, struct sha1_cd_ctx, or if it can reuse sha1_ctx. If we want to provide a return value from sha1_cd_digest to reflect processing of the entire message, we will likely need an extended context with a flag to record if collisions were detected by some preceding sha1_cd_update call. If we provide return values for both sha1_cd_update and sha1_cd_digest (and expect applications using this feature to check them all), we might be able to get away with using the same struct sha1_ctx.
* Add colliding inputs to the testsuite, both for regular sha1, and for testing the new feature. There are tests exhibiting collisions in md5-test.c, but I don't think the sha1-tests.c has been touched since https://shattered.io/static/shattered.pdf was published.
* Consider how to deal with future changes to the list of known attack patterns. If a Nettle upgrade may change the result sha1_cd_digest, we might need to provide a version number for the counter-cryptanalysis used.
* Consider if it's worth doing also for md5?
Regards, /Niels