Cryptographic Competition
New Skein Family Speeds Hash FunctionsBy Jon Callas, CTO, PGP Corporation
PGP Corporation is participating in creating a new family of cryptographic hash functions as part of a worldwide competition. Our goal is to ensure that information protection that relies on hash functions is both secure and fast. The competition sponsor is the National Institute of Standards and Technology (NIST), a U.S. federal government agency.
NIST held a similar competition about 10 years ago for a new encryption cipher, the Advanced Encryption Standard (AES). AES became the Federal Information Processing Standard (FIPS) 197 standard, and is still used widely in both the public and private sectors.
The current competition is for a new hash algorithm, to be called "SHA-3", to augment the hash algorithms currently in FIPS 180-2. We cryptographers know that the existing hash functions have flaws. In 2004 I wrote an article on their vulnerabilities which is still relevant.
October 31 was the deadline for all SHA-3 submissions to be in NIST's hands, and 64 submissions were made. PGP Corporation is one of the competitors, with a family of hash functions that we have named Skein (rhymes with rain).
Why Hash Functions Matter
Hash functions are a critical building block of cryptographic systems. A hash function takes an arbitrary chunk of data (text) and produces a fixed-length smaller chunk (the "hash"). Consider both the text and the hash to be strings of letters or numbers. Ideally, the hash will be unique; at least it should be unlikely that other text will produce the same hash. The uses for cryptographic hash functions include:
- Digital signatures
- Data authentication based on keyed hash message authentication code (HMAC)
- Key derivation functions
- Random number generators
Skein Twists and Turns
The Skein team of cryptographers includes Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jesse Walker, and me.
In designing Skein, we went for a radical back-to-basics strategy: we looked closely at what we cryptographers know how to do well. Another of our main strategies was external. This is a competition: we not only have to build a good hash function, we have to convince you that we've built a good hash function. Our construction must be secure, and easy for smart people—cryptographers and non-cryptographers alike—to decide that it is secure.
Going back to basics, our team knows how to build secure block ciphers and build them into secure hash functions. Also, there are many easy-to-understand block ciphers and ways of building them into secure hash functions. So we decided that we would construct our new hash functions out of a block cipher.
We also looked at some new work done on so-called "tweakable" cryptography. Usually, a cryptosystem comprises the data and the key. A tweakable system has an extra value, the tweak, which changes the basic system. For example, imagine that the key "ABC" will encrypt the data "XYZ" into "123". If you have a tweak of 0, it might give you "123"; but with a tweak of 1, you get "HYR". Every tweak securely changes the output. An example of a tweakable system application would be disk encryption, where the tweak could be the place on the disk the data resides.
We built a new block cipher we call Threefish. It comes in 256-bit, 512-bit, and 1024-bit sizes (for both block size and key size), and has a 128-bit tweak. We combined this with a tweakable hash construction we call UBI (Unique Block Iteration) that uses the tweakable cipher to make sure that the hash function handles every block uniquely. We also derived some exciting proofs of security, and did a great deal of cryptanalysis on the system.
A Matter of Time
The Skein hash function that our work has produced is very fast. Its code, the Threefish cipher, itself runs twice as fast as AES. (We've learned a lot in the last 10 years about ciphers.) UBI allows us to fold security measures into the tweak, and thus be a very fast hash function. In fact, we are proud to report that Skein operates two to three times faster than the current generation SHA-2 hash functions.
The NIST competition will go on awhile—it's equivalent to the Olympics for cryptographers. Public and NIST reviews of the candidate algorithms will take several years. The winning SHA-3 and new standard will be announced in 2012.
Key action
Get more information about Skein, including documents and sample code.
