Entries Tagged "SHA-3"

Page 1 of 2

Will Keccak = SHA-3?

Last year, NIST selected Keccak as the winner of the SHA-3 hash function competition. Yes, I would have rather my own Skein had won, but it was a good choice.

But last August, John Kelsey announced some changes to Keccak in a talk (slides 44-48 are relevant). Basically, the security levels were reduced and some internal changes to the algorithm were made, all in the name of software performance.

Normally, this wouldn’t be a big deal. But in light of the Snowden documents that reveal that the NSA has attempted to intentionally weaken cryptographic standards, this is a huge deal. There is too much mistrust in the air. NIST risks publishing an algorithm that no one will trust and no one (except those forced) will use.

At this point, they simply have to standardize on Keccak as submitted and as selected.

CDT has a great post about this.

Also this Slashdot thread.

EDITED TO ADD (10/5): It’s worth reading the response from the Keccak team on this issue.

I misspoke when I wrote that NIST made “internal changes” to the algorithm. That was sloppy of me. The Keccak permutation remains unchanged. What NIST proposed was reducing the hash function’s capacity in the name of performance. One of Keccak’s nice features is that it’s highly tunable.

I do not believe that the NIST changes were suggested by the NSA. Nor do I believe that the changes make the algorithm easier to break by the NSA. I believe NIST made the changes in good faith, and the result is a better security/performance trade-off. My problem with the changes isn’t cryptographic, it’s perceptual. There is so little trust in the NSA right now, and that mistrust is reflecting on NIST. I worry that the changed algorithm won’t be accepted by an understandably skeptical security community, and that no one will use SHA-3 as a result.

This is a lousy outcome. NIST has done a great job with cryptographic competitions: both a decade ago with AES and now with SHA-3. This is just another effect of the NSA’s actions draining the trust out of the Internet.

Posted on October 1, 2013 at 10:50 AM • View Comments

Keccak is SHA-3

NIST has just announced that Keccak has been selected as SHA-3.

It’s a fine choice. I’m glad that SHA-3 is nothing like the SHA-2 family; something completely different is good.

Congratulations to the Keccak team. Congratulations—and thank you—to NIST for running a very professional, interesting, and enjoyable competition. The process has increased our understanding about the cryptanalysis of hash functions by a lot.

I know I just said that NIST should choose “no award,” mostly because too many options makes for a bad standard. I never thought they would listen to me, and—indeed—only made that suggestion after I knew it was too late to stop the choice. Keccak is a fine hash function; I have absolutely no reservations about its security. (Or the security of any of the four SHA-2 function, for that matter.) I have to think more before I make specific recommendations for specific applications.

Again: great job, NIST. Let’s do a really fast stream cipher next.

Posted on October 2, 2012 at 4:50 PM • View Comments

SHA-3 to Be Announced

NIST is about to announce the new hash algorithm that will become SHA-3. This is the result of a six-year competition, and my own Skein is one of the five remaining finalists (out of an initial 64).

It’s probably too late for me to affect the final decision, but I am hoping for “no award.”

It’s not that the new hash functions aren’t any good, it’s that we don’t really need one. When we started this process back in 2006, it looked as if we would be needing a new hash function soon. The SHA family (which is really part of the MD4 and MD5 family), was under increasing pressure from new types of cryptanalysis. We didn’t know how long the various SHA-2 variants would remain secure. But it’s 2012, and SHA-512 is still looking good.

Even worse, none of the SHA-3 candidates is significantly better. Some are faster, but not orders of magnitude faster. Some are smaller in hardware, but not orders of magnitude smaller. When SHA-3 is announced, I’m going to recommend that, unless the improvements are critical to their application, people stick with the tried and true SHA-512. At least for a while.

I don’t think NIST is going to announce “no award”; I think it’s going to pick one. And of the five remaining, I don’t really have a favorite. Of course I want Skein to win, but that’s out of personal pride, not for some objective reason. And while I like some more than others, I think any would be okay.

Well, maybe there’s one reason NIST should choose Skein. Skein isn’t just a hash function, it’s the large-block cipher Threefish and a mechanism to turn it into a hash function. I think the world actually needs a large-block cipher, and if NIST chooses Skein, we’ll get one.

Posted on September 24, 2012 at 6:59 AM • View Comments

NIST Defines New Versions of SHA-512

NIST has just defined two new versions of SHA-512. They’re SHA-512/224 and SHA-512/256: 224- and 256-bit truncations of SHA-512 with a new IV. They’ve done this because SHA-512 is faster than SHA-256 on 64-bit CPUs, so these new SHA variants will be faster.

This is a good thing, and exactly what we did in the design of Skein. We defined different outputs for the same state size, because it makes sense to decouple the internal workings of the hash function from the output size.

Posted on February 18, 2011 at 6:22 AM • View Comments

NIST Announces SHA-3 Finalists (Skein is One of Them)

Yesterday, NIST announced the five hash functions to advance to the third (and final) round in the SHA-3 selection process: BLAKE, Grøstl, JH, Keccak, and Skein. Not really a surprise; my predictions—which I did not publish—listed ECHO instead of JH, but correctly identified the other four. (Most of the predictions I saw guessed BLAKE, Grøstl, Keccak, and Skein, but differed on the fifth.)

NIST will publish a report that explains its rationale for selecting the five it did.

Next is the Third SHA-3 Candidate Conference, which will probably be held in March 2012 in Washington, DC, in conjunction with FSE 2012. NIST will then pick a single algorithm to become SHA-3.

More information about Skein and the SHA-3 selection process, including lots of links, is here. Version 1.3 of the Skein paper, which discusses the new constant to defeat the Khovratovich-Nikolié-Rechberger attack, is here (description of the tweak here). And there’s this new analysis of Skein.

And if you ordered a Skein polo shirt in September, they’ve been shipped.

Posted on December 10, 2010 at 12:04 PM • View Comments

Wanted: Skein Hardware Help

As part of NIST’s SHA-3 selection process, people have been implementing the candidate hash functions on a variety of hardware and software platforms. Our team has implemented Skein in Intel’s 32 nm ASIC process, and got some impressive performance results (presentation and paper). Several other groups have implemented Skein in FPGA and ASIC, and have seen significantly poorer performance. We need help understanding why.

For example, a group led by Brian Baldwin at the Claude Shannon Institute for Discrete Mathematics, Coding and Cryptography implemented all the second-round candidates in FPGA (presentation and paper). Skein performance was terrible, but when they checked their code, they found an error. Their corrected performance comparison (presentation and paper) has Skein performing much better and in the top ten.

We suspect that the adders in all the designs may not be properly optimized, although there may be other performance issues. If we can at least identify (or possibly even fix) the slowdowns in the design, it would be very helpful, both for our understanding and for Skein’s hardware profile. Even if we find that the designs are properly optimized, that would also be good to know.

A group at George Mason University led by Kris Gaj implemented all the second-round candidates in FPGA (presentation, paper, and much longer paper). Skein had the worst performance of any of the implementations. We’re looking for someone who can help us understand the design, and determine if it can be improved.

Another group, led by Stefan Tillich at University of Bristol, implemented all the candidates in 180 nm custom ASIC (presentation and paper). Here, Skein is one of the worst performers. We’re looking for someone who can help us understand what this group did.

Three other groups—one led by Patrick Schaumont of Virginia Tech (presentation and paper), another led by Shin’ichiro Matsuo at National Institute of Information and Communications Technology in Japan (presentation and paper), and a third led by Luca Henzen at ETH Zurich (paper with appendix, and conference version)—implemented the SHA-3 candidates. Again, we need help understanding how their Skein performance numbers are so different from ours.

We’re looking for people with FPGA and ASIC skills to work with the Skein team. We don’t have money to pay anyone; co-authorship on a paper (and a Skein polo shirt) is our primary reward. Please send me e-mail if you’re interested.

Posted on September 1, 2010 at 1:17 PM • View Comments

More Skein News

Skein is my new hash function. Well, “my” is an overstatement; I’m one of the eight designers. It was submitted to NIST for their SHA-3 competition, and one of the 14 algorithms selected to advance to the second round. Here’s the Skein paper; source code is here. The Skein website is here.

Last week was the Second SHA-3 Candidate Conference. Lots of people presented papers on the candidates: cryptanalysis papers, implementation papers, performance comparisons, etc. There were two cryptanalysis papers on Skein. The first was by Kerry McKay and Poorvi L. Vora (presentation and paper). They tried to extend linear cryptanalysis to groups of bits to attack Threefish (the block cipher inside Skein). It was a nice analysis, but it didn’t get very far at all.

The second was a fantastic piece of cryptanalysis by Dmitry Khovratovich, Ivica Nikolié, and Christian Rechberger. They used a rotational rebound attack (presentation and paper) to mount a “known-key distinguisher attack” on 57 out of 72 Threefish rounds faster than brute force. It’s a new type of attack—some go so far as to call it an “observation”—and the community is still trying to figure out what it means. It only works if the attacker can manipulate both the plaintexts and the keys in a structured way. Against 57-round Threefish, it requires 2503 work—barely better than brute force. And it only distinguishes reduced-round Threefish from a random permutation; it doesn’t actually recover any key bits.

Even with the attack, Threefish has a good security margin. Also, the attack doesn’t affect Skein. But changing one constant in the algorithm’s key schedule makes the attack impossible. NIST has said they’re allowing second-round tweaks, so we’re going to make the change. It won’t affect any performance numbers or obviate any other cryptanalytic results—but the best attack would be 33 out of 72 rounds.

Our update on Skein, which we presented at the conference, is here. All the other papers and presentations are here. (My 2008 essay on SHA-3 is here, and my 2009 update is here.) The second-round algorithms are: BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein. You can find details on all of them, as well as the current state of their cryptanalysis, here. NIST will select approximately five algorithms to go on to the third round by the end of the year.

In other news, we’re once again making Skein polo shirts available to the public. Those of you who attended either of the two SHA-3 conferences might have noticed the stylish black Skein polo shirts worn by the Skein team. Anyone who wants one is welcome to buy it, at cost. Details (with photos) are here. All orders must be received before October 1, and we’ll have all the shirts made in one batch.

Posted on September 1, 2010 at 6:01 AM • View Comments

New Attack on Threefish

At FSE 2010 this week, Dmitry Khovratovich and Ivica Nikolic presented a paper where they cryptanalyze ARX algorithms (algorithms that use only addition, rotation, and exclusive-OR operations): “Rotational Cryptanalysis of ARX.” In the paper, they demonstrate their attack against Threefish. Their attack breaks 39 (out of 72) rounds of Threefish-256 with a complexity of 2252.4, 42 (out of 72) rounds of Threefish-512 with a complexity of 2507, and 43.5 (out of 80) rounds of Threefish-1024 with a complexity of 21014.5. (Yes, that’s over 21000. Don’t laugh; it really is a valid attack, even though it—or any of these others—will never be practical.)

This is excellent work, and represents the best attacks against Threefish to date. (I suspect that the attacks can be extended a few more rounds with some clever cryptanalytic tricks, but no further.) The security of full Threefish isn’t at risk, of course; there’s still plenty of security margin.

We have always stood by the security of Threefish with any set of non-obviously-bad constants. Still, a trivial modification—changing a single constant in the key schedule—dramatically reduces the number of rounds through which this attack can penetrate. If NIST allows another round of tweaks to the SHA-3 candidate algorithms, we will almost certainly take the opportunity to improve Skein’s security; we’ll change this constant to a value that removes the rotational symmetries that this technique exploits. If they don’t, we’re still confident of the security of Threefish and Skein.

And we’re always pleased to see more cryptanalysis against Threefish and Skein.

Posted on February 7, 2010 at 8:06 AM • View Comments

1 2

Sidebar photo of Bruce Schneier by Joe MacInnis.