Adding collision detection

[nwalfield]

Like it or not, SHA-1 is still used in practice. In Sequoia PGP, we initially decided to bad list SHA-1. However, a developer of Secure Drop recently approached us and asked us to reconsider this decision. They have users who use certificates secured by SHA-1. And, unfortunately, they don't have processes to update these offline certificates. But, even if they did, they doubt that their users would implement them ("never change a running system").

This motivated me to see who else is using SHA-1 in the OpenPGP ecosystem. My results are tabulated here. The results are depressing. The short version is: Microsoft's Security Notification certificate (created Oct. 31, 2019!) uses SHA-1. 106 of the 884 certificates in the Debian keyring are completely unusable without accepting SHA-1, and another 80 have at least one User ID or subkey that uses SHA-1! 32 of the 76 Arch packagers' certificates are unusable without accepting SHA-1, and 14 further certificates rely on SHA-1 for at least one User ID or subkey. I also discovered that Fedora misconfigured the tooling used to generate their release keys: although they generate 4k RSA keys, they rely exclusively on SHA-1! (The configuration is now fixed.)

Unfortunately, the OpenPGP ecosystem is not in a good place to get people to fix their certificates. First, most users don't even know there is a problem. Due to the publication of SHA-1 is a shambles, GnuPG now rejects new third-party certifications made using SHA-1, but self signatures and binding signatures using SHA-1 are still accepted without warning. RNP (used by TB) appears to accept anything. They only plan to add a warning when SHA-1 is used. Second, updating an existing certificate to not use SHA-1 is hard, and not always entirely possible using GnuPG!

This creates enormous pressure on us (Sequoia) to also accept SHA-1. Initially, we thought that we could accept SHA-1 for self signatures, because they only need to be preimage resistant. But, it appears that there might be a variant of the impersonation attack presented in the SHA-1 is a Shambles paper that could use a collision to forge a self signature.

A different approach would be to use counter cryptanalysis techniques. This idea and their application to MD5 and SHA-1 was published by Marc Stevens. He also published a library that implements these mitigations for SHA-1. According to the README:

This library and command line tool were designed as near drop-in replacements for common SHA-1 libraries and sha1sum. They will compute the SHA-1 hash of any given file and additionally will detect cryptanalytic collision attacks against SHA-1 present in each file. It is very fast and takes less than twice the amount of time as regular SHA-1.

More specifically they will detect any cryptanalytic collision attack against SHA-1 using any of the top 32 SHA-1 disturbance vectors with probability 1:
...
The possibility of false positives can be neglected as the probability is smaller than 2^-90.

The library supports both an indicator flag that applications can check and act on, as well as a special safe-hash mode that returns the real SHA-1 hash when no collision was detected and a different safe hash when a collision was detected.

This library is written in C and licensed under the MIT software license. It would be great if Rust Crypto could include these techniques.

I see two ways to do this: 1. The hash functions are changed to be fallible. 2. A parallel interface is added.

[nwalfield]

In a later paper, Speeding up detection of SHA-1 collision attacks using unavoidable attack conditions (2017), Stevens writes (Section 8):

Our improved implementation was deemed effective enough for Git, GitHub,Google Drive, Gmail and others to already deploy it inpractice

Here's a blog post from gitlab.

[newpavlov]

I think it will be certainly an interesting (feature-gated?) addition to the sha-1 crate. We probably don't want to add traits for such scenario, so this functionality will be probably better implemented in the form of inherent methods. For example we can poison the inner state if attack detected and use try_finalize inherent method to retrieve the result (and simply panic in finalize).

[nwalfield]

That's an interesting idea.

I was thinking that if we used a trait, one could use it everywhere. Then when attacks and mitigations are published against, say, SHA256, existing code wouldn't have to be modified.

[newpavlov]

We can revisit this question after we will get a similar functionality for 2-3 algorithms in total, before that it looks a bit premature. It should be possible to add such methods to traits in a backwards-compatible fashion. But until then, I don't think we should promote reliance on such mitigations, it should be clear that they are an ugly hack for legacy and outdated systems.

[nwalfield]

I think that is a reasonable position, thanks.

[tarcieri]

Then when attacks and mitigations are published against, say, SHA256, existing code wouldn't have to be modified.

While there's a long history of hash functions being broken, and attacks always get better, SHA-256 may very well be the first hash function to stand the test of time.

At this point, breaking it would seem to involve discovery of a new class of attacks, and we have no reason to suspect that will happen today (any more so than breakage of any other modern hash function).

I agree with @newpavlov that we shouldn't pursue trait-based abstractions around this sort of thing until we have more than one algorithm where it would be useful (although having said that, md5 comes to mind).

[dignifiedquire]

There is now a PR ready for review implementing this: #566