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

Comments

Clive RobinsonSeptember 1, 2010 8:17 AM

@ Bruce,

"The second was a fantastic piece of cryptanalysis by Dmitry Khovratovich, Ivica Nikolié and Christian Rechberger... ... But changing one constant in the algorithm's key schedule makes the attack impossible."

Sounds like the process is working :)

Grande MochaSeptember 1, 2010 8:36 AM

@ Bruce

Do you have a feel for the likely third round candidates? I'd be curious just to know which algorithms you feel should 'very likely' make it to the next round or any that you think definitely shouldn't.

RichSeptember 1, 2010 9:15 AM

@Bruce:

Thank you sir for the link to the code. I greatly appreciate it. It is always nice to see a professional's work.

Bruce SchneierSeptember 1, 2010 11:36 AM

"Do you have a feel for the likely third round candidates?"

I have my top five. I haven't decided if I want to share them.

Bruce SchneierSeptember 1, 2010 11:44 AM

"Sounds like the process is working :)"

That's the idea.

There's a fine line between making minor changes to frustrate specific attacks, and constantly changing the algorithm in random ways to frustrate other cryptographers. I think NIST is doing well walking that line w.r.t. tweaks.

EdSeptember 1, 2010 1:25 PM

"I haven't decided if I want to share them."

How about posting a checksum of your predictions?

garrisonSeptember 1, 2010 1:32 PM

"I have my top five. I haven't decided if I want to share them."

You could just post your top three. That way you leave some ambiguity for the other two, and you don't risk insulting your colleagues.

Nick PSeptember 1, 2010 2:52 PM

@ Bruce

"I have my top five. I haven't decided if I want to share them."

That's kind of lame considering the open and adversarial nature of the competition. How bout you just post the hash of their names, then express sorrow when your readers brute force it? Make the hash SHA-512, just so the lay media will freak out about the "successful brute force attack".

JackSeptember 1, 2010 7:08 PM

Do you have an ETA as to when the new key schedule constant (along with associated updated test vectors, etc) will be announced? I was checking skein-hash.info last week hoping to see an update on this, and no specifics in your slides either...

Also, have you/the team given any consideration to if you'll spend any time designing/specifying a key schedule for Threefish that can use shorter keys than the block size? For some applications Threefish would be ideal (modulo the relatively short time for analysis thus far) but a 512 or 1024 bit key would be unwieldy; having a reasonable (and 'standard', ie interoperable) specification for using Threefish with a shorter key (say matching current AES sizes) would be useful. Is concatenating the input key enough times and then truncating to 512 bits OK? Or pad the input key with 0x8000...? Obviously many options, probably most of them OK, but having one specified/fixed scheme would allow for different implementations to behave the same way which is obviously a very useful property.

JurjenSeptember 2, 2010 1:53 AM

Just a thought:
The well known way to speed up carry computations for additions is "carry save addition", where you remember the carries instead of rippling them through.
These words are easy to rotate, and maybe there is a trick to combine this with XOR in some way. This might speed up things a bit.

PaeniteoSeptember 2, 2010 2:43 AM

@Jack: "designing/specifying a key schedule for Threefish that can use shorter keys than the block size?"

Just apply an appropriate instantiation of Skein to the key before you feed it into Threefish ;-)

More seriously, we do have PBKDF2 for such things, don't we?
There does not seem to be a need to specify a dedicated key derivation method for any particular algorithm.

JessSeptember 2, 2010 7:11 PM

NIST is great, isn't it? I can think of another project they should be running: the white spaces process over at the FCC. The only legitimate arguments on that project are technical, but since it's the FCC the politics will delay it until the need has passed.

RFSeptember 3, 2010 12:26 AM

Since nothing's been cracked wide open, performance matters a lot. Then simplicity. And you don't want the finalists to all be too similar, so I'd include RAX, AES-based, and others.

I don't even know the details on performance and cryptanalytic results. I'll say Skein, CubeHash, Grøstl, Shabal, and Keccak, just because I can. (BLAKE would be my sixth. CubeHash and Keccak are there mostly because I think the designs are pretty.)

ChrisSeptember 3, 2010 5:15 PM

@Jack: Note that Threefish's minimum block size (and key size) is 256 bits, not 512 bits.

JHDSeptember 4, 2010 3:11 AM

My wife, the librarian, informs me that the proper successor to twofish is redfish, not threefish. I agree, and second her disappointment.

RFSeptember 5, 2010 1:40 PM

@Jack: An ideal cipher should work OK with any key with enough entropy in it, whether you repeat a shorter value, pad, etc. Some ciphers like RC4 have bad key-schedule weaknesses that mean you should feed them unrelated, random-looking keys like hashes (or not use them). AES isn't like that but the key schedule is its weak point; better to feed it hashes too.

Threefish, and all the other keyed permutations in SHA-3 candidates, were designed and analyzed to avoid key schedule weaknesses, because those can quickly translate to breaks or pseudo-breaks of the hash. If there were powerful attacks on Threefish with partial knowledge about the key, weak keys, related keys, or whatever, Skein probably wouldn't become SHA-3. So you could argue that you *ought* to be able to extend a Threefish key to 512 bits (or 256) any old way you want.

Anyway, PBKDF2 not only hashes the input but also has the advantage of creating work for an attacker brute-forcing the password. Seems wise to use it or something in that spirit.

JackSeptember 7, 2010 8:58 AM

@Chris Yes, but the 64 bit variants Threefish-512 and Threefish-1024 are much faster on modern 64 bit processors in terms of cycles/byte so they would probably be preferable for most new applications.

AlbertSeptember 15, 2010 2:48 AM

I am cheering for Keccak. My biggest shock is that Rivest's didn't make it this far. My second biggest shock is how slow Skein seems to be running in hardware. I'm hoping to see hardware tweaks and optimizations across the board.

I am curious Bruce's top five choices as well.

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..