Channels ▼
RSS

Design

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.

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

Figure 2: Keccak's internal functions.

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.

Figure 3: A simplified representation of a compression block in Skein.

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.


Related Reading






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video