What the heck is going on with NIST’s cryptographic standard, SHA-3?

(Warning: this is a fairly technical post about cryptographic standards setting.)

UPDATE [2013-10-09]: The Keccak team provided me with a response to issues I raise in this post, arguing that some of what I say here is incorrect and misleading. In the interest of transparency, I’m reproducing their comments — with their permission — below this post.

The cryptographic community has been deeply shaken since revelations earlier this month that the National Security Agency (NSA) has been using a number of underhanded methods – stealing encryption keys, subverting standards setting processes, planting backdoors in products – to undermine much of the encryption used online. This includes crucial pieces of e-commerce like HTTPS (SSL/TLS) and Virtual Private Networks (VPN) that we use each day to purchase things online, to socialize in private, and that businesses use to communicate confidential and proprietary information. While the reporting has been vague and hasn’t pointed to specific software versions or protocols that have been compromised, last week RSA Security – a major supplier of cryptographic software and hardware – initiated a product recall of sorts, warning users that one of its popular software encryption products contained a likely NSA-planted backdoor. The practical implication of the RSA recall is that much of the encryption that used this product since 2007 isn’t nearly as secure as it was supposed to be.

Those of us who follow developments in the cryptographic community have noticed another troubling development: there are a number of cryptographers upset with how the National Institute of Standards and Technology (NIST) is standardizing a new set of encryption algorithms called SHA-3 (which stands for the third version of the Secure Hashing Algorithm). The remainder of this post explains what is going on with SHA-3 and how NIST could defuse this particular controversy while it still has the chance.

(Warning: In this post, I’m assuming the reader is familiar with the concepts underlying basic encryption tools, called “cryptographic primitives,” such as hash functions, digital signatures, and message authentication codes.)

What is SHA-3?

SHA-3 is the “next generation” hash algorithm being standardized by NIST. In 2005, researchers developed an attack that called into question the security guarantees of an earlier secure hash algorithm, SHA-1. The characteristics of this 2005 attack seemed to hint that it could be refined to attack many of the secure hash functions at the time, including SHA-0, MD4, MD5 and even SHA-2. At the time, for many cryptographers, the message was clear: a new hash algorithm is needed and it should be based on completely different underlying mathematics that are not susceptible to the attacks threatening known hash functions. To be clear: SHA-1 is thought to be on its way out, as people expect the earlier attacks to be improved considerably in the coming years and there hasn’t been any result that calls into question the soundness of SHA-2 at all. Attacks always improve, so it’s imperative that there is an alternative hash function ready to go when and if the floor falls out of the earlier hash functions.

NIST’s cryptographic technology group is world-renowned for cryptographic algorithm standardization. In 2007, NIST began the process to develop and standardize a new secure hash algorithm that would be called SHA-3. The process for choosing a new algorithm was designed as a competition: new candidate algorithms were submitted by more than 60 research teams and over five years the entrants were whittled down to a set of finalists, from which a winner was chosen. In October of last year, NIST announced that a team of Italian and Belgian cryptographers had won the competition with their submission named, “Keccak” (pronounced “KECH-ack”).

What has NIST done with SHA-3?

Since the announcement of Keccak as the winner, NIST has been working hard to turn Keccak into a standard. That is, NIST can’t just point to the academic paper and materials submitted by the Keccak team and call that a standard. NIST has to write the algorithm up in a standards-compliant format and include it in other NIST cryptographic standards documents, such as a successor to the Secure Hash Standard document (FIPS Publication 180-4).

Here’s where the controversy starts.

One of the most accomplished civilian cryptographers, NIST’s John Kelsey, gave an invited talk at a conference in August, the Workshop on Cryptographic Hardware and Embedded Systems 2013 (CHES’13), where he described some of the changes NIST has made to Keccak in turning it into a standard. The changes were detailed in five slides (slides 44-48) of Kelsey’s slide deck for his talk. Two major changes puzzled some in attendance:

• In the name of increased performance (running faster in software and hardware), the security levels of Keccak were drastically reduced. The four versions of the winning Keccak algorithm had security levels of 224-bits, 256-bits, 384-bits, and 512-bits. However, from Kelsey’s slides, NIST intends to standardize only two versions, a 128-bit and a 256-bit version.
• Some of the internals of the algorithm had been tweaked by NIST – some in cooperation with the team that submitted Keccak – to improve performance and allow for new types of applications.

Essentially, NIST had changed Keccak to something very different from what won the 5-year competition. Since this talk, cryptographers have been abuzz with this news and generally very critical of the changes (e.g., folks like Marsh Ray on Twitter).

What are the issues with SHA-3 standardization?

So, what’s the big deal? Well, the problems here cluster in five areas:

1. Process: From a simple due process perspective, after a five-year hard-fought competition, to make large changes to the winning algorithm is simply problematic. The algorithm being standardized is very different from the winning Keccak, which beat 62 other high-powered cryptography research groups in a 5-year competition. (To be fair, it’s not like these changes came out of the blue. However, given the new political environment reality itself has changed.)
2. No security improvement: The SHA-3 version of Keccak being proposed appears to provide essentially the same level of security guarantees as SHA-2, its predecessor. If we are going to develop a next generation hash, there certainly should be standardized versions that provide a higher security level than the older hash functions! NIST, in the original call for submissions, specifically asked for four versions in each submission, with at least two that would be stronger than what was currently available, so it’s hard to understand this post-competition weakening.
3. Unclear implications of internal changes: The changes made to Keccak to get to SHA-3 may be so substantial as to render the cryptanalysis that was performed during the competition moot. That is, all the intense number crunching cryptographers performed during the competition to try and break the submitted ciphers to prove their strength/weakness simply doesn’t apply to the modified form of Keccak that NIST is working on.
4. No real need for high-performance hashes: NIST said it weakened the security levels of the winning Keccak submission to boost performance. (Weaker versions of hash functions run faster.) However, there is not clearly a need for another fast hash algorithm. For example, to get exceedingly technical for a moment: in communications security, hashes are used for a few purposes and most are computed on small inputs – where performance isn’t a concern – and in cases where performance is a concern due to large inputs (e.g., with “message authentication codes” or MACs), many applications are moving away from hash-based MACs (HMAC) to other types of MACs like GMAC that are not based on hash functions.
5. NIST’s reputation is undermined: Kelsey’s CHES’13 talk was given in mid-August, two weeks before the NSA encryption revelations. Those revelations suggest that NSA, through an intelligence program called BULLRUN actively worked to undermine NIST’s effort to standardize strong cryptography. NIST could not have known how the changes it made might appear once that reporting had cast a pall over NIST cryptographic standards setting. The changes made to Keccak undoubtedly weaken the algorithm, calling NIST’s motives into question in light of the NSA revelations (regardless of their actual intentions).

None of this is irreversible.

What could NIST do to defuse this controversy?

Kelsey’s slides indicate that NIST is on track to standardize the NIST-modified version of Keccak as SHA-3 and issue a draft standard in late October for public comment. If the issues above are not addressed in that draft standard, there will be considerable hue and cry from the cryptographic community and it will only serve to reinforce the more general concerns about NIST’s cooperation with the NSA. It’s in no one’s interest to feed the flames of NIST scaremongering and we all have an interest in NIST as a trusted place for science and standardization. In that spirit, there are a number of things NIST can do to calm this storm (and please consider joining NIST’s Hash Forum to discuss this further):

• Add back high-security modes: NIST must ensure that SHA-3 has strong modes of operation. NIST should at least add back in a 512-bit security level version of Keccak so those users who want exceedingly high security and don’t worry as much about performance have a standardized mode that they can use. In fact, if NIST is worried about performance, it probably makes sense to standardize the as-submitted versions of Keccak (224, 256, 384, 512-bit security levels) and add in a much weaker but high-performance 128-bit version for those users who want to make that trade-off. This would be the “Kumbaya” solution, as it would have five security levels with both the NIST-modified versions and the as-submitted Keccak versions.
• Justify optimizations and internal changes: NIST has obviously made significant internal changes to the Keccak algorithm. This means that the NIST-modified Keccak and the winner of the SHA-3 competition are likely to be very different. To be sure, there are probably some very good reasons for the changes, but we don’t know what they are, and it would be unfortunate to learn them simply in the draft standard as published in October. Extensive changes should technically be subject to the cryptanalysis that was brought to bear during the actual competition. Unfortunately, it will be impossible to muster the cryptographic scrutiny necessary to examine the NIST-modified Keccak as the resources and teams that worked on this during the competition are no longer available. Here, it makes sense for NIST to standardize both the winning version of Keccak and NIST’s optimized version (“SHA-3-Opt” maybe?), so that implementers can have their pick of whether they want the Keccak that was subject to the grueling competition or an improved version that hasn’t been subject to as much scrutiny.
• Improve the standardization process: No one doubts that NIST runs high-quality cryptographic competitions. The many-year competitions that resulted in AES (the Advanced Encryption Standard) and SHA-3 marshaled the most gifted cryptographic thinkers in the world to shake down very exotic forms of mathematics to result in very strong, clever and useful practical outcomes. The resulting algorithms look indistinguishable from magic to many of us who are not steeped in the fine art of cryptography. However, the process of getting from the algorithm that won the competition to a standard is a dark and mysterious process, and it need not be. While the relationship between NSA and NIST has always made many of us uneasy, in light of recent revelations, it’s especially important that this standardization step be open and transparent with a formal process that works to ensure that all decisions are made in a well-documented manner and that conditions that ensured an algorithm withstood withering scrutiny during a competition do not subsequently change dramatically during the standardization process.

At CDT, we work hard to make sure that standards processes serve the public interest in an open, free and innovative Internet. We’ll be advocating for changes in standards processes at NIST so that it remains an unbiased, trusted, and scientific venue for developing cybersecurity and cryptographic standards.

UPDATE [2013-09-24T17:41:24]: Changed title to better reflect that SHA-3 is not an encryption standard but a hash function standard (without using “hash function” in the title). Better qualified that SHA-1 is likely weak in the face of government-level adversaries. Further update [2013-09-25T06:09:38]: clarified that SHA-1 is essentially on its way out.

Response from the Keccak Team (2013-10-08):

• For the latter aspect, the selection of SHA-3 improves the current security state by offering a primitive that is very different from SHA-2, and hence this increases diversity. Additionally the design principle and parameter selections are well motivated in our documentation, while the same cannot be stated for SHA-1 and SHA-2. NIST does not intend to de-commission SHA-2, so the user can freely choose between SHA-2 and SHA-3. Our construction, the cryptographic sponge, is radically different from the traditionally Merkle-Damgard hash function.
• For the former aspect, the advantage of SHA-3 is that it has a very comfortable safety margin (4 to 5 rounds broken out of 24), arguably better than the current safety margin of SHA-2, and has a security claim that is simpler and more conservative than that of SHA-2.