Several times, the American government has held open competitions to create new cryptographic standards. Important examples include the Data Encryption Standard (DES) selected in 1976 and the Advanced Encryption Standard (AES) chosen in 2001. As mentioned before, the hunt is now on for a new hash function. These are one-way forms of encryption that play a number of vital roles, such as making it possible to save only encrypted versions of passwords in password databases that might be compromised.
Bruce Schneier, who made an unsuccessful bid for his TwoFish cipher to be accepted as the AES, is now part of the team that has created the Skein Hash Function for the ongoing National Institute of Standards and Technology competition. The function is based around a successor to TwoFish called, unsurprisingly, Threefish. All entries must be submitted by tomorrow and will be publicly scrutinized over the next four years or so. The result should be a more secure successor to the SHA hash functions.
Will the winner of the competition get anything aside from fame?
The winner gets to give their algorith away:
“Should my submission be selected for SHA-3, I hereby agree not to place any restrictions on the use of the algorithm, intending it to be available on a worldwide, non-exclusive, royalty-free basis.”
No prize is mentioned, though the Federal Register Notice does say:
“NIST extends its appreciation to all submitters and those providing public comments during the SHA-3 development process.”
One error in the post above – the new standard will be called SHA-3, and will therefore be part of the SHA series, rather than a successor to them.
NIST must appreciate all submitters and make a separate website for all submitted hash algorithms to the public. It will be easy for anyone who can start evaluating on them.
There may be some improper submissions during the competition. NIST should consider and allow them in the competition.
More SHA-3 News
By Bruce Schneier
NIST has published all 51 first-round candidates. (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.
Skein News
By Bruce Schneier
Skein is one of the 14 SHA-3 candidates chosen by NIST to advance to the second round. As part of the process, NIST allowed the algorithm designers to implement small “tweaks” to their algorithms. We’ve tweaked the rotation constants of Skein. This change does not affect Skein’s performance in any way.
The revised Skein paper contains the new rotation constants, as well as information about how we chose them and why we changed them, the results of some new cryptanalysis, plus new IVs and test vectors. Revised source code is here.
The latest information on Skein is always here.
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 cryptanlysis 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.