Hi Simo,

On Mon, 02 Nov 2020 14:31:34 +0100, Simo Sorce wrote:

On Mon, 2020-11-02 at 12:53 +0100, Neal H. Walfield wrote: This change would have to be conditional as it will break compatibility for the very use case you mention, data at rest saved moons ago.

I see two ways forward.

If I recall the C calling conventions correctly, it should be possible to change sha1_digest from returning void to returning an int in a backwards compatible way. Then, a user of the return code would check some function at run time to see whether the function really returns an int.

That's ugly. For us (Sequoia [1]), we'd be happy to have a parallel API.

[1] https://sequoia-pgp.org/

For SHA1, Nettle has the following functions [2]:

void sha1_init (struct sha1_ctx *ctx) void sha1_update (struct sha1_ctx *ctx, size_t length, const uint8_t *data) void sha1_digest (struct sha1_ctx *ctx, size_t length, uint8_t *digest)

[2] http://www.lysator.liu.se/~nisse/nettle/nettle.html#Legacy-hash-functions

So we could add:

void sha1_collision_detection_init(...); void sha1_collision_detection_update (struct sha1_ctx *ctx, size_t length, const uint8_t *data) error_code_t sha1_collision_detection_digest (struct sha1_ctx *ctx, size_t length, uint8_t *digest)

What do you think? Or, am I misunderstanding what you mean by breaking compatibility?

Thanks!

:) Neal

"Neal H. Walfield" neal@walfield.org writes:

So we could add:

void sha1_collision_detection_init(...); void sha1_collision_detection_update (struct sha1_ctx *ctx, size_t length, const uint8_t *data) error_code_t sha1_collision_detection_digest (struct sha1_ctx *ctx, size_t length, uint8_t *digest)

What do you think? Or, am I misunderstanding what you mean by breaking compatibility?

I haven't yet read the background, so I don't know what I think about the feature in general. But from an api point of view, that looks reasonable. Do all three operations need new functions? Do you need an extended context struct too?

Regards, /Niels

"Neal H. Walfield" neal@walfield.org writes:

I'm not that familiar with Nettle's API, so I don't know if the following is sufficiently idiomatic.

That said, we could do the following: we could add a flag to the sha1 context to indicate to the update function that it should try to detect collision attempts, we could add a few ifs to the update function to do the checks, and we could add a second function to return whether a collision was detected:

void sha1_check_for_collisions(struct sha1_ctx *ctx); int sha1_detected_collision(struct sha1_ctx *ctx);

What do you think?

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.

If we come up with a new API anyway, we should make all hash functions fallible, because sooner or later, any algorithm may fall.

Cheers, Justus

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