NISTIR 7896

Third-Round Report of the SHA-3
Cryptographic Hash Algorithm
Competition
Shu-jen Chang
Ray Perlner
William E. Burr
Meltem Sönmez TuranJohn M. Kelsey
Souradyuti Paul
Lawrence E. Bassham

http://dx.doi.org/10.6028/NIST.IR.7896

NISTIR 7896

Third-Round Report of the SHA-3
Cryptographic Hash Algorithm
Competition
Shu-jen Chang
Ray Perlner
William E. Burr
Meltem Sönmez TuranJohn M. Kelsey
Souradyuti Paul
Lawrence E. Bassham
Computer Security Division
Information Technology Laboratory

http://dx.doi.org/10.6028/NIST.IR.7896
November 2012

U.S. Department of Commerce
Rebecca M. Blank, Acting Secretary
National Institute of Standards and Technology
Patrick D. Gallagher, Under Secretary of Commerce for Standards and Technology and Directorii

Abstract
The National Institute of Standards and Technology (NIST) opened a public competition on
November 2, 2007, to develop a new cryptographic hash algorithm – SHA-3, which will augment
the hash algorithms specified in the Federal Information Processing Standard (FIPS) 180-4,
Secure Hash Standard (SHS). The competition was NIST’s response to advances in thecryptanalysis of hash algorithms.
NIST received sixty-four submissions in October 2008, and selected fifty-one first-roundcandidates on December 10, 2008; fourteen second-round candidates on July 24, 2009; and five
third-round candidates – BLAKE, Grøstl, JH, Keccak and Skein, on December 9, 2010, toadvance to the final round of the competition. Eighteen months were provided for the public
review of the finalists, and on October 2, 2012, NIST announced the winning algorithm of the
SHA-3 competition – Keccak. This report summarizes the evaluation of the five finalists and theselection of the SHA-3 winner.
KEY WORDS: Cryptographic hash algorithm; Cryptographic hash function; Cryptography;
Cryptographic hash competition; SHA-3 competition.

iii

Acknowledgements
NIST thanks the submitters of all the candidate algorithms, especially the submitters of the SHA3 finalists for their continued diligence and support. NIST is also grateful for the efforts of thosein the cryptographic community that provided security, implementation, and performance
analyses of the candidate algorithms throughout the competition, and those who provided
feedback on the hash forum or published papers on the various technical aspects of thecandidates. Specifically, NIST thanks the organizers of the following projects:
SHA-3 Zoo:
Christian Rechberger, Jean-Phillipe Aumasson, Florian Mendel, Tomislav Nad,
Martin Schläffer, Gilles van Assche;
ECRYPT Benchmarking of All Submitted Hashes (eBASH):
Daniel J. Bernstein, Tanja Lange;eXternal Benchmarking eXtension (XBX):
Christian Wenzel-Benner, Jens Gräf;
George Mason University Department of Electrical and Computer Engineering Hardware
Benchmarking:Kris Gaj, Jens-Peter Kaps;
Virginia Tech Department of Electrical and Computer Engineering ASIC Benchmarking:
Patrick Schaumont, Leyla Nazhand-Ali;
Eidgenössische Technische Hochschule Zürich (ETHZ) ASIC Implementation:
Frank K. Gürkaynak;
And the authors of the following reports:
ECRYPT II SHA-3 Design and Cryptanalysis Report:
Christian Rechberger, Tor E. Bjørstad, Joan Daemen, Christophe De Cannière,
Praveen Gauravaram, Dmitry Khovratovich, Willi Meier, Tomislav Nad, Ivica
Nikolić, Matt Robshaw, Martin Schläffer, Søren S. Thomsen, Elmar Tischhauser,
Deniz Toz, Gilles Van Assche, Kerem Varıcı;
ECRYPT II Intermediate Status Report:
Praveen Gauravaram, Florian Mendel, María Naya-Plasencia, Vincent Rijmen,
Deniz Toz;for their outstanding contributions and support to the SHA-3 competition.
In addition, NIST extends its appreciation to the KU Leuven Department ElektrotechniekESAT/COSIC team led by Bart Preneel, and Sebastiaan Indesteege for their outstanding support
to the First SHA-3 Candidate Conference.
The authors of this report also thank NIST’s Hirofumi Sakane and Caroline Scace for theirsupport in conducting power analysis of the finalists. Last but not least, the authors thank theother members of NIST’s SHA-3 team, who reviewed the candidate algorithms and the publiccomments, performed testing, provided technical input and administrative support, andparticipated in numerous meetings during the five-year competition. They are: Elaine B. Barker,
Sara J. Caswell, Donghoon Chang, Lily Chen, Quynh Dang, Morris J. Dworkin, James R.
Nechvatal, Rene Peralta, William T. Polk, and Andrew Regenscheid.

iv

TABLE OF CONTENTS
1.

Introduction ...................................................................................................................... 1
1.1
1.2
1.3

2.

Evaluation Criteria ............................................................................................................ 4
2.1
2.2
2.3

3.

4.2

4.3

Security Overview ..................................................................................................... 9
4.1.1 Overview of Security Resources .................................................................. 10
4.1.2 Domain Extenders and Proofs ..................................................................... 10
4.1.3 Cryptanalysis and Security Margin .............................................................. 12
4.1.4 Distinguishing Attacks and Differential Properties........................................ 15
4.1.5 Depth of Analysis and Understandability of Algorithms ................................ 16
4.1.6 Tweak History of the Finalists ...................................................................... 16
4.1.7 Side Channel Attacks and Countermeasures .............................................. 18
Finalist Profiles and Cryptanalysis .......................................................................... 19
4.2.1 BLAKE ........................................................................................................ 20
4.2.2 Grøstl .......................................................................................................... 23
4.2.3 JH................................................................................................................ 26
4.2.4 Keccak ........................................................................................................ 28
4.2.5 Skein ........................................................................................................... 31
Security Summary .................................................................................................. 33

Performance Comparison of the SHA-3 Finalists ........................................................ 35
5.1

5.2

6.

Security .................................................................................................................... 5
Performance ............................................................................................................. 6
Other Algorithm and Implementation Characteristics ................................................ 6
Complementing SHA-2 ............................................................................................. 7
Selection Conclusion ................................................................................................ 7

Security Analysis of the Finalists .................................................................................... 9
4.1

5.

Security .................................................................................................................... 4
Cost and Performance .............................................................................................. 4
Algorithm and Implementation Characteristics .......................................................... 4

Selection Process............................................................................................................. 5
3.1
3.2
3.3
3.4
3.5

4.

Purpose of this Document......................................................................................... 1
Background .............................................................................................................. 1
Organization of this Document.................................................................................. 3

Software Performance ............................................................................................ 35
5.1.1 Computer Systems – the Current Playing Field ........................................... 35
5.1.2 Candidate Software Performance Studies ................................................... 36
5.1.3 Beyond The Superscalar ............................................................................. 42
5.1.4 Software Performance Summary ................................................................. 45
Hardware Performance........................................................................................... 46
5.2.1 High-Performance Implementations ............................................................ 48
5.2.2 Compact Implementations ........................................................................... 52
5.2.3 Discussion of SHA-2 and the SHA-3 Finalists ............................................. 55
5.2.4 Hardware Performance Summary ............................................................... 57

Other Considerations ..................................................................................................... 58

v

6.1
6.2
7.

Intellectual Property ................................................................................................ 58
Other Features ....................................................................................................... 58

Conclusion ...................................................................................................................... 59

References .............................................................................................................................. 60
Appendix A – eBASH Shootout Plots ................................................................................... 71vi

List of Acronyms
AES-NI
ALU
AMD
ARM
ARX
ASIC
AVX
CF
CISC
CMOS
CPU
DPA
eBASH
EM
ETHZ
FIPS
FPGA
FRN
GMU
GPU
HAIFA
HMAC
ISA
IV
kGE
MAC
MD
MIPS
NIST
OC-48
PPC
PRF
RAM
RISC
RSA
RSA-FDH
SCA
SFS
SHA-3
SHS
SIMD
SSE
UBI
VT
XBX
XOR

Advanced Encryption Standard – New Instructions
Arithmetic Logic Unit
Advanced Micro Devices
Advanced RISC Machine
Modular Addition, Rotation, and eXclusive OR
Application Specific Integrated Circuit
Advanced Vector eXtensions
Compression Function
Complex Instruction Set Computer
Complementary Metal–Oxide–Semiconductor
Central Processing Unit
Differential Power Analysis
ECRYPT Benchmarking of All Submitted Hashes
Electromagnetic
Eidgenössische Technische Hochschule Zürich
Federal Information Processing Standard
Field Programmable Gate Array
Federal Register Notice
George Mason University
Graphics Processor Unit
HAsh Iterative FrAmework
Keyed-Hash Message Authentication CodeInstruction Set Architecture
Initialization Valuekilo Gate Equivalents
Message Authentication CodeMerkle-Damgård
Microprocessor without Interlocked Pipeline Stages
National Institute of Standards and Technology
Optical Carrier-48 (Transmission Rate)
PowerPC
Pseudo Random Function
Random Access Memory
Reduced Instruction Set Computer
Rivest, Shamir, and Adelman
RSA Full Domain Hash
Side Channel Analysis
Semi Free Start
Secure Hash Algorithm-3
Secure Hash Standard
Single Instruction Multiple Data
Streaming SIMD Extensions
Unique Block Iteration
Virginia TecheXternal Benchmarking eXtension
Exclusive OR

vii

1. Introduction
1.1

Purpose of this Document

This report summarizes the third and final round of the SHA-3 (Secure Hash Algorithm-3)
Cryptographic Hash Algorithm Competition. The third round began on January 31, 2011, when
the National Institute of Standards and Technology (NIST) posted the finalists’ submissions forthe third round, and ended on October 2, 2012, when NIST announced the SHA-3 winner –Keccak. This report explains the evaluation and selection process.
1.2

Background

NIST opened a public competition on November 2, 2007, to develop a new cryptographic hashalgorithm (referred to as SHA-3) to augment the hash algorithms specified in Federal Information
Processing Standard (FIPS) 180-2, Secure Hash Standard 1 [1]. The competition was NIST’s
response to advances in the cryptanalysis of hash algorithms in recent years. An attack by Wanget al. [4], and extended by many others, introduced serious concerns about the security of the
SHA-1 government standard hash algorithm when used for the generation of digital signaturesand in other security applications that require collision resistance.
NIST proposed a Draft Minimum Acceptability Requirements, Submission Requirements, andEvaluation Criteria for Candidate (Hash) Algorithms for public comment in a Federal Register
Notice in January 2007 (FRN-Jan07) [5]. These requirements and evaluation criteria were
updated, based on public feedback, and included in a later, second Federal Register Notice
published on November 2, 2007 (FRN-Nov07) [6], which called for the submission of candidate
algorithms and launched the “SHA-3” competition.
The competition, modeled after the Advanced Encryption Standard (AES) Competition [7] in
1997, generated great interest in the cryptographic community, and inspired numerous SHA-3
entries from around the world. NIST received sixty-four entries by October 2008, and selected
fifty-one first-round candidates in December 2008, fourteen second-round candidates in July
2009, and five third-round candidates – BLAKE, Grøstl, JH, Keccak, and Skein, on Dec. 9, 2010,
to advance to the final round of the competition. Table 1 lists these finalists and their submitters.
Algorithm

Designer

BLAKE [8]Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel,
Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Hongjun Wu
Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche
Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare,
Tadayoshi Kohno, Jon Callas, Jesse Walker

Grøstl [9]JH [10]Keccak [11]Skein [12]Table 1. SHA-3 Finalists

1
FIPS 180-2 [1], Secure Hash Standard, was the government hash standard when the SHA-3 competition began; it wassuperseded by FIPS 180-3[2], Secure Hash Standard, in October 2008, and again by FIPS 180-4 [3], Secure Hash
Standard, in March 2012.

1

NIST has published a report for the first and second round of the competition. These reports [13,14], and all the relevant information about the SHA-3 competition, are available at NIST’s hashcompetition website: http://www.nist.gov/hash-competition.
For the third round of the competition, NIST also allowed the submitters of the remaining
candidates to make minor modifications to their algorithms by Jan. 16, 2011. Such modifications
are often referred to as “tweaks” by the cryptographic community. NIST posted the final tweaked
submissions on January 31, 2011, and started the third round of the competition.
The review process of the finalists spanned nineteen months, and included a final SHA-3
Candidate Conference [15] held in March 2012. Throughout the competition, the cryptographic
community provided an enormous amount of feedback to NIST. Most of the comments were sent
to NIST or to the Hash Forum [16], which is a public email list, hash-forum@nist.gov,
established to facilitate dialogue about the hash workshops that NIST held prior to thecompetition, and the SHA-3 competition. In addition, some organizers held hash workshops [17,18, 19, 20, 21, 22, 23], or set up public websites to facilitate cryptanalysis or performancebenchmarking of the candidates, such as the SHA-3 Zoo [24], the ECRYPT Benchmarking of All
Submitted Hashes (eBASH) [25], and the eXternal Benchmarking eXtension (XBX) [26] sites.
Many of the cryptanalysis and performance studies were published as papers in major
cryptographic conferences or leading cryptographic journals. ECRYPT II has also published tworeports [27, 28] on the SHA-3 candidates prior to the finalists’ third-round tweaks.
Based on the public feedback and internal review of the finalists, NIST selected Keccak as the
SHA-3 winner. NIST made the selection announcement on October 2, 2012 [29], and officiallyended the SHA-3 competition. Table 2 shows the competition timeline, including major events
leading to the start of the SHA-3 competition.
Date
10/31-11/1/2005
8/24-8/25/2006
1/23/2007

11/2/2007
10/31/2008
12/10/2008
2/25-2/28/2009
7/24/2009
9/28/20098/23-8/24/2010
12/9/2010
1/31/2011
3/22-3/23/2012
10/2/2012

Event
Cryptographic Hash Workshop [30], NIST, Gaithersburg, Maryland.
Second Cryptographic Hash Workshop [31], UCSB, California.
Issued the Federal Register Notice Announcing the Development of New Hash
Algorithm(s) for the Revision of Federal Information Processing Standard(FIPS) 180-2, Secure Hash Standard [5].
Issued the Federal Register Notice Announcing a Request for Candidate
Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3)
Family [6]. SHA-3 competition began.
SHA-3 Submission Deadline.
First-round candidates announced. The first round began.
First SHA-3 Candidate Conference [32], KU Leuven, Belgium.
Second-round candidates announced. The first round ended.
Second-round candidates posted for public review. The second round began.
Second SHA-3 Candidate Conference [33], UCSB, California.
SHA-3 finalists announced. The second round ended.
Third-round candidates posted for public review. The third round began.
Third SHA-3 Candidate Conference [15], Washington, D.C.
Keccak announced as the SHA-3 winner. SHA-3 competition ended.
Table 2. SHA-3 Competition Timeline

2

1.3

Organization of this Document

This document is organized as follows. Section 2 summarizes the evaluation criteria specified in
FRN-Nov07. Section 3 describes the selection process of the SHA-3 winner. Section 4summarizes the five finalists and their security analyses that are publically available. Section 5compares the software and hardware performance of the finalists. Section 6 discusses otherconsideration factors associated with the finalists. Section 7 concludes the report.

32. Evaluation Criteria
Throughout the competition, NIST used the evaluation criteria specified in FRN-Nov07 [6] toevaluate the candidates. These criteria were discussed and further clarified at the First SHA-3
Candidate Conference in KU Leuven, Belgium, in February 2009. In order of importance, NIST
considered the security, cost, and algorithm and implementation characteristics of a candidate inits selection decision.
2.1

Security

FRN-Nov07 identified security as the first evaluation criterion, and listed the following as the
major evaluation factors:
(i)
(ii)

(iii)
(iv)
(v)

applications of hash functions; 2
specific requirements when hash functions are used to support Keyed-Hash
Message Authentication Code (HMAC) [34], Pseudo Random Functions (PRFs),
or Randomized Hashing;additional security requirements of hash functions;evaluations relating to attack resistance; andother consideration factors.

NIST studied the large amount of feedback received from the cryptographic community, anddiscusses the security analysis of the finalists in Section 4.
2.2

Cost and Performance

FRN-Nov07 identified cost as the second evaluation criterion, which includes:(i)computational efficiency, which refers to the speed of the algorithm; and(ii)memory requirements, which include the code size and the random-accessmemory (RAM) requirements for software implementations, as well as the gatecounts for hardware implementations.
For the cost and performance evaluations of the finalists, NIST studied the results obtained fromseveral major benchmarking efforts. The candidates’ performance in both software and hardware
implementations are compared in Section 5.
2.3

Algorithm and Implementation Characteristics

FRN-Nov07 also identified an evaluation criterion related to the flexibility and simplicity of acandidate’s design. Candidates with greater flexibility are preferable, such as flexibility inrunning efficiently on a wide variety of platforms, or flexibility in using parallelism, or
instruction-set extensions, to achieve higher performance. Furthermore, a candidate would be
judged on its relative design simplicity, with the intent to encourage easy-to-understand and easyto-analyze designs to provide more confidence in its security.
These characteristics of the finalists are addressed in Sections 3, 4, 5, and 6, as appropriate.

2

In this report, the terms “hash function” and “hash algorithm” are used interchangeably.

4

3. Selection Process
The selection of Keccak as the SHA-3 algorithm was a very difficult decision – all five finalists
would have made acceptable choices for SHA-3. NIST’s decision was based on a number ofconsiderations, particularly security, performance, and the desire for SHA-3 to complement theexisting SHA-2 algorithms. In addition to rating highly with respect to these primaryconsiderations, Keccak also benefited from a simple and elegant design, a great deal of flexibility
in choosing parameters, and other features, such as a built-in authenticated-encryption mode.
3.1

Security

NIST compared the security properties of the finalists, based on the published design documents
and cryptanalysis produced during the competition, and on the security proofs provided by both
the designers and other researchers. This data was useful in making the decision, but it required
some interpretation; each algorithm has its own mix of published attacks and design logic, andeach has received a somewhat different depth of cryptanalysis. However, NIST was able toextract the following points from this information:a. No finalist has a published attack that, in any real sense, threatens its practical security,and each of the finalists has a security proof for its domain extender 3 that shows that the
security of the whole hash function is ultimately based on the security of its underlying
components.
b. NIST was able to estimate the security margins of the candidates, based on the largest
number of rounds of the hash functions or underlying components that has beensuccessfully attacked using collision-type attacks. By this metric, which is discussed in
more detail in Section 4.1.3, Grøstl and JH have the smallest security margins, Skein has
a somewhat larger security margin than Grøstl and JH, and BLAKE and Keccak havevery large security margins. None of the candidates has an absolutely unacceptablesecurity margin, but it would be difficult for NIST to select Grøstl or JH without
seriously considering adding more rounds.
c. There are also a number of distinguishing attacks and differential properties published on
the finalists and their underlying component functions. It was not entirely clear how tointerpret these results, but they largely left the same impression as the collision-typeattacks: if distinguishers costing more than the claimed security strength of a 512-bit hashfunction are omitted, Grøstl and JH have differential properties that extend through mostor all of the rounds, while the remaining three candidates only have distinguishers that
extend through about half of their rounds.
d. The cryptanalysis performed on BLAKE, Grøstl, and Skein appears to have a great dealof depth, while the cryptanalysis on Keccak has somewhat less depth, and that on JH has
relatively little depth.
e. While the tweaks on BLAKE, Keccak, and JH were sufficiently minor in that all thecryptanalysis performed throughout the competition applies to their final versions, Grøstl
and Skein were tweaked more significantly to address attacks on their first- and secondround versions. That said, even in the cases of Grøstl and Skein, most of the earlier
cryptanalysis carries over to the final version with only minor modifications; only the3

A definition for this term is provided in Section 4.1.2.

5

attacks targeted by the third-round tweaks are significantly affected, and in both cases,
the tweaks appear to be effective in eliminating the relevant vulnerabilities.
f.

NIST also considered the security of the finalists against side channel analysis, but there
was little available to distinguish between the finalists. While a case can be made that
ARX-based (Modular Addition, Rotation, and eXclusive OR-based) designs like BLAKE
and Skein may be more expensive to secure against side channel analysis than logicbased designs like Keccak and JH, any of the candidates can probably be made secureagainst side channel analysis with sufficient effort on the implementation end.

Keccak received a significant amount of cryptanalysis, although not quite the depth of analysis
applied to BLAKE, Grøstl, or Skein. This cryptanalysis left Keccak with a huge security margin –only five out of its 24 rounds has been broken by a near-collision attack. Keccak’s large security
margin, after significant cryptanalytic effort, suggests that Keccak will remain secure in the
future.
3.2

Performance

NIST was fortunate to have a great depth of performance data on the five finalists that could also
be compared with the performance data of the SHA-2 algorithms. This data included software
implementations on many different kinds of Central Processing Units (CPUs), and hardware
implementations in both Field Programmable Gate Arrays (FPGAs) and Application SpecificIntegrated Circuits (ASICs). All this data made simple comparisons very difficult; mostalgorithms excelled on some platforms and lagged on others. However, a few patterns emerged
from the performance data, which affected NIST’s decision:a. All five finalists perform well enough to be usable in most applications.
b. None of the five finalists is the best for every application, and none offers reallycompelling improvements over the SHA-2 algorithms.
c. The ARX-based algorithms, BLAKE and Skein, perform extremely well in software.
d. Keccak has a clear advantage in throughput/area performance in hardware
implementations.
e. Grøstl and JH are considerably slower than the other three algorithms in most software
implementations.
Keccak provides an excellent set of performance trade-offs – it is broadly competitive with SHA-2
in software, while providing much better throughput/area performance in hardware.
3.3

Other Algorithm and Implementation Characteristics

In addition to the bare essentials of security and performance, NIST also considered otherfeatures, which was another evaluation criterion identified in FRN-Nov07.
Keccak benefits from a very clean and elegant design, which is adaptable to a wide variety ofcircumstances. Its sponge domain extender makes it easy to analyze the security implications ofchanging the message block size to improve performance, and provides a mechanism forextending the output size to fit applications like RSA Full Domain Hash (RSA-FDH). Keccak
6also provides an 800-bit version of its internal permutation, which, if studied further from asecurity perspective, may be vetted and approved by NIST at some time in the future. If thispossibility is realized, the 800-bit permutation will increase the flexibility of Keccak even further.
While several of the candidates provide additional functionality above and beyond the simple
drop-in replacement for existing hash functions, Keccak’s built-in authenticated-encryption modeis one of the better “extras” offered and is a very natural extension of the sponge construction.
Overall, Keccak’s elegant design, flexibility, and “extras,” like its authenticated-encryptionmode, were points in its favor as the SHA-3 winner.
3.4

Complementing SHA-2

One additional consideration contributed to the selection of Keccak as the SHA-3 winner: SHA-3
will be deployed into a world in which the use of SHA-2 is widespread, and will coexist with
SHA-2 as an approved hash function. This makes a strong argument for an SHA-3 design thatcomplements that of SHA-2.
a. SHA-2 is a software-oriented ARX design, as are BLAKE and Skein. In terms of
performance and implementation properties, these two algorithms are rather similar to
SHA-2.
b. Because SHA-2 is an ARX-based design with a key schedule, it has some importantdesign elements in common with BLAKE and Skein, although neither is closely related
to SHA-2. However, cryptanalytic tools that apply to SHA-2 in the future seem more
likely to apply to BLAKE or Skein than to the other three finalists.
c. Keccak is a hardware-oriented design that is based entirely on simple bit-oriented
operations and moving bits around. Its performance and implementation properties are
significantly different from those of SHA-2.
Among all the finalists, NIST believes that Keccak provides the most advantages as an addition to
NIST’s toolbox of cryptographic algorithms. Keccak's software performance is broadly
comparable to that of the SHA-2 algorithms, but its hardware performance is much better, andKeccak does not need the 32- or 64-bit integer additions or key schedule that are required by
SHA-2.
3.5

Selection Conclusion

NIST’s decision rested almost entirely on the generous contributions of time and effort by thecryptographic community. Multiple implementations of the algorithms in hardware and software
made meaningful performance comparisons possible, and most of this work was done byvolunteers. Analyzing the security of a new cryptographic hash function is extremely demanding,requiring hard work from people with rare expertise and talents. This analysis was provided by
the members of the cryptographic community, including, but not limited to, the submitters of the
SHA-3 candidates. Without this huge volume of published information, representing a great many
years of skilled effort, NIST could never have run this competition.
Based on the data available, all five finalists appear to be excellent hash algorithms, providing
acceptable performance and security properties. Any of the five would have made an acceptablechoice for SHA-3.

7

Keccak offers acceptable performance in software, and excellent performance in hardware. It has
a large security margin, suggesting a good chance of surviving without a practical attack during
its working lifetime. Keccak is also a fundamentally new and different algorithm that is entirely
unrelated to the SHA-2 algorithms. For all these reasons, NIST chose Keccak as the new SHA-3
algorithm. Keccak's bit-oriented design may facilitate better understanding in the future, but atpresent the newness of the design means it is somewhat less well-understood than the ARX or Sbox-based designs.

8

4.

Security Analysis of the Finalists

This section describes the security of the five finalists. It is organized as follows: Section 4.1
gives an overview of the criteria that NIST used in comparing the depth and significance of
published cryptanalysis results on the five finalists and includes several tables comparing thefinalists according to these criteria. Section 4.2 summarizes the design and lists the publishedcryptanalysis results for each of the finalists. Section 4.3 gives NIST’s assessment of what
conclusions can be drawn from the results described in the first two subsections.
4.1

Security Overview

Security is the most important criterion for a new hash function; performance or implementation
advantages of a broken hash function are irrelevant. This section of the report discusses how
NIST weighed the evidence regarding the security of each of the five finalists, and how thisweighing helped determine the final selection of SHA-3.
The submission packages of the five finalists, and the published analysis of the finalists during
the four years of public review, provide significant information on their security. This
information falls into six categories:
a. Proofs of security relating to the hash functions' structure. These proofs typically show thatthe hash function has various good properties, assuming some good properties of theunderlying compression function, block cipher, or fixed permutation.

b. Cryptanalysis results on the hash function or its components that relate directly to the core
security properties of a hash function: preimage-resistance, second-preimage-resistance, andespecially, collision-resistance. Even when these attacks involve giving an attacker more
power than they would have in an attack on the full hash function, as with semi-free-startcollisions, these results are often the best indication available of how well the hash function
will survive future attacks. The fraction of the hash function (or underlying component
function) broken by these attacks can be used to calculate a security margin - the fraction of
the hash function's rounds that are still unbroken. For the SHA-3 finalists and SHA-2,
collision and near-collision attacks are the most informative source of information about thehash functions' security; the published preimage attacks have much higher required work, 4
and are, therefore, less worrisome.
c. Theoretical distinguishers on the hash function or its components. These involve someproperty that would not be present in an ideal hash function or component, but which has no
obvious relevance to any practical security concern about the hash function. Sometimes,
using these properties even requires more work than the claimed security level of the hashfunction.
d. Depth and maturity of cryptanalysis results. Some algorithms have received more
cryptanalysis than others; some have analysis that seems to be noticeably more mature (forexample, many different papers building on one another would indicate maturity). This isnecessarily somewhat subjective; different cryptographers might come to somewhat different
conclusions. A naïve approach might merely count the cryptanalysis papers. This is importantin evaluating the meaningfulness of the security margins of the hash function; a hash function
4

This reflects the fact that a brute-force collision attack on a hash function requires only the square root of the workrequired for a brute-force preimage attack.

9

that has had little analysis may have a large security margin simply because few cryptanalysts
have spent any time studying it.
e. Tweak history of the finalists. Prior to the start of the second and third rounds of thecompetition, the designers of the remaining candidates were allowed to make minor changes,
referred to as “tweaks,” to their designs. Some designers simply tweaked their algorithms byincreasing the number of rounds, which does not invalidate previous analysis results; otherschose to modify the internal structure of a component function to address a particular attack,or to improve some property of the hash function. Tweak history affects the meaningfulnessof the security margin of a hash function in a way similar to that of the depth of cryptanalysis.
If an algorithm has been tweaked in ways that invalidate previous cryptanalysis results, thenthe cryptanalysis on the final version of the algorithm is correspondingly less mature.
f.

Side channel analysis. Different algorithms have different implementation properties, andthus may have different susceptibility to side channel attacks, or may be more or lessexpensive to defend against such attacks. While most applications of hash functions do notneed resistance against side channel attacks, some important ones (most notably MAC
algorithms and key-derivation functions) do require this resistance, so differences invulnerability to side channel attacks, or in the cost of defending against them, matter for theselection of SHA-3.

No finalist was broken or seriously threatened by any attack published so far. All the finalists
have proofs relating their security to ideal properties of their underlying compression function,
permutation, or block cipher. Two of the finalists (Keccak and JH) have distinguishing attacks ontheir underlying primitives. However, the distinguishing attack on Keccak's permutation is far
beyond the security level claimed by a 512-bit hash function. The security results by themselves
did not disqualify any finalists, but they offered the best-available evidence for assessing the
likelihood that future cryptanalysis may threaten these algorithms.
4.1.1

Overview of Security Resources

NIST’s understanding of the security of the finalist hash functions is based on the work of thecryptographic community, as it appears in published cryptanalysis and security-proof papers.
Some of these papers were presented at the NIST-sponsored SHA-3 conferences; others were
presented at other conferences. In general, the results have had some level of peer review, though
it is always possible that incorrect results could have made it past the review. Some results
provide concrete findings, such as collisions for reduced-round versions of the hash functions,which can be verified; others are too expensive to be implemented in practice.
4.1.2

Domain Extenders and Proofs

Hash function design can be broken into two parts: building a fixed-size component like acompression function or fixed permutation, and then using that fixed-size component to build ahash function that can process variable-length strings up to some huge maximum length. The
construction used to build the full hash function is called a domain extender. The next two
subsections discuss the analysis of the fixed-size components used in the finalist hash functions.
This section discusses the analysis of the domain extenders of the finalists. Unlike thecryptanalysis results, the results on domain extenders are mainly built on proofs relating theproperties of the full hash function to the properties of the underlying fixed-length components.

10

BLAKE, Grøstl, and Skein build their full, arbitrary-input-length hash function from a fixedinput-length hash function called a compression function. At a lower level, the compressionfunctions of BLAKE and Skein are based on block ciphers, whereas that of Grøstl is based on apair of fixed permutations. The security properties of these hash functions can either be viewed as
being inherited from their compression functions or directly from the underlying components of
their compression functions. JH and Keccak build their full hash functions directly from a fixed
permutation. In each case, the full hash function inherits its security properties from the propertiesof this permutation.
Published proofs show that the security of all five finalists can be inferred from properties of theirunderlying building blocks. This kind of proof cannot guarantee that the hash function is secure,but it does show that certain kinds of weaknesses in the full hash function can only happen as aresult of corresponding weaknesses in its underlying building blocks. Because of this, proofs ofthis kind guarantee security against generic attacks – attacks that only exploit the domain
extender and not the internals of the underlying building blocks. Since cryptanalysts anddesigners spend most of their time considering the underlying building blocks, this is an
important guarantee.
Table 3 summarizes the security proofs for the finalists' and SHA-2’s domain extenders. All
numbers in this table are in bits. The sizes of the key, block, and tweak are denoted by k, b and t,
respectively, and L denotes the length of the target message in blocks. “Coll,” “Pre,” “2nd Pre,”and “Indiff” denote the approximate proven generic security against collision, preimage, second
preimage, and indifferentiability attacks, respectively. References for the finalists’ security
bounds are presented in Subsections 4.2.1.1 – 4.2.5.1.
For the purpose of the SHA-3 decision, these results can be summarized as follows:a. All five finalists have indifferentiability proofs, which guarantee that the hash function resists
generic attacks up to at least the complexity of a brute-force collision search, assuming thatthe underlying primitive is ideal.5b. Under the same assumption, all of the candidates except JH are proven to have near-optimalsecurity relating to the core properties of collision, preimage, and second-preimage
resistance. Even in the case of JH, the indifferentiability proof guarantees some genericsecurity for these properties (the optimal security, in the case of collision search), and there is
no known way for an attacker to exploit the JH domain extension to find preimages, orsecond preimages more efficiently than a brute-force search.
Nothing in these results provides a strong justification for selecting or discarding any of the five
finalists. However, these results are quite important for evaluating the finalists' security, as theyshow that the security of the full hash functions depends only on the security of the underlying
primitives, which is where the overwhelming majority of the cryptanalytic effort has been
focused so far.

5

Due to the length extension property, the indifferentiability bound for SHA-2 is 1. According to FRN-Nov07, SHA-3
candidates were required to resist attacks exploiting this property, but this was not considered a requirement for earlier
hash functions (i.e., those developed prior to the SHA-3 competition). Essentially all Internet protocols, in particular
those using HMAC [34], are designed to be secure even if they use a hash function that has the length extension
property.

11

Algorithm

DomainExtenderUnderlying
Primitive

BLAKE

HAIFA

Block cipher

GrøstlGrøstlA pair of
permutations

Primitive
size

Hash
size

k=512
b=512
k=1024b=1024
512
512
1024
1024

224
256
384
512
224
256
384
512
224
256
384
512
224
256
384
512
224
256
384
512
224
256
384
512

JH

JH

Permutation

1024

KeccakSpongePermutation

1600

Skein

UBI

Tweakable
block cipher

k=512
b=512
t=128

Block cipher

k=512
b=256
k=1024b=512

SHA-2 6

MD

Security
Coll
112
128
192
256
112
128
192
256
112
128
192
256
112
128
192
256
112
128
192
256
112
128
192
256

Pre
224
256
384
512
224
256
384
512
224
256
256
256
224
256
384
512
224
256
384
512
224
256
384
512

2nd Pre
224
256
384
512

224
256
256
256
224
256
384
512
224
256
384
512

Indiff
128
128
256
256
128
128
256
256
256
256
256
256
224
256
384
512
256
256
256
256

256 – log2L

1

512 – log2L

1

256 – log2L
512 – log2L

7

Table 3. Proven Generic Security of the SHA-3 Finalists and SHA-2 in Bits

4.1.3

Cryptanalysis and Security Margin

The most important security requirements for a hash function are collision and preimage
resistance. Informally, collision-resistance means that it is very difficult to find two different
input strings that yield the same message digest, while preimage-resistance means that it is very
difficult to find an input string that yields a particular desired message digest. This subsection
discusses the published attacks on the hash functions that relate to these core security propertiesof a hash function. In particular, the subsection focuses on the security against collision andrelated attacks, rather than on preimage attacks.
Given the attacks published on the SHA-3 finalists, collision attacks are more informative about
the ultimate security of the hash functions for three reasons. First, it is often possible to speed up
the brute-force search of a preimage by a small number of bits using a clever representation of theinternal state of the hash function and its computations – there are a number of results along theselines on the finalists, and while the techniques used are clever, it is difficult to see any
implications of these attacks for the security of the hash functions. Second, brute-force preimage
6

SHA-2’s domain extender is optimally collision and preimage resistant under the ideal cipher model [35]. The
security of the Merkle-Damgård (MD) domain extender against second-preimage attacks is n- log2L, where L is thelength of the message in blocks [36], assuming the compression function behaves like a random oracle.
7
Note that these security estimates ignore any constant factors in the proofs that are unrelated to the input and output
sizes of the hash function and its components.

12

attacks on the SHA-3 finalists are extremely computationally demanding, requiring at least 2224
compression function computations, and the published cryptanalytic preimage attacks typicallyhave much higher complexities than the published collision and related attacks for this reason.
And finally, for the SHA-3 finalists, the preimage attacks were not the attacks that covered themost rounds with more than a tiny advantage over a brute-force search.
Table 4 shows the collision-type attacks that cover the largest number of rounds for each of the
finalists, while maintaining an attack complexity less than that of a brute-force collision search.
The best-known collision attack on SHA-2 is also shown, for reference. The column marked “CFCall” gives the time complexity of the best attack, relative to the computational cost of one
execution of the hash algorithm’s compression function.
Algorithm

RoundsPercent
BrokenCF Call

Reference

4/14

29 %

221

[37]

6/10

60 %

2120

[38]

26/42

62 %

2112

[39]

Hash function

5/24

21 %

Example
given

[40]

Semi-free-startnear collision

Compressionfunction

32/72

44 %

2105

[41]

Collision

Hash function

24/64

38 %

Example
given

[42]

Attack Type

TargetSemi-free-startnear collisionSemi-free-startcollision
Semi-free-startnear collision

CompressionfunctionCompressionfunctionCompressionfunction

KeccakNear collision

Skein
SHA-2

BLAKE
GrøstlJH

Table 4. Best Known Collision-type Attacks against the SHA-3 Finalists and SHA-2

In many ways, these attacks are hard to compare with one another. For example, the best attacks
on BLAKE, Keccak, and SHA-2 can be implemented in practice, whereas the best attacks on
Grøstl, JH, and Skein would require huge computational resources to implement, and cannot be
fully verified. The best attacks on Keccak and SHA-2 apply to the hash function as a whole,while the best attacks on BLAKE, Grøstl, JH, and Skein apply to their underlying compressionfunctions, and give the attacker more control over the inputs to those functions than they would
have in an attack on the full hash function. More fundamentally, comparing cryptanalytic results
can favor algorithms that are not heavily analyzed, or algorithms that require the development of
new techniques to analyze them.
Despite these limitations, however, these results are what is available; they, along with somesecurity arguments offered by the designers, are the basis for comparing the finalists' security
against cryptanalysis. It is a truism that attacks only get better. The SHA-3 competition has
brought a great deal of analysis to bear on the finalists, but the winner will inevitably be the focusof even more cryptanalytic effort, and so it must be assumed that the existing published attacks
will improve over time.
The first piece of information that can be taken from these results is that, after four years ofintense analysis, no attack has come anywhere close to threatening the core security properties ofany of the five finalists. This provides some reassurance about the SHA-3 process. If two or threeof the five finalists had been broken or seriously threatened by now, this would raise questions
about the community's ability to develop secure hash functions.

13

The second piece of information from these results is that there are differences in the size of the
security margins of the different finalists, where the security margin is defined as the fraction of
the hash or compression function that has not been successfully attacked. (For example, an attack
on six rounds of a ten-round hash function would give a 40 % security margin.) Keccak has thelargest security margin, with 79 % of its hash function still unbroken; JH has the smallest security
margin, with 38 % unbroken. Comparing these security margins must be done carefully, given the
different kinds of attacks, work factors, and amounts of cryptanalysis performed on the different
candidates. Table 5 tries to summarize this picture. The depth of analysis is a rather subjective
measure, based on NIST’s reading of the literature. This measure takes into account not only the
number of cryptanalysis papers published, but also the depth and maturity of the analysis and thetools used to cryptanalyze the algorithm. The “depth of cryptanalysis” measure is described insomewhat more detail in Section 4.1.5.

Algorithm

Best
AttackSecurity
MarginWork

Depth of Analysis

BLAKE

Semi-free-start nearcollision

71 %Practical

High

GrøstlSemi-free-start collision

40 %Impractical

Very High 8

JH

Semi-free-start nearcollision

38 %Impractical

Low

KeccakNear collision

79 %Practical

MediumSkein

Semi-free-start nearcollision

56 %Impractical

High8

SHA-2

Collision

62 %Practical

MediumTable 5. Security Margins for the Five Finalists Based on Collision-type Attacks

This way of looking at the cryptanalysis results is quite unfavorable to JH, which received
relatively limited cryptanalysis, and still seems to have a rather small security margin. It isrelatively favorable to BLAKE and Keccak (with large security margins, despite a reasonable
depth of analysis), and also to Skein (with a relatively large security margin, despite a reasonable
depth of analysis, and a best attack with an impractically high amount of work required). The
picture for Grøstl is less clear; Grøstl has a relatively low security margin, but is the most deeply
analyzed finalist, and its best attack requires an impractically high amount of work and applies
only to its compression function.
Considering this table alongside the performance of the different algorithms makes the picture
somewhat clearer: JH and Grøstl are generally the two slowest algorithms in software. An
extremely fast algorithm whose security margin is uncomfortably narrow most likely can simply
be tweaked by adding rounds, and NIST explicitly stated in its call for submissions that it might
adjust the number of rounds for the winner. This is not an appealing option for an algorithm
whose performance is already marginal. If JH or Grøstl were selected, they would likely have tokeep their relatively narrow security margins in order to maintain acceptable performance.

8

These two algorithms were significantly tweaked for the third round. Some of the cryptanalysis performed on theearlier versions of the algorithms no longer applies.

14

Considering the 512-bit versions of the hash functions gives very similar results; there aresomewhat fewer results on 512-bit versions, but because brute-force attacks against a 512-bit
hash function are more expensive than the corresponding brute-force attacks against a 256-bit
hash function, more expensive analyses can be considered to be valid attacks, and this sometimes
allows an attack to extend another round or two.
4.1.4

Distinguishing Attacks and Differential Properties

Many of the cryptanalytic attacks on the finalists do not directly attack the core hash function
properties of collision- and preimage-resistance. Instead, they attempt to find some unexpected
property of the underlying primitives (block ciphers and fixed permutations) on which thefinalists are based. For example, there may be a predictable relationship between the XOR
differences of two input messages and their corresponding message digests – i.e., a differential
property. It is not at all clear how relevant these results are in evaluating the security of the
finalists. These distinguishing attacks have no practical relevance in attacking the hashfunctions. However, there is a good reason to give them at least some weight: all five finalists
have proofs of security on their domain extenders, showing that if their underlying component
functions behave in an ideal way, the full hash function will be secure according to some formal
definition. A theoretical distinguishing attack is a way of showing that these components do not
behave in an ideal way, and thus potentially undermining these proofs. Table 6 shows the bestknown distinguishing attacks and differential-property analyses.

Algorithm

TargetRoundsFraction of
TargetAnalyzed

CF Call

Reference

BLAKE-256

Block Cipher

7/14

50 %

2232

[43]

Grøstl-256

Permutation

9/10

90 %

2368

[44]

42/42

100 %

2304

[39]

24/24

100 %

21579

[45]

14/24

58 %

2255.77

[46]

37/72

52 %

2511.2

[47]

36/72

50 %

2454

[48]

46/64

72 %

246

[49]

JH

Compression
Function
Permutation

KeccakPermutation
Compression
Function
Skein

SHA-2

Compression
Function
Hash
Function

Table 6. Best Known Distinguishing Attacks and Differential Properties for the Finalists and SHA-2

Note that for BLAKE, Grøstl, and SHA-2, which have both 256- and 512-bit functions, this tableapplies only to the 256-bit functions.

15

4.1.5Depth of Analysis and Understandability of Algorithms

Another aspect of the published security results that NIST considered in the selection of SHA-3
was how well understood the finalists seemed to be, and how understandable they ultimately
appear to be.
Evaluating the depth of analysis on each of the finalists is inherently somewhat subjective;
different cryptographers may come to different conclusions when reading the literature. However,this evaluation is also necessary, because the security margins discussed above can be misleading
if some algorithms have received little or no analysis, while others have been carefully
scrutinized for weaknesses. More importantly, choosing a SHA-3 winner involves making a
prediction that this winner is very unlikely to suffer some practical attack during its working
lifetime. Unfortunately, the state-of-the-art in hash function cryptanalysis and design doesn'tallow this prediction to be made with certainty. NIST had to rely on its own evaluation of the best
attacks, and also of how much further the best published attacks might be pushed, with further
analysis.
It is easy, but rather misleading, to quantify the amount of analysis by counting the number ofcryptanalysis papers published on each finalist. Certainly, NIST took notice of how many papers
were published on each algorithm, but this metric can be misleading on many levels: finalists
with substantial tweaks often had more papers published simply to apply old attacks to thetweaked algorithm; some algorithms may have attracted more relatively small results as opposed
to a smaller number of deeper results; and algorithms with more weaknesses may even haveattracted more papers attacking them. Instead, NIST considered the depth of cryptanalysis on the
different finalists.
The only finalist NIST believed to be seriously called into question by this analysis was JH,
which has received much less analysis than the other finalists, and yet has a relatively small
security margin. NIST also considered the depth of analysis in looking at security margins; therelatively large security margin of Keccak and the relatively small security margin of Grøstl
partly reflect the difference in the intensity of cryptanalysis they received during the competition.
Grøstl, Skein, and BLAKE received more analysis than Keccak, probably because of Grøstl's
similarity with AES and several other SHA-3 candidates, and Skein’s and BLAKE's similarity
with the large number of ARX-based hash functions meant that many existing techniques andtools existed for beginning the analysis.
One common bit of feedback that NIST received from the community involved ARX vs. nonARX designs. Recall that an ARX design gets its security from the combination of addition,
rotation, and exclusive OR operations. (Many ARX-based hash functions and ciphers include
other elements, such as bitwise logical functions and variable rotates.) BLAKE and Skein are
ARX designs, as are the existing SHA-2 hash functions. Some people in the cryptographic
community feel that this kind of design is inherently hard to understand, and expressed apreference for non-ARX designs that may ultimately be better understood. It was not clear how
much weight to give this feedback, given that at present, all widely used hash functions are ARX
designs, and the two ARX-based finalists appear to be more extensively analyzed than Keccak or
JH.
4.1.6

Tweak History of the Finalists

In the Federal Register Notice [6] that called for the SHA-3 algorithm submissions, NIST
indicated that a submission package could include a tunable security parameter, such as the16number of rounds, which would allow the selection of a range of possible security/performancetrade-offs. That parameter, the number of rounds, was indeed utilized by all the designing teamsof the finalists, and was specified in their submission packages. Prior to the start of the second
and third rounds of the competition, the designers of the remaining candidates were also allowed
to make minor changes, referred to as “tweaks,” to their designs. Some designers simply tweaked
their algorithms by increasing the number of rounds, which does not invalidate previous analysis
results; others chose to modify the internal structures of a component function. These tweaks are
summarized in Table 7.
Algorithm
BLAKE

GrøstlSecond-Round
Names
TweaksBLAKE-28 None
BLAKE-32
BLAKE-48
BLAKE-64

Names
BLAKE-224
BLAKE-256
BLAKE-384
BLAKE-512

Grøstl-0

Grøstl

None

JH

JH

None

JH42

KeccakKeccakMessage block size
(rate) increased.

KeccakThird-RoundTweaksNumber of rounds increased
from 10 to 14 for BLAKE-224
and BLAKE-256; and from 14
to 16 for BLAKE-384 and
BLAKE-512.
Shift values in Q changed.
Round constants in P and Q
changed.
Number of rounds increased
from 35.5 to 42.
Padding rule simplified.
Diversifier parameter removed.

Skein

Skein

Number of rounds
increased from 18
to 24.
Rotation constantschanged.

Skein

The restriction on the supported
values of r removed.
Key schedule parity constantchanged.

Table 7. Tweak History of the SHA-3 Finalists

Of the finalists, BLAKE and JH were only tweaked to increase the number of rounds. This does
not affect any cryptanalysis prior to the tweak and is, therefore, the most innocuous type of
tweak.
Keccak changed the block sizes and padding rules, which affects generic security, but left theunderlying 1600-bit permutation unaltered. Keccak also increased the number of rounds from 18
to 24. These tweaks are also fairly innocuous. All of the cryptanalysis on Keccak’s 1600-bit
permutation remains valid, and the changes in generic security caused by the tweaks are wellunderstood.
Skein and Grøstl were both tweaked in ways that invalidated some cryptanalysis made prior to
the final round. In each case, the third-round tweak was targeted at specific cryptanalysis. Skein’s
tweak targeted attacks exploiting the rotational symmetry of the key-schedule parity constant, andGrøstl’s tweak targeted attacks exploiting the similarity of the P and Q permutations to one
another. In both cases, cryptanalysis similar to the targeted attacks ceased to be a major threat,
and attacks that were not targeted by the tweak needed some modification, but were, for the mostpart, readily adapted to apply to the final version. Skein was also modified in the second round in17

a way that could potentially affect analyses done on the first-round version of Skein, but thistweak was not in response to any specific attack.
4.1.7

Side Channel Attacks and Countermeasures

4.1.7.1 Overview of Side Channel Attacks on Hash Functions
Side channel attacks exploit the physical properties of an implementation of a cryptographic
algorithm to learn some information about the algorithm’s internal state. For example, a given
software implementation of a hash function might take slightly more or less time to process an
input string, depending on the contents of the string. The side channels commonly considered in
the literature are timing, power, and electromagnetic (EM) emissions.
4.1.7.2

Applicability of Side Channel Attacks

Side channel attacks are relevant only in a narrow subset of hashing applications. In many
applications, such as digital signatures, the input to the hash function is not a secret, andtherefore, side-channels on the hash function are not relevant. Side channel attacks can be used toreveal some secret information that has been processed by a hash function, but cannot be used toviolate the core collision- and preimage-resistance properties of a hash function. Side channels
are relevant when there is a secret value being processed by the hash function, such as a keyderivation key or the key in a MAC computation, and when the device implementing the hashfunction can be observed carefully by an attacker. For example, a power-analysis attack is only
practical when an attacker can precisely measure the power used during cryptographic
computations – such attacks pose a lot more threat to smartcard applications than to server
applications.
One finalist, Keccak, has an interesting property that was first noticed internally at NIST anddescribed in [50] (and presented in [51]): because the hash function does not have any noninvertible steps, an attacker who learns the entire intermediate state for any HMAC-Keccak
computation can use this to determine the original key used for the HMAC computation, and canforge arbitrary messages for this key. By contrast, the other four finalists and the SHA-2
algorithms are somewhat less vulnerable; determining some arbitrary intermediate state of the
HMAC computation can allow some forgeries (extensions of previously observed messages), butdoes not reveal the HMAC key or allow arbitrary forgeries. This property does not appear to
NIST to have a major security impact, however.
4.1.7.3 Published Side Channel Attacks and Analysis on the SHA-3 Finalists
Side channel attacks work by finding some statistical relationship between things that an attacker
can measure, such as the power or time required to do some computation, and some secretinternal state of the algorithm. In general, a naïve implementation of a cryptographic algorithm isvery likely to be vulnerable to a side channel attack, and indeed, side channel attacks werereported on straightforward implementations of all five SHA-3 finalists [52, 53]. Devices thatneed to resist these attacks introduce countermeasures to limit the amount of information leaked.
The countermeasures can exist at various levels, from the design of transistors all the way up to
the design of protocols. Some countermeasures are more or less algorithm-independent; others
are specific to a particular kind of cryptographic algorithm.
The reported side channel attacks on the SHA-3 finalists used power, EM analysis, and timingside channels. In broad terms, side channel attacks can be targeted at hardware (ASIC or FPGA)

18

implementations, low-end software implementations (on small microprocessors without memory
caches), and high-end software implementations. In general, EM and power analysis are moredifficult on hardware implementations than on software implementations [52].
Based on [52, 53, 54, 55, 56], the SHA-3 finalists can be broken into three groups with respect toside channel attacks: the S-box-based design, the logical-operations-based designs, and the ARXbased designs.
Grøstl, which uses the eight-bit S-box from AES, is the only S-box-based design. There arecountermeasures against side channel attacks that can be used to protect S-box accesses. Naïve
high-end software implementations of Grøstl are vulnerable to cache-timing attacks related tothose found against AES [57]. However, the use of the AES-NI instructions eliminates the timing
channel, and there are efficient bit- and byte-slice implementations of Grøstl for high-end
software [58] that prevent timing attacks, even without the AES-NI instructions. (These
implementations would move Grøstl into the logical-operations category.)
JH 9 and Keccak use logical operations – these are probably the easiest algorithms to protect
against side channel attacks, and the Keccak team proposed some techniques for protecting
Keccak implementations from side channel attacks in [55].
BLAKE and Skein, like the SHA-2 algorithms, are ARX-based designs, which require 32- or 64bit integer additions and rotates. These are probably the most expensive designs to protect fromside channel analysis.
Unfortunately, the published analyses offered very limited information about the difficulty of
implementing each of the SHA-3 finalists in a way that is resistant to side channel attacks.
One general technique for protecting an algorithm from side channel attacks is called masking[55], which involves dividing the secret values into “shares” and then operating on the shares
independently. The more shares the variables are divided into, the higher the order of differential
power analysis 10 (DPA) the algorithm can be protected against. The type of operations that analgorithm requires determines how the shares are derived and recombined. The operations can bedivided into two categories: logical and arithmetic. Creating shares for either of the operation
types is straightforward; however, when the two operation types are mixed, a conversion must be
performed to convert the shares from one representation to the other. Since Keccak and the bitslice implementation of JH only use logical operations, creating shares and using them isstraightforward. However, the ARX-based algorithms (BLAKE and Skein) use a combination oflogic and arithmetic operations; these algorithms require a great deal of computation for themasking to protect against SCA, which results in severe performance degradation.
4.2

Finalist Profiles and Cryptanalysis

This section provides a brief description of each finalist, including its basic building blocks,
domain extender, and tunable parameters. Each description is followed by a summary of theexisting security analysis, including the analyses of any previous versions of the algorithm. The
inclusion of these analyses is intended to provide references as to why certain candidates were
tweaked in order to address previously unknown vulnerabilities. As much as is feasible, theanalyses are presented in chronological order.
9

While JH uses two 4x4-bit S-boxes, the suggested bit-sliced implementation of JH uses logical operations to
implement these S-boxes rather than a table look-up.
10
A powerful category of side channel attacks.

194.2.1BLAKE

BLAKE uses HAIFA [59] as its domain extender. The BLAKE compression function is based ona wide-pipe block cipher using a modified Davies-Meyer construction. The block cipher operates
on an inner state that can be represented as a four-by-four matrix of words. BLAKE-224 and
BLAKE-256 use a 512-bit-wide block cipher consisting of 32-bit words, while BLAKE-384 and
BLAKE-512 use a 1024-bit-wide block cipher consisting of 64-bit words. The internal state is
initialized using an Initialization Value (IV), a salt and a counter, and is updated using the Gfunction, which is based on the ChaCha stream cipher [60]. The G function updates the columns
and the disjoint diagonals of the state using ARX operations. The input-message words andconstants are selected using round-dependent fixed permutations. The designers defined four toy
versions for analysis purposes, namely: BLOKE, FLAKE, BLAZE, and BRAKE.
To generate 224-, 256-, 384- and 512-bit message digests, four instances were proposed:
BLAKE-28, -32, -48 and -64. For the final round of the competition, these functions wererenamed to BLAKE-224, -256, -384 and -512; and the tunable parameter of BLAKE – thenumber of rounds – was increased from 10 to 14 rounds for BLAKE-224 and -256, and from 14
to 16 rounds for BLAKE-384 and -512.
4.2.1.1

Analysis of the BLAKE Domain Extender

Andreeva et al. [61] proved that BLAKE-256 is secure against preimage, second-preimage andcollision attacks up to 2256, 2256, and 2128 queries, respectively; similarly, BLAKE-512 is secure up
to 2512, 2512, and 2256 queries against the above attacks if the underlying block cipher is structurally
strong. Andreeva et al. [61] and Chang et al. [62] observed that the compression function of
BLAKE does not behave ideally, even if its underlying block cipher is ideal. Then, Andreeva et
al. [61] and Chang et al. [62] proved that, under the assumption that the block cipher is ideal,
BLAKE-256 and BLAKE-512 are indifferentiable from random oracles up to 2128 and 2256
queries, respectively; this means that they are secure against all nontrivial generic attacks up to2128 and 2256 queries, respectively.
4.2.1.2

Pre-Round 3 Analysis

The first public analysis of BLAKE was done by Li and Xu [63]. The authors found a method tocontrol some of the intermediate hash words using message modification techniques, andpresented free-start collision and preimage attacks for BLAKE, with the compression function
reduced to 2.5 rounds. The time complexities are 296, 2112, 2160 and 2224 for the collision attack,and 2209, 2241, 2355 and 2481 for the preimage attack, for BLAKE-28, -32, -48, and -64,
respectively.
Guo and Matusiewicz [64] presented a near-collision attack for the compression function of
BLAKE-32, reduced to four middle rounds, starting from round three, with complexity 256. The G
function is linearized by replacing the modular addition with the XOR operation, and thenrotation-invariant differences are introduced to the chaining value, the salt, the counter, and themessage to obtain 24-bit near collisions.
Aumasson et al. [65] proved that one round of BLAKE is a permutation of the message andpresented an efficient inversion algorithm. The authors presented an improved preimage attack on
1.5 rounds, with complexity 2128, and impossible differentials for the permutation with five and20

six rounds for BLAKE-32 and -64, respectively. The authors also described near collisions forfour of the middle rounds of the compression function of BLAKE-32.
Sönmez Turan and Uyan [66] used a hill-climbing approach that introduced random differences
to message blocks and showed practical near collisions with 47 and 72 bits of difference for thecompression function of BLAKE-32, reduced to 1.5 and two rounds, respectively, withcomplexity 226.
Vidali et al. [67] presented an efficient method for an arbitrary number of collisions for the fullround BLOKE and an internal collision attack on BRAKE.
Su et al. [37] used linear differential techniques to analyze the near-collision resistance of thecompression function of BLAKE and showed near-collision attacks on 152, 396, and 306 bits forthe compression functions of BLAKE-32, -64 and -64, reduced to four, four, and five middle
rounds, with complexity 221, 216, and 2216, respectively.
Ming et al. [68] studied the reversibility properties of the internal permutation of BLAKE. The
authors presented some differential properties of G and G-1, and showed that BLAKE has strong
resistance against differential attacks.
Biryukov et al. [43] applied the boomerang attack to BLAKE-32 and obtained distinguishers on
the compression function, reduced to seven rounds, and on the keyed permutation, reduced toeight rounds, with complexity of 2232 and 2242, respectively. The authors argued that the attack isapplicable to the other versions of BLAKE as well. Leurent [69] noted that the characteristics
used for the eight-round attack are incompatible.
Table 8 summarizes the cryptanalysis results on BLAKE before its Round 3 submission. In thistable and the summary-of-cryptanalysis tables to follow, a “SFS Collision” denotes a “Semi-FreeStart Collision,” and “CF” stands for “Compression Function.” Attacks with an empty table entry
for “Memory” have negligible memory complexity.

21

TargetHash function
Hash function
Hash function
Hash function
Hash function
Hash function
Hash function
Hash function
CF
Hash function
Block Cipher
Block Cipher
CF
Hash function
CF
CF
CF
CF
CF
Block Cipher

Attack type
Preimage
Preimage
Preimage
Preimage
Collision
Collision
Collision
Collision
Near collision
Preimage
Impossible
differential
Impossible
differential
SFS near collision
Collision
SFS collision
Near collision
Near collision
Near collision
Distinguisher
Distinguisher

Output
224
256
384
512
224
256
384
512
256
256

Variant CF Call Memory Reference
2.5 rounds
2209
[63]
241
2.5 rounds
2[63]
2.5 rounds
2355
[63]
2.5 rounds
2481
[63]
96
2.5 rounds
2[63]
2.5 rounds
2112
[63]
2.5 rounds
2160
[63]
2.5 rounds
2224
[63]
56
4 rounds
2[64]
1.5 rounds
2128
[65]

224,256

5 rounds[65]

384,512

6 rounds

[65]

256
all
all
256
512
512
256
256

2 rounds
BLOKE
BRAKE
4 rounds
4 rounds
5 rounds
7 rounds
8 rounds

exampleexampleexample
221
216
2216
2232
2242

[66]
[67]
[67]
[37]
[37]
[37]
[43]
[43]

Table 8. Summary of Cryptanalysis Results on BLAKE Prior to its Round 3 Submission

4.2.1.3

Round 3 Analysis

Only a few cryptanalysis papers were published on the final version of BLAKE. However, since
the only substantive change made for the third round of the competition was an increase in thenumber of rounds, previous analyses of BLAKE are still valid.
Tuple cryptanalysis is a variant of structural cryptanalysis that uses ordered multisets. Aumasson
et al. [70] presented a distinguisher, using Tuple cryptanalysis, on the four-round permutation of
BLAKE-256, with time complexity of 264.
Dunkelman and Khovratovich [71] used an iterative differential characteristic based on two
different characteristics of the internal permutation, and combined it with a rebound process tofind colliding pairs in the compression function, reduced to three rounds, with a complexity of
260. The attack was extended to six rounds, with a complexity of 2456 and a memory requirementof 2354.
Table 9 summarizes the cryptanalysis results on BLAKE’s Round 3 submission.
TargetAttack type Output Variant CF Call Memory Reference
Block Cipher Distinguisher
256
4 rounds
264
[70]
456
354
Block Cipher Distinguisher
256
6 rounds
2
2[71]
Table 9. Summary of Cryptanalysis Results on BLAKE’s Round 3 Submission

224.2.2

GrøstlGrøstl is a wide-pipe Merkle-Damgård (MD) hash algorithm with an output transformation. The
compression function is a novel construction, using two fixed 2n-bit permutations – denoted by P
and Q – in parallel to produce a 2n-bit compression function. Intermediate chaining values are
512 bits wide for Grøstl-256, and 1024 bits for Grøstl-512. The output transformation processes
the final chaining state and discards half the bits of the result to yield an n-bit message digest.
Grøstl-256 has ten rounds, while Grøstl-512 has fourteen rounds.
The permutations, P and Q, are based on the structure of AES, reusing the AES S-box, but
expanding the size of the block to 512 bits for Grøstl-224 and Grøstl-256, and to 1024 bits for
Grøstl-384 and Grøstl-512 in a straightforward way.
Grøstl was tweaked for the third round of the competition to eliminate the attacks on the originalsubmission.
4.2.2.1

Analysis of the Grøstl Domain Extender

Andreeva et al. [73] showed that, if the underlying permutations P and Q are free from all
structural weaknesses and are independent, Grøstl-256 is secure against preimage, secondpreimage and collision attacks up to 2256, 2256-log2L, and 2128 queries (where L denotes the length ofthe message in blocks). Similarly, Grøstl-512 is secure against the above attacks up to 2512, 2512log2L, and 2256 queries. Under the same assumptions, Grøstl-256 and Grøstl-512 are indifferentiablefrom random oracles up to 2256 and 2512 queries, respectively [74]; this guarantees the security of
Grøstl-256 and Grøstl-512 against all nontrivial generic attacks up to 2256 and 2512 queries.
In [75] Kelsey noted the importance of truncation in the output transformation of the Grøstl hashfunction.
4.2.2.2

Pre-Round 3 Analysis

Prior to the third round, Mendel et al. [76] showed a six-round (out of ten) semi-free-startcollision on the Grøstl-256 compression function, with 2120 time and 264 memory complexity.
Mendel et al. [77] improved this result and showed a six-round semi-free-start collision on the
Grøstl-256 compression function, with 264 time and 264 memory complexity; a seven-round
distinguisher on the permutation component of the Grøstl-256 compression function, with 255
time complexity; and a seven-round distinguisher on the output transformation of Grøstl-256,
with 256 time complexity.
Gilbert and Peyrin [78] provided a seven-round semi-free-start collision on the Grøstl-256
compression function that requires 2120 time and 264 memory; and an eight-round distinguisher for
the Grøstl-256 compression function that requires 2112 time and 264 memory.
Mendel et al. [79] also presented a four-round collision on the Grøstl-256 hash algorithm,
requiring 264 time and memory; a seven-round semi-free-start collision on the Grøstl-256
compression function, requiring 2120 time and 264 memory; a five-round collision on the
Grøstl-512 compression function, requiring 2176 time and 264 memory; and a seven-round semifree-start collision on the Grøstl-512 compression function, requiring 2152 time and 264 memory.
Peyrin [80] demonstrated a five-round collision on the Grøstl-256 hash algorithm that requires 279
time and 264 memory; a six-round collision on the Grøstl-512 hash algorithm, requiring 2177 time23and 264 memory; a full-round distinguisher on the Grøstl-256 compression function, with 2192
time and 264 memory complexity; a full-round distinguisher on the Grøstl-256 component
permutations, with 2192 time and 264 memory complexity; an eleven-round distinguisher on the
Grøstl-512 compression function, with 2640 time and 264 memory complexity; and an elevenround distinguisher on the Grøstl-512 component permutations, with 2640 time and 264 memory
complexity.
In addition, Ideguchi et al. [81] showed a six-round collision on the Grøstl-256 hash algorithm,
requiring 2112 time and 232 memory; a seven-round semi-free-start collision on the Grøstl-256
compression function, requiring 280 time and 264 memory; an eight-round semi-free-start collisionon the Grøstl-256 compression function, requiring 2192 time and 264 memory 11; a seven-round
distinguisher on the Grøstl-256 component permutations, requiring 219 time, with no significant
memory requirement; and an eight-round distinguisher on the Grøstl-256 component
permutations, requiring 264 time and 264 memory.
The attacks have improved over time, as the basic techniques (rebound attacks, super-S-box
attacks, and differentials considered between the corresponding rounds of the P and Q
permutations) are extended and refined. The time complexities of the rebound attacks on Grøstl
by Peyrin [80] have been improved by a factor of about 210 by Naya-Plasencia [82]; however, this
attack does not apply to the tweaked submission for the final round of the competition.
Sasaki et al. [83] found semi-free-start collisions on Grøstl-512, reduced to seven rounds, with
2152 time and 256 memory complexity. They also found a distinguishing attack on the internal
permutations of Grøstl-256, reduced to eight rounds, with 248 time and 28 memory complexity.
In a presentation [84] at FSE 2011, Boura et al. mentioned that techniques similar to thosedescribed in their paper [85] could be used to produce a zero-sum distinguisher with timecomplexity 2509 for the 512-bit permutations of Grøstl-256.
Table 10 summarizes the cryptanalysis results on Grøstl before its Round 3 submission.

11

This is above the collision bound, and therefore, is listed as a distinguisher in Table 10.

24

TargetAttack typeOutputVariant

CF
CF
Permutation
Output transform
Permutation
Permutation
CF
CF
Hash function
Hash function
CF
CF
Permutation
Permutation
Permutation
CF
CF
CF
Hash function
Hash function
Hash function
Hash function
Hash function
CF
CF
Permutation
Permutation
CF
Permutation
CF
CF
Permutation
Permutation

SFS collision
SFS collision
Distinguisher
Distinguisher
Distinguisher
Distinguisher
SFS collision
Distinguisher
Collision
Collision
SFS collision
SFS collision
Distinguisher
Distinguisher
Distinguisher
Distinguisher
Distinguisher
Distinguisher
Collision
Collision
Collision
Collision
Collision
SFS collision
Distinguisher
Distinguisher
Distinguisher
Distinguisher
Distinguisher
Distinguisher
SFS collision
distinguisher
Distinguisher

256
224,256
224,256
224,256
256
256
256
256
224,256
384,512256
384,512
256
256
512
256
256
512
256
512
224
256
256
224,256
224,256
224,256
224,256
256
256
512
512
256
256

6 rounds
6 rounds
7 rounds
7 rounds
7 rounds
8 rounds
7 rounds
8 rounds
4 rounds
5 rounds
7 rounds
7 rounds
9 rounds
10 rounds
11 rounds
9 rounds
10 rounds
11 rounds
5 rounds
6 rounds
5 rounds
5 rounds
6 rounds
7 rounds
8 rounds
7 rounds
8 rounds
10 rounds
10 rounds
11 rounds
7 rounds
8 rounds
10 rounds

CF
Call
2120
264
255
256
256
2112
2120
2112
264
2176
2120
2152
280
2192
2640
280
2192
2640
279
2177
248
248
2112
280
2192
219
264
2182
2175
2630
2152
248
2509

Memory Reference
264
264

264
264
264
264
264
264
264
264
264
264
264
264
264
264
264
232
232
232
264
264
264
264
264
264
256
28

[76]
[77]
[77]
[77]
[78]
[78]
[78]
[78]
[79]
[79]
[79]
[79]
[80]
[80]
[80]
[80]
[80]
[80]
[80]
[80]
[81]
[81]
[81]
[81]
[81]
[81]
[81]
[82]
[82]
[82]
[83]
[83]
[84]

Table 10. Summary of Cryptanalysis Results on Grøstl Prior to its Round 3 Submission

4.2.2.3

Round 3 Analysis

In response to the differential attacks mentioned above [79, 80, 81], Grøstl was tweaked [72] forthe final round to introduce more structural differences between the P and Q permutations, and tochange the round constants and the shift values in Q. These changes have rendered the previous
attacks ineffective.
Schläffer [38] published the first cryptanalysis on the tweaked Grøstl and showed a semi-freestart collision on the Grøstl-256 compression function, reduced to six rounds, with 2120 time and
264 memory complexity. This paper also showed a semi-free-start collision on the six-round
Grøstl-512, with 2180 time and 264 memory complexity. For collisions on the full hash function,25

only three rounds have been successfully attacked, with 264, 264 and 2192 time complexities andnegligible memory for Grøstl-224, Grøstl-256, and Grøstl-512, respectively.
Using rebound cryptanalysis techniques, Jean et al. [44] discovered differential properties for up
to nine rounds of the Grøstl-256 permutation, with 2368 time and 264 memory complexity; and up
to ten rounds of the Grøstl-512 permutation, with 2392 time and 264 memory complexity.
Khovratovich [86] studied the preimage resistance of the output transformation function of
Grøstl-256, and found a biclique attack [47] for up to six rounds, with 2251 time complexity.
Wu et al. [87] also published pseudo-preimage attacks on up to five rounds of Grøstl-256, with
2245 time and 2230 memory complexity, and up to eight rounds of Grøstl-512, with 2507 time and2507 memory complexity.
Table 11 summarizes the cryptanalysis results on Grøstl’s final-round submission.
TargetAttack typeOutputVariant

Hash function
Hash function
CF
CF
CF

Collision
Collision
SFS collision
SFS collision
SFS collision
Differential
Property
Differential
property
Differential
property
Differential
property

224,256
512
256
384
512

3 rounds
3 rounds
6 rounds
6 rounds
6 rounds

CF
Call
264
2192
2120
2180
2180

256

9 rounds

512

Permutation
Permutation
Permutation
Permutation
Outputtransform
Outputtransform
Outputtransform
Hash function
Hash function

MemoryReference

264
264
264

[38]
[38]
[38]
[38]
[38]

2368

264

[44]

8 rounds

2280

264

[44]

512

9 rounds

2328

264

[44]

512

10 rounds

2392

264

[44]

Preimage256

6 rounds

2251

Preimage256

5 rounds

2206

248

[87]

Preimage

512

8 rounds

2495

216

[87]

5 rounds
8 rounds

245

230

[87]
[87]

Pseudo-preimage
Pseudo-preimage

256
512

2
2507

[86]

2
2507

Table 11. Summary of Cryptanalysis Results on Grøstl’s Final-Round Submission

4.2.3

JH

The JH family of hash algorithms for different hash sizes is based on a single compressionfunction, F8, which uses a fixed 1024-bit permutation, E8. In F8, a message block of 512 bits is
XORed with the first 512 bits of the input of E8, and the last 512 bits of the output of E8. The
permutation E8 uses two 4x4-bit S-boxes, S0 and S1, an eight-bit linear permutation L, and a
permutation P8. Different members of the JH family are distinguished by the different IVs used,
and the message digests are obtained by truncating the final output to the desired hash sizes. JH
was tweaked after the second round by increasing the number of rounds from 35.5 to 42.

26

4.2.3.1

Analysis of the JH Domain Extender

Several papers have analyzed the domain extender of JH. Bhattacharyya et al. [88], and Mendel
and Thomsen [89] analyzed the preimage resistance of the JH domain extender from an
information-theoretic point of view; however, the actual complexities of the attacks are no better
than a brute-force search [90]. Bagheri [91] showed that a pseudo-collision of JH can easily befound, since JH’s compression function is invertible; however, since the IV of JH is a fixed
constant that is determined by the message-digest size, the pseudo-collision attack is notconsidered to be a serious threat to JH.
Bhattacharyya et al. [88] also showed that the indifferentiability security of the JH domain
extender is guaranteed up to approximately 172 bits.
Lee and Hong [92] showed that the JH domain extender achieved optimal collision resistance(256 bits for the 512-bit output size, and 192, 128, and 112 bits for the other three sizes).
Andreeva et al. [73] have improved the second-preimage resistance of the JH domain extenderfrom 172 bits to approximately 256 bits.
Moody et al. [93] improved the indifferentiability security bound of the JH domain extender from172 bits to approximately 256 bits.
4.2.3.2

Pre-Round 3 Analysis

Turan and Uyan [66] used hill-climbing techniques to produce a semi-free-start near collision on
ten rounds of JH’s compression function, with 223.24 time complexity. Rijmen et al. [94] proposeda semi-free-start collision attack for sixteen rounds of the JH hash function, with 2178.24 time and2101.12 memory complexity, and a semi-free-start near-collision attack for twenty-two rounds of
JH’s compression function, with 2156.56 time and 2143.70 memory complexity. Naya-Plasencia [82]proposed a semi-free-start collision attack for sixteen rounds of JH’s compression function, with
296.12 time and 296.12 memory complexity, and a semi-free-start near-collision attack for twentytwo rounds of JH’s compression function, with 295.63 time and 295.63 memory complexity.
Table 12 summarizes the cryptanalysis results on JH before its Round 3 submission.
TargetCF
Hash function
CF
CF
CF
CF

Attack typeOutput Variant CF Call Memory Reference
SFS near collisionall
10 rounds
223.24[66]
SFS collision
256
16 rounds
2178.24
2101.12[94]
156.77143.70SFS near collision256
19 rounds
2
2[94]
SFS near collision
256
22 rounds
2156.562143.70[94]
SFS collision
256
16 rounds
296.12296.12
[82]
95.63
95.63
SFS near collision
256
22 rounds
2
2[82]

Table 12. Summary of Cryptanalysis Results on JH Prior to its Round 3 Submission

4.2.3.3

Round 3 Analysis

Naya-Plasencia et al. [39] extended their previous analysis to produce semi-free-start internal
near collisions on 37 rounds of the JH compression function, with 2352 time and 257.6 memory

27complexity, and used similar techniques to find differential characteristics for all 42 rounds of theE8 permutation, with 2304 time and 257.6 memory complexity.
Table 13 summarizes the cryptanalysis results on JH’s Round 3 submission.
TargetAttack typeOutput Variant CF Call Memory Reference
Permutation Differential Property
all
42 rounds
2304
257.6
[39]
352
Permutation Differential Property
all
42 rounds
2
257.6
[39]
352
57.6
CF
SFS near collisionall
37 rounds
2
2
[39]
CF
SFS near collisionall
26 rounds
2112
257.6
[39]
Table 13. Summary of Cryptanalysis Results on JH’s Round 3 Submission

4.2.4

KeccakKeccak follows the sponge construction model [95], with a 1600-bit permutation. The message
block size varies according to the output size: Keccak-512 has a block size of 576 bits, Keccak384 has 832 bits, Keccak-256 has 1088 bits, and Keccak-224 has 1152 bits. In keeping with thestandard terminology for a sponge construction, the message block size is referred to as r, forrate, and the difference between the permutation size and the message block size is referred to asc, for capacity.
The Keccak team also defined a number of additional variants of Keccak. First, they defined a
one-size-fits-all variant “Keccak,” with rate 1024 and capacity 576, that they believe can be used,in practice, for any output size. The Keccak team does not consider this the official submitted
version for producing 512-bit and 384-bit outputs, since it does not provide the expected
preimage-resistance. However, the Keccak team argues that all the attacks that arise from thereduced capacity have an unrealistically high complexity of at least 2288 operations, and “Keccak”
with an output of 384 or 512 bits would be significantly faster than the submitted Keccak-384 andKeccak-512. The Keccak team also produced scaled-down versions of the Keccak permutation,with 25, 50, 100, 200, 400, and 800 bits, instead of 1600, and set up a cryptanalysis contest [96]challenging cryptanalysts to attack versions of Keccak with the capacity set to as few as 160 bits.
The permutation can be considered as a substitution-permutation network with five-bit-wide Sboxes, or as a combination of a linear mixing operation and a very simple nonlinear mixing
operation.
The recommended security parameter for Keccak is twenty-four rounds, which was tweaked, inthe second round, from the eighteen rounds specified in the original submission. Additionally, themessage block sizes of the 224-bit and 256-bit versions were increased from 1024 bits to 1152
and 1088 bits, respectively, as part of the second-round tweak. Keccak was also tweaked in thethird round, by simplifying the padding rule.
4.2.4.1

Analysis of the Keccak Domain Extender

Bertoni et al. [97] proved that Keccak-n is secure against preimage, second-preimage, andcollision attacks up to 2n, 2n, and 2n/2 queries if the underlying permutation is ideal. Bertoni et al.
[97] proved that, under the same assumption, Keccak-n is indifferentiable from a random oracle
up to 2n queries, which means that Keccak-n is secure against all nontrivial generic attacks up to
2n queries.

28

Gligoroski et al. [98] observed that if a particular second-preimage is found (most likely requiring
a one-time effort equivalent to brute-force), then an arbitrary number of second-preimages can befound very easily for any message.
4.2.4.2

Pre-Round 3 Analyses

Aumasson and Khovratovich [99] attempted algebraic attacks against significantly reduced-roundversions of Keccak by applying automatic cryptanalysis tools (a triangulation tool, and cube
testers) to Keccak’s permutation. The analysis was limited to three- and four-round versions of
Keccak, but the authors conjectured that structures may be observed in the permutation for up to
ten rounds. The authors of [99] concluded that Keccak has a comfortable security margin toprevent structural distinguishers.
Morawiecki and Srebrny [100] used SAT-solver techniques to find preimages for three rounds of
Keccak, with 40 unknown message bits.
Aumasson and Meier [46] first showed practical zero-sum distinguishers on nine rounds of the
Keccak permutation, and impractical distinguishers on a sixteen-round variant. Boura andCanteaut [101] later extended this to eighteen rounds. However, at a complexity of 21370, this
attack is only of theoretical interest. The Keccak team increased the number of rounds to twentyfour after the initial distinguisher was announced. Responses to [46] and [101] from the Keccak
team were provided in [102, 103]. Very high-complexity distinguishers continued to be
published: Boura and Canteaut [104] attacked 20 rounds, with a complexity of 21586. Boura et al.
[85] attacked all 24 rounds, with a complexity of 21590.
Lathrop [105] was able to use a cube attack to conduct a key-recovery attack on a secret prefix
Message Authentication Code (MAC), with a four-round Keccak variant.
Table 14 summarizes the cryptanalysis results on Keccak before its Round 3 submission.
TargetPermutation
Hash function
Permutation
Permutation
Permutation
Permutation
Permutation
Permutation
Secret-prefix MAC

Attack type Output Variant CF Call
Observations
all
Preimage1024
3 rounds
234
Distinguisher
all
9 rounds
229.83Distinguisher
all
14 rounds
2255.77
Distinguisher
all
16 rounds 21023.88
Distinguisher
all
18 rounds
21370
Distinguisher
all
20 rounds
21586
Distinguisher
all
24 rounds
21590
Key recovery
224
4 rounds
219

Reference
[99]
[100]
[46]
[46]
[46]
[101]
[104]
[85]
[105]

Table 14. Summary of Cryptanalysis Results on Keccak Prior to its Round 3 Submission

4.2.4.3

Round 3 Analyses

Morawiecki [106] used SAT-solver techniques to find preimages for two rounds of Keccak, with
80 unknown message bits, and to find collisions on two rounds of Keccak, with a 160-bit output.
Both were contest versions, with capacity reduced to 160 bits. Morawiecki demonstrated the low
attack complexity by actually performing the attack, rather than by computing a theoreticalcomplexity.

29

Duan and Lai [45] improved the time complexity of the 24-round zero-sum distinguisher attack to21579.
Duc et al. [107] applied rebound techniques to find a rebound differential property for eightrounds of the Keccak permutation, with a time complexity of 2491.47.
Bernstein [108] used algebraic techniques to speed up a brute-force second-preimage search for
up to eight rounds of Keccak.
Naya-Plasencia et al. [109] presented a preimage attack on two rounds of Keccak-224 andKeccak-256, a collision attack on two rounds, and a near-collision attack on three rounds of
Keccak-224 and Keccak-256.
Dinur et al. [40] produced example collisions for Keccak-224 and Keccak-256, reduced to four
rounds, and near collisions on five rounds.
Table 15 summarizes the cryptanalysis results on Keccak’s Round 3 submission.
TargetAttack typeOutputVariantr={240,640,1440},
c=160,
1, 2 rounds
r={240,640,1440},
c=160,
1, 2 rounds
24 rounds

Hashfunction

Collision

160

Hash
function

Preimage80

Distinguisher
Differential
Propertyall
all

8 rounds

Distinguisher

224,256

4 rounds

Permutation
Permutation
HashfunctionHashfunctionHashfunctionHashfunctionHashfunctionHashfunctionHashfunctionHashfunctionHashfunction

CF Call

MemoryReference

Example[106]

Example

[106]

21579

[45]

491.47

[107]

2

225

[109]

25

Near collision

224,256

3 rounds

Collision

224,256

2 rounds

2

[109]

233

[109]

33

2

229

[109]

6 rounds

2506

2176

[108]

512

7 rounds

2507

2320

[108]

512

8 rounds

2511.5

2508

[108]

Collision

224,256

4 rounds

Example[40]

Near collision

224,256

5 rounds

Example[40]

2nd Preimage

224,256

2 rounds

2nd Preimage

512

2nd Preimage
2nd Preimage

Table 15. Summary of Cryptanalysis Results on Keccak’s Round 3 Submission30

4.2.5Skein

Skein is an iterative hash algorithm that is built on a tweakable block cipher – Threefish.
Threefish is used to build the compression function of Skein using a modified Matyas-MeyerOseas construction, which is then iterated using a domain extender similar to the HAIFA domain
extender used by BLAKE. The designers refer to the whole construction as a Unique Block
Iteration (UBI). The internal structure of Threefish is a 72-round substitution-permutation
network using a 128-bit MIX function consisting of 64-bit addition, rotate and XOR operations,each used exactly once per MIX function.
For the second round, Skein was tweaked by modifying the rotation constants, which thesubmitters felt had not been fully optimized for the first round of the competition. For the final
round of the competition, Skein was tweaked by modifying a constant in the key schedule ofThreefish to harden the function against rotational cryptanalysis.
4.2.5.1

Analysis of the Skein Domain Extender

Bellare et al. [110] proved that Skein-n is secure against preimage and collision attacks up to
approximately 2n and 2n/2 queries, respectively, if the underlying tweakable block cipher (i.e.,
Threefish) is ideal. They also proved that, under the same assumption, Skein is indifferentiablefrom a random oracle up to 2256 queries, which means that Skein is secure against all nontrivial
generic attacks up to 2256 queries. Andreeva et al. [73] proved that Skein-512 is second-preimageresistant up to 2512 queries, under the same assumption.
4.2.5.2

Pre-Round 3 Analysis

Early attacks on Threefish included a 33-round key-recovery attack by Chen and Jia [111], and a
35-round distinguisher by Aumasson et al. [112]. McKay and Vora [113] published an attack on
Threefish, using pseudo-linear functions to analyze the block cipher, yielding a 15-round keyrecovery attack. In addition, linear differential analysis by Su et al. [37] produced near collisions
on 24 rounds of the Skein compression function.
The most severe attacks on earlier versions of Skein exploited the near-rotational symmetries of
its MIX function (where only the lack of a carry bit at either end of the 64-bit adder breaks thesymmetry). The first of these attacks was the related-key, key-recovery attack of Khovratovichand Nikolic [114] on 39 rounds of Threefish-256, and 42 rounds of Threefish-512. Later,
Khovratovich et al. [115] provided a rotational distinguisher, based on the concept of rotational
collisions. By using what the authors described as a rebound attack, they extended thedistinguisher to 53 and 57 rounds of the Skein-256 and Skein-512 compression functions,
respectively. However, the Round 3 tweak, changing the key schedule constant from
0x5555555555555555 to 0x1BD11BDAA9FC1A22, renders the rotational properties of the MIX
function far less useful to the attacker. No comparable rotational attacks have been proposed on
the final round version of Skein.
Table 16 summarizes the cryptanalysis results on Skein before its Round 3 submission.

31

TargetAttack typeOutput Variant CF Call Memory Reference
Block cipher
Key recovery
512
32 rounds
2195
212
[111]
324.6
Block cipher
Key recovery
512
33 rounds
2[111]
Block cipher
Key recovery
512
34 rounds
2474.4[111]
CF
Near collision
512
17 rounds
224[112]
Block cipher Impossible differential
512
21 rounds[112]
Block cipher
Key recovery
512
26 rounds
2507.8[112]
Block cipher
Key recovery
512
32 rounds
2312
271
[112]
Block cipher
Distinguisher
512
35 rounds
2478
[112]
232
Block cipher
Key recovery
256
15 rounds
2
[113]
CF
Near collision256
24 rounds
260
[37]
CF
Near collision
512
24 rounds
2230
[37]
395
CF
Near collision1024
24 rounds
2[37]
Block cipher
Key recovery
256
39 rounds
2254.1[114]
Block cipher
Key recovery
512
42 rounds
2507
[114]
CF
Distinguisher
256
53 rounds
2251
[115]
503
CF
Distinguisher
512
57 rounds
2[115]
Table 16. Summary of Cryptanalysis Results on Skein prior to its Round 3 Submission

4.2.5.3

Round 3 Analysis

Several cryptanalysis papers have been published regarding the Round 3 version of Skein.
Khovratovich et al. [47] published attacks using a splice-and-cut attack, augmented by adifferential structure called a biclique. This resulted in a 22-round preimage attack on Skein-512,
requiring 2511 compression-function calls, and a 37-round pseudo-preimage attack, requiring 2511.2
compression-function calls. Khovratovich [86] also used bicliques to find collisions on 14 rounds
of Skein-512, and 12 rounds of Skein-256, using 2254.5 and 2126.5 compression-function calls,
respectively; and preimages on 14 rounds of Skein-256, using 2251.4 compression-function calls. In
another attack paper, Yu et al. [41] used differential cryptanalysis to find semi-free-start nearcollisions on 32 rounds of Skein-256, using 2105 compression-function calls. Yu et al. [48] also
published a 36-round distinguisher on the Skein-512 compression function, using 2454
compression-function calls, and a 34-round key-recovery attack on Threefish-512, using 2424
compression-function calls.
Aumasson et al. [70] used Tuple cryptanalysis, which was also applied to BLAKE, to find a
distinguisher on a 17-round version of Threefish.
Table 17 summarizes the cryptanalysis results on Skein’s Round 3 submission.

32

TargetAttack typeOutput Variant CF Call Memory Reference
Hash function
Preimage
512
22 rounds
2511
26
[47]
508
6
Hash function Pseudo-preimage
512
22 rounds
2
2[47]
Hash function Pseudo-preimage
512
37 rounds
2511.2
264[47]
Hash function
Collision
512
14 rounds
2254.5[86]
126.5
Hash function
Collision256
12 rounds
2[86]
Hash Function
Preimage256
14 rounds
2251.4[86]
CF
SFS near collision
256
32 rounds
2105
[41]
CF
Distinguisher
512
32 rounds
2104.5[48]
454
CFDistinguisher
512
36 rounds
2[48]
Block Cipher
Key recovery
512
34 rounds
2424[48]
Block Cipher
Distinguisher
512
17 rounds
264
264
[70]
Table 17. Summary of Cryptanalysis Results on Skein’s Round 3 Submission

4.3

Security Summary

No finalist was considered to be a clear winner or loser from the security analysis. While thedetails of the security proofs on domain extenders differ somewhat between finalists, all haveproofs that relate the security of their full hash functions to the security of their underlying
compression functions and fixed permutations. None of the published cryptanalytic attacks comeanywhere close to threatening the security of any of the five finalists. The publisheddistinguishing attacks are interesting, but do not have obvious implications for the security of the
finalists.
However, there are important differences between the finalists. JH and Grøstl have relatively
small security margins that, when combined with their performance in software, probably cannot
be addressed by increasing their numbers of rounds. Skein's security margin is a little larger, andcould be further expanded by adding rounds, if necessary, given its excellent software
performance. BLAKE and Keccak have very large security margins. Furthermore, JH and Grøstl
have distinguishing attacks against them that reflect this difference – the best distinguishingattack on the JH permutation distinguishes all 42 rounds, and the best attack, on the underlying
permutations of Grøstl, distinguishes 90 % of its rounds. By contrast, the only distinguishingattack on more than 14 of the 24 rounds of Keccak has a complexity that is far beyond any
security bound expected of a 512-bit or shorter hash function, and Skein and BLAKE have noknown distinguishing attacks that come close to threatening their full-round versions.
Grøstl, Skein, and BLAKE have a large number of attack papers reflecting considerable depth ofanalysis, and Keccak has somewhat less, but still received considerable cryptanalytic attention.
JH received significantly less analysis, and still has a relatively small security margin, suggestingthat more analysis might further erode its security margin. Based on the available literature, JH
does not appear to be very well-understood yet, and this influenced NIST’s selection of a winner.
Another area where there has been some preliminary analysis of the security of the candidates istheir resistance to side channel attacks. This area is somewhat difficult to analyze, since these
attacks depend on the implementation of the algorithm, and not just the algorithm itself. As such,
any algorithm can be implemented to be secure against side channel analysis if the implementer iswilling to pay a large enough performance penalty. The challenges involved in defending againstside channel analysis, however, vary among the finalists. Grøstl may be difficult to defend against
cache-timing attacks on software platforms that do not have native support for the AES S-box in
hardware. While the other finalists are unlikely to be vulnerable to timing attacks, they may still33

need countermeasures to defend against power-analysis attacks, and in this respect, BLAKE andSkein may suffer somewhat, since it is somewhat harder to mask the modular addition
instructions used in those algorithms.

34

5. Performance Comparison of the SHA-3 Finalists
This section discusses the performance of the finalist candidates when implemented in softwareand hardware.
All of the SHA-3 finalist candidates, as well as SHA-2, have four variants with 224-, 256-, 384and 512-bit message-digest outputs. Skein and JH generate all four message-digest sizes with thesame compression function, and therefore, all four run at about the same rate12. Keccak also uses
a single compression function to generate all four output sizes, but the bigger the output, thesmaller the message block that is processed by each compression-function call, and therefore, thebigger the message digest, the slower Keccak runs. BLAKE, Grøstl and SHA-2 use two different
compression functions, one for 384- and 512-bit message digests, and another for 224- and 256bit message digests; these two hash-function variants usually run at different speeds on the same
platform.
Therefore, in the performance discussions, these algorithms will be referred to as:• BLAKE-256 and BLAKE-512• Grøstl-256 and Grøstl-512• JH• Keccak-224, Keccak-256, Keccak-384 and Keccak-512• Skein• SHA-256 and SHA-512
In the performance discussion, whenever the name of an algorithm is used without a specificdigest size attached, then the statement applies for all four digest sizes.
5.1

Software PerformanceThis section compares the performance of the SHA-3 candidate algorithms and SHA-2 when
implemented in software on many of the most widely used current computing platforms. The
general categories of computers considered are discussed below.
5.1.1

Computer Systems – the Current Playing Field

The software performance of the SHA-3 finalists has been measured in the following classes ofcommercially available computers:
AMD64 13: These machines are general-purpose Complex Instruction Set Computers (CISC) witha 64-bit-word orientation and Single Instruction Multiple Data (SIMD) vector units. They all run
the 64-bit-oriented AMD64 instruction set architecture (ISA). AMD64 machines predominate
today in desktop, laptop and netbook computers, as well as servers of all sorts. They typicallyhave very large RAM memories, and increasingly have two or more independent “cores,” eachcapable of independently executing a program thread. Each core typically has superscalar,pipelined execution units supporting 64-bit-word integer, logic and floating-point operations andis able to simultaneously launch two instructions at each clock cycle. Typically, there is also a12This is perhaps not as good an assumption for hardware as for software, because different digest sizes have an effecton the area of the circuit, and possibly the clock rate as well, but the effect is usually small.
13
This report adopts the “AMD64” nomenclature of the eBASH website. Other common designations for this
instruction-set architecture are “x86-64” and “Intel-64”. This choice of names is for ease of comparison with the wealthof data on the eBASH website and does not indicate any NIST endorsement of any vendor or product for any purpose.

35

vector unit in each core. Since vector units were introduced for the x86 architecture in the 1990s,
they have gone in stages from eight 64-bit registers to sixteen 256-bit registers for the latestannounced products. The most recent machines have vector units that can simultaneously execute
eight 32-bit operations or four 64-bit operations in a 256-bit vector register. Most desktop, laptop
and server computers sold today are AMD64 machines.
X86: These are the 32-bit predecessors of the AMD64 computers. Many legacy systems run on
X86 computers, which now usually are AMD64 machines operating in the X86 mode. Most fairly
recent examples include a vector unit and super-scalar execution units.
ARM-NEON 14: These machines run a relatively high-end implementation of the ARM ISA witha vector unit. The NEON vector instruction set uses registers that can be viewed as thirty-two 64bit registers or sixteen 128-bit registers. Many of the SHA-3 finalists benefit significantly from64-bit instructions or bit-slice implementations on wider words, and run markedly faster on the
NEON-equipped ARM machines.
32-bit RISC: These Reduced Instruction Set Computers (RISC) are scalar or super-scalarmachines that are typically used today in a wide range of applications from smart phones, tablet
computers, and appliances, such as GPS units and music players, to controllers and sensors
embedded in many products. By far the most widely used RISC ISA is the ARM, which is widely
licensed in a variety of “cores” that are incorporated in ASIC. Other legacy 32-bit RISC ISAs
studied in the SHA-3 competition include the PowerPC (PPC), and MIPS (Microprocessor
without Interlocked Pipeline Stages) ISAs.
Embedded Microcontrollers: These are small computers, typically included on an ASIC withmemory and other application-specific logic. In this category, the primary constraint is usually
the RAM memory, although power may be another constraint. This is the most diverse category,
and there are a number of ISAs, including low-end implementations of the 32-bit ARM, as wellas sixteen and eight-bit microcontrollers. Applications for such computers include smart cards,
sensors, smart meters, servo controllers, some RFID tags and a plethora of potentially networked
appliances.
5.1.2

Candidate Software Performance Studies

Several studies have been done that compare SHA-2 and the SHA-3 finalists using programs
written by a single programmer or a small team for a specific platform or language, or with a
specific design goal. These include studies of optimized Java code running on a current AMD64
computer [116], and optimized assembler code on the ARM11 processor [117], which is widelyused in smart phones and tablet computers, but does not include the NEON vector engine.
However, the vast bulk of the available SHA-3 finalist performance data was provided by two
cooperative projects, eBASH (ECRYPT Benchmarking of All Submitted Hashes) [25], and XBX(eXternal Benchmarking eXtension) [26], both are part of the ECRYPT Benchmarking of
Cryptographic System (eBACS) [118]. These two projects consolidated algorithm
implementations from many different sources, ran them on many different computers andreported on their performance. NIST appreciates and is grateful for the significant efforts of all
involved.

14

NEON is a 128-bit SIMD architecture extension for the ARM Cortex™-A series processors.

36

5.1.2.1

eBASH: General-Purpose Computers

During the course of the SHA-3 competition, a large number of hash functions were
benchmarked on general-purpose computers, and a significant amount of data on all of them canbe found on the eBASH site (http://bench.cr.yp.to/ebash.html). Many C-language and someassembly implementations of all the finalists were submitted by different programmers toeBASH, then compiled with a range of different options and run on a large number of different
computers. The best comparative presentation of the data for the SHA-3 finalists and SHA-2 isthe “shootout” graphs [119] found at: http://bench.cr.yp.to/results-sha3.html, and NIST madeextensive use of this data, which includes six graphs that summarize algorithm performance forvarious message lengths. In the shootout presentation, only the program with the best
performance for each SHA-3 finalist on each computer is represented in the summary graphs.
These summaries include data from fifteen AMD64 processor models, two X86 processor
implementations, the PPC G4, four different ARM core designs and one MIPS32 implementation.
In many cases, the eBASH benchmarks were run on several different computers with the samegeneral processor model.
Figures A1-A6 in Appendix A show the six eBASH summary graphs, as of September 10, 2012.
Only the 512-bit and 256-bit variants are plotted. Throughput is stated in machine cycles-perbyte, where fewer cycles indicate better performance. The fastest performance of the bestalgorithms on the latest machines is about six cycles per byte.
One other feature of the eBASH website deserves special attention here. At
http://bench.cr.yp.to/primitives-sha3.html, there is a table labeled “Which hash functions aremeasured? (SHA-2/SHA-3 excerpt),” which is a table of all the variants of all the SHA-3
finalists, plus SHA-512 and SHA-256, and three “tree mode” implementations of BLAKE andKeccak that implement i-thread parallel implementations of the hash algorithms. The
implementations that depend heavily on vector units are often given names that identify the typeof vector unit: SSE (for Streaming SIMD Extensions), AVX (for Advanced Vector eXtensions),
MMX 15 for AMD64 or x86 machines, or NEON for ARM machines.
The computers used in eBASH are classified into four of the five groups described above:• AMD64: use the AMD64 ISA and generally include a vector unit.
• X86: use the 32-bit X86 ISA and may include a vector unit.
• ARM-NEON: use the 32-bit ARM ISA with the NEON vector unit.
• 32-bit RISC: use the following 32-bit RISC ISAs: ARM, MIPS or PPC. A vector unit is
not used.
To try to visually distill the complex graphs of the eBASH website into a simpler presentation,
the performance of each algorithm is categorized into high, medium or low levels (shown as
green, aqua, and red, respectively) for the four different classes of computers in Tables 18 and 19.
A candidate’s performance on these platforms is marked at the specific cell with the platform
identified, such that a reader can quickly grasp the candidate’s performance by reading across thealgorithm row.
Table 18 is for long messages (greater than 4096 bytes), while Table 19 illustrates shortermessages of 64 bytes. These are based on the eBASH “shootout” graphs for six different sizes ofmessages (long, 4096-bytes, 1536-bytes, 576-bytes, 64-bytes and 8-bytes). These simpler
presentations are essentially “eyeball” judgments of relatively noisy data; the reader can study
15

MMX is a single instruction, multiple data (SIMD) instruction set designed by Intel and introduced in 1996.

37

Figures A-1 through A-6 in Appendix A (the actual detailed eBASH shootout plots) to see how
well the categorizations fit the data. The data for JH, in particular, seems erratic; this is apparently
because the fastest JH vector code was completed very late, and had been run on some, but notall, the benchmark machines. This, however, makes little comparative difference, because eventhe fastest JH implementations are among the slowest of the algorithms. For each class ofmachine, the performance of the fastest algorithms ranged between four and eight times the speedof the slowest. When data points seem spread across both high and medium, or medium and low,crosshatching is used to draw attention to this.
5.1.2.1.1
Platform

Long Messages
High Performance
AMD64

X86

Algorithm
BLAKE512BLAKE256

AMD64
AMD64

X86

ARMNEON
ARMNEON
ARMNEON

Medium Performance
32bit
RISC

32-bitRISC

ARMNEON

32bit
RISC
32-bit
RISC

AMD64

JH
Keccak512
Keccak256

AMD64
AMD64

X86

ARMNEON
AMD64

X86

ARMNEON

X86

X86

ARMNEON

ARMNEON

X86

SHA-51232-bitRISC

Low Performance
AMD64

X86

ARMNEON

32bit
RISC

AMD64

X86

ARMNEON

32-bit
RISC

AMD64

X86

ARMNEON

32-bit
RISC

AMD64

X86

AMD64

X86

ARMNEON

32-bitRISC
32-bit
RISC

AMD64
AMD64
(AES
NI)
AMD64
(AES
NI)

Grøstl256

SHA-256

X86

X86

Grøstl512

Skein

AMD64

X86

32-bitRISC
32-bitRISC
32-bit
RISC

X86

ARMNEON

AMD64

High Performance
Medium Performance
Low Performance
Performance straddling two categories
Table 18. eBASH Performance Comparison for Long (> 4096-byte) Messages

AMD64: Skein (all sizes) and BLAKE-512 are consistently the fastest algorithms and the only
two algorithms that generally are faster than SHA-512 on AMD64 platforms. BLAKE-256 is also
fast on the newer AMD64 platforms of one vendor with larger vector-register files [120], but isslower on most of the machines of the other major vendor. This may reflect differences in thevector units of the two vendors. Keccak-256, SHA-512 and SHA-256 are in the medium-levelgroup, averaging about half the speed of the high-level group, along with Grøstl-512 and Grøstl256 on very new machines with the AES New Instructions (AES-NI). JH is also in the medium
group for very recent AMD64 processors with 256-bit vector registers, but not for older

38

processors with 128-bit vector registers. Grøstl-512, Grøstl-256 (no AES-NI), JH and Keccak-512
are in the low group, with performance only around ¼ of that of the high-performance group.
X86: The high group includes BLAKE-256, and SHA-256, all of which are ARX-type 32-bitword algorithms. Skein does fairly well, straddling the high-medium groups, despite using 64-bit
operations on a 32-bit machine. BLAKE-512, JH, Keccak-256 and SHA-512 have medium
performance. The low group consists of Grøstl and Keccak-512.
ARM - NEON: The high group consists of BLAKE, Skein and SHA-256, the medium groupcontains JH and Keccak-256, and the low group consists of Grøstl, Keccak-512 and SHA-512.
The ability of the NEON vector unit to perform 64-bit operations may help Skein and BLAKE512 on this processor.
32-bit RISC: The high-performance algorithms are BLAKE-256 and SHA-256; the medium
group contains BLAKE-512, Keccak-256, Skein and SHA-512. Grøstl, JH and Keccak-512 are in
the low group.
5.1.2.1.2
Platform

64-byte Messages
High Performance
AMD64

X86

Algorithm
BLAKE512BLAKE256
Grøstl512

ARMNEON

Medium Performance
32bit
RISC

AMD64

AMD64
AMD64

X86
X86

ARMNEON

32-bit
RISC

AMD64
(AES
NI)

JH

AMD64

Keccak512
Keccak256

AMD64
X86
AMD64

SHA-512
SHA-256

X86

AMD64

AMD64

X86

ARMNEON

32-bitRISC

ARMNEON
ARMNEON

32bit
RISC
32-bitRISC

Low Performance
AMD64

X86

ARMNEON

32bit
RISC

AMD64

X86

ARMNEON

32-bit
RISC

AMD64

X86

ARMNEON

32-bitRISC

ARMNEON

32-bitRISC

AMD64

Grøstl256

Skein

X86

X86

ARMNEON
ARMNEON
ARMNEON
ARMNEON
ARMNEON

32-bitRISC
32-bitRISC
32-bitRISC
32-bit
RISC

X86

X86

AMD64

High Performance
Medium Performance
Low Performance
Performance straddling two categories
Table 19. eBASH Performance Comparison for 64-byte Messages

This comparatively small message size starts to show the effects of both fixed-per-message
overhead and of different input block sizes, which range from 512 to 1088 bits. Average cycles-

39per-byte seem to be about twice that of long messages, but the ordering of algorithms haschanged remarkably little. At this message size, Keccak-512 looks about as good in comparison
to others as it ever will, since 64 bytes just fits, with padding, in a single message block andKeccak has no extra finalization round, while other algorithms either need two blocks, process asignificantly larger-than-needed 128-byte message block or have an extra finalization round thathas a bigger relative effect on short messages.
AMD64: As with long messages, BLAKE and Skein lead all others. BLAKE-256 is in the highgroup on new machines with large vector-register sizes, but drops down into the medium groupfor older AMD64 machines. Grøstl-256 stays in the medium group with JH, Keccak-512,
Keccak-256, SHA-512 and SHA-256, for machines that implement the AES-NI instructions, but
falls into the low group on machines that do not implement the AES-NI instructions. Keccak-512
is in the medium group with Keccak-256, because its relatively small 576-bit input block inputs
the entire message in one block. Grøstl-512 is in the low group even with the AES-NI
instructions, probably because of the extra overhead of its final “blank” round.
X86: BLAKE-256, Skein and SHA-256 are in the high group on this 32-bit-word ISA. The
medium group consists of BLAKE-512, JH and Keccak-256. Grøstl-256, Grøstl-512, Keccak-512
and SHA-512 show low performance.
ARM-NEON: The high-performance group consists of BLAKE-256 and SHA-256; the medium
group consists of BLAKE-512, JH, Keccak-512, Keccak-256, Skein and SHA-512; and the lowgroup consists of Grøstl-256 and Grøstl-512.
32-bit RISC: BLAKE-256 and SHA-256, the two algorithms that use 32-bit modular addition
extensively, are in the high group; BLAKE-512, Keccak-512, Keccak-256, Skein and SHA-512
are in the medium-performance group, while Grøstl-256, Grøstl-512 and JH make up the lowgroup.
5.1.2.2

XBX: Embedded Microcontrollers

Most of the data on embedded microcontrollers comes from the XBX effort; its homepage is at:
http://xbx.das-labor.org/trac. XBX [26] focused on embedded computers, where it is usual tocompile or assemble code on some development system, and then run it on a small computer or“microcontroller.” The XBX team collected and measured SHA-3 implementations on eight
embedded platforms. Some of the 32-bit ARM processors benchmarked on XBX were as
powerful as some of the machines tested by eBASH, and included vector units, while others were8- and 16-bit machines, characteristically used with very little memory.
In contrast to eBASH, XBX gives the RAM and ROM requirements of the fastest
implementations for each processor tested, and “area” versus speed plots, for each of theimplementations measured. The area metric used in the XBX is: area = 4 × RAM + ROM. This isa heuristic based on the general observation that RAM memory requires about four times the area
on a chip as ROM memory. In the larger systems used in eBASH, the memory required by hashalgorithms is rarely an issue, but memory use is often an issue and sometimes the major
constraint with embedded microcontrollers. In addition to XBX, [117] gives optimized
implementations for all five finalists plus SHA-2 on the ARM-11 processor, which has beencommonly used in cell phones, but has been supplanted by newer processors in high-end cell
phones.

40

Eight-bit: Only one 8-bit microcontroller was tested, the Atmel ATmega128P. The smallest area
and the best performance was attained by Grøstl-256, perhaps the only software case where
Grøstl was the fastest algorithm. This probably is because of the eight-bit orientation of the AES
operations used by Grøstl. BLAKE-256 was nearly as fast as Grøstl, but took somewhat morearea. Keccak-256 was also compact and third in throughput. Interestingly, SHA-256 wascomparatively big and slow, and SHA-512 had the worst overall performance of any algorithm.
Sixteen-bit: Only one 16-bit microcontroller, the Texas Instruments’ MSP430FG4618, was tested.
Overall, BLAKE-256 was fast and small, and SHA-256 was second. Grøstl-256 was small but
fairly slow. Keccak-256 was a bit bigger than BLAKE-256 and somewhat faster than Grøstl-256,
but no match for either BLAKE-256 or SHA-256. Keccak-256 requires a relatively small areaand has reasonably good throughput.
ARM (thumb instructions): This version of the ARM processor is a low-end microcontroller that
only implements the 16-bit thumb instructions. The XBX authors consider small area to be theprimary goal for this platform, and BLAKE and JH-256 are the two smallest algorithms. BLAKE256 and SHA-256 have the highest (very similar) throughputs, but the area requirement for SHA256 is higher than for BLAKE-256. Keccak has a fairly small area requirement, and Keccak-256
is third in overall performance. Skein has the largest area requirement, and Grøstl-512 and JH are
simply slow.
32-bit RISC: This class includes several ARM processors running the regular 32-bit instructions(but without the NEON vector processor) and a 32-bit MIPS processor. Both XBX and [117]provide data for the 32-bit RISC processor. SHA-256 is the fastest algorithm overall, followed by
BLAKE-256. Since these are both 32-bit-oriented ARX algorithms, it is expected that SHA-256
and BLAKE-256 should be the fastest algorithms. Skein, BLAKE-512, Keccak-256 and SHA512 vie for third place, depending on the specific processor, while Grøstl-256, Grøstl-512 and JH
are much (typically three to eight times) slower than SHA-256. BLAKE-256 and Grøstl-256 areusually the smallest algorithms in area.
ARM with NEON: This is a relatively fast ARM core with the addition of a vector unit that
supports 64-bit operations. With the addition of the vector unit, Skein becomes the fastest
algorithm, followed fairly closely by BLAKE-256, BLAKE-512 and SHA-256, Skein is about
twice as fast as Keccak-256, three times as fast as Keccak-512, and four to nine times the speedof JH and Grøstl. The overall results are similar to those on eBASH for ARMs with the NEON
vector unit, although JH seems to do somewhat worse in the XBX benchmarks than is shown in
the eBASH results.
The XBX investigators give an overall ranking for embedded computers that factors in theirunderstanding of whether the usual goal for the particular computer is throughput or minimum
area. In that ranking, BLAKE is first, while Skein is in second place, but only slightly better than
Keccak and Grøstl. The investigators did not include SHA-2 in this ranking; however,considering the good performance of SHA-256 on 32-bit RISC machines, if SHA-2 were
included, it might beat Skein for second place, since there are four 32-bit platforms where SHA-2
is the fastest algorithm, although rarely by a large margin. However, the smallest SHA-256
implementations nearly always require somewhat more area than the smallest BLAKE-256
implementations, so BLAKE-256 has the overall advantage over SHA-2.

41

5.1.3

Beyond The Superscalar

The sophisticated superscalar arithmetic logic units (ALUs) of large-scale general-purpose
computers attempt to extract as much parallel execution as they can from programs written as asingle-thread sequence of instructions. Additional parallel execution may be explicitly
programmed by taking advantage of multiple core processors that can run independent threads, orby using vector units that perform the same operation on a number of words in parallel.
Most large-scale general-purpose processor chips today have between two and eight cores, eachcapable of executing an independent program thread. Since all of the SHA-3 finalists can be runefficiently as a thread on a single core, it seems obvious that very large files can be broken into npieces and each piece hashed in parallel on separate cores in an n-core processor. The message
digest of each separate piece may then be hashed in tree fashion. However, operating-systemlevel interprocess synchronization may be expensive enough to limit the utility of this to verylarge files, and it is hard to see why one of the finalists would be better suited to parallel
execution in separate process threads than any other finalist.
Graphics Processor Units (GPUs) were not considered in the competition. GPUs are common on
processors for laptop, desktop and even tablet computers. They are arrays of fairly specialized
processors that are organized for stream processing, and are most commonly used for image andvideo rendering. Gaming and High-Definition video applications have driven GPU development.
GPUs have been applied to cryptography, but more for cryptanalysis than for protecting data.
GPUs may be well suited to applications that can be divided into many independent processes,
such as password cracking, but it is hard to envision much near-term use of GPUs for dataprotection.
Vector units with eight 64-bit registers became available in X86 machines in 1996. Thesemachines could simultaneously perform one 64-bit or two 32-bit operations in a register. In 2012,
the current generation of AMD64 machines has sixteen 256-bit registers. Current machines cansimultaneously do four 64-bit operations or eight 32-bit operations in a register. The total size ofthe vector-register file has increased by a factor of eight in about 16 years.
Vector units are both evolving rapidly and spreading from large-scale general-purpose computers
to embedded computers. They are often the vehicle for the addition of new instructions, such as
the AES extensions to the AMD64 instruction set. Vector units facilitate more efficient
implementations of bit-slice designs, such as JH; of AES and algorithms that use the AES Sboxes (e.g., Grøstl); and of BLAKE-256 on the more recent AMD-64 machines. On ARM
machines that implement the Neon vector unit, they speed up most of the finalists. Some new
instructions will be useful for hash functions; for example, rotate instructions are not available inmost current vector processors, but are announced for inclusion in the next generation of AMD64 machines.
Figures 1-3 graph the eBASH data for three recent AMD64-architecture processors that
implement recent vector units operating on 256-bit vectors. In these graphs, each bar represents
the mean cycles-per-byte for the fastest implementation of each algorithm on one of the three
processors. Smaller bars mean faster throughput. The five finalist algorithms plus SHA-2 areplotted; however, in the case of Skein and JH, only one bar is plotted, because all four output
sizes use the same compression function, and run at about the same rate. In these graphs, one
designation is used for two or four message-digest sizes when they run at the same rate; one bar isplotted for each version with a different rate. For example, since BLAKE-256 and BLAKE-224
run at the same speed, only BLAKE-256 is plotted, but all four digest sizes are plotted for42

Keccak, because each runs at a different speed. For consistency with other algorithms, thenomenclature for Keccak has also been changed in this report from that used for eBASH, which
generally labels the Keccak variants by their capacity; for example, the eBASH “keccakc512,”
which outputs a 256-bit message digest, becomes “keccak-256” in Figures 1-3.
It is reasonable to expect vector-register files to continue to grow, more instructions to be added,
and to find more use of vector units, even in embedded systems. It seems too big an assumption
to expect that because AES has inspired additional support instructions, that SHA-3 would also
do so. If it did, that would likely be very far in the future, unless the instructions, like vector
rotates, have more general uses than implementing hash functions alone.
Figure 1 plots the cycles-per-byte of long messages for “h6sandy,” an Intel® Core i3-2310M 16,
which is a “Sandy Bridge” internal architecture processor with two 2100 MHz cores that is
intended for laptop computers. Figure 2 plots cycles-per-byte of long messages for “sandy0,” anIntel Core i7-2600K, which is a Sandy Bridge four-core 3400 MHz processor that is intended for
relatively high-end desktop computers. Figure 3 plots cycles-per-byte of long messages for“hydra6,” an AMD FX-8120, which is a “Bulldozer” internal architecture processor with four
3100 MHz cores, also intended for desktop applications. The Intel Sandy Bridge processors
implement the AVX vector instruction set, with sixteen 256-bit registers; the AMD Bulldozer
processors implement the XOP vector instruction set, which is similar to the AVX instruction set,with some additional extensions, including, in particular, the 32- and 64-bit rotate operations.
There is one significant difference between the two Sandy Bridge processors: sandy0 implements
the AES-NI instructions, and h6sandy does not. The AES-NI instructions affect only theperformance of Grøstl.
2011 Intel Core i32310M; h6sandy; supercop-20120521
30

cycles/byte

25
20
15
10
5
0

Figure 1. SHA-3 Finalists Cycles/Byte on Sandy Bridge Laptop Processor with Current Vector Unit

16
The identification of certain products in this document does not imply recommendation by the US National Instituteof Standards and Technology (NIST) or other agencies of the US Government, nor does it imply that the products
identified are necessarily the best available for the purpose.

43

2011 Intel Core i7-2600K; SB+AES; sandy0; supercop-20120521
25

cycles/byte

20
15
10
5
0

Figure 2. SHA-3 Finalists Cycles/Byte on Sandy Bridge Desktop Processor with Current Vector Unit2011 AMD FX-8120; hydra6, supercop-20120521
25

cycles/byte

20
15
10
5
0

Figure 3. SHA-3 Finalists Cycles/Byte on the Bulldozer Desktop Processor with Current Vector Unit

Skein does not seem to benefit from the vector units, probably because of the different rotation
constants used in its MIX operations, even though four parallel MIX operations occur in eachround. Skein, however, is one of the fastest algorithms on all three of these machines, relying on
their superscalar general-purpose ALUs.
BLAKE logically allows parallel execution of four of its building-block G functions, with theirrotates; unlike Skein, BLAKE’s four parallel rotates all use the same rotation values, facilitating

44

vectorization. On these machines with the most advanced vector units, BLAKE-256 (which uses
32-bit words) becomes almost as fast as Skein-256, which uses 64-bit words and, in older
AMD64 machines, has a bigger advantage over BLAKE-256. BLAKE-512 is slightly faster than
Skein-512 on these newer machines, although Skein-512 has the advantage on older AMD64
machines.
Word rotation, used extensively by BLAKE, Skein and Keccak, is not usually a directly
implemented instruction in current vector instruction sets, but it can be implemented by shifts and
XORs. Keccak does relatively better on the Bulldozer, because only the Bulldozer implements
vector-rotate instructions, giving about a factor of 1.7 speed improvement over older vector units[121]. BLAKE also benefits from the Bulldozer rotate instruction [120]. A single Skein threadprobably will not be helped very much by a simple rotate instruction that rotates all words by thesame amount. Grøstl is significantly helped by the AES-NI instructions and corresponding AES
extension on the Bulldozer. JH clearly benefits from vector implementations, but still is among
the slowest on all three processors.
In addition to the five finalists and the SHA-2 algorithms described above, two “tree-modes,”Bblake-256 and keccak-256treed2, were implemented on all three processors, while another treemode, Bblake-512, was implemented for the AMD FX-8120. These modes generate a single 512or 256-bit message digest from two parallel streams using the regular compression function, andare examples of “Processing Multiple Buffers in Parallel” [122] or “multi-buffering” to increase
performance; in these particular cases, this is done by dividing a single file into two parts to behashed in parallel. The same technique can also be applied to two independent hash streams, as
might occur on a server with many simultaneously active TLS connections.
Gueron and Krasnov [123] have investigated “multi-lane” parallel hashing modes for SHA-256,
and for a four-lane version of SHA-256 with 8192-byte messages on the Intel® Core™ i7-3770“Ivy Bridge”16 processor with the AVX vector instruction set, they obtained 5.46 clocks per byte.
This is a little (5 % to 8 %) better than the results that they obtained for multi-lane versions ofBlake-512 and Blake-256, and about 22 % better than a multi-lane version of Keccak. From theirwork it seems fair to conclude that, for large messages with a multi-lane hashing mode, or wheremulti-buffering allows the parallel execution of multiple hash operations, SHA-256 is very
competitive in throughput, and that 32-bit-word-oriented algorithms (SHA-256 or Blake-256) canbe as fast on big 64-bit-oriented processors as 64-bit-word algorithms, wherever multi-lane or
multi-buffered execution is practical. These may be the bulk of cases where hash function
performance is an issue.
All of the candidates and SHA-2 potentially can benefit from a tree mode or multi-buffer
implementations, although perhaps to varying degrees. The different rotation values thatcomplicate vectorizing a single Skein thread should not matter in a multi-buffer implementation.
However, there has not been enough work done on this to draw strong conclusions about whichalgorithms benefit most. In the future, NIST expects to consider a hashing recommendation for astandardized parallel hashing mode.
5.1.4

Software Performance Summary

Skein and BLAKE, the two ARX finalist candidates, have the best overall software performance.
Only Skein and BLAKE seem to be faster than SHA-2 in most cases.
Skein has the advantage of a single compression function for all four message-digest sizes, which
reduces code size if all four message-digest sizes are required. Skein-256 has a small to moderate

45performance advantage over BLAKE-256 on AMD64 platforms, which may, or may not, carryover to future 64-bit ARMv8 [124] processors if the processors adopt superscalar ALUs similar tothe ones used in AMD64 processors. BLAKE-512 seems to gain a modest performance advantage
over Skein-512 on more recent AMD64 machines by better fitting their vector units.
On 32-bit machines (mainly ARM processors) without vector units, BLAKE-256 is the overall
leader, although it has only a small throughput advantage over SHA-256. On ARMs with the
NEON vector unit, Skein seems the fastest algorithm, followed fairly closely by BLAKE.
On small embedded computers, BLAKE-256 has the best overall performance. BLAKE-256’s
throughput is usually at or near the top, although occasionally slightly less than SHA-256, while
BLAKE-256 generally has smaller memory requirements than SHA-2 and most of the othercandidates.
Keccak is reasonably fast for 224- and 256-bit message-digest sizes on a range of machines, but
Keccak-512 is among the slower algorithms on most machines. Keccak benefits significantly
from vector rotate instructions, which may become common on future processors. Like Skein,
Keccak uses one compression function for all four digest sizes, and is amenable to compact
implementations.
Grøstl-256 seems to need special instruction-set support for AES S-boxes to achieve even themedium level of throughput performance on computers with a 64- or 32-bit word orientation.
Even with such support, Grøstl-512 ranks near the bottom in throughput. However, on the one
eight-bit microcontroller tested, Grøstl-256 was the fastest finalist and one of the most compact.
JH seems to benefit from larger vector sizes, but even with vector instruction sets that allow 128bit operations, it is difficult to achieve a medium-level performance. JH may be more competitiveon vector units with 256-bit or larger vector registers.
5.2

Hardware Performance

There are two major implementation technologies for cryptographic circuits: Field Programmable
Gate Arrays and Application Specific Integrated Circuits. FPGAs are programmable devices thatallow the quick implementation of logic circuits that can easily be tested and modified. They aremainly used for relatively low-volume products. ASICs are custom integrated circuits that are
fabricated on a silicon wafer. The initial fixed costs for the design and fabrication of ASICs ishigher and takes longer than for FPGAs, but the performance (throughput and energy-requiredper-message-bit, or energy-per-bit for short, to compute the hash of a message) of ASICs is muchbetter than FPGAs. ASICs are also much less expensive than comparable FPGA implementations
when a large number of ASICs are produced. The modern paradigm for implementing highvolume electronics is a system on a chip: an ASIC with a processor, some memory and various
support and external interface circuits, possibly including cryptographic hardware. The ASIC
share of the market is considerably larger than the FPGA share, but there is still a significant
FPGA market, since FPGAs reduce fixed costs, get products to market faster and changes aremuch easier during the design process.
It was practical to conduct FPGA design studies of the SHA-3 finalists, where many variations on
a design were implemented and their performance measured, but was much too expensive to do
the same thing with ASICs. However, the relative performance of the finalist algorithms in ASICs
and FPGAs are often, but not always, similar [125, 126]. In particular, a good correlation has
been shown between results obtained using standard-cell CMOS 65nm UMC ASIC technology

46

and a 65nm high-performance Altera FPGA family Stratix III [125]. The similar correlation may
not exist between a different ASIC technology and a different FPGA family, due to significant
differences among various ASIC standard-cell libraries, and various internal architectures ofmodern FPGA families.
The data obtained from ASIC implementations during the SHA-3 competition is particularly
valuable, because ASICs will be used for high-volume applications. However, the performancedata from FPGA studies gave more detailed insight into the effects of design trade-offs. The
existing ASIC implementations of the SHA-3 finalists implement a full round of the algorithm, oreven unroll several rounds; FPGA studies also provided insight into folded partial-round
implementations and various unrolled or pipelined implementations. Some finalist algorithms use
different compression functions for their 256- and 512-bit variants; in order to reduce theimplementation cost, only the 256-bit ASIC implementations of the finalists were built.
There are many hardware design trade-offs. While the memory required by a hash function insoftware is not usually a concern on any but very small processors, the area needed by a hardware
hash-function implementation affects the space available for other functions on the integrated
circuit and the price of the final product. Computers running software can exploit only certain
patterns of parallel execution − for example, a word addition and a rotate at the same time, or
adding or XORing the same value to several words in parallel. On the other hand, a circuit can be
designed to simultaneously execute every operation where parallel execution is logically possible.
However, parallel execution requires additional area on the chip, and many designs sacrificeparallel execution or do not unroll logic, when it would speed up the circuit, in order to save area.
Reusing complex circuit elements saves area, but usually slows throughput and adds additionalswitching and control logic, so at some point, little or no area savings may result. The usual
overall performance metric for a hardware hash-function implementation is throughput/area.
The compression function of each of the SHA-3 finalists repeatedly executes a fairly simple
round function. This is inherently a serial process. When the entire round is implemented in asingle clock cycle, the result often gives the best throughput-to-area ratio, and this appears to be
the case for SHA-2 and several of the finalists. However, the round functions themselves usuallyconsist of repetitions of similar operations, so a round can be “folded” and only a part of theround implemented in a single clock cycle. At the other extreme, the round functions can be
unrolled, and more than one round can be executed in a single clock cycle, but, while the circuit
gets bigger because of the unrolling, the throughput usually does not get proportionately higher.
Skein, in particular, benefits from unrolling because unrolling allows the rotation circuitry to be
simplified, and because the delay of k consecutive additions is much smaller than k times thedelay of a single addition, where k is an unrolling factor (typically 4).
When several rounds or operations within a round are unrolled, it is possible to pipeline several
independent hash-function streams by adding extra memory to the circuit, and this may improve
the overall throughput/area ratio of the circuit, but not the maximum throughput of a single hashfunction stream. This is analogous to “multi-buffering” [122] software hash functions with vector
units. Skein benefits from pipelining [127], as can BLAKE [125].
All the SHA-3 finalist candidates can be efficiently implemented with 32- and 64-bit logic orarithmetic operations in order to run well on contemporary, general-purpose computers. The timeneeded for a modular addition of the natural word size of a general-purpose computer is often as
fast as bitwise logic operations. In hardware, this is not the case: word-length bitwise logic isfaster than addition with its carry propagation delays. Therefore, the fastest hash function on a
general-purpose computer is not necessarily the fastest hash function in hardware.

47

Of the five finalists, BLAKE and Skein are designed with multiple modular addition operations,while Keccak, Grøstl and JH are not. Not surprisingly, of these five algorithms, BLAKE andSkein have the best throughput on general-purpose computers, while Keccak, Grøstl and JH
usually give better throughput/area performance on hardware implementations. SHA-2 also uses
modular addition, but with more non-linear bitwise operations, and requires fewer adder circuits
than either BLAKE or Skein.
The George Mason University Cryptographic Engineering Research Group (GMU CERG)
Database provided a website resource similar to the eBASH and XBX software benchmarking
efforts. The GMU CERG Database consolidated results from all groups that had published resultsof the SHA-3 finalist hardware implementations, and had views of the ASIC Rankings [128] andthe FPGA rankings [129].
5.2.1

High-Performance Implementations

In the final round of the competition, there were three complete ASIC implementations of the256-bit versions of all five finalists and SHA-2. The studies were done by teams at GMU [125],
The Eidgenössische Technische Hochschule Zürich (ETHZ) [130], and Virginia Tech (VT) [131].
The GMU designs were optimized for maximum throughput/area, while the ETHZ designs were
optimized for throughput/area at a data rate of 2.488 Gbps (the rate of an OC-48 channel). Boththe GMU and ETHZ designs were implemented on the same ASIC with a 65 nm CMOS
technology, and the results were reported by Gürkaynak et al. [130]. The VT designs were
optimized for throughput/area, implemented in a 130 nm CMOS technology and the results werereported by Gao et al. [131, 132] and summarized in [128].
It is difficult to directly compare the throughput of implementations with such different
technologies, but areas are stated in kGate Equivalents (kGE), which are roughly comparable. To
make a rough comparison of all three sets of designs, the method employed by Gaj et al. [125] intheir “shootout” section was used to normalize the throughput/area and energy/bit results for the
candidate implementations, relative to the SHA-256 implementation by the same group using thesame technology. High throughput/area designs of SHA-2 seem to be well understood, and all
three implementations seem to have roughly the same area in kGEs, so NIST considered that thisapproach was justified and allows a rough comparison of the performance of 65 nm GMU and
ETHZ implementations with the 130 nm VT ASIC implementations on the same normalized
scale. This comparison for throughput/area is somewhat unfair to the ETH implementations,because they were optimized for a specific throughput, not, for maximum throughput/area.
Figure 4 below compares the areas for the designs, and Figure 5 compares their throughputs.
Figures 6 and 7 give the normalized throughput/area and energy per bit. For these designs it isclear that only Keccak-256 is better than SHA-256 in throughput/area, by a factor between two
and four. SHA-2 gives its best throughput/area performance with a smaller circuit than any of the
finalists. Grøstl and Skein usually require significantly larger areas to achieve their best
throughput/area ratios. In energy-per-bit consumed, Keccak and SHA-256 are roughly
comparable, and better than the four remaining finalists.

48

Area
180
160
140

kGEs

120
100

VT

80

ETHZ

60

GMU

40
20
0
KeccakJH

Grøstl

Skein

Blake

SHA-2

Figure 4. Area in kGate Equivalents for Three 256-bit ASIC Implementations

Comparable ASIC performance data is not available for the 512-bit finalists. It is obvious thatBLAKE-512 and Grøstl-512 will roughly double in area; that the area of Keccak-512 will stayabout the same, but the throughput will decrease to a bit more than half the rate of Keccak-256;
and that the throughput of JH and Skein will stay about the same. The throughput of BLAKE-512
and Grøstl-512 will be reduced by their increase over the number of rounds required for the 256bit variants, but increased by their larger message-block sizes.
However, there is FPGA data to directly compare the speed differences between 256-bit and 512bit hash functions. Gaj et al. reported on a broad examination of high- and medium- speed FPGA
implementations of the finalists [125], including folded, unrolled and pipelined implementations,and both 256-bit and 512-bit variants for four different FPGA devices. In their “shootout” section,
they combined their data with that of implementations from all other published implementations,
including Latif et al. [133], and selected the design with the best throughput/area for each of thealgorithms and FPGA devices. Figures 8 and 9 below plot the throughput/area for the best
implementations of each of the 256-bit and 512-bit finalists, normalized by the throughput/area of
SHA-256 or SHA-512 to adjust for the performance differences among the FPGA devices. The
best Keccak designs appear to have about a factor of two advantage over SHA-2 for both the 256bit and 512-bit hash functions. JH-256 and Grøstl-256 have very similar maximum
throughput/area ratios that are very close to that of SHA-256. Skein-256 and BLAKE-256 havemaximum throughput/area ratios of about half that of SHA-256. However, JH-512 is now clearlyin second place behind Keccak-512, and is better than SHA-512, while Grøstl-512 and Skein-512
are similar and a bit below SHA-512. BLAKE-512 is in last place, with a little better than half thethroughput/area ratio of SHA-512.
Clearly, in ASICs or FPGAs, and at 256-bits or 512-bits, Keccak has the best throughput/area
ratio for medium- to high-performance implementations of the finalists, and is the only finalistthat is generally better than SHA-2 in throughput/area. Keccak also has the most compact
implementation of any of the finalists when they are optimized for throughput/area. In addition,49

Keccak exhibits the lowest energy-consumption-per-message-bit of any of the finalists, and has
about the same energy-per-bit requirement as SHA-2.

Throughput
35
30

Gbps

25
20

VT
ETHZ

15

GMU
10
5
0
KeccakJH

Grøstl

Skein

Blake

SHA-2

Figure 5. Throughputs of Three 256-bit ASIC Implementations

Throughput/area
4.5

Normalized by SHA-256

4.0
3.5
3.0
2.5

VT

2.0

ETHZ

1.5

GMU

1.0
0.5
0.0
KeccakJH

Grøstl

Skein

Blake

Figure 6. Normalized Throughput/area for Three 256-bit ASIC Implementations

50

Energy/bit
7

Normalized by SHA-256

6
5
4

VT
ETHZ

3

GMU
2
1
0
KeccakJH

Grøstl

Skein

Blake

Figure 7. Normalized Energy per Bit for Three 256-bit ASIC Implementations

256-bit: best throughput/area for all architectures
3.0

Normalized by SHA-256

2.5
2.0

Virtex 5
Virtex 6

1.5Stratix III
1.0

Stratix IV

0.5
0.0
KeccakJH

Grøstl

Skein

Blake

Figure 8. (Normalized) Best Throughput/area for 256-bit FPGA Implementations

51

512-bit: best throughput/area for all architectures
3.0

Normalized by SHA-512

2.5
2.0

Virtex 5
Virtex 6

1.5Stratix III
1.0

Stratix IV

0.5
0.0
KeccakJH

Grøstl

Skein

Blake

Figure 9. (Normalized) Best Throughput/area for 512-bit FPGA Implementations

5.2.2

Compact Implementations

Extremely small or “lightweight” implementations perform differently from the highperformance implementations discussed above, in that they do not implement a full round, rather
they find some way to “fold” the round or to reuse the same circuitry several times to execute around, and are harder to evaluate. For compact implementations, the first concern is with the areaof the circuit: the application designer may want the smallest implementation that meets somethroughput target, or may want the smallest implementation possible, and be willing to live withthe performance that results. Several papers described lightweight implementations of the 256-bit
versions of the finalists, and one lightweight study featured the 512-bit versions of the SHA-3
finalists.
Kavun and Yalçın [134] reported lightweight “word-serial” implementations for the five finalists
in a 90 nm CMOS ASIC, with areas between 9.2 and 15.5 kGEs. The word-serial designs
implemented a small number of word-sized logic circuits (such as 32-bit XOR, AND, modular
addition or rotation) that were reused in a serial fashion, supplemented, where convenient oradvantageous, by a few specialized logic circuits for parallel operations, such as the Skein
permutation of 64-bit words or the Keccak π permutation. Their results are summarized in Table
20. Their most compact implementation was for Grøstl-256, and the best throughput/area ratio
was for BLAKE-256. The authors estimated that for an additional 2 kGE, they could haveproduced a Grøstl-256 implementation with about the same area and throughput as BLAKE-256,
so BLAKE-256 and Grøstl-256 seem best suited to this kind of implementation. For comparison,
the optimized throughput/area implementations of SHA-256 provided by Gürkaynak et al. [130]used around 25 kGE in area, so these implementations were around half the area of a highperformance SHA-256 implementation.
While most lightweight-implementation studies focused on 256-bit versions of the algorithms,
Kerckhof et al. [135] implemented lightweight versions of the 512-bit variants of the finalists. Allof these 512-bit implementations used a 64-bit internal path, which is a natural choice, as most of52

the algorithms are designed to operate well on 64-bit processors. Grøstl-512 had the highest
throughput/area ratio of any of the finalists, about five times that of Keccak and at least twice thatof any other algorithm. The authors claimed that “the clear advantage of Keccak in a highthroughput FPGA implementation context vanishes in a low area one.”
Algorithm
BLAKE-256
Grøstl-256
JH-256
Keccak-256
Skein-256Word(bits)
32
32
32
64
64

Area
Throughput
Throughput/Area(kGE)(kbps@100kHz)(Bps/GE)
11.3
213
18.88
9.2
40
4.32
13.6
36
2.61
15.2
91
5.96
15.5
86
5.58

Table 20. Compact ASIC “Word-serial” Implementations of the 256-bit Finalists

Jungk [136] reported a study of constrained 256-bit implementations on the Virtex-5 FPGAs thatmade extensive use of distributed RAM in his implementations. The Keccak design is not folded
along 64-bit Keccak “lanes,” but rather folded into units of eight 5-bit × 5-bit “slices.” Jungk
concluded that the results hinted that Grøstl is the best overall performer for compact
implementations when the throughput/area ratio is the most important consideration. Grøstl isfollowed by JH, Keccak, and BLAKE, which are close together, while Skein trails behind. Whenarea is the most important consideration, JH appears to be the best, followed by BLAKE, Grøstl,Keccak and Skein.
Kaps et al. [137] reported a GMU study on area-constrained FPGA implementations. The GMU
study fixed two targets: one of 768 slices and another of 450 to 650 slices, plus one block of
RAM for the Xilinx Spartan-3 FPGAs. GMU designed the highest throughput implementations of
the 256-bit finalists and SHA-256 that they could under those constraints. Figure 10 shows theareas used for the GMU Spartan-3 implementations, while Figure 11 gives the throughput/area
for the implementations. BLAKE-256 appears to be the clear throughput/area winner, followed
by Grøstl-256 and then JH-256. Only BLAKE-256 and Grøstl-256 are better than SHA-256.
Figure 12, from the Kaps presentation [137], plots the GMU designs (ported to a Virtex-5) andthe Jungk designs in a throughput versus area chart. In this chart, the relative performancechanges as the area doubles and triples. At the smaller sizes (around 500 slices), BLAKE is thefastest, but by 1200 slices, Grøstl-256 becomes the overall throughput/area leader. By about 1700
slices, Keccak-256 passes Blake, but is still slower than Grøstl-256. In this range, Skein is theslowest algorithm, and JH, while better than Skein, seems to always require more area than theother three to achieve the same throughput.
At et. al. [138] implemented Grøstl-256 and Grøstl-512 as well as AES-128, AES-192 and AES256 with an 8-bit data path that requires only 169 slices on a Virtex-6 FPGA. Because Grøstl uses
the AES S-boxes and similar operations, much of the circuitry is shared, and including AES adds
only 67 slices.

53

Compact Spartan-3 area
900
800
700

Slices600
500

with BRAM

400

logic Only

300
200
100
0
KeccakJH

Grøstl

Skein

Blake

SHA-256

Figure 10. Area of GMU Compact Spartan-3 Implementations of the 256-bit VariantsCompact Spartan-3 throughput/area
0.45
0.40

Mbps/slice

0.35
0.30

long msg BRAM

0.25

long msg logic only

0.20

short msg BRAM

0.15

short msg logic only

0.10
0.05
0.00
KeccakJH

Grøstl

Skein

Blake

SHA-256

Figure 11. Throughput/Area for GMU Spartan-3 Implementations of the 256-bit Variants

54

Figure 12. Comparison of GMU Constrained Implementations Ported to Virtex-5 with Jungk [136]
Implementations

5.2.3

Discussion of SHA-2 and the SHA-3 Finalists

The implementations of SHA-2 and each of the finalists is discussed below.
5.2.3.1

SHA-2

The SHA-2 algorithms use a conventional Davies-Meyer construction with a chaining variable ofeight words and a message block input of sixteen words. SHA-256 uses 32-bit words, while
SHA-512 uses 64-bit words in its design. Except for the word size and the number of rounds thatis called for, the two compression functions are similar and rely on bitwise AND operations in theround function and modular addition, in the message expansion and the round function, fornonlinearity. Only two words of the chaining variable require recomputation during each round,and part of round i+1 can be pre-computed during round i. SHA-2’s round function has nosymmetries that permit straightforward folding, but the whole round function is still quite
compact, usually resulting in a fairly good throughput/area ratio, − as good as or better than anyof the finalists except for Keccak. A “full” SHA-2 implementation is only a little bigger thanmany folded implementations of the SHA-3 finalists. SHA-2 provides a reasonably goodbenchmark for comparison with the finalists, because hardware implementation of SHA-2 hasbeen well studied [139, 140, 141] and is apparently mature. Consequently, there seems to be lessvariation in the size and throughput of various implementations of SHA-2 by different
investigators using the same devices, than for the SHA-3 finalists. Many of the investigators
exploring hardware performance included SHA-2 for comparative purposes in their studies. To
compare implementations by different investigators using different technologies or FPGA devices
in a single chart, Figures 6 through 9 are normalized using the performance of SHA-2 for thesame implementer and technology.

55

5.2.3.2

BLAKE

In hardware, BLAKE is one of the most flexible SHA-3 finalists, since it can be folded verticallyand horizontally by two or four, and pipelines readily within a single round. BLAKE gives thebest performance of any algorithm for very compact FPGA implementations, and the same would
probably be true for ASIC implementations. Like SHA-2, BLAKE has the advantage of two
different compression functions to aid compact 256-bit implementations, one with 32-bit words
and the other with 64-bit words. High-performance implementations of BLAKE in FPGAs or
ASICs typically require about twice the size of SHA-2, with about the same throughput, so
BLAKE’s throughput/area ratio is roughly half that of SHA-2. This ratio seems to hold for both
BLAKE variants. When FPGA implementations of BLAKE are folded to be smaller than SHA-2(roughly half the size of SHA-2), they seem, at best, to give about half the throughput/area resultof full SHA-2 implementations on the same FPGA device, and sometimes much less.
5.2.3.3

GrøstlGrøstl relies on the eight-bit AES S-boxes for nonlinearity, and a Grøstl implementation canshare circuitry with an AES implementation where both algorithms are needed [138, 142, 143].
Grøstl uses two very similar fixed permutations of either 512 or 1024 bits to build the round
function for 256-bit and 512-bit variants, respectively. There are many possible design variations
for Grøstl, more, perhaps, than any other finalist. Most designs take several times the area of
SHA-2. However, Jungk [136] reported on a Grøstl-256 implementation that was folded eightways on a Virtex-5 FPGA, with a size similar to a full SHA-256 implementation. This
implementation gave about ¾ the throughput/area performance of the GMU SHA-2
implementation on the Virtex-5, and a somewhat better performance than Jungk’s folded Keccak
implementation on the Virtex-5. While high-performance Grøstl implementations seem to bequite large and nearly always have a lower throughput/area ratio than SHA-2, Grøstl is generally
better than BLAKE and Skein in throughput/area.
5.2.3.4

JH

Like Skein, JH has a single compression function that is used by both 256-bit and 512-bit variants
and, like Skein, the 256- and 512-bit hash functions run at about the same throughput rate. Thismeans that 512-bit JH implementations are more competitive in throughput/area, compared to theother 512-bit algorithms than is the JH 256-bit implementation. JH can be readily folded andpipelined, and Jungk [136] and Kerckhof et al. [135] both reported highly folded FPGA
implementations that were compact, but slow (compared to the BLAKE implementations withsimilar area). In the GMU FPGA throughput/area “shootout,” JH-256 has about the same result as
SHA-256, while JH-512 is better than SHA-512, but worse than Keccak-512.
5.2.3.5

KeccakThe Keccak permutation has a 1600-bit state that can be viewed as a 5 × 5 array of 64-bit “lanes”
or as sixty-four 5 × 5-bit “slices”. In software, the algorithm is conveniently implemented as 64bit logic operations, rotations, loads and stores. However, general-purpose computers cannot
exploit most of the parallelism latent in the algorithm, and a full hardware implementation of
Keccak is naturally highly parallelizable, resulting in a very good throughput/area ratio, typically
about twice or more of the throughput/area ratio of a full-round SHA-2 implementation. Keccak
is the only finalist that is consistently better than SHA-2 in throughput/area for high-performance
hardware implementations. A full-round implementation of Keccak-256 in either ASICs or

56

FPGAs seems to be significantly (two to four times) bigger, but much faster (four to ten times)
than SHA-256. Keccak-512 uses the same compression function as Keccak-256, and has about
half the throughput rate, and SHA-512 gives a somewhat lower throughput/area measurement, sothat Keccak-512 retains a reduced, but still substantial, throughput/area advantage over SHA-512.
The results for compact implementations are more complex. Keccak can be folded either along
the lanes or in units of 1, 2, 4, 8, 16 or 32 slices. Kerckhof et al. [135] implemented a laneoriented, folded version of Keccak with five 64-bit registers and a 64-bit barrel rotator, but got
lower performance than the other four finalists and concluded that Keccak is inherently lesssuitable for compact FPGA implementation than the other SHA-3 finalists. However Jungk [136]studied compact FPGA implementations of the finalists and used an eight- (of 64) slice FPGA
implementation of Keccak, getting a somewhat larger, but much faster, implementation that issecond in his study only to Grøstl in throughput/area. This suggests that reasonably efficient,
folded implementations of Keccak are possible, but such folded Keccak implementations have
only about average performance.
5.2.3.6

Skein

A Skein round consists of four parallel MIX operations, each with one 64-bit modular addition
operation, one 64-bit rotation and one 64-bit XOR operation. Skein has 72 rounds, with a threetier round structure: subkeys are added every four rounds, and the rotation pattern repeats every
eight rounds. When the eight rounds are unrolled, no logic is required for the rotations. The
maximum throughput/area performance of a non-pipelined Skein implementation seems to occur
when four rounds are implemented in a single cycle. Walker et al. [127] reported on an ASIC
design with two pipelined stages in eight rounds as a good hardware trade-off for a router orserver processing multiple hash streams. The Skein round can be folded vertically, and Jungk[136] reported a Skein-256 implementation that used only three 32-bit adders, but this design was
about the same size and five to seven times slower than the full-round implementations of SHA256 reported by Gaj et al. [125] on the same FPGA device. Overall, Skein lends itself to unrolled,
pipelined implementations that can achieve high overall throughput; however, this approachrequires a comparatively large area. Since the same compression function is used for both Skein256 and Skein-512, Skein-512 is more competitive in throughput/area. Skein is not a good choicefor compact 256-bit hash function implementations or when it is implemented to maximize
throughput/area (typically by unrolling four rounds), since it requires around three times the areaof SHA-256.
5.2.4

Hardware Performance Summary

In high-performance implementations, Keccak is the clear throughput/area winner, and the only
candidate that is better than SHA-2. Skein and BLAKE have the lowest maximum throughput toarea ratio.
In very compact implementations, if the assumption that a 256-bit variant would be preferredover a 512-bit variant is correct, then it would be expected that the two finalists with different
256-bit and 512-bit compression functions, BLAKE-256 and Grøstl-256, would have an
advantage; this appears to be the case for hardware implementations. However, the advantage is
not entirely because of the separate compression functions − they are also very amenable tofolding and pipelining, and it is probably easier to tailor their implementations to a specific size
because of this flexibility. Reasonably efficient, folded or serial implementations of all of thealgorithms seem achievable, but BLAKE and Grøstl seem the most flexible.

57

6. Other Considerations
6.1

Intellectual Property

One of the SHA-3 submission requirements is the Intellectual Property Statement. Eachsubmission package needed to contain a set of signed statements to indicate that the submitted
algorithm would be available worldwide on a royalty free basis during the competition, andremain so after the competition if the algorithm is chosen as the SHA-3 winner. These statements
included:• Statement by the Submitter,• Statement by Patent (and Patent Application) Owner(s) (if applicable), and• Statement by Reference/Optimized Implementations' Owner(s).
For the last two statements, separate statements were required if multiple individuals are
involved. FRN-Nov07 [6] provides full details of these requirements.
All of the SHA-3 finalist packages satisfied this requirement; and the designers have reconfirmed
their commitment to this agreement in the last stage of the selection process.
6.2

Other Features

A number of candidate algorithms suggested ways that their submissions could be modified to
produce added functionality above and beyond the ways that current hash functions are generally
used. BLAKE’s domain extender incorporates a salt field, which could be used for more efficient
randomized hashing, for example, and its compression function is built from a 512- or 1024-bit
wide block cipher that could potentially be used on its own. Keccak’s sponge domain extenderalso provides a significant amount of flexibility. It can be fairly easily modified to produce alarger or smaller message digest, or to trade off bits of security against generic attacks forincreased performance in a controlled way. The Keccak team also published an efficient way ofusing the Keccak permutation in an authenticated-encryption mode [144].
The Skein team probably devoted the most effort of any of the finalists towards developing extra
functionality. In addition to the tweakable block-cipher, Threefish, which Skein is based upon,
the Skein team also suggested ways that Skein could be used for a variety of applications
including tree-mode hashing, a custom MAC construction, hashing the public key into message
digests for signatures, a stream cipher, and a way of “personalizing” Skein for specificapplications to avoid two different algorithms hashing the same data in ways that could be
exploited by an attacker.
The Skein team also published a paper [145] strongly advocating that NIST standardize similar
extras, whatever the final SHA-3 winner is. The highest priority applications, according to thepaper, were support for more efficient MAC constructions than HMAC, and support for
nonstandard message-digest sizes. Other features listed as important were tree-based hashing, andhash-based signatures. Finally, the paper listed two more applications as “nice to have:” astandardized technique for “personalization,” and a hash-function-based authenticated-encryption
mode.

58

7. Conclusion
After a very long and complex evaluation process, NIST has selected Keccak as the winner of the
SHA-3 Competition. It was chosen from a field of five very strong candidates, each of which
provides some outstanding performance characteristics and design features. All five finalists
appear to provide an adequate security margin, as well.
Contrary to the fears leading up to the SHA-3 Competition, SHA-2 has held up well in the face ofcontinued cryptanalysis. The new SHA-3 will need to compete with an existing algorithm (SHA2) that also offers very strong security and performance. Keccak was chosen, not just for its verystrong overall security and performance, but because it offers exceptional performance in areas
where SHA-2 does not, and because it relies on completely different architectural principles fromthose of SHA-2 for its security.
Keccak has a large security margin, good general performance, excellent efficiency in hardware
implementations, and a flexible design. Keccak uses a new “sponge construction” domain
extender, which is based on a fixed permutation, that can be readily adjusted to trade genericsecurity strength for throughput, and can generate larger or smaller hash outputs, as required. The
Keccak designers have also defined a modified chaining mode for Keccak that provides
authenticated encryption.
NIST plans to augment the current hash standard, FIPS 180-4, to include the new SHA-3
algorithm, and publish a draft FIPS 180-5 for public review. After the close of the publiccomment period, NIST will revise the draft standard, as appropriate, in response to the publiccomments that NIST receives. A final review, approval, and promulgation process will thenfollow. Additionally, NIST may consider standardizing additional constructions based on the
Keccak permutation, such as an authenticated-encryption mode, in the future. Any such future
standardization efforts will be conducted in consultation with the public, the Keccak design teamand the larger cryptographic research community.

59

References 17
[1]

[2]

[3]

[4]
[5]

[6]

[7]

[8]

[9]

[10]
[11]

[12]

FIPS PUB 180-2, Secure Hash Standard (SHS), Information Technology Laboratory,
National
InstituteofStandards
andTechnology,
August2002,
http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf
FIPS PUB 180-3, Secure Hash Standard (SHS), Information Technology Laboratory,
National
InstituteofStandards
andTechnology,
October
2008,
http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf
FIPS PUB 180-4, Secure Hash Standard (SHS), Information Technology Laboratory,
National
InstituteofStandards
andTechnology,
March
2012,
http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf
X. Wang, Y. L. Yin, H. Yu, “Collision Search Attacks on SHA-1,” 2005,
http://www.c4i.org/erehwon/shanote.pdf
Announcing the Development of New Hash Algorithm(s) for the Revision of Federal
Information Processing Standard (FIPS) 180-2, Secure Hash Standard, Federal Register /Vol. 72, No. 14 / Tuesday, January 23, 2007 / Notices 2861,
http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Jan07.pdf
Announcing Request for Candidate Algorithm Nominations for a New Cryptographic
Hash Algorithm (SHA-3) Family, Federal Register/ Vol. 72, No. 212 / Friday, November
2,
2007
/
Notices
62212,
http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf
J. Nechvatal, E. Barker, L. Bassham, W. Burr, M. Dworkin, J. Foti, E. Roback, “Reporton the Development of the Advanced Encryption Standard (AES),” Information
Technology Laboratory, National Institute of Standards and Technology, October 2,
2000, http://csrc.nist.gov/archive/aes/round2/r2report.pdf
J.-P. Aumasson, L. Henzen, W. Meier, R. C.-W. Phan, “SHA-3 proposal BLAKE,”
Submission to NIST (Round 3), 2011, http://csrc.nist.gov/groups/ST/hash/sha3/Round3/submissions_rnd3.html
P. Gauravaram, L. R. Knudsen, K. Matusiewicz, F. Mendel, C. Rechberger, M. Schläffer,
S. Thomsen, “Grøstl A SHA-3 Candidate,” Submission to NIST (Round 3), 2011,
http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html
H. Wu, “The Hash Function JH,” Submission to NIST (Round 3), 2011,
http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html
G. Bertoni, J. Daemen, M. Peeters, G. V. Assche, “Keccak Specifications,” Submission to
NIST(Round3),
2011,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/submissions_rnd3.html
N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, J.
Walker, “The Skein Hash Function Family,” Submission to NIST (Round 3), 2011,
http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html

17

A number of the references below are to online resources provided by individuals or organizations thatare not affiliated with NIST. While some effort was made to provide links to resources that NIST expects toremain available over the long term, this was not always possible. In these cases, NIST felt that eventemporarily available online resources were of value.

60

[13]

[14]

[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]

[23]
[24]
[25]
[26]
[27]

[28]

[29]

[30]

A. Regenscheid, R. Perlner, S. Chang, J. Kelsey, M. Nandi, S. Paul, “Status Report on theFirst Round of the SHA-3 Cryptographic Hash Algorithm Competition,” NIST IR 7620,
September2009,
http://csrc.nist.gov/groups/ST/hash/sha3/Round1/documents/sha3_NISTIR7620.pdf
M. Sönmez Turan, R. Perlner, L. Bassham, W. Burr, D. Chang, S. Chang, M. Dworkin, J.
Kelsey, S. Paul, R. Peralta, “Status Report on the Second Round of the SHA-3
Cryptographic Hash Algorithm Competition,” NIST IR 7764, February 2011,
http://csrc.nist.gov/groups/ST/hash/sha3/Round2/documents/Round2_Report_NISTIR_7764.pdf
The Third SHA-3 Candidate Conference, Washington, DC, March 22-23, 2012,
http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/March2012/index.html
Hash Forum, http://csrc.nist.gov/groups/ST/hash/email_list.html
ECRYPT Hash Workshop 2007, Barcelona, Spain, May 24-25, 2007,
http://events.iaik.tugraz.at/HashWorkshop07/
Hash Functions in Cryptology: Theory and Practice, Leiden, The Netherlands, June 2-6,
2008, http://www.lorentzcenter.nl/lc/web/2008/309/info.php3?wsid=309
International Workshop on Security 2009 (IWSEC09), Toyama, Japan, October 28-30,
2009, http://www.iwsec.org/2009/index.html
Hash3: Proofs, Analysis, and Implementation, Tenerife, Spain, November 16-20, 2009,https://www.cosic.esat.kuleuven.be/ecrypt/courses/tenerife09/index.shtml
ECRYPT II Hash
Workshop, Tallinn, Estonia, May 19-20, 2011,
http://www.ecrypt.eu.org/hash2011/
Quo Vadis Cryptology? SHA-3 Contest - 7th International Workshop on the State of the
Art in Cryptology and New Challenges Ahead, Warsaw, Poland, May 23-24, 2011,
http://cryptography.gmu.edu/quovadis/
Hash Workshop on SHA3 Finalists, Kolkata, India, December 9-10, 2011,
http://www.isical.ac.in/~coec/workshop/hash2011.html
ECRYPT SHA-3 Zoo, http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo
D. Bernstein and T. Lange (editors), eBASH: ECRYPT Benchmarking of All Submitted
Hashes, http://bench.cr.yp.to/ebash.html
External Benchmarking Extension (XBX), http://xbx.das-labor.org/trac
C. Rechberger, T. Bjørstad, J. Daemen, C. De Cannière, P. Gauravaram, D.
Khovratovich, W. Meier, T. Nad, I. Nikolić, M. Robshaw, M. Schläffer, S. Thomsen, E.
Tischhauser, D. Toz, G. Van Assche, K. Varıcı, “ECRYPT II SHA-3 Design and
Cryptanalysis Report,” August 2010, http://www.ecrypt.eu.org/documents/D.SYM.4.pdf
P. Gauravaram, F. Mendel, M. Naya-Plasencia, V. Rijmen, D. Toz, “ECRYPT II
Intermediate
StatusReport,”July2011,
http://www.ecrypt.eu.org/documents/D.SYM.7.pdf
Information Technology Laboratory, National Institute of Standards and Technology,“SHA-3
Selection
Announcement,”
October2,
2012,
http://csrc.nist.gov/groups/ST/hash/sha-3/sha-3_selection_announcement.pdf
Cryptographic Hash Workshop, NIST Gaithersburg, MD, October 31-November 1, 2005,
http://csrc.nist.gov/groups/ST/hash/first_workshop.html

61

[31]
[32]
[33]
[34]

[35]

[36]

[37]

[38]
[39]

[40]
[41]

[42]
[43]

[44]

[45]

[46]

The Second Cryptographic Hash Workshop, UCSB, CA, August 24-25, 2006,
http://csrc.nist.gov/groups/ST/hash/second_workshop.html
The First SHA-3 Candidate Conference, KU Leuven, Belgium, February 25-28, 2009,http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/index.html
The Second SHA-3 Candidate Conference, UCSB, CA, August 23-24, 2010,
http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/
FIPS PUB 198-1, The Keyed-Hash Message Authentication Code (HMAC), Information
Technology Laboratory, National Institute of Standards and Technology, July 2008,
http://csrc.nist.gov/publications/fips/fips198-1/FIPS-198-1_final.pdf
J. Black, P. Rogaway, T. Shrimpton, “Black-Box Analysis of the Block-Cipher-BasedHash-Function Constructions from PGV,” CRYPTO 2002, pp. 320-335,
http://www.cs.ucdavis.edu/~rogaway/papers/hash.pdf
C. Bouillaguet, P. Fouque, “Practical Hash Functions Constructions Resistant toGeneric Second Preimage Attacks Beyond the Birthday Bound,” Soumis dansInformation Processing Letters (IPL), 2011, http://www.di.ens.fr/~fouque/pub/ipl11.pdf
B. Su, W. Wu, S. Wu, L. Dong, “Near-Collisions on the Reduced-Round Compression
Functions of Skein and BLAKE,” Cryptology ePrint Archive, Report 2010/355, 2010,
http://eprint.iacr.org/2010/355.pdf
M. Schläffer, “Updated Differential Analysis of Grøstl,” January 2011,
http://www.groestl.info/groestl-analysis.pdf
M. Naya-Plasencia, D. Toz, K. Varıcı, “Rebound Attack on JH42,” Advances in
Cryptology – ASIACRYPT 2011, LNCS 7073, pp. 252-269, Springer, 2011,
http://rd.springer.com/chapter/10.1007/978-3-642-25385-0_14
I. Dinur, O. Dunkelman, A. Shamir, “New Attacks on Keccak 224 and Keccak 256,”
Cryptology ePrint Archive, Report 2011/624, 2011, http://eprint.iacr.org/2011/624.pdf
H. Yu, J. Chen, K Wang, X. Wang, “Near-Collision Attack on the Step-Reduced
Compression Function of Skein-256,” Cryptology ePrint Archive, Report 2011/148,
2011, http://eprint.iacr.org/2011/148.pdf
S. Sanadhya, P. Sarkar, "New Collision Attacks against Up to 24-Step SHA-2,”
Cryptology ePrint Archive, Report 2008/270, 2008, http://eprint.iacr.org/2008/270.pdf
A. Biryukov, I. Nikolić, A. Roy, “Boomerang attacks on BLAKE-32,” Fast Software
Encryption
2011,
LNCS
6733,
pp.
218-237,
Springer,2011,
http://www.springerlink.com/content/r72k542v10330131/
J. Jean, M. Naya-Plasencia, and T. Peyrin, “Improved Rebound Attack on the Finalist
Grøstl,”FSE
2012,
Washington
DC,
March
19-21,
2012,
http://www.di.ens.fr/~jean/pub/fse2012.pdf
M. Duan, X. Lai, “Improved Zero-Sum Distinguisher for Full Round Keccak-f
Permutation,”
Cryptology
ePrintArchive,
Report2011/023,2011,
http://eprint.iacr.org/2011/023.pdf
J.P. Aumasson, W. Meier, “Zero-sum Distinguishers for Reduced Keccak-f and for theCore Functions of Luffa and Hamsi,” Email to Hash Forum, September 9, 2009,http://www.131002.net/data/papers/AM09.pdf

62

[47]

[48]

[49]
[50]
[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]
[61]

D. Khovratovich, C. Rechberger, A. Savalieva, “Bicliques for Preimages: Attacks on
Skein-512 and the SHA-2 family,” Cryptology ePrint Archive, Report 2011/286, 2011,
http://eprint.iacr.org/2011/286.pdf
H. Yu, J. Chen, K Wang, X. Wang, “The Boomerang Attacks on the Round Reduced
Skein-512,”
Cryptology
ePrintArchive,
Report2012/238,2012,
http://eprint.iacr.org/2012/238.pdf
M. Lamberger, F. Mendel, “Higher-Order Differential Attack on Reduced SHA-256,”
Cryptology ePrint Archive, Report 2011/037, 2011, http://eprint.iacr.org/2011/037.pdf
D. Chang, “Midgame Attacks and Defense Against Them,” unpublished manuscripts,
April 2012.
D. Chang and M. Yung, “Midgame Attacks (and their consequences),” Crypto 2012
Rump
Session,
August21,
2012,
http://crypto.2012.rump.cr.yp.to/008b781ca9928f2c0d20b91f768047fc.pdf
M. Zohner, M. Kasper, M. Stottinger, “Side Channel Analysis of the SHA-3 Finalists,”
the Third SHA-3 Candidate Conference, Washington, DC, March 22-23, 2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/ZOHNER_paper.pdf
O. Benoit, T. Peyrin, “Side channel Analysis of Six SHA-3 Candidates,” CHES 2010,
LNCS
6225,
pp.
140-157,
Springer,2010,
http://www.springerlink.com/content/822377q22h78420u/?MUD=MP
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Note on Side Channel Attacks and
Their
Countermeasures,”http://keccak.noekeon.org/NoteSideChannelAttacks.pdf.
Submitted to the hash forum on May, 15, 2009, http://cio.nist.gov/esd/emaildir/lists/hashforum/msg01511.html
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Building Power Analysis Resistant
Implementations of Keccak,” the Second SHA-3 Candidate Conference, UCSB, CA,2010,
http://csrc.nist.gov/groups/ST/hash/sha3/Round2/Aug2010/documents/papers/BERTONI_KeccakAntiDPA.pdf
S. Hoerder, M. Wojcik, S. Tillich, D. Page, “An Evaluation of Hash Functions on a
Power Analysis Resistant Processor Architecture,” Cryptology ePrint Archive, Report
2010/614, 2010, http://eprint.iacr.org/2010/614.pdf
D. Osvik, A. Shamir and E. Tromer, “Cache Attacks and Countermeasures: the Case of
AES,”
Cryptology
ePrintArchive,
Report2005/271,
2005,
http://reference.kfupm.edu.sa/content/c/a/cache_attacks_and_countermeasures__the_c_3
469711.pdf
M. Schläffer, “Cryptanalysis of AES-Based Hash Functions,” PhD Thesis, March 2011,
Graz
UniversityofTechnology,
Austria,
https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=58178
E. Biham, O. Dunkelman, “A Framework for Iterative Hash Functions — HAIFA,” NIST
SecondCryptographic
Hash
Workshop,
UCSB,
CA,August2006,
http://csrc.nist.gov/groups/ST/hash/documents/DUNKELMAN_NIST3.pdf
D. Bernstein, “ChaCha, A Variant of Salsa20,” http://cr.yp.to/chacha.html
E. Andreeva, A. Luykx, and B. Mennink, “Provable Security of BLAKE with Non-Ideal
Compression Function,” Third SHA-3 Candidate Conference, Washington DC, March

63

[62]
[63]
[64]
[65]

[66]

[67]

[68]

[69]

[70]

[71]

[72]

[73]

[74]

[75]
[76]

http://csrc.nist.gov/groups/ST/hash/sha22-23,
2012,
3/Round3/March2012/documents/papers/MENNINK_paper.pdf
D. Chang, M. Nandi, and M. Yung, “Indifferentiability of the hash algorithm BLAKE,”
Cryptology ePrint Archive, Report 2011/623, 2011, http://eprint.iacr.org/2011/623
J. Li, L. Xu, “Attacks on Round-reduced BLAKE,” Cryptology ePrint Archive, Report
2009/238, 2009, http://eprint.iacr.org/2009/238.pdf
J. Guo, K. Matusiewicz, “Round-reduced Near-Collisions of BLAKE-32,” WEWoRC
2009, http://www1.spms.ntu.edu.sg/~guojian/doc/blake-col.pdf
J.-P. Aumasson, J. Guo, S. Knellwolf, K. Matusiewicz, W. Meier, “Differential andInvertibility Properties of BLAKE,” Cryptology ePrint Archive, report 2010/043, 2010,
http://eprint.iacr.org/2010/043.pdf
M. Sönmez Turan, E. Uyan, “Practical Near-Collisions for Reduced Round Blake,
Fugue, Hamsi and JH,” the Second SHA-3 Candidate Conference, UCSB, CA, 2010,
http://csrc.nist.gov/groups/ST/hash/sha3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf
J. Vidali, P. Nose, E. Pašalic, “Collisions for Variants of the BLAKE Hash Function,”
Proceedings of Information Processing Letters, vol. 110, Issue 14-15, 2010,
http://lkrv.fri.uni-lj.si/~janos/blake/collisions.pdf
M. Ming, H. Qiang, S. Zeng, “Security Analysis of BLAKE-32 Based on Differential
Properties,” 2010 International Conference on Computational and Information Sciences,
pp. 783-786, 2010, http://dl.acm.org/citation.cfm?id=1933979
G. Leurent, “ARXtools: A toolkit for ARX Analysis,” the Third SHA-3 Candidate
Conference,
Washington
DC,
March
22-23,
2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/LEURENT_paper.pdf
J.-P. Aumasson, G. Leurent, W. Meier, F. Mendel, N. Mouha, R.C.W. Phan, Y. Sasaki, P.
Susil: “Tuple cryptanalysis of ARX with application to BLAKE and Skein,” ECRYPT II
HashWorkshop
2011,May
19-20,
2011,
http://www.ecrypt.eu.org/hash2011/proceedings/hash2011_01.pdf
O. Dunkelman, D. Khovratovich, “Iterative differentials, symmetries and message
modification in BLAKE-256,” ECRYPT II Hash Workshop 2011, May 19-20, 2011,
http://www.ecrypt.eu.org/hash2011/proceedings/hash2011_02.pdf
P. Gauravaram, L. R. Knudsen, K. Matusiewicz, F. Mendel, C. Rechberger, M. Schläffer,
S. Thomsen, “Tweaks on Grøstl,” Submission to NIST (Round 3), 2011,
http://www.groestl.info/Round3Mods.pdf
E. Andreeva, B. Mennink, B. Preneel and M. Skrobot, “Security Analysis andComparison of the SHA-3 Finalists BLAKE, Grøstl, JH, Keccak, and Skein,” the Third
SHA-3 Candidate Conference, Washington DC, March 22-23, 2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/ANDREEVA_paper.pdf
E. Andreeva, B. Mennink, B. Preneel, “On the Indifferentiability of the Grøstl Hash
Function,”
LNCS
6280,
pp.
88-105,
Springer,2010,
http://rd.springer.com/chapter/10.1007/978-3-642-15317-4_7
J. Kelsey, “Some notes on Grøstl,” 2009, http://ehash.iaik.tugraz.at/uploads/d/d0/Grostlcomment-april28.pdf
F. Mendel, C. Rechberger, M. Schläffer, S. Thomsen, “The Rebound Attack:
Cryptanalysis of Reduced Whirlpool and Grøstl,” Proceedings of FSE, LNCS 5665, pp.

64

[77]

[78]

[79]

[80]
[81]

[82]

[83]

[84]

[85]

[86]

[87]

[88]

[89]
[90]

260-276, Springer, 2009, http://www2.mat.dtu.dk/people/S.Thomsen/MendelRSTfse09.pdf
F. Mendel, T. Peyrin, C. Rechberger, M. Schläffer, “Improved Cryptanalysis of theReduced Grøstl Compression Function, ECHO Permutation and AES Block Cipher,”Proceedings
of
SAC,
5867,
pp.
16-35,
2009,https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=44420
H. Gilbert, T. Peyrin, “Super-Sbox Cryptanalysis: Improved Attacks for AES-likepermutations,”
Cryptology
ePrintArchive,
Report2009/531,
2009,
http://eprint.iacr.org/2009/531.pdf
F. Mendel, C. Rechberger, M. Schläffer, S. Thomsen, “Rebound Attacks on the Reduced
Grøstl Hash Function,” Proceedings of CT-RSA, LNCS 5985, pp. 350-365, Springer,
2010, http://www.springerlink.com/content/p016144684v473r6/
T. Peyrin, “Improved Differential Attacks for ECHO and Grøstl,” Cryptology ePrint
Archive, Report 2010/223, 2010, http://eprint.iacr.org/2010/223.pdf
K. Ideguchi, E. Tischhauser, B. Preneel, “Improved Collision Attacks on the ReducedRound Grøstl Hash Function,” Cryptology ePrint Archive, Report 2010/375, 2010,
http://eprint.iacr.org/2010/375.pdf
M. Naya-Plasencia, “How to Improve Rebound Attacks,” Cryptology ePrint Archive,
Report 2010/607, 2010, http://eprint.iacr.org/2010/607.pdf. Also published in Advancesin Cryptology - CRYPTO 2011, LNCS 6841, pp. 188-205, Springer, 2011,
http://rd.springer.com/chapter/10.1007/978-3-642-22792-9_11
Y. Sasaki, Y. Li, L. Weng, K. Sakiyama, K. Ohta, “Non-full-active Super-Sbox Analysis:
Applications to ECHO and Grøstl,” Proceedings of Asiacrypt, LNCS 6477, pp. 38-55,
2010, http://www.springerlink.com/content/b288848681x52214/
C. Boura, A. Canteaut, C. De Canniere, “Higher Order Differential Properties of Keccak
andLuffa”(Presentation),
FSE
2011,
Feb.
15,
2011,
http://fse2011.mat.dtu.dk/slides/Higherorder%20differential%20properties%20of%20Keccak%20and%20Luffa.pdf
C. Boura, A. Canteaut, C. De Canniere, “Higher Order Differential Properties of Keccak
andLuffa,”
Cryptology
ePrintArchive,
Report2010/589,
2010,
http://eprint.iacr.org/2010/589.pdf
D. Khovratovich, “Bicliques for permutations: collision and preimage attacks in stronger
settings,”
Cryptology
ePrintArchive,
Report2012/141,2012,
http://eprint.iacr.org/2012/141.pdf
S. Wu, D. Feng, W. Wu, J. Guo, L. Dong, and J. Zou, “(Pseudo) Preimage Attack on
Round-Reduced Grøstl Hash Function and Others (Extended Version),” Cryptology
ePrint Archive, Report 2012/206, 2012, http://eprint.iacr.org/2012/206
R. Bhattacharyya, A. Mandal, M. Nandi, “Security Analysis of the Mode of JH Hash
Function,”
FSE
2010,
LNCS
6147,
pp.
168-191,2010,
http://www.isical.ac.in/~rishi_r/FSE2010-146.pdf
F.
Mendel,S.
Thomsen,“An
Observationon
JH-512,”
2008,
http://ehash.iaik.tugraz.at/uploads/d/da/Jh_preimage.pdf
H. Wu, “The Complexity of Mendel and Thomsen's Preimage Attack on JH-512,” 2009,http://ehash.iaik.tugraz.at/uploads/6/6f/Jh_mt_complexity.pdf

65

[91]

[92]
[93]

[94]

[95]
[96]
[97]

[98]

[99]
[100]

[101]

[102]

[103]

[104]

[105]

N. Bagheri, “Re: Free start collision, second preimage, and Preimage on JH,” Email to
Hash Forum, November 29, 2008, http://cio.nist.gov/esd/emaildir/lists/hashforum/msg00981.html
J. Lee, D. Hong, “Collision resistance of the JH hash function,” Cryptology ePrint
Archive, Report 2011/019, 2011, http://eprint.iacr.org/2011/019.pdf
D. Moody, S. Paul, D. Smith-Tone, “Improved indifferentiability security bound for the
JH mode,” the Third SHA-3 Candidate Conference, Washington, DC, 2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/PAUL_paper.pdf
V. Rijmen, D. Toz, and K. Varıcı, “Rebound Attack on Reduced-Round Versions of JH,”
FSE
2010,
LNCS
6147,
pp.
286-303,2010,https://www.cosic.esat.kuleuven.be/publications/article-1431.pdf
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Sponge Functions,” ECRYPT Hash
Workshop, 2007, http://sponge.noekeon.org/SpongeFunctions.pdf
KeccakCrunchy
CryptoCollisionandPre-imageContest,http://keccak.noekeon.org/crunchy_contest.html
G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, “On the Indifferentiability of theSponge Construction,” EUROCRYPT 2008, LNCS 4965, pp. 181-197, Springer-Verlag,
Berlin, 2008, http://rd.springer.com/chapter/10.1007/978-3-540-78967-3_11
D. Gligoroski, R. Ødeård, and R. Jensen, “OBSERVATION: An explicit form for a classof second preimages for any message M for the SHA-3 candidate Keccak,” Cryptology
ePrint Archive, Report 2011/261, 2011, http://eprint.iacr.org/2011/261
J.P. Aumasson, D. Khovratovich, “First Analysis of Keccak,” 2009,http://www.131002.net/data/papers/AK09.pdf
P. Morawiecki, M. Srebrny, “A SAT-based Preimage Analysis of Reduced KECCAKHash Functions,” Cryptology ePrint Archive, Report 2010/285, 2010,
http://eprint.iacr.org/2010/285.pdf
C. Boura, A. Canteaut, “A Zero-Sum Property for the Keccak-f Permutation with 18
Rounds,”
Email
to
Hash
Forum,
January14,2010,
http://wwwrocq.inria.fr/secret/Anne.Canteaut/Publications/zero_sum.pdf
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Note on Zero-sum Distinguishers of
Keccak-f,”
Email
to
Hash
Forum,
January15,2010,
http://keccak.noekeon.org/NoteZeroSum.pdf
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Note on Keccak Parameters andUsage,”
Email
to
Hash
Forum,
February23,2010,
http://keccak.noekeon.org/NoteOnKeccakParametersAndUsage.pdf
C. Boura, A. Canteaut, “Zero-Sum Distinguishers for Iterated Permutations andApplications to Keccak-f and Hamsi-256,” Selected Areas in Cryptography, 2010,https://www.rocq.inria.fr/secret/Christina.Boura/data/sac.pdf
J. Lathrop, “Cube Attacks on Cryptographic Hash Functions,” Master’s Thesis,
RochesterInstituteofTechnology,
May
21,
2009,
https://ritdml.rit.edu/bitstream/handle/1850/10821/20782_pdf_C9905D10-60E8-11DEAE1A-0950D352ABB1.pdf?sequence=166

[106]
[107]
[108]

[109]

[110]

[111]

[112]

[113]

[114]
[115]

[116]

[117]

[118]
[119]

[120]

P. Morawiecki, First Solutions to Keccak Crunchy Crypto Contest, Submitted on July 29,
2011, http://keccak.noekeon.org/crunchy_contest.html
A. Duc, J. Guo, T. Peyrin, L. Wei, “Unaligned Rebound Attack: Application to Keccak,”
Cryptology ePrint Archive, Report 2011/420, 2011, http://eprint.iacr.org/2011/420.pdf
D. Bernstein, “Second Preimages for 6 (7? (8??)) Rounds of Keccak?,” Email to Hash
Forum,
November
27,
2010,
http://cio.nist.gov/esd/emaildir/lists/hashforum/msg02232.html,
or
http://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailinglist_Bernstein-Daemen.txt
M. Naya-Plasencia, A. Röck, and W. Meier, “Practical Analysis of Reduced-Round
Keccak,” INDOCRYPT 2011, LNCS 7107, pp. 236-254, Springer, 2011,
http://naya.plasencia.free.fr/Maria/papers/Keccak_differential.pdf
M. Bellare, T. Kohno, S. Lucks, N. Ferguson, B. Schneier, D. Whiting, J. Callas, and J.
Walker, “Provable Security Support for the Skein Hash Family," Version 1.0, Apr 2009,http://www.skein-hash.info/sites/default/files/skein-proofs.pdf
J. Chen, K. Jia, “Improved Related-Key Boomerang Attacks on Round-Reduced
Threefish-512,”
Cryptology
ePrintArchive,
Report2009/526,2009,
http://eprint.iacr.org/2009/526.pdf
J.P. Aumasson, Ç. Çalık, W. Meier, O. Özen, R. Phan, K. Varıcı, “Improved
Cryptanalysis of Skein,” Cryptology ePrint Archive, Report 2009/438, 2009,http://eprint.iacr.org/2009/438.pdf
K. McKay, P. Vora, “Pseudo-Linear Approximations for ARX Ciphers: With Application
toThreefish,”
Cryptology
ePrintArchive,
Report2010/282,2010,
http://eprint.iacr.org/2010/282.pdf
D. Khovratovich, I. Nikolic, “Rotational Cryptanalysis of ARX,” proceedings of
FSE2010, pp. 333-346, 2010, http://www.skein-hash.info/sites/default/files/axr.pdf
D. Khovratovich, I. Nikolic, C. Rechberger, “Rotational Rebound Attacks on Reduced
Skein,”
Cryptology
ePrintArchive,
Report2010/538,2010,
http://eprint.iacr.org/2010/538.pdf
C. Hanser, “Performance of the SHA-3 Candidates in Java,” the Third SHA-3 Candidate
Conference,
Washington,
DC,
March
22-23,
2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/HANSER_paper.pdf
P. Schwabe, B. Yang, and S. Yang, “SHA-3 on ARM11 processors,” the Third SHA-3
CandidateConference,
Washington,
DC,
March
22-23,
2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/YANG_paper.pdf
D.
Bernstein
and
T.
Lange
(editors),eBACS:
ECRYPT
Benchmarking of Cryptographic Systems, http://bench.cr.yp.to/
D. Bernstein and T. Lange, “The New SHA-3 Software Shootout,” the Third SHA-3
CandidateConference,
Washington,
DC,
March
22-23,
2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/BERNSTEIN_paper.pdf
S. Neves and J.-P. Aumasson, “BLAKE and 256-bit advanced Vector Extensions,” theThird SHA-3 Candidate Conference, Washington, DC, March 22-23, 2012,67http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/NEVES_paper.pdf[121] G. Van Assche, “Keccak, tree hashing and rotation instructions,” Email to Hash Forum,
May 30, 2012, http://cio.nist.gov/esd/emaildir/lists/hash-forum/msg02431.html[122] V. Gopal, J. Guilford, W. Feghali, E. Ozturk, G. Wolrich, and M. Dixon, “Processing
Multiple Buffers in Parallel to Increase Performance on Intel Architecture Processors,”Intel
Corporation
White
Paper,
July2010,
http://download.intel.com/design/intarch/papers/324101.pdf[123] S. Gueron and V. Krasnov, “Parallelizing message schedules to accelerate thecomputations of hash functions,” Cryptology ePrint Archive, Report 2012/067, 2012,
http://eprint.iacr.org/2012/067.pdf[124] R. Grisenthwaite, “ARMv8 Technology Preview,” Presentation at ARM 2011 TechCon,
http://www.arm.com/files/downloads/ARMv8_Architecture.pdf[125] K. Gaj, E. Homsirikamol, M. Rogawski, R. Shahid, and M. Sharif,“Comprehensive Evaluation of High-Speed and Medium-Speed Implementations ofFive SHA-3 Finalists Using Xilinx and Altera FPGAs,” Cryptology ePrint Archive,
Report 2012/368, 2012, http://eprint.iacr.org/2012/368[126] X. Guo, S. Huang, L. Nazhandali and P. Schaumont, "On The Impact of Target
Technology in SHA-3 Hardware Benchmark Rankings,” Cryptology ePrint Archive,
Report 2010/536, 2010, http://eprint.iacr.org/2010/536[127] J. Walker, F. Sheikh, S. Mathew and R. Krishnamurthy, “A Skein-512 Hardware
Implementation,” the Second SHA-3 Candidate Conference, UCSB, CA, 2010,
http://csrc.nist.gov/groups/ST/hash/sha3/Round2/Aug2010/documents/papers/WALKER_skein-intel-hwd.pdf[128] GMU Cryptographic Engineering Research Group, ATHENa Database of ASIC Results ASIC
Rankings,
availableat
http://cryptography.gmu.edu/athenadb/asic_hash/rankings_view[129] GMU Cryptographic Engineering Research Group, ATHENa Database of FPGA Results
FPGA
Rankings,
availableat
http://cryptography.gmu.edu/athenadb/fpga_hash/rankings_view[130] F. Gürkaynak, K. Gaj, B. Muheim, E. Homsirikamol, C. Keller, M. Rogawski, H.
Kaeslin, and J. Kaps, “Lessons Learned from Designing a 65 nm ASIC for Evaluating
Third Round SHA-3 Candidates,” the Third SHA-3 Candidate Conference, Washington,
DC,
March
22-23,
2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/GURKAYNAK_paper.pdf[131] X. Guo, M. Srivastav, S. Huang, D. Ganta, M. Henry, L. Nazhandali, and P. Schaumont,"ASIC Implementations of Five SHA-3 Finalists,” Proceedings of 2012 Design
Automation and Test in Europe Conference, DATE 2012, track A5 on Secure Systems,
Dresden,Germany,Mar.
12-16,
2012,
http://rijndael.ece.vt.edu/sha3/publications/DATE2012SHA3.pdf[132] M. Srivastav, X. Guo, S. Huang, D. Ganta, M. Henry, L. Nazhandali, and P. Schaumont,"Design and Benchmarking of an ASIC with Five SHA-3 Finalist Candidates,”Elsevier Microprocessors and Microsystems: Embedded Hardware Design (MICPRO),68

[133]

[134]

[135]

[136]

[137]

[138]

[139]

[140]

[141]

[142]

[143]

Special Issue on Digital System Security and Safety (in press), preprint available
at http://rijndael.ece.vt.edu/schaum/papers/2012micpro.pdf
K. Latif, M. Rao, A. Aziz and A. Mahboob, “Efficient Hardware Implementations andHardware Performance,” the Third SHA-3 Candidate Conference, Washington, DC,
March
22-23,
2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/KASHIF_paper.pdf
E. Kavun, T. Yalçın, “On the Suitability of SHA-3 Finalists for Lightweight
Applications,” the Third SHA-3 Candidate Conference, Washington, DC, March 22-23,2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/KAVUN_paper.pdf
S. Kerckhof, F. Durvaux, N. Veyrat-Charvillon, F. Regazzoni, G. de Dormale, and F.
Standaert, “Compact FPGA Implementations of the Five SHA-3 Finalists,” ECRYPT II
HashWorkshop
2011,May
19-20,
2011,
http://www.ecrypt.eu.org/hash2011/proceedings/hash2011_10.pdf
B. Jungk, “Evaluation Of Compact FPGA Implementations For All SHA-3 Finalists,” theThird SHA-3 Candidate Conference, Washington, DC, March 22-23, 2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/JUNGK_paper.pdf
J. Kaps, P. Yalla, K. Surapathi, B. Habib, S. Vadlamudi and S. Gurung, “Lightweight
Implementations of SHA-3 Finalists on FPGAs,” the Third SHA-3 Candidate Conference,
Washington, DC, March 22-23, 2012, http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/KAPS_paper.pdf,,
Presentation
at
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/presentations/KAPS_presentation.pdf
N. At, J. Beuchat, E. Okamoto, I. San, and T. Yamazaki, “A Low-Area Uniﬁed Hardware
Architecture for the AES and the Cryptographic Hash Function Grøstl,” Cryptology
ePrint Archive, Report 2012/535, 2012, http://eprint.iacr.org/2012/535.pdf
R. Chaves, G. Kuzmanov, L. Sousa, S. Vassiliadis, “Improving SHA-2 Hardware
Implementations,”
Cryptology
ePrintArchive,
Report2006/24,2006,
http://www.iacr.org/archive/ches2006/24/24.pdf
R. Chaves, G. Kuzmanov, L. Sousa, S. Vassiliadis, “Cost-Efficient SHA Hardware
Accelerators,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol.
16,
No.
8,
pp.
999-1008,
August2008,
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4560238
M. Rogawski, X. Xin, E. Homsirikamol, D. Hwang and Kris Gaj, “Implementing SHA-1
and SHA-2 Standards on the Eve of SHA-3 Competition,” CryptArchi 2009, Jun 25-27,
2009,
Prague,http://cryptography.gmu.edu/athena/presentations/CryptArchi_2009_rogawski.pdf
K. Järvinen, "Sharing resources between AES and the SHA-3 second round candidates
Fugue and Grøstl,” the Second SHA-3 Candidate Conference, UCSB, CA, 2010,
http://csrc.nist.gov/groups/ST/hash/sha3/Round2/Aug2010/documents/papers/Jarvinen_paper_20100709.pdf
M. Rogawski and K. Gaj, “A High-Speed Unified Hardware Architecture for the AES
and SHA-3 Candidate Grøstl,” Proceedings of the 15th Euromicro Conference on Digital69[144][145]

System Design, Special Session on Architectures and Hardware for Security Applications(AHSA),
Cesme,
Izmir,
Turkey,September
5-8,
2012,
http://mason.gmu.edu/~mrogawsk/arch/dsd2012.pdf
G. Bertoni, J. Daemen, M. Peeters, G. V. Assche, “Duplexing the sponge: single-passauthenticated encryption and other applications,” the Second SHA-3 Candidate
Conference,
UCSB,
CA,
2010,
http://csrc.nist.gov/groups/ST/hash/sha3/Round2/Aug2010/documents/papers/DAEMEN_DuplexSponge.pdf
S. Lucks, D. McGrew, D. Whiting, “Batteries Included - Features and Modes for Next
Generation Hash Functions,” the Third SHA-3 Candidate Conference, Washington, DC,
March
22-23,
2012,
http://csrc.nist.gov/groups/ST/hash/sha3/Round3/March2012/documents/papers/LUCKS_paper.pdf

70Appendix A – eBASH Shootout Plots71

72
Figure A-1. eBash SHA-3 Finalist Performance for Long Messages

73
Figure A-2. eBash SHA-3 Finalist Performance for 4096 Byte Messages

74
Figure A-3. eBash SHA-3 Finalist Performance for 1536 Byte Messages

75
Figure A-4. eBash SHA-3 Finalist Performance for 576 Byte Messages

76
Figure A-5. eBash SHA-3 Finalist Performance for 64 Byte Messages

77
Figure A-6. eBash SHA-3 Finalist Performance for 8 Byte Messages