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 • 31 Comments

Comments

Nathan ChristiansenDecember 10, 2010 12:42 PM

I am just grateful CubeHash did not make it.

I was tired of seeing Dr. Bernstein's tirades against criticisms to the CubeHash submission on the hash list.

Volker HetzerDecember 10, 2010 12:46 PM

Congratulations!
Did you get the hardware performance problem sorted out?
I remember Skein being slow on an FPGA.

George H. H. MitchellDecember 10, 2010 1:19 PM

The analysis of Skein (your final link) appears to have been created by a total knit wit.

SKEINDecember 10, 2010 2:57 PM

Congratulations!!!

You are the winners

BLAKE, Grøstl, JH, Keccak are poorly designed, bad documented.

Bruce SchneierDecember 10, 2010 3:07 PM

"BLAKE, Grøstl, JH, Keccak are poorly designed, bad documented."

Actually, I like BLAKE, Grostl, and Keccak quite a lot.

B

Bruce SchneierDecember 10, 2010 3:08 PM

"Did you get the hardware performance problem sorted out? I remember Skein being slow on an FPGA."

We think so. A lot of it was inefficient designs. Several of the researchers updated their results after the conference.

B

Bruce SchneierDecember 10, 2010 3:31 PM

"If you do another round of those Skein polos, I would definitely go in for one."

Perhaps in another year.

Brian MDecember 10, 2010 4:03 PM

Congratulations! I'm also glad you got the FPGA problem fixed.

I was wondering where my shirt was. Now I can act all smug and say I predicted the SHA-3 winner, and wear my bragging rights. ;)

EliDecember 10, 2010 4:43 PM

@George H. H. Mitchell: Agreed. I'm sure that one needled Bruce a bit. Knot that he'd have any trouble unravelling their work, mind you.

Larry HimesDecember 11, 2010 7:56 AM

Congratulations to the Skein Team. No matter who the ultimate winner is, I think that Bruce and company have made a significant contribution to the state of the art with Threefish, UBI, and the optional argument system. They've essentially provided a secure, extensible API for hash function usage within applications. This was something "above and beyond" the requirements of NIST, but was sorely needed in my view. Good work.

Clive RobinsonDecember 12, 2010 1:13 AM

@ Eli, al,

Will you guys stop spinning a yarn

It's not as though it's going without a hitch

Also it goes against the bight

And yes there are many many more jokes in a similar thread, that could be whipped up to the bitter end.

IlyaDecember 12, 2010 9:51 PM

Bruce, you should have named your hash more like Skæïn or something.

Judging by the AES exercise, NIST favors hard-pronounced names. Thus Grøstl is more likely to be chosen as SHA-3. Especially after these recent DJB/Lange attacks on Skein (http://eprint.iacr.org/2010/623)

James NobisDecember 14, 2010 8:21 AM

"I was tired of seeing Dr. Bernstein's tirades"

Sadly, I think you are too optimistic in thinking they will end for sha-3. Though, the mailing list has been quiet since the 9th.

Sam TrenholmeDecember 14, 2010 8:38 AM

My favorite two submissions are Keccak and Skein. I really like the flexibility of Skein; its underlying block cipher is the (to the extent of my knowledge) only secure block cipher with a built-in tweak parameter, and Skein is incredibly flexible (stream cipher, tree hash, block cipher, etc.).

That said, I prefer Keccak over Skein; Skein has a really bad performance hit on architectures without a 64-bit addition (yes, I know 32-bit desktop computers have 64-bit adds. I also know that 32-bit routers and cell phones often times don't have a 64-bit add), and the fact that Keccak only uses permutations and XOR allow its design to use fewer hardware gates than Skein.

The others I haven't looked at since I'm not really interested in a hash primitive that can't also be used as a stream cipher.

Grande MochaDecember 14, 2010 5:51 PM

I find it interesting that the only finalist with AES heritage is Grøstl. I was expecting ECHO or FUGUE to make it in as well just so there would be more than one AES-based design in the finals.

Grande MochaDecember 14, 2010 5:55 PM

@James Nobis

Although Dr. Bernstein is quite an interesting character, he has done some extremely valuable work. His leadership in the ebash project has really helped the competition, and his point of view (although perhaps not his tone) is often very relevant.

ArvindDecember 14, 2010 5:59 PM

Why not use all five in series?
Seems to me the hashs would still be quite varied, and cracking it to get info about the original content would be much harder.

James NobisDecember 14, 2010 9:57 PM

Grande Mocha,

I agree that he has much to contribute and offer. Unfortunately, seeing another email to the sha-3 list from him is like hearing fingernails on a chalkboard.

PaeniteoDecember 15, 2010 6:10 AM

@Arvind: "Why not use all five in series?"

Performance? Ease of implementation (software + hardware)?

It is much the same reasons why a Rijndael>Serpent>Twofish>RC6>Mars-cascade was not chosen as the AES (or Ninefold-DES, for that matter).

Nick PDecember 15, 2010 2:33 PM

@ Paeniteo

True. I'd like to add that just using two good algorithms can give extra security with an acceptable performance hit. For example, putting files in even a triple-encrypted truecrypt volume on a PC with a good processor is quite fast. Cryptophone, a more realistic example, uses both AES and Twofish to encrypt phone calls. I could also see multiple encryption, esp hardware accelerated, working for instant messaging, low res video streaming, link/IP encryptors, and even viewing web sites. The performance should be fine in all of these applications.

So, I encourage anyone concerned with the security of a block cipher to use multiple ciphers in these areas. Also, the VIA Eden line provides cheap hardware acceleration for AES, SHA-1, SHA2, RSA, and TRNG. Using VIA plus OpenBSD/ipsec = $300 per endpoint for ultra-fast VPN. Double encryption (probably using a bridging mode) is $600 per endpoint. Won't be standardized, but these products offer nice price, performance, and security gains.

MCDMay 20, 2011 6:23 PM

As cryptographers are stuck with XOR, ADD and fixed rotations and can't even use s-boxes these days, has anyone ever considered partly replacing mod 2^64 ADDs by mod 2^8 ADDs in cryptographic primitives to further increase algebraic complexity by having 3 different algebraic operations: ADD mod 2^64, ADD mod 2^8 and XOR (= ADD mod 2^1)?

For the MIX primitive in Threefish, I would suggest a small change in replacing the 2/4/8 parallel mod 2^64 ADDs of every odd round number to 8-times the number of parallel mod 2^8 ADDs and keeping the 2^64 ADDs of every even round number as they are.

This way, you get more algebraic complexity for a little less computational resources, because we have exchanged some longer ADDs to some shorter ADDs, which needs less carry ripple time|lookahead-gates|fixed-wired rom space|clock cycles|power depending on what kind of hard- or software you are implementing Threefish or Skein.

You don't even need to double the minimum cell instance size for extremely low gate count single-round implementations, as you can easily toggle an 64 bit adder into 8x 8 bit adders when using carry ripple adders(usual in such small designs) by just breaking the carry line every 8th propagation bit depending on the last bit of the round counter(needed in such implementations anyways).

Nevertheless, this modification would be a little slower on most RISC CPUs and µC that do not have 8 bit adders, in which case you would need to use a few instructions(2 ands, 1 or, 2 adds, 1 shift for every 8x8 bit adds instead of 1 64 bit add on a 64 bit CPU) to hack around it: old ALPHA before BWX, simple MIPS, ARM, SPARC and PowerPC all without any SIMD extensions and a few whacky integer DSPs. However, the test platform from NIST, the Intel Core Duo and the x86/x86-64 in general, the AVRs and small µCs, the ASIC and FPGA implementations are all not affected by this little performance drawback. The question is whether this is acceptable.

This seems like a great novel idea, but maybe to novel to be applied to a real-world cryptographic primitive without being thoroughly analyzed beforehand. And maybe to late to be applied to Threefish/Skein at this stage in the NIST SHA3 competition.

Just my offhanded thoughts by a cup of tea.

MCDMay 20, 2011 6:38 PM

PS: If someone really wants to apply this change to the MIX function of Threefish/Skein, one shouldn't forget to rerun the evolutionary program to find new good rotation constants.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..