Schneier on Security
A blog covering security and security technology.
« Alternate Scanning Technologies |
| New TSA Security Test »
December 10, 2010
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
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
If you do another round of those Skein polos, I would definitely go in for one.
Congratulations Skein Team!
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.
Did you get the hardware performance problem sorted out?
I remember Skein being slow on an FPGA.
The analysis of Skein (your final link) appears to have been created by a total knit wit.
You are the winners
BLAKE, Grøstl, JH, Keccak are poorly designed, bad documented.
"BLAKE, Grøstl, JH, Keccak are poorly designed, bad documented."
Actually, I like BLAKE, Grostl, and Keccak quite a lot.
"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.
"If you do another round of those Skein polos, I would definitely go in for one."
Perhaps in another year.
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. ;)
@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.
@Eli: Darn it all, you guys have me in stitches.
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.
@ 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.
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)
I hope weave seen the last of the puns, but I'm a frayed knot.
"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.
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.
Congrats to Bruce and the rest of the Skein team!
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.
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.
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.
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.
@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).
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.
Oops, didn't notice that last link in your post. Don't mind me!
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.
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.
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.