Finding the New Encryption Standard, SHA-3

Keccak divides the message data into 8-bit chunks. If a remainder exists, Keccak realigns that chunk to its least significant bits. Next, Keccak uses a sponge construct as its compression block. It takes 24 rounds of block operations to hash a given message. The block itself renders the hash states as a 5-by-5 array of 64-bit elements, a total of 1600 bits. Within the Keccak compression block is a sequence of five permutation routines (Figure2). The 5-by-5 array is represented by a [, its column and row indices by variables i and j. The bit positions of each array element are referred to by the variable k.

The first routine, theta, computes the column parity of a []. It then combines the parity bit with the adjacent columns. The second routine, rho, rotates each array element, the bitwise rotation following a triangular number sequence (t). It, however, excludes element a[0,0] from the rotation. The next routine, pi, permutes the 25 elements of a[] according to a fixed pattern. After that is the routine chi. This one adds the row elements bitwise, thus making the hash state non-linear. The final routine, iota, combines each array element with a round constant R. It breaks up any symmetry induced by the other four routines.

Like the other finalists, Keccak is simple and easy to analyze. Thanks to its sponge construct, Keccak can generate hashes of variable bit lengths. The same construct also allows Keccak to serve as a MAC routine or as a stream cipher. As for performance, Keccak is one of the faster candidates, clocking at an average of 12.5 cycles per byte on an Intel Core 2.

Skein was designed by a team that includes Niels Ferguson, Bruce Schneier, and others. It uses many of the same design concepts from the Threefish block cipher. Like Threefish, Skein processes its message data in chunks. The chunk size is chosen to match the internal hash state and the hash output. Also like Threefish, Skein does not use S-boxes to mix its hash state bits. Instead, it relies on modular additions and exclusive-ors to induce the needed non-linearity.


Figure 3 shows two rounds of an extremely simplified compression block in Skein. First, Skein injects an internal sub-key (S0) into the message chunks. It mixes the chunks in pairs and sends the mixed pair to a permutation routine (P). After that, Skein subjects the permuted chunks to a second round of mixes and permutations. Once it has performed the rounds, Skein injects a second sub-key (S1) into the chunks. The results of that last injection then form the hash output. It takes Skein 72 rounds of mixes and permutations to produce a 256- and 512-bit hash, 80 rounds for a 1024-bit hash.

Skein is a fast routine. It averages about 6.1 cycles per byte on an Intel Core 2 processor. Skein has a simple code structure, one that uses just three primitive operators to generate a hash. It is easy to optimize, easy to port to various system platforms. It can even work within the resource-frugal confines of an embedded system.

Most of all, Skein is able to withstand collision attacks. Its code structure has been analyzed thoroughly by both authors and third-party developers.

Next Week…

Next week, I'll present the final part of this discussion, showing the implementing of these algorithms in code and I'll test them with an eye to comparing them with the current OpenSSL implementation.

José R. C. Cruz is a freelance engineering writer living in North Vancouver, British Columbia. He frequently contributes articles to MacTech and REALStudio Developer. His most recent article for Dr. Dobb's was How to Secure and Authenticate Images Using Watermarks.

Click here to read Part II of this series.