New paper on ARX cryptanalysis

At the Fast Software Encryption (FSE 2010) conference, Dmitry Khovratovich and Ivica Nikolic are presenting a paper on the cryptanalysis of ARX cryptosystems. ARX stands for Addition, Rotation, and Xor (eXclusive or). Combining these three operations is a general way to construct efficient cryptographic primitives, and we actually followed this way when designing Skein. The paper actually analyzes Threefish, the block cipher inside Skein.

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 44 (out of 80) rounds of Threefish-1024 with a complexity of 21014.5, though the attack on Threefish-1024 omits the key addition after round 44.

This is a great result and is the best attack that we've seen against Threefish. We expect that attacks more than a handful of rounds past this are not going to be possible.

Even more interestingly, a tiny modification of one of the internal constants of Threefish (C5) dramatically reduces the effectiveness of this attack.

We stand by the security of the full-round Threefish and Skein with any set of obviously non-bad constants. But if NIST allows another round of tweaks to the SHA-3 candidate algorithms, we will almost certainly take the opportunity to improve Threefish's security; we'll change this constant to a value that removes the rotational symmetries that the attack exploits.  If they don't, we're still confident of the security of Threefish and Skein.

We're pleased to see more cryptanalysis against Threefish and Skein.