How are hash functions analyzed in an open competition?

Question

There was a well-known SHA-3 Competition held between 2007 and 2012, where the winner would be standardized as SHA-3. Now that the competition has ended and NIST has released reports on the different rounds. From the Round 3 report it looks like all five finalists are fairly competitive. It'd be interesting to understand why Keccak stands out in the competition and becomes the winner.

In the report, NIST mentioned several aspects of security analysis such as domain extenders, security margin, etc. However, NIST also admits that no finalist was considered to be a clear winner or loser from the security analysis in the same report. What kinds of cryptanalysis methods do we have at hand? Given the fact that no candidate algorithm is broken, how do we determine (or gain confidence) that one is better than another?

Answer 1

To assert the security of a Cryptogaphic primitive, one usually uses differential cryptanalysis (that is the first tool but not the sole one).

From the report you can read:

1. Security

Grøstl and JH have differential properties that extend through most or all of the rounds, while the remaining three candidates only have distinguishers that extend through about half of their rounds.

and also :

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.

The idea here is to have a kind of security feeling between the different kind of constructions. I was recently participating in the design of a new scheme, we were paying a really big attention to the constants we were choosing in order to avoid differentials (or even worse, iterative differentials)...

2. Speed and Hardware support

All the finalist have a the speed required, while the ARX designed scheme have the software advantage, using hardware instructions leads to even faster hashing. Thus Keccak being hardware friendly helped it to get the edge.

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. Scheme

Keccak also provide a new kind of scheme that is completely different to the usual Merkle–Damgård construction: the Sponge construction.

4. Conclusion

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 generic security 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.

TL;DR:

Lets say that you want to buy a new computer. You have $Computer_1$ and $Computer_2$ in front of you. Both have:

• the same price,
• the same CPU (speed),
• the same RAM size (security),

but $Computer_2$ also provides you as a plus PCIe card support (sponge construction). You know that at the moment you don't need that PCIe support... Which one do you chose ? I get the feeling that you would go for the second one because you don't know what the future is made of and you will want to upgrade if possible later and that might use PCIe.