Paper 2009/526

Improved Related-Key Boomerang Attacks on Round-Reduced Threefish-512

Jiazhe Chen and Keting Jia

Abstract

Hash function Skein is one of the 14 NIST SHA-3 second round candidates. Threefish is a tweakable block cipher as the core of Skein, defined with a 256-, 512-, and 1024-bit block size. The 512-bit block size is the primary proposal of the authors. Skein had been updated after it entered the second round, the only differences between the original and the new version are the rotation constants. In this paper we construct related-key boomerang distinguishers on round-reduced Threefish-512 based on the new rotation constants using the method of \emph{modular differential}. With these distinguishers, we mount related-key boomerang key recovery attacks on Threefish-512 reduced to 32, 33 and 34 rounds. The attack on 32-round Threefish-512 has time complexity $2^{195}$ with memory of $2^{12}$ bytes. The attacks on Threefish-512 reduced to 33 and 34 rounds has time complexity of $2^{325.56}$ and $2^{483}$ encryptions respectively, and both with negligible memory. The best key recovery attack known before is proposed by Aumasson et al. Their attack, which bases on the old rotation constants, is also a related-key boomerang attack. For 32-round Threefish-512, their attack requires $2^{312}$ encryptions and $2^{71}$ bytes of memory.

Note: new results are added