In October 2012, the National Institute of Standards and Technology (NIST) chose the Keccak algorithm as the new SHA-3 standard. Keccak offers many benefits, such as performance and good resistance traits. In this article, I take a concise look at Keccak's workings. I examine its engine and see how it renders the message text into a hash. In addition, I compare Keccak against SHA-1 and SHA-2 using four standard tests.
Readers should have a working knowledge of C and Objective-C, and a very basic understanding of encryption.
Limitations of SHA-1 and SHA-2
A notable problem with SHA-1 and SHA-2 is that they both use the same engine, called Merkle-Damgard, to process message text. This meansthat a successful attack on SHA-1 becomes a potential threat on SHA-2.
Consider SHA-1 for instance. A brute force attack usually takes at least 280 rounds (a round is a single cycle of transformation of the interim hash value) to find a collision in a full-round SHA-1. But in February 2005, Xiaoyun Wang and colleagues used a differential path attack to break a full-round SHA-1, and it took only 269 cycles to succeed. That same attack was later corroborated by Martin Cochran in August 2008.
In 2012, Mark Stevens used a series of cloud servers to perform a differential path attack on SHA-1. His attack produced a near-collision after 258.5 cycles. He also estimated a modified attack can manage a full-collision after 261 cycles.
As to SHA-2, the only successful attacks were those against a limited round SHA-2 hash. The most effective attack was against a 46-round SHA-2 (512-bit variant) and against a 41-round SHA-2 (256-bit variant). It took 2253.6 cycles to break the 256-bit variant and 2511.5 cycles for the 512-bit variant.
The fact remains that, while no successful attacks against a full-round SHA-2 have been announced, there is no doubt that attack mechanisms are being developed in private. This is one reason why NIST sponsored the SHA-3 competition, which led to the development and recent adoption of Keccak.
The Road to SHA-3
To be considered for the SHA-3 standard, candidate hash functions had to meet four conditions set by NIST. If a candidate failed to meet these conditions, it was disqualified:
- The candidate hash function had to perform well regardless of implementation. It should expend minimal resources even when hashing large amounts of message text. Many proposed candidates were actually unable to meet this requirement.
- The candidate function had to be conservative about security. It should withstand known attacks, while maintaining a large safety factor. It should emit the same four hash sizes as SHA-2 (224-, 256-, 384-, or 512-bits wide), but be able to supply longer hash sizes if need be.
- The candidate function had to be subjected to cryptanalysis. Both source code and analytical results were made public for interested third-parties to review and comment. Any weaknesses found during analysis were to be addressed, through tweaks or through redesign.
- The candidate function had to exercise code diversity. It could not use the Merkle-Damgard engine to produce the message hash.
The SHA-3 competition saw 51 candidate functions enter the first round of evaluations. Out of those, 14 managed to advance to the second round. Round three saw the candidates whittled down to five. And from those five, Keccak was declared the winner.
The Keccak algorithm (pronounced "ket-chak") is the work of Guido Bertoni, Joan Daemen, Michael Peters, and Giles Van Assche. It was submitted as an SHA-3 candidate in October 2008.
Keccak uses an innovative "sponge engine" to hash the message text. It is fast, with a reported average speed of 12.5 cycles per byte on an Intel Core 2 processor. Its simple design lends well to hardware implementation.
Keccak can resists known attacks with a minimum complexity of 2
n is the hash size. It has a wide safety margin. To date, third-party cryptanalysis has shown no serious weaknesses in Keccak. Nevertheless, Keccak's creators have started the Crunchy Crypto Contest, challenging others to find and report successful and verifiable attacks on Keccak.
Digging into Keccak
At the time of writing, NIST has yet to publish the official document for SHA-3 (FIPS 180-5). Thus, the following information is gleaned from Keccak's reference document and from third-party sources.
There are three parts to the Keccak algorithm (Figure 1).
Figure 1: Basic blocks of the Keccak hash function.
Hash() serves as the entry function. It takes four input arguments: the hash size (
n) in bits, the message text (
M) and its size (
N) in bits, and a hash variable (
H). The hash variable must be created using the library function
malloc() as follows:
HashReturn E; char *H; n = 224; H = (char *)malloc(sizeof(char) * n / 8); //... E = Hash(n, M, N, H);
Init() function prepares the internal state (
S) for the given hash size. The
Update() function starts the compression or absorb phase. This is where the message text is combined with the internal state, then permutated. The
Final() function starts the extraction or squeeze phase. This is where bits from the internal state are extracted and assembled to form the hash value. The first
n bits of the assembled hash then serves as the message hash. All four functions return an error result. A zero result means a function completed its task without errors.