The SHA-1 Controversy

For tutorial purposes, I have used the MD5 hash function. But these days MD5 is considered passinstead most of the world is moving over to the U.S. governments Secure Hash Algorithm, known as SHA-1, a standard adopted by the National Institutes of Standards and Technology (NIST) back in the early 1990s.

Today SHA-1 is a widely respected algorithm, but it has a troubled history. Back in 1993, the U.S. government was trying to get industry to adopt the so-called Clipper Chipa secret encryption system designed by the National Security Agency. During the so-called "crypto wars" that raged around Clipper, NIST proposed that the U.S. government adopt its own Secure Hash Algorithm as part of the Federal Information Processing Standards. For technical reasons, hash functions should have twice as many bits as the encryption algorithms that they work with. Clipper was an 80-bit encryption algorithm, so the standard was designed to produce a 160-bit fingerprint.

One might think that the governments standard, with its 160-bit fingerprint, would be more secure than the 128-bit MD5. But like Clipper itself, SHA was designed by the National Security Agencyand both NIST and the NSA declined to explain the principles that were used in its design. Some people wondered if the NSA might have hidden some kind of back door inside the algorithm so that the agency could generate collisions on demand. Such a back door could be used, for example, to produce faked digital signaturessomething that the Central Intelligence Agency might find useful. A fake digital signature might be used, for example, to sign an electronic order giving an U.S. spy access to a database in a foreign country.

Lots of cryptographers and other academics analyzed the SHA algorithm and couldnt find anything wrong with it. On May 11, 1993, NIST proclaimed SHA as the nations Secure Hash Algorithm. But the ink was barely dry on this decree when NIST announced that it had made a mistake. For reasons that would not be revealed at the time, NIST published a modified version of the Secure Hash Algorithmthe algorithm that we now call SHA-1.

The conspiracy theorists in the cryptography community (and there are many) had a field day. Was SHA so powerful that the NSA had decided that it had to be dumbed down? Or had NSA perhaps planted a back door in SHAand somebody at NIST had found out? Were both algorithms equally secure, and the cryptographers at the NSA were just messing with peoples minds?

In August 1998, the world more-or-less learned the answer to the SHA vs. SHA-1 mystery. Florent Chabaud and Antoine Joux, two French cryptographers, came up with a theoretical attack against the first version of SHAan attack against which SHA-1 just happened to be secure. Almost certainly, the folks at NSA knew about this attack and proposed SHA-1 as a countermeasure. Whats interesting here is that NSAs cryptographers probably didnt know about the attack when SHA was first proposed in 1993which means that the worlds top cryptographic agency was only five years ahead of the cryptographers in academia.

Today hash functions are also commonly used to generate repeatable but unpredictable random numbers, for converting typed passwords into values suitable for using as encryption keys. Instead of storing passwords directly, many computer systems store the hash of a password. This prevents somebody who breaks into a computer from learning everybodys password.

Hash functions have been proposed as a way to fight spam and as the basis for digital cash systems. Mathematician Peter Wayner published a book called Translucent Databases a few years ago in which he showed how hash functions could be used for storing information in a database in a way thats protected by the organization thats running the database. A college admissions department, for example, could store student social security numbers in the database so that these numbers could still be used as identifiers on applications, but so that nobody in the admissions office could sit down at a terminal and get a list of students and their numbers. So far, though, none of those approaches have really gotten off the ground.

All in all, cryptographic hashes are one of the most interesting and useful mathematical techniques that cryptographers have come up with over the past 20 yearsand were still finding new uses for them all the time.