Speaking of Security – The RSA Blog and Podcast

The National Institute of Standards and Technologies (NIST) announced on the 2^nd of October that the winner of the SHA-3 competition is KECCAK (pronounced ketchack). Interestingly, it was 12 years ago to the day that NIST announced the Advanced Encryption Standard (AES) algorithm. Also of note is that Joan Daemen is a member of both teams that designed the winning algorithms.

So why did NIST choose KECCAK and what does this mean for SHA-2? This article discusses what KECCAK brings to the table, and how and when SHA-3 will be used.

KECCAK

Guido Bertoni, Joan Daemen, Michael Peeters and Gilles Van Assche designed KECCAK. The algorithm appears to have been created specifically for the SHA-3 competition and is based on previous collaborations by the designers, but has a very different design philosophy from the previous work.

The heart of the algorithm is its sponge function, which has two phases: absorption and squeezing. The absorption phase repeatedly takes r bits of the input, XORs it with r bits of the state and applies a function to mix the state until all the input bits are used up. KECCAK uses a simple mixing function based on AND, NOT, XOR and rotate operations.

The squeezing phase produces the output by repeatedly returning r-bits of the state and mixing the state until all output bits are returned. This means that the choice of r and the total size of the state can be altered for different security strengths.

The designers have also considered using the sponge function in other cryptographic operations like Pseudo-Random Number Generation (PRNG) and Authenticated Encryption (AE). Using the sponge function in PRNG and AE offers opportunities for reducing application size, but at the cost of relying on the security of one algorithm construct. It will be interesting to see how the cryptographic community responds.

The designers claim that KECCAK has a thick safety margin. This claim comes from the ‘tweak’ made during the competition that was to increase the number of rounds. It appears that no attack was discovered during the competition that necessitates this change. Therefore the original number of rounds was secure and extra security is added for each extra round added.

The performance characteristics for KECCAK are quite controversial. Software implementations of KECCAK have no significant performance advantage over those of SHA-2. Practical results show that KECCAK is about the same speed as SHA-2 but on some CPUs is as much as twice as slow. KECCAK really shines however when implemented in hardware. While more on-chip area is used, performance can be as much as 8 times better on hardware than SHA-2.

The designers of KECCAK also considered its use for Message Authentication Code (MAC) generation. MD5, SHA-1, SHA-2 and other hash algorithms suffer from the length-extension weakness. The HMAC construct was created to overcome this problem but is not needed for SHA-3. This means that the MAC construct for SHA-3 is greatly simplified and potentially faster because the only change required is to append the key to the input data.

Usage of SHA-3

The new SHA-3 algorithm is announced not as a replacement for SHA-2 but to complement the existing algorithms. In fact, NIST expects SHA-2 to be used for the foreseeable future. So why have NIST chosen a SHA-3 algorithm at all?

When the process started about 5 years ago, significant attacks on the SHA-1 algorithm were being published. The SHA-2 algorithms use a very similar construct and NIST wanted to be sure there was an alternative algorithm available if the attacks could be extended or improved to work on SHA-2. In the process of choosing a SHA-3 algorithm, research into new attacks appears to have proven the security of SHA-2 algorithms rather than expose any problems. As a result, NIST changed the focus of the competition.

The SHA-3 competition became about finding a companion algorithm with different properties. As stated previously, implementations of SHA-3 are slower than SHA-2 in software, but much faster in hardware. Intel, AMD, Oracle and ARM have instructions that perform the SHA-2 algorithm. It seems the future will be to use fast SHA-3 implementations in hardware on general purpose CPUs.

Also, SHA-3 can be used for more efficient ‘MAC’ing, and the sponge function in a PRNG and AE. These schemes are not yet standardized but potentially mean that the components of SHA-3 be used for all symmetric cryptographic functions.

Finally, due to the significant differences in design, it is unlikely that new cryptoanalytic attacks will apply to both SHA-2 and SHA-3 algorithms.

Conclusion

SHA-3 is a useful addition to the cryptographic algorithm family. It is faster in hardware and has the potential to be extended to other cryptographic operations. Based on the history of AES, software implementations of SHA-3 will not be available to applications for some time and hardware for longer still. Also, cryptographic protocol standards need time to catch up.

Keep using SHA-2 for now and prepare for SHA-3 and its derivatives in the long term.

Author: Sean Parkinson, RSA Security, Brisbane AU

•