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

Fri Sep 27 07:53:39 PDT 2013

https://www.cdt.org/blogs/joseph-lorenzo-hall/2409-nist-sha-3

by Joseph Lorenzo Hall [1]

September 24, 2013

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

The cryptographic community has been deeply shaken since revelations earlier
this month [2] 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
[3] 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 diffuse 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 [4], digital signatures [5], and message authentication codes
[6].)

What is SHA-3?

SHA-3 is the “next generation” hash algorithm being standardized by NIST. In
2005, researchers developed an attack [7] 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 [8] 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 [9] 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) [10].

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) [11], 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 [12]. 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 [13]).

What are the issues with SHA-3 standardization?

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

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.) 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.  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.  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 [14] that are not based on hash functions.  NIST’s reputation
is undermined: Kelsey’s CHES’13 talk was given in mid-August, two weeks
before the NSA encryption revelations. Those revelations [2] 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 diffuse 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
[15] 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.

NIST

Copyright © 2013 by Center for Democracy & Technology.

The content throughout this website that originates with CDT can be freely
copied and used as long as you make no substantive changes and clearly give
us credit. Details.

Source URL: https://www.cdt.org/blogs/joseph-lorenzo-hall/2409-nist-sha-3

Links:

[1] https://www.cdt.org/personnel/joseph-lorenzo-hall

[2]
http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=all&_r=0

[3] http://www.wired.com/threatlevel/2013/09/rsa-advisory-nsa-algorithm/

[4] http://en.wikipedia.org/wiki/One-way_hash_function

[5] http://en.wikipedia.org/wiki/Digital_signatures

[6] http://en.wikipedia.org/wiki/Message_authentication_code

[7] https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html

[8] http://www.nist.gov/itl/csd/ct/

[9] http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html

[10] http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf

[11] http://www.chesworkshop.org/ches2013/start.php

[12] https://docs.google.com/file/d/0BzRYQSHuuMYOQXdHWkRiZXlURVE/

[13] https://twitter.com/marshray/status/380800393367674880

[14] http://en.wikipedia.org/wiki/Galois/Counter_Mode

[15] http://csrc.nist.gov/groups/ST/hash/email_list.html