SHA1 is broken

[Brian Warner]

​https://shattered.it announced the first (public) SHA1 collision yesterday. We've known this was coming for years, but their work provided a vivid demonstration.

There's unfortunately one place in Foolscap that still uses SHA1: TubIDs are defined to be the base32-encoded SHA1 hash of the certificate. (The TLS certificates themselves use SHA256 for their DigestAlgorithm).

The presence of a collision attack means that, with enough effort (110 GPU-years), and some clever X.509 format-twiddling, you could create two different TLS certs that present as the same TubID. This is counter to the intention of TubIDs, so it's a valid bug. (Note that the published attack uses a PDF-specific prefix, so I don't believe it could be used to generate a valid X.509 collision, so any would-be attacker would have to duplicate the computation effort of the shattered.it team).

However I'm going to call it a low-priority one, because what really matters in the Foolscap context is a second-preimage attack, and nobody believes that's happening any time soon (it *still* hasn't happened for MD5, 13 years after a collision was published; in fact the only once-considered-secure cryptographic hash function for which a preimage attack exists is SNEFRU-2, from 1990.. even MD2 is still preimage-resistant).

Unlike a certificate authority, Foolscap doesn't sign anything on behalf of outside callers. With a collision, you could produce a TubID with two different certs, but you'd be the one deciding the public RSA keys that went into both certs. For this to be useful to an attacker, they need to make a new cert (with their public key, i.e. one that matches a private key which they control) that hashes to the same TubID as your pre-existing one. That requires a pre-image attack.

So we should fix this, but I don't think it needs to be anytime soon. We might even manage to move to Ed25519 first (see #219).

Details of the fix: we'll replace the TubID with a longer string, and maybe put a version identifier in front. Maybe ​https://github.com/multiformats/multihash . We'll need to tolerate old SHA1-based tubids. The code around ​https://github.com/warner/foolscap/blob/master/src/foolscap/negotiate.py#L683 should look at theirTubID, determine the hash being used from its format, hash the peer's cert that way, then compare the results.

(I thought maybe the peer should send a negotiation option that says "please use hash=X to compute my tubid", but it already effectively does that, in the my-tub-id offer field).

At the end of the day, our Tub compares the connection's TubID against the one in the FURL that it's trying to reach. So algorithm=null -style shenanigans (e.g. a multihash that declares to use 0 bits, or something) won't help an attacker pretend to be any legitmate (normal-length) server, as long as no preimage attack is successful.