On May 28, 2014, the National Institute of Standards and Technology (NIST), an agency of the United States Department of Commerce, released its latest draft for the SHA-3 (Secure Hash Algorithm-3) standard hash function. What is unique about this announcement is that its ancestry involves Edward Snowden, NSA, NIST, and leading cryptographers, all wrestling over…random numbers.
That’s right…random numbers. To understand how this came to be, we need to examine one of the most controversial aspects of the Snowden leaks, specifically involving (well-grounded) theories that the NSA may have weakened random number generators, known as pseudorandom number generators (PRNGs) in the cryptography community, as nothing is truly random, as everything is somewhat deterministic.
PRNGs have several important uses in cryptography. For this story, the relevant uses are:
1. Generating secret numbers used for sharing secrets.
2. Generating a fixed-length digest of a variable-length message.
Let’s first examine the first use of PRNGs, which is for generating keys for the use of sharing secrets. In the simplest cipher, that of the Caesar Cipher (see Figure 1), this means that the amount of letters to shift is generated randomly so an attacker will have to guess as many shift-numbers as possible, as opposed to guessing based on the intuition of the keymaster; imagine a keymaster who always used his/her birthday month as the shift-number…that wouldn’t be too hard to guess!
What happens, though, when a PRNG isn’t truly random? For instance, imagine a roulette wheel where each slice has an equal area and sits on a flat surface; this would be a fair wheel, as the ball would land on any spot randomly. What if, though, we tilt the roulette wheel in one direction? In this case, the ball will much more likely land on the lowest portion of the wheel, which would be much less random than in the flat roulette wheel case.
A similar weakening of PRNGs occurred on a massive scale within the cyber security world during the 2000’s. One of the major leaks of the Edward Snowden affair was the NSA’s highly-classified Project BULLRUN. One of the goals of BULLRUN was to weaken cryptographic standards. It is known that one commonly-used PRNG, the Dual_EC_DRBG PRNG, was weakened. This caused much panic and upheaval within the cryptographic community, as Dual_EC_DRBG’s use is widespread.
Now we return to our headline news, regarding SHA-3. From 2007 to 2012, NIST held a competition among 64 submissions for the best hash function, which would do the second function of a PRNG, which is to output a fixed-length message digest of a variable-length message. Hash functions are required to be random in the sense that a given digest cannot be created by picking an input message (preimage resistance) and two input messages should not be found that produce the same digest (collision and second preimage resistance). Hash functions and their digests are used to ensure the integrity of messages and public key certificates; if even a tiny change is made in the input message, the digest should change dramatically, indicating a breach of integrity, known as the avalanche effect.
The winning algorithm in the SHA-3 competition was Keccak. However, when NIST finally announced the winner, it introduced some subtle changes to Keccak in its proposed SHA-3 standard. That’s where the uncertainty and upheaval began. Bruce Schneier, a leading cryptographer, said: “Normally, this wouldn't be a big deal. But in light of the Snowden documents that reveal that the NSA has attempted to intentionally weaken cryptographic standards, this is a huge deal. There is too much mistrust in the air. NIST risks publishing an algorithm that no one will trust and no one (except those forced) will use.”
Keccak’s designers defended NIST: “NIST's current proposal for SHA-3, namely the one presented by John Kelsey at CHES 2013 in August, is a subset of the Keccak family. More concretely, one can generate the test vectors for that proposal using the Keccak reference code (version 3.0 and later, January 2011). This alone shows that the proposal cannot contain internal changes to the algorithm.”
Schneier replied to the Keccak team: “I misspoke when I wrote that NIST made ‘internal changes’ to the algorithm…The Keccak permutation remains unchanged…I do not believe that the NIST changes were suggested by the NSA…I believe NIST made the changes in good faith, and the result is a better security/performance trade-off….This is a lousy outcome….This is just another effect of the NSA's actions draining the trust out of the Internet.”
On November 1, 2013, John Kelsey, a NIST cryptographer, announced to NIST’s online Hash Forum that SHA-3 would reopen for discussion again, “We are not going to try to move forward with the proposed version of SHA3 I presented at CHES. We were and are comfortable with that version on technical grounds, but the feedback we've gotten indicates that a lot of the crypto community is not comfortable with it.”
This week, NIST is trying again to win the trust of public cryptographers by releasing a new draft of SHA-3. The public has 90 days to comment on it. There will also be a one-day workshop in August to address concerns about it. Will SHA-3 restore the public’s trust in NIST, once again? Knowing that similar issues of mistrust have played out with the Data Encryption Standard, I think everyone will move on from this.