Channels ▼
RSS

Design

Recent Contributions to Cryptographic Hash Functions


Design Rationale and Comparison

In this section, we summarize and compare the design rationale for both algorithms.

Skein Design Rationale

The Skein team had a number of goals:

  • Design for simplicity. Simple designs, rather than complex ones, are easier to optimize and analyze for security flaws.
  • Maximize security per clock. Performance trumps security in practice, so extract as much security as possible from each cycle. In particular, it is important to use only the simplest instructions that have been highly optimized on every platform. Exploit the super-scalar behavior of modern processors and maximize the diffusion from each operation. Through a series of experiments the Skein team discovered that simpler round functions with more rounds optimize both performance and security.
  • Achieve high performance and easy implementation on all processors. Building in a performance advantage for one processor family over another is a disadvantage in a public competition.

The Skein team made a number of critical design decisions when designing the algorithm:

  • Base the design on a block cipher. This is the most conservative security choice. The community knows better how to analyze designs based on block ciphers. Moreover, there is a well-established theory on how to turn a block cipher into a hash function.
  • Build your own block cipher. The Skein team obtained better performance and a simpler security analysis with a new cipher of the correct block size instead of adapting an existing narrow-block cipher.
  • Make the block cipher tweakable. This introduces great flexibility in designing a new mode at no cost.
  • Replace the cascade construction with something better. The cascade construction has many known defects; the tweak allows UBI to offer provable security, and it suffers from none of the cascade construction's problems.
  • Use Matyas-Meyer-Oseas construction instead of Davies-Meyer. Attacks against Matyas-Meyer-Oseas-based compression functions are chosen plaintext attacks; attacks against Davies-Meyer-based compression functions are related key attacks. The community has more experience defeating chosen plaintext attacks than related key attacks.
  • Do not use table lookups. Most cipher designs use a table called an S-box. Lookups in the S-box enable side-channel attacks on software implementations, where the encryption key can be read by monitoring thepower, timing, or EMI of the processor. Threefish is not subject to these attacks since it incorporates no table lookups.
  • Build in three different internal state sizes and allow output of any size. This allows flexibility in the level of security available across different use cases.
  • Change the design when necessary. The design should be changed when doing so allows for simpler security proofs.

Vortex Design Rationale

The Vortex team had a number of goals:

  • Design for performance. Vortex uses algorithms that are implemented by using dedicated instructions in future IA processors. These are instructions for AES round computation (AES-NI) and carry-less multiplication (GFMUL-NI). The Vortex team argues that such instructions will become a trend in the industry.
  • Maximize security per clock. Like Skein, Vortex extracts as much security as possible from each cycle. In particular, it uses independent AES round operations in each block. Such operations can potentially be completed in a single clock in future processors. It also introduces parallelism in the design of its compression function (two AES rounds and their key schedules can be executed in parallel); and finally, it maximizes the diffusion from each operation. Diffusion is supported by the AES round algorithms (S-box substitution, ShiftRows, MixColumns) as well as by the multiplication stage that follows.
  • Achieve high performance and easy implementation on future processors. The Vortex team believes that instructions for AES round computation and carry-less multiplication will become a trend in the industry. This is because (i) several hardware vendors including IBM and Sun are either implementing or researching them; (ii) even processors for embedded systems now include AES hardware; and (iii) there is a precedence in the industry that good instruction sets are widely adopted (for example, SSE instructions).

The Vortex team made a number of critical design decisions when designing the algorithm:

  • Base the design on a well-known and secure block cipher. Vortex uses an AES round as a building block. AES is a well-studied block cipher, and the AES round operation offers very good mixing across 32 bits, as a standalone operation, and 128 bits if repeated several times.
  • Strengthen the AES key schedule. Hashing is a one-way operation so additions with carries are permitted in the design of a hash function. Vortex strengthens the AES key schedule by adding round constants with carries and performing S-box substitution across all round key bytes.
  • Combine the outputs of two parallel AES transformations by using carry-less or integer multiplication. Multiplication is a highly non-linear operation and can be used for destroying bit differentials.
  • Replace the cascade construction with something better. Vortex uses the EMD construction and a tweak value to preserve the pseudo-random function and the pseudo-random oracle properties.
  • Use Matyas-Meyer-Oseas construction instead of Davies-Meyer. This is similar to the rationale of the Skein team. The community has more experience defeating chosen plaintext attacks than related key attacks.
  • Use Rijndael S-boxes instead of table lookups. Rijndael S-boxes have a special structure that allows them to be implemented by using combinatorial logic as opposed to table lookups. Thus, side-channel attacks can be averted.

Comparison of the Skein and Vortex Designs

It is now possible to highlight some similarities and differences between the Skein and Vortex designs. We begin with the similarities.

Similarities Between the Skein and Vortex Designs

Both designs are based on block ciphers, and they both use the Matyas-Meyer-Oseas construction to convert the related key attacks against the deployed hash function designs into chosen plaintext attacks. The cryptographic community has more experience defeating chosen plaintext attacks than related key attacks.

Both designs use a flavor of the cascade construction to paste together the hash of different blocks output by a compression function, and they both double hash the final output; that is, the output from the cascade construction is rehashed to become the final output. Both do this to address vulnerabilities that arise from processing the final block with a construction such as Davies-Meyer or Matyas-Meyer-Oseas, within the cascade construction.

Differences Between the Skein and Vortex Designs

The differing design approaches reflect the differing skill sets of the two teams. The Skein team members were skilled in designing block ciphers. In contrast, the Vortex team members did not design a new block cipher, but instead used an existing one. The Skein design allows its security claims to be derived from the security of a block cipher. The Vortex design effort emerged from the need to demonstrate a secure hash function by using the new AES round and carry-less multiplication instructions for future IA processors, which the Vortex team members designed.

Skein uses significantly more rounds (72/72/80) than Vortex, stemming from the different design decisions made by each team. The Skein team's experiments indicated diffusion per clock is maximized by numerous simple rounds. The Vortex designers instead were motivated by performance; they believed the best performance is achieved by using fewer rounds, based on very powerful diffusion primitives.

Skein's support for a hash value of any length from 1 to 264 bytes allowed the team to prove the property that Skein cannot be differentiated from a random oracle if Threefish acts like an ideal cipher. There are two ways to think about any algorithm: (1) as a monolithic black box, where you have no knowledge of any of the algorithm's internal parts, and (2) as presented in this article, where we know the details of the algorithm's internal structure. By saying that Skein cannot be differentiated from a random oracle, therefore, we mean that it is impossible, even in principle, for Skein to construct any statistical test that exploits differences in the two views. This means that Skein is structurally sound and that its security depends only on the security of Threefish. Vortex's final output is of a fixed length, but the second hash allows it to act like a fixed-length random oracle.

None of the Skein components use table lookups such as S-boxes, so it is more difficult to launch side-channel attacks on Skein than on specific implementations of Vortex. Vortex avoids these attacks by relying on a hardware logic implementation for the AES S-boxes.

Summary

In this article we reviewed the theory of hash functions, the state of knowledge about them, and some of Intel's contributions to this field of research. Hash functions are basic building blocks that are central to cryptography's mission, but recent attacks by Joux and Wang have undermined our confidence in classical constructions. Because of this insecurity, there has been a wave of new research into hash functions, and Intel has been at the forefront, with two independent and radically different submissions to the international NIST hash competition.

References

[1] A. Joux. "Iterated Collisions on Iterated Hash Functions." Crypto 2004, Lecture Notes in Computer Science (LNCS) 3621, Springer-Verlag, Berlin, 2005.

[2] X. Wang, Y. Yin, and H. Yu. "Finding Collisions in the full SHA-1." Crypto 2005, LNCS 2947, Springer-Verlag, Berlin, 2004

[3] A. Lenstra, X. Wang, and B. de Berger. "Colliding X.509 Certificates." At http://eprint.iacr.org

[4] A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.

[5] R. Merkle. "Secrecy, authentication, and public key systems." Stanford University Ph.D. thesis, 1979. Available as "Technical Report No. 1979-1," Information Systems Laboratory, Stanford University, Palo Alto, California, 1979.

[6] I. Damgård. "A Design Principle for Hash Functions." Crypto 1989, LNCS 435, Springer-Verlag, Berlin, 1989.

[7] R. Winternitz. "A secure one-way hash function built from DES." In Proceedings of IEEE Symposium on Security and Privacy, 1984.

[8] S. Matyas, C. Meyer, and J. Oseas. "Generating strong one-way functions with cryptographic algorithms." IBM Technical Bulletin, 27, 1985.

[9] J. Black, P. Rogaway, and T. Shrimpton. "Black box analysis of blockcipher-based hash functions from PGV." Crypto 2002, LNCS 2442, Springer-Verlag, Berlin, 2002.

[10] The National Institute of Standards and Technology. US Government agency sponsor for competition on next-generation hash design. At http://csrc.nist.gov

[11] M. Liskov, R. Rivest, and D. Wagner. "Tweakable Block Ciphers." Crypto, LNCS 2442, Springer-Verlag, Berlin, 2002.

[12] National Security Agency. Skipjack and KEA Specifications. May 29, 1998. At http://csrc.nist.gov

[13] M. Kounavis and S. Gueron. "Vortex: A new Family of One-Way Hash Functions Based on Rijndael Rounds and Carry-less Multiplication." At http://eprint.iacr.org

[14] S. Gueron. "Advanced Encryption Standard (AES) Instructions Set." At http://software.intel.com

[15] S. Gueron and M. Kounavis. "Carry-Less Multiplication and its Usage for Computing the GCM Mode." At http://software.intel.com


Jesse Walker is an Applied Cryptographer in Intel's Communication Technology Laboratory. He can be contacted at jesse.walker@intel.com. Michael E Kounavis is a Senior Research Scientist working with Intel Labs. His e-mail is michael.e.kounavis@intel.com. Shay Gueron is an Intel Principal Engineer. He can be reached at shay.gueron@intel.com. Gary Graunke is a Senior Staff Architect for cryptography at Intel. His e-mail is gary.graunke@intel.com. Copyright (c) 2009 Intel Corporation. All rights reserved.


This article and more on similar subjects may be found in the Intel Technology Journal, June 2009 Edition, Advances in Internet Security.


Related Reading


More Insights






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