Entries Tagged "Skein"

Page 2 of 2

More SHA-3 News

NIST has published all 51 first-round candidates in its hash algorithm competition. (Presumably the other submissions — we heard they received 64 — were rejected because they weren’t complete.) You can download the submission package from the NIST page. The SHA-3 Zoo is still the best source for up-to-date cryptanalysis information.

Various people have been trying to benchmark the performance of the candidates, but — of course — results depend on what metrics you choose.

And there’s news about Skein’s performance. And two Java implementations. (Does anyone want to do an implementation of Threefish?) In general, the Skein website is the place to go for up-to-date Skein information.

Posted on December 11, 2008 at 1:16 PMView Comments

Skein and SHA-3 News

There are two bugs in the Skein code. They are subtle and esoteric, but they’re there. We have revised both the reference and optimized code — and provided new test vectors — on the Skein website. A revision of the paper — Version 1.1 — has new IVs, new test vectors, and also fixes a few typos in the paper.

Errata: Version 1.1 of the paper, reference, and optimized code corrects an error in which the length of the configuration string was passed in as the size of the internal block (256 bits for Skein-256, 512 for Skein-512, and 1024 for Skein-1024), instead of a constant 256 bits for all three sizes. This error has no cryptographic significance, but affected the test vectors and the initialization values. The revised code also fixes a bug in the MAC mode key processing. This bug does not affect the NIST submission in any way.

NIST has received 64 submissions. (This article interviews one of the submitters, who is fifteen.) Of those, 28 are public and six have been broken. NIST is going through the submissions right now, making sure they are complete and proper. Their goal is to publish the accepted submissions by the end of the month, in advance of the Third Cryptographic Hash Workshop to be held in Belgium right after FSE in February. They expect to quickly make a first cut of algorithms — hopefully to about a dozen — and then give the community about a year of cryptanalysis before making a second cut in 2010.

Lastly, this is a really nice article on Skein.

These submissions make some accommodation to the Core 2 processor. They operate in “little-endian” mode (a quirk of the Intel-like processors that reads some bytes in reverse order). They also allow a large file to be broken into chunks to split the work across multiple processors.

However, virtually all of the contest submissions share the performance problem mentioned above. The logic they use won’t optimally fit within the constraints of a Intel Core 2 processor. Most will perform as bad or worse than the existing SHA-1 algorithm.

One exception to this is Skein, created by several well-known cryptographers and noted pundit Bruce Schneier. It was designed specifically to exploit all three of the Core 2 execution units and to run at a full 64-bits. This gives it roughly four to 10 times the logic density of competing submissions.

This is what I meant by the Matrix quote above. They didn’t bend the spoon; they bent the crypto algorithm. They moved the logic operations around in a way that wouldn’t weaken the crypto, but would strengthen its speed on the Intel Core 2.

In their paper (PDF), the authors of Skein express surprise that a custom silicon ASIC implementation is not any faster than the software implementation. They shouldn’t be surprised. Every time you can redefine a problem to run optimally in software, you will reach the same speeds you get with optimized ASIC hardware. The reason software has a reputation of being slow is because people don’t redefine the original problem.

That’s exactly what we were trying to do.

EDITED TO ADD (11/20): I wrote an essay for Wired.com on the process.

Posted on November 19, 2008 at 6:14 AMView Comments

The Skein Hash Function

NIST is holding a competition to replace the SHA family of hash functions, which have been increasingly under attack. (I wrote about an early NIST hash workshop here.)

Skein is our submission (myself and seven others: Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, and Jesse Walker). Here’s the paper:

Executive Summary

Skein is a new family of cryptographic hash functions. Its design combines speed, security, simplicity, and a great deal of flexibility in a modular package that is easy to analyze.

Skein is fast. Skein-512 — our primary proposal — hashes data at 6.1 clock cycles per byte on a 64-bit CPU. This means that on a 3.1 GHz x64 Core 2 Duo CPU, Skein hashes data at 500 MBytes/second per core — almost twice as fast as SHA-512 and three times faster than SHA-256. An optional hash-tree mode speeds up parallelizable implementations even more. Skein is fast for short messages, too; Skein-512 hashes short messages in about 1000 clock cycles.

Skein is secure. Its conservative design is based on the Threefish block cipher. Our current best attack on Threefish-512 is on 25 of 72 rounds, for a safety factor of 2.9. For comparison, at a similar stage in the standardization process, the AES encryption algorithm had an attack on 6 of 10 rounds, for a safety factor of only 1.7. Additionally, Skein has a number of provably secure properties, greatly increasing confidence in the algorithm.

Skein is simple. Using only three primitive operations, the Skein compression function can be easily understood and remembered. The rest of the algorithm is a straightforward iteration of this function.

Skein is flexible. Skein is defined for three different internal state sizes — 256 bits, 512 bits, and 1024 bits — and any output size. This allows Skein to be a drop-in replacement for the entire SHA family of hash functions. A completely optional and extendable argument system makes Skein an efficient tool to use for a very large number of functions: a PRNG, a stream cipher, a key derivation function, authentication without the overhead of HMAC, and a personalization capability. All these features can be implemented with very low overhead. Together with the Threefish large-block cipher at Skein core, this design provides a full set of symmetric cryptographic primitives suitable for most modern applications.

Skein is efficient on a variety of platforms, both hardware and software. Skein-512 can be implemented in about 200 bytes of state. Small devices, such as 8-bit smart cards, can implement Skein-256 using about 100 bytes of memory. Larger devices can implement the larger versions of Skein to achieve faster speeds.

Skein was designed by a team of highly experienced cryptographic experts from academia and industry, with expertise in cryptography, security analysis, software, chip design, and implementation of real-world cryptographic systems. This breadth of knowledge allowed them to create a balanced design that works well in all environments.

Here’s source code, text vectors, and the like for Skein. Watch the Skein website for any updates — new code, new results, new implementations, the proofs.

NIST’s deadline is Friday. It seems as if everyone — including many amateurs — is working on a hash function, and I predict that NIST will receive at least 80 submissions. (Compare this to the sixteen NIST submissions received for the AES competition in 1998.) I expect people to start posting their submissions over the weekend. (Ron Rivest already presented MD6 at Crypto in August.) Probably the best place to watch for new hash functions is here; I’ll try to keep a listing of the submissions myself.

The selection process will take around four years. I’ve previously called this sort of thing a cryptographic demolition derby — last one left standing wins — but that’s only half true. Certainly all the groups will spend the next couple of years trying to cryptanalyze each other, but in the end there will be a bunch of unbroken algorithms; NIST will select one based on performance and features.

NIST has stated that the goal of this process is not to choose the best standard but to choose a good standard. I think that’s smart of them; in this process, “best” is the enemy of “good.” My advice is this: immediately sort them based on performance and features. Ask the cryptographic community to focus its attention on the top dozen, rather than spread its attention across all 80 — although I also expect that most of the amateur submissions will be rejected by NIST for not being “complete and proper.” Otherwise, people will break the easy ones and the better ones will go unanalyzed.

EDITED TO ADD (10/30): Here is a single website for all information, including cryptanalysis, of all the SHA-3 submissions. A spoke to a reporter who told me that, as of yesterday, NIST had received 30 submissions. And three news articles about Skein.

Posted on October 29, 2008 at 6:35 AMView Comments

A New Secure Hash Standard

The U.S. National Institute of Standards and Technology is having a competition for a new cryptographic hash function.

This matters. The phrase “one-way hash function” might sound arcane and geeky, but hash functions are the workhorses of modern cryptography. They provide web security in SSL. They help with key management in e-mail and voice encryption: PGP, Skype, all the others. They help make it harder to guess passwords. They’re used in virtual private networks, help provide DNS security and ensure that your automatic software updates are legitimate. They provide all sorts of security functions in your operating system. Every time you do something with security on the internet, a hash function is involved somewhere.

Basically, a hash function is a fingerprint function. It takes a variable-length input — anywhere from a single byte to a file terabytes in length — and converts it to a fixed-length string: 20 bytes, for example.

One-way hash functions are supposed to have two properties. First, they’re one-way. This means that it is easy to take an input and compute the hash value, but it’s impossible to take a hash value and recreate the original input. By “impossible” I mean “can’t be done in any reasonable amount of time.”

Second, they’re collision-free. This means that even though there are an infinite number of inputs for every hash value, you’re never going to find two of them. Again, “never” is defined as above. The cryptographic reasoning behind these two properties is subtle, but any cryptographic text talks about them.

The hash function you’re most likely to use routinely is SHA-1. Invented by the National Security Agency, it’s been around since 1995. Recently, though, there have been some pretty impressive cryptanalytic attacks against the algorithm. The best attack is barely on the edge of feasibility, and not effective against all applications of SHA-1. But there’s an old saying inside the NSA: “Attacks always get better; they never get worse.” It’s past time to abandon SHA-1.

There are near-term alternatives — a related algorithm called SHA-256 is the most obvious — but they’re all based on the family of hash functions first developed in 1992. We’ve learned a lot more about the topic in the past 15 years, and can certainly do better.

Why the National Institute of Standards and Technology, or NIST, though? Because it has exactly the experience and reputation we want. We were in the same position with encryption functions in 1997. We needed to replace the Data Encryption Standard, but it wasn’t obvious what should replace it. NIST decided to orchestrate a worldwide competition for a new encryption algorithm. There were 15 submissions from 10 countries — I was part of the group that submitted Twofish — and after four years of analysis and cryptanalysis, NIST chose the algorithm Rijndael to become the Advanced Encryption Standard (.pdf), or AES.

The AES competition was the most fun I’ve ever had in cryptography. Think of it as a giant cryptographic demolition derby: A bunch of us put our best work into the ring, and then we beat on each other until there was only one standing. It was really more academic and structured than that, but the process stimulated a lot of research in block-cipher design and cryptanalysis. I personally learned an enormous amount about those topics from the AES competition, and we as a community benefited immeasurably.

NIST did a great job managing the AES process, so it’s the perfect choice to do the same thing with hash functions. And it’s doing just that (.pdf). Last year and the year before, NIST sponsored two workshops to discuss the requirements for a new hash function, and last month it announced a competition to choose a replacement for SHA-1. Submissions will be due in fall 2008, and a single standard is scheduled to be chosen by the end of 2011.

Yes, this is a reasonable schedule. Designing a secure hash function seems harder than designing a secure encryption algorithm, although we don’t know whether this is inherently true of the mathematics or simply a result of our imperfect knowledge. Producing a new secure hash standard is going to take a while. Luckily, we have an interim solution in SHA-256.

Now, if you’ll excuse me, the Twofish team needs to reconstitute and get to work on an Advanced Hash Standard submission.

This essay originally appeared on Wired.com.

EDITED TO ADD (2/8): Every time I write about one-way hash functions, I get responses from people claiming they can’t possibly be secure because an infinite number of texts hash to the same short (160-bit, in the case of SHA-1) hash value. Yes, of course an infinite number of texts hash to the same value; that’s the way the function works. But the odds of it happening naturally are less than the odds of all the air molecules bunching up in the corner of the room and suffocating you, and you can’t force it to happen either. Right now, several groups are trying to implement Xiaoyun Wang’s attack against SHA-1. I predict one of them will find two texts that hash to the same value this year — it will demonstrate that the hash function is broken and be really big news.

Posted on February 8, 2007 at 9:07 AMView Comments

Sidebar photo of Bruce Schneier by Joe MacInnis.