NIST publishes a Report on the SHA-3 Finalists Selection Process

Feb 17 2011

A few hours ago, but two months after the list of finalists announce, the NIST published a long-awaited report on the SHA-3 finalists selection process. The full 32-pages report is available here. In this post, I would like to emphasize and summarize the more salient facts.

The goal of NIST’s report consists in

[...] explaining the evaluation and selection process for the second round of the competition. A summary of the public analyses of each second-round candidate, and justifications for whether or not a candidate is advanced to the third (and final) round of the competition are provided [...].

The NIST mentions some of the information sources used to perform the selection:

For its security evaluations, NIST studied the large amount of feedback received from the cryptographic community via e-mail discussions in the official mailing list, and the SHA-3 Zoo web page, as well as the security arguments presented by the designers. NIST researchers also conducted their own internal cryptanalysis of the candidates.

For its software evaluations, NIST considered various benchmarking comparisons. The primary contributor was the ECRYPT Benchmarking of All Submitted Hashes (eBASH) project that provided speed measurements of the SHA-3 candidates on a wide variety of 32- and 64-bit platforms. Another software-benchmarking project – the eXternal Benchmarking eXtension (XBX) – provided performance results on small devices. [...]

NIST’s foremost selection criterion was security, which is not very surprising:

Security was NIST’s primary criterion in selecting the finalists. None of the second-round candidates was completely broken according to the criteria NIST laid out [...]. NIST received many security observations, including “partial attacks” on several candidates, i.e., cryptanalysis of weakened variants. Absent more conclusive information on the security of these candidates, a principal concern was the potential for extending these cryptanalyses. NIST tried to extrapolate the severity of any partial attacks, and thus to estimate the “security margin”, as an estimate of susceptibility of the full hash algorithms to future attacks.

An important caveat is that this extrapolation is only meaningful when the algorithm has received a significant amount of cryptanalysis, and when there is a good deal of granularity in choosing any tunable parameter that was provided for the algorithm. [...] Algorithms that received very little cryptanalysis, and algorithms without a clearly adjustable security parameter were, therefore, evaluated with more suspicion.

The second main criteria was, also unsurprisingly, performances, with a rather important focus on the software parallelism capabilities of the candidates:

Performance was also important in choosing the finalists. NIST chose finalists that could be implemented on as wide a variety of platforms as possible, while still maintaining reasonably good performance. [...]

Discussions included the implementation possibilities for the algorithms: 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 could be achieved by conventional superscalar arithmetic logic units (ALUs) capable of simultaneously launching several instructions per clock cycle.  NIST also noted that several algorithms exploited the power of 64-bit-wide ALUs. Candidates that performed poorly in hardware or on platforms without a specialized AES instruction, for example, were not selected, since many platforms do not provide this capability.

Another selection criterion was the way how the algorithms were tweaked by their designers during the competition:

Although NIST allowed the designers to tweak (i.e., make minor modifications to) their algorithms for the second round, extensive tweaks in order to avoid certain attacks were a cause for concern. 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, since these tweaks made much of the first-round cryptanalysis on the algorithms obsolete. However, NIST did consider whether the best attacks on some of the candidates seemed amenable to mitigation by a simple modification.

Provable security was also considered in a positive way, obviously but it is interesting to note that it was not part of the main selection criteria:

NIST also considered positive security arguments and proofs in making its decision. Since block cipher cryptanalysis appears to be more advanced than hash algorithm cryptanalysis, arguments that link the security of the candidates to a component that can be treated as a block cipher or fixed permutation were especially valuable.

Finally, all the exotic features brought by the candidate algorithms were not so important:

Additional design features, such as a built-in pseudorandom function (PRF) or an authenticated encryption mode were also briefly discussed, but played little part in the selection of the finalists.

Here is a copy-paste of the argumentation for the decisions of (non-)selection for each of the 14 semi-finalists:

  • BLAKE was selected as a finalist, due to its high security margin, good performance in software, and its simple and clear design.
  • Although BMW has very good software performance, and good potentials for pipelining and area-efficient high-throughput values, a disadvantage of the algorithm is its irregular and not-well-understood design. Since the compression function of BMW does not have a conventional iterated-round structure, there appears to be no obviously simple way to adjust the security margin, or to trade performance for security. Moreover, the attacks on the algorithm, even after an extensive tweak, did not provide confidence in the security of the algorithm. For these reasons, BMW was not selected as a finalist.
  • CubeHash is a simple, well-understood design that received extensive third-party analysis. The design is suitable for constrained environments, as it requires a small area in hardware, and little RAM or ROM in software. However, it has poor performance without the use of a vector unit, resulting in a large overhead for short messages. Moreover, no single variant for the 512-bit digest size achieves the required theoretical security with acceptable performance. Another disadvantage of the design is the existence of the symmetric properties that are arguably a potential avenue for future attacks. NIST felt that an additional year of study would not be enough to determine whether or not the symmetric properties pose a threat. Therefore, NIST felt that CubeHash could not be chosen as SHA-3 with confidence, and thus should not be selected as a finalist.
  • Although ECHO appears to be a simple secure design, it was not selected as a finalist, due to its all-around poor performance.
  • Fugue is an innovative design and has decent, all-around performance. Its designers also proved that collisions are unlikely to be found using differential cryptanalysis techniques. Nonetheless, Fugue has received only a very small amount of cryptanalysis. The most important published result, Aumasson and Phan’s distinguisher on Fugue’s finalization function, raised some concern. NIST felt that it would not be possible to establish confidence in the hash algorithm after another year of cryptanalysis; therefore, it was not selected as a finalist.
  • Grøstl was selected as a finalist because of its well-understood design and solid performance, especially in hardware. While Grøstl’s security margin is not ideal, NIST views it in light of the extensive amount of cryptanalysis that has been published, both on Grøstl itself and the larger AES structure on which Grøstl is based. Due to the large amount of existing cryptanalysis, NIST feels that future results are less likely to dramatically narrow Grøstl’s security margin than that of the other candidates.
  • Hamsi was not selected as a finalist, mainly due to the second-preimage attacks and high ROM requirements.
  • JH was selected as a finalist because of its solid security margin, good all-around performance, and innovative design.
  • Keccak was selected as a finalist, mainly due to its high security margin, its high throughput and throughput-to-area ratio and the simplicity of its design.
  • Although Luffa is an above-average performer, especially in hardware, it has not received as much cryptanalysis as many of the other second-round candidates. The little cryptanalysis there has been on Luffa, however, raises significant questions about its security; the security margin of the compression function is quite small, and full distinguishers on the sub-permutations have also been discovered. In addition, there is no published security proof showing that even strong sub-permutations would lead to a strong hash function. Therefore, Luffa was not selected as a finalist.
  • Shabal uses a novel design for its mode of iteration and basic building blocks. It was not, however, selected as a finalist, mainly due to security concerns. Although the security of the full hash algorithm was not compromised, the discovery of non-randomness properties with low time complexities raised concerns among NIST’s cryptographers about the possibility of more powerful attacks in the future. While Shabal’s security proof was modified to take known attacks into account, it did not convince NIST’s cryptographers that Shabal would remain secure against future attacks.
  • SHAvite-3 was not selected as a finalist, due to the lack of security in the key schedule of the underlying block cipher, leading to a relatively low security margin for the 512-bit version of the hash function. In addition, SHAvite-3 has a relatively low throughput-to-area ratio.
  • SIMD was not selected as a finalist, due to its large area requirements and the existence of the symmetric states.
  • Skein was selected as a finalist, mainly due to its high security margin and speed in software.

Interestingly, reading this, one can speculate a bit on NIST’s internal discussions based on the length of the justification paragraph: while Blake, JH, Keccak and Skein, as well as ECHO, Hamsi, Shavite-3 and SIMD appear to have been easy candidates for selection and  non-selection, respectively, more justifications are provided for the seemingly borderline candidates BMW, CubeHash, Fugue, Luffa, Shabal and Grøstl, the latter looking like being the more discussed finalist. But this last paragraph is only pure personal speculation, of course !

If you enjoyed this post, please consider leaving a comment or subscribing to the RSS feed to have future articles delivered to your feed reader.

No responses yet

Leave a Reply

*