The SHA family, and the death of a hash function

The standards, in order

The Secure Hash Standard has been reissued five times, and the numbering rewards ten minutes of memorisation.

• FIPS 180 (1993) — the original SHA, now called SHA-0.
• FIPS 180-1 (1995) — SHA-1, a 160-bit digest, issued after weaknesses were found in SHA-0. Also published as RFC 3174.
• FIPS 180-2 (2002) — adds SHA-256, SHA-384 and SHA-512. These and their later siblings are collectively SHA-2, and they share SHA-1's underlying structure and the same kinds of modular arithmetic and logical operations.
• FIPS 180-3 (2008) — adds SHA-224, a truncation of SHA-256.
• FIPS 180-4 (August 2015) — adds SHA-512/224 and SHA-512/256, truncations of SHA-512, motivated by SHA-512 being faster than SHA-256 on many 64-bit machines.
• FIPS 202 (August 2015) — SHA-3.

Two parameters per algorithm are worth holding. The block size is 512 bits for the 32-bit-word variants (SHA-1, SHA-224, SHA-256) and 1024 bits for the 64-bit-word ones (SHA-384, SHA-512 and the SHA-512 truncations). The security is the digest size divided by two, in every row, because the birthday bound governs. SHA-1's 160-bit digest gives 80-bit security; SHA-256 gives 128-bit.

SHA-2 is a family, not an algorithm — a distinction that catches people out, because SHA-224 and SHA-512/224 produce the same output size from two different algorithms.

SHA-3 is a complement, not a replacement

SHA-3 was not standardised because SHA-2 broke. It has not broken; NIST still considers it secure for general use. SHA-3 exists because SHA-2 is structurally similar to SHA-1, and SHA-1 fell — so a structurally different construction, held in reserve, means one break cannot take out both. The competition began in 2007 with two hard requirements: the winner had to be a drop-in substitute for SHA-2 at 224, 256, 384 and 512 bits, and it had to preserve SHA-2's online nature, processing 512- or 1024-bit blocks as they arrive rather than buffering the whole message. Its compactness also makes it attractive for embedded devices.

Worked example — one consequence chain, end to end

This is the best short narrative in the course of what “a hash function died” actually means, and it is worth being able to tell in order.

Originally, most X.509 certificates were signed over an MD5 digest of their contents. Research advances in constructing MD5 collisions produced a technique for building a new certificate, for a different identity, whose contents hash to the same value as an existing valid certificate — and therefore can reuse that certificate's signature. Note what property this needs: the attacker constructs both documents, so this is a failure of collision resistance. Nobody inverted MD5, and no certificate authority's private key was ever stolen.

The Flame malware's authors used exactly this to forge what appeared to be a valid Microsoft code-signing certificate. Windows machines accepted Flame's components as Microsoft-signed software. The malware remained undetected for more than two years before it was identified in 2012.

The industry response ran on its own timetable. Through the 2000s MD5 use declined and SHA-1 was recommended instead. Then, in 2017, SHA-1 collisions were produced, and SHA-1 in turn stopped being considered secure. As of early 2017, most browsers reject certificates signed with SHA-1 or MD5, and one of the SHA-2 algorithms is the requirement.

Run the chain forward one step and you can predict what a SHA-256 collision would cost: not stolen keys, not decrypted traffic, but the ability to obtain a signature over one document and attach it to a different one — every code-signing certificate, every signed software update and every signed contract in the world, all at once. That is why the birthday bound is not an academic footnote. A 256-bit digest buys 128-bit collision security, and 128 bits is the number that has to stay out of reach.