In cryptography, rotational cryptanalysis is a generic cryptanalytic attack against algorithms that rely on three operations: modular addition,

rotation Rotation or rotational/rotary motion is the circular movement of an object around a central line, known as an ''axis of rotation''. A plane figure can rotate in either a clockwise or counterclockwise sense around a perpendicular axis intersect ...

and

XOR Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (one ...

— ARX for short. Algorithms relying on these operations are popular because they are relatively cheap in both hardware and software and run in constant time, making them safe from

timing attack In cryptography, a timing attack is a side-channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, an ...

s in common implementations. The basic idea of rotational cryptanalysis is that both the bit rotation and XOR operations preserve correlations between bit-rotated pairs of inputs, and that addition of bit-rotated inputs also partially preserves bit rotation correlations. Rotational pairs of inputs can thus be used to "see through" the cipher's cascaded ARX operations to a greater degree than might be expected. This ability to "see" correlations through rounds of processing can then be exploited to break the cipher in a way that is similar to

differential cryptanalysis Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can a ...

. The term "rotational cryptanalysis" was coined by

Dmitry Khovratovich Dmitry Khovratovich is a Russian cryptographer, currently a Lead Cryptographer for the Dusk Network, researcher for the Ethereum Foundation, and member of the International Association for Cryptologic Research. Biography Khovratovich, together w ...

and Ivica Nikolić in 2010 paper "Rotational Cryptanalysis of ARX", which presented the best cryptanalytic attacks at that time against a reduced-round Threefish cipher — part of the Skein hash function, a

SHA-3 competition The NIST hash function competition was an open competition held by the US National Institute of Standards and Technology (NIST) to develop a new hash function called SHA-3 to complement the older SHA-1 and SHA-2. The competition was formally ann ...

candidate. A follow-up attack from the same authors and Christian Rechberger breaks

collision resistance In cryptography, collision resistance is a property of cryptographic hash functions: a hash function ''H'' is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs ''a'' and ''b'' where ''a'' ≠ ' ...

of up to 53 of 72 rounds in Skein-256, and 57 of 72 rounds in Skein-512. It also affects the Threefish cipher.

References

Cryptographic attacks {{crypto-stub