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):

“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.”

 
This can be misleading. There are no four versions of Keccak. Keccak is a family of hash functions tunable by the size of its internal state and by a security parameter called capacity. Although any choice of capacity is valid, we highlighted 5 values for the capacity, namely 448, 512, 576, 768 and 1024 bits. The new proposal keeps only one of these 5 values (512 bits), and introduces a new one, 256.
 
“Drastically reduced” can also be misleading. The chosen capacities lead to very high security levels. As explained in our post at http://keccak.noekeon.org/yes_this_is_keccak.html, the corresponding two security strength levels are 2^128, which is rock-solid (and does not degenerate under multi-target attacks), and an extremely high 2^256 (e.g., corresponding to RSA keys of 15360 bits [NIST SP 800-57]). Discussing security above 2^256 is meaningless.
 
“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.”

 
This is incorrect. The proposal uses exactly the same cryptographic primitive as selected at the end of the SHA-3 competition. As explained in our post, one can generate test vectors for that proposal using our reference code submitted for round 3 (January 2011). This alone proves that there cannot be any internal tweaks.
 
If you are referring to “changes to the padding”, this is in fact just domain separation by appending a few bits at the end of the input but keeping the original multi-rate sponge padding, as we proposed in our paper on Sakura. This is also explained in our post.
 
“Essentially, NIST had changed Keccak to something very different from what won the 5-year competition”

 
This is simply incorrect. The current proposal is a subset of the (unmodified) Keccak family. See also the comment above on the validity of our reference code.
 
“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.”

 
Again, this is incorrect as there were no changes made to Keccak.
 
“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.”

 
This is incorrect and can be misleading.
 
For one thing, Keccak and the sponge construction are sound, while SHA-2 is trivially differentiable from a random oracle (RO) via length-extension attacks.
 
The purpose of SHA-3 is not to provide primitives with higher claimed security levels, but instead to propose primitives that have better safety margin with respect to these claimed security levels and to protect against possible extensions of the attacks on SHA-1 to similar algorithms such as the SHA-2 family.
  • 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.
 
“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. […]”

 
This is incorrect, as there were no changes made to Keccak. The cryptanalysis performed during the entire competition is still valid. The round function never changed since the submission of Keccak to the SHA-3 contest in 2008.
 
“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. […]”

 
Performances of the candidates have been a key factor in the selection process, if you look the program of the last SHA-3 conference organized by NIST there are plenty of presentation on the performances comparison of the candidate on different platform. Even in the call NIST asked for algorithms with performances comparable to SHA-2. During the process some of the expert commented that if SHA-3 was not going to be faster than SHA-2 it would have been a useless standard (unless SHA-2 badly broken). Part of the fast adoption of AES can be attributed to its much better performances compared to 3DES.
 
In the current proposal, the performance improvement comes for a big part from the dismissal of the Keccak instances with c=768 and c=1024 (or 2^384 and 2^512 security, respectively), the latter of which is about twice slower than instances with c=512 or less. This is a fair perfomance-security trade-off to make since claiming security beyond 2^256 is meaningless (see also our post on that subject). Furthermore, a user satisfied with 2^128 security (same resistance against collision as SHA-256) also has the freedom to use SHAKE256, which is about 25% faster than SHAKE512 with 2^256 security.
 
NIST’s reputation is undermined: […] 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).”

 
We can comment only for the SHA-3 process as Keccak team, Joan could talk about the AES competition if you want. The process that NIST follows in the case of SHA-3 is very open, interactive and motivated. One can hardly argue that NIST is trying to reduce security level of SHA-3 when these security levels are clearly documented and openly communicated to the community at large, and that NIST are continuously and proactively asking for feedback before the publication of the draft of the FIPS that will be available for public comments. Finally, without any doubt, there is no change in the algorithm since the proposal is a *subset* of the original Keccak submission.
 
“What could NIST do to defuse this controversy? […] 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. […]”

 
What we are doing is to stay on the facts and on the technical topics.
 
“Add back high-security modes: […].”

 
We think that [NIST SP 800-57] is setting good standard for security. We have not seen discussion that SP 800-57 should embed 512 bits security level. We think that 2^128 security is rock-solid, and 2^256 gives an incredibly high level. Going to 2^512 is just a waste of energy.
 
“Justify optimizations and internal changes: […]”

 
The recommendations set forth in this paragraph would be very valid if only they would not rely on a wrong assumption. There is no need for further examination because there is no changes in the primitive. Regarding the security levels, the differences between the current proposal and initial submission are only in the selection of a different set of parameters, which is clearly understood and described in the Keccak submission. (See also our post at http://keccak.noekeon.org/yes_this_is_keccak.html .)

Share Post