Call for Papers

NIST has selected five SHA-3 candidate algorithms to advance to the third (and final) round:

• BLAKE
• Grøstl
• JH
• Keccak
• Skein

The selection was challenging, because we had a strong field of fourteen hash algorithms remaining in the SHA-3 competition that were very strong contenders for the hash function standard. Security was our greatest concern, and we took this very seriously, but none of these candidates was clearly broken.  However, it is meaningless to discuss the security of a hash function without relating security to performance, so in reality, NIST wanted highly secure algorithms that also performed well. We preferred to be conservative about security, and in some cases did not select algorithms with exceptional performance, largely because something about them made us “nervous,” even though we knew of no clear attack against the full algorithm.

Performance is multidimensional: no algorithm excelled in every dimension.  Every second-round candidate achieved at least tolerable performance on mainstream desktop or server systems, although the performance range was significant.  There were bigger differences on constrained platforms and in hardware, where area is as much a performance factor as speed.  A couple of algorithms were wounded or eliminated by very large area requirements – it seemed that the area they required precluded their use in too much of the potential application space.  Some algorithms allowed very high levels of fine-grain parallelism that could be realized well with hardware, some exploited parallelism with vector units, and some seemed to fully exploit the considerable parallelism that can be achieved by conventional superscalar arithmetic logic units (ALUs) that can simultaneously launch several instructions per clock cycle.  Several algorithms also exploited the power of 64-bit-wide ALUs.

No algorithm survived to become a finalist that did not have a clear round structure that could be readily adjusted to trade security for performance.  NIST eliminated several algorithms because of the extent of their second-round tweaks or because of a relative lack of reported cryptanalysis – either tended to create the suspicion that the design might not yet be fully tested and mature. NIST was generally comfortable with tweaks to the number of rounds or to constants, but more suspicious of changes that seemed to affect the structure of the compression functions.

Some teams announced the tweaks that they would make if they were selected for the final round.  NIST evaluated the second-round submissions, but not the proposed tweaks.  However, we did consider whether the best attacks on some of the candidates seemed amenable to mitigation by a simple modification.

NIST also considered diversity in the selection of the finalists. The selected five finalists incorporated a number of new design ideas that have arisen in the last few years, such as the HAIFA and sponge hash constructions.  The finalists include designs whose nonlinearity is based on the AES S-box, on a smaller (4- or 5-bit wide) S-box efficiently implemented as a sequence of basic logical instructions, and on the interaction between addition and XOR operations.

NIST thanks the submitters of all fourteen second-round candidates. Every second-round candidate was a very professional effort, and every candidate had strong features to recommend it.   We also thank the many individuals and organizations who helped with the cryptanalysis of the candidates, or who provided performance data from their own implementations of the candidate algorithms. This selection would not have been possible without their help.

NIST will publish a report on the selection of the SHA-3 finalists in the near future that explains the rationale for the selections on an algorithm-by-algorithm basis.

If tweaks are being considered for the final round, the submissions are due on January 16, 2011. Specific submission requirements will be provided to the designers of the five SHA-3 finalists.

Bill Burr

William E. Burr

Manager, Cryptographic Technology Group

NIST

Phone: 301-975-2914

Fax: 301-975-8670

All specialized implementations fit in less than one kilobyte of code, down to less than half a kilobyte on some platforms (e.g. 404 bytes for ARM-Thumb, 450 bytes on 32-bit x86). They nonetheless provide at least 60% of the speed achieved by optimized, unrolled C code on the same platforms. Moreover, these implementations all follow coding rules which make them immediately applicable to any application: the API is reentrant and thread-safe, it supports streaming operations, and the code is position-independent (it can be used in DLL). Each implementation simultaneously supports Shabal for all the 16 defined output sizes (all multiples of 32, from 32 to 512 bits), which includes the four standard SHA-3 output sizes (224, 256, 384 and 512 bits).

Download: Compact Implementations of Shabal (273)

Download: Optimized implementations for PowerPC platforms (205)

We also include two optimized assembly implementations for x86 processor with SSE2 instructions, in 32-bit and 64-bit mode. Shabal was not designed to take advantage of vector instruction sets such as SSE2. But a moderate usage of these instruction can nonetheless help speed up the implementation of Shabal. Achieved bandwidth is around 5.9 cpb in both 32-bit and 64-bit mode. SSE2 instructions are available on all Intel processors from the Pentium 4 onward, and are a standard part of the 64-bit ABI.

Download: Optimized implementations of Shabal (282)

Authors: Emmanuel Bresson, Anne Canteaut, Thomas Fuhr, Thomas Icart, María Naya-Plasencia, Pascal Paillier, Jean-René Reinhard, Marion Videau

Note: This work was partially supported by the French Agence Nationale de la Recherche through the SAPHIR2 project under Contract ANR-08-VERS-014.

Download:

Internall Distinguishers in Indifferentiable Hashing: The Shabal Case (448)

Authors: Julien Francq and Céline Thuillet

Note: This  work  was partially  supported  by  the French  Agence Nationale de la Recherche through the SAPHIR2 project under Contract ANR-08-VERS-014.

Download PDF: Unfolding Method for Shabal on Virtex-5 FPGAs: Concrete Results (362)

Download implementations (529Mo)

Download:

High-Speed Implementation of the SHA-3 Candidate Shabal (444)

• Internal Distinguishers in Indifferentiable Hashing:  The Shabal Case
• Unfolding Method for Shabal on Virtex-5 FPGAs: Concrete Results

The list of accepted papers is available at

http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/AcceptedPapersListing_SHA3_2010.pdf

This code was benched on an Intel x86 Core2 Q6600 system, clocked at 2.4 GHz and running Linux. The compiler is Intel C/C++ compiler version 11.1. Achieved speed (for long messages) is 631 MB/s (in 32-bit mode; 621 MB/s in 64-bit mode); this is the cumulative bandwidth of the four parallel instances (each instance is hashed with a bandwidth of about 158 MB/s). All of this is on a single CPU core.

See the mshabal.h header file for documentation on the API. The code itself should compile properly with GCC, the Intel C/C++ compiler, and Microsoft Visual C (this was tested with GCC 4.4.1 and Visual C 2005).

Download: SSE2-enhanced parallel implementations of the Shabal hash functions (354)

(c) 2010 SAPHIR project. This software is provided ‘as-is’, without any epxress or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software.

Permission is granted to anyone to use this software for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to no restriction.

Technical remarks and questions can be addressed to:
<thomas.pornin at cryptolog.com>