# Rotational cryptanalysis

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Rotational_cryptanalysis
> Markdown URL: https://mediated.wiki/source/Rotational_cryptanalysis.md
> Source: https://en.wikipedia.org/wiki/Rotational_cryptanalysis
> Source revision: 1349277713
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In cryptography, **rotational cryptanalysis** is a generic [cryptanalytic attack](/source/Cryptanalytic_attack) against algorithms that rely on three operations: [modular addition](/source/Modular_arithmetic), [rotation](/source/Circular_shift) and [XOR](/source/Exclusive_or) — **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 attacks](/source/Timing_attack) in common implementations.

The basic idea of rotational cryptanalysis is that both the [bit rotation](/source/Bitwise_operation) and [XOR](/source/Exclusive_or) 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 cryptosystems cascaded ARX operations to a greater degree than might be expected.[1] This ability to "see" correlations through rounds of processing can then be exploited to break the cryptosystem in a way that is similar to [differential cryptanalysis](/source/Differential_cryptanalysis).

The term "rotational cryptanalysis" was coined by [Dmitry Khovratovich](/source/Dmitry_Khovratovich) and Ivica Nikolić in 2010 paper "Rotational Cryptanalysis of ARX", which presented the best cryptanalytic attacks at that time against a reduced-round [Threefish](/source/Threefish) cipher — part of the [Skein hash function](/source/Skein_hash_function), a [SHA-3 competition](/source/SHA-3_competition) candidate.[1][2] A follow-up attack from the same authors and Christian Rechberger breaks [collision resistance](/source/Collision_resistance) of up to 53 of 72 rounds in Skein-256, and 57 of 72 rounds in Skein-512.[3] It also affects the [Threefish](/source/Threefish) cipher up to 39 for 256-bit keys, 42 rounds for 512-bit keys, and 43 rounds for 1024 bit keys with complexities 2 252.4 {\displaystyle 2^{252.4}} , 2 507 {\displaystyle 2^{507}} , and 2 1014.4 {\displaystyle 2^{1014.4}} , respectively.[1]

## Method

Rotational cryptanalysis takes advantage of the fact that the XOR function preserves the rotations that are done to a piece of data with a probability of 1, and that while modular addition does not always preserve the rotation, the probability can be high enough (depending on the cryptosystem) that reduced-round versions, cryptosystems modified with modular addition removed, or extremely weak ARX cryptosystems that do not utilize enough additions can become easily vulnerable.

Let any letter be a given variable in binary, and let any operations and or data in parentheses "()" be a given statement regarding data that has been shifted an "r" amount.

*(x ⊕ {\displaystyle \oplus } y)=(x) ⊕ {\displaystyle \oplus } (y)*, and "*(x)r"* is trivially equal to *"(x shifted by r)"* (as x and r are the only things that determine the output).

Modular addition of 2 n {\displaystyle 2^{n}} is trickier as it can be non-linear in most cases. The probability-hood of a given string that was shifted surviving modular addition (that is, "(x+y) = (x)+(y)") equals:

( 1 / 4 ) ( 1 + 2 r − n + 2 − r + 2 − n ) {\displaystyle (1/4)(1+2^{r-n}+2^{-r}+2^{-n})} [1]

where "n" is the exponent in 2 n {\displaystyle 2^{n}} , and r is the rotation amount like before.

The probability of a piece of rotated binary surviving an ARX cryptosystem is ( p r ) q {\displaystyle (p{r})^{q}} , where "pr" is the probability-hood of surviving a singular modular addition given the above formula, and "q" is the amount of additions within the ARX scheme.[1] In order for the attack to be theoretically relevant, the probability of getting the key from the attack must be below the chance of discovering it randomly (that is, the average case complexity of 2 n {\displaystyle 2^{n}} of the rotational cryptanalytic attack must be below the 2 n {\displaystyle 2^{n}} of raw brute-force). The full versions of most ARX cryptosystems are not vulnerable, but their reduced rounds are as the probability of recovering the key is higher at the start of the mixing process (the rounds) than at the end.

It is also important to note that many ARX schemes have constant terms that need to be XOR'ed and added within the regular scheme. This is not an issue in cases where the constants that are used are rotated (as already mentioned, *(x ⊕ {\displaystyle \oplus } y)=(x) ⊕ {\displaystyle \oplus } (y),* with one of the variables potentially being the constant) but constants that are not rotated decrease the probability of the rotations surviving. The authors of the original attack paper attempt to cover for this by introducing "error correction" variables that were found by the [Monte-Carlo method](/source/Monte_Carlo_method) that aim to maximize the chance of the constants being nullified throughout the round process. The error correction constant has a chance of removing the constant obfuscation for a given round of a cryptosystem by XOR'ing the output of the function with the given error constant.

For example, in [Skein](/source/Skein_(hash_function)), the error constant has a probability of creating the below equivalence, reversing the hash [compression function](/source/One-way_compression_function) to the point before constants are involved:

S k e i n ( ( X ) ⊕ E ) = ( S k e i n ( X ) ) {\displaystyle Skein((X)\oplus {E})=(Skein(X))} [4] where "e" is the error constant and " ( S k e i n ( X ) ) {\displaystyle (Skein(X))} " is the output of the round function at the given time without the constant involved.

Error correction constants are unique to each cryptosystem, and presumably must be found by Monte-Carlo simulations. There is currently no publicly known formula to discover the error correction variable needed on the fly.

## Limitations

Apart from the reduced-round nature of rotational cryptanalysis and the [luck](/source/Luck) needed for a successful attack, a big mitigation against it is to add the amount of additions needed to fit the security level of the cipher. For an ARX cipher that requires 2 128 {\displaystyle 2^{128}} security, there must approximately at most 128 modular additions as per the previous ( p r ) q {\displaystyle (p{r})^{q}} equation, not including the other limitations.

The attack method for [Threefish](/source/Threefish) requires a [chosen-plaintext-attack](/source/Chosen-plaintext_attack) to occur, which comes with the limitations of such an attack.

Another limitation is that there is no guarantee that successful application of the error correction variables will undo constants within rounds. The original paper claims that the chance of constants being randomly nullified in a given round become lower as the [hamming weight](/source/Hamming_weight) becomes higher.[1] Raising hamming weights of constants in key rounds and compression rounds increases the security margin.

## References

1. ^ [***a***](#cite_ref-Khovratovich2010_1-0) [***b***](#cite_ref-Khovratovich2010_1-1) [***c***](#cite_ref-Khovratovich2010_1-2) [***d***](#cite_ref-Khovratovich2010_1-3) [***e***](#cite_ref-Khovratovich2010_1-4) [***f***](#cite_ref-Khovratovich2010_1-5) Khovratovich, Dmitry; Nikolic, Ivica (2010). ["Rotational Cryptanalysis of ARX"](https://scholar.archive.org/work/mq7kxdfdmvh53numspafm2of6a). In Hong, Seokhie; Iwata, Tetsu (eds.). *Fast Software Encryption, 17th International Workshop, FSE 2010, Seoul, Korea, February 7-10, 2010, Revised Selected Papers*. Lecture Notes in Computer Science. Vol. 6147. Springer. pp. 333–346. [doi](/source/Doi_(identifier)):[10.1007/978-3-642-13858-4_19](https://doi.org/10.1007%2F978-3-642-13858-4_19). [ISBN](/source/ISBN_(identifier)) [978-3-642-13857-7](https://en.wikipedia.org/wiki/Special:BookSources/978-3-642-13857-7).

1. **[^](#cite_ref-2)** [Bruce Schneier](/source/Bruce_Schneier) (2010-02-07). ["Schneier on Security: New Attack on Threefish"](http://www.schneier.com/blog/archives/2010/02/new_attack_on_t.html).

1. **[^](#cite_ref-rotational-rebound_3-0)** Dmitry Khovratovich; Ivica Nikolic; Christian Rechberger (2010-10-20). ["Rotational Rebound Attacks on Reduced Skein"](http://eprint.iacr.org/2010/538). *Cryptology ePrint Archive*.

1. **[^](#cite_ref-4)** ["Rotational Rebound Attacks on Reduced Skein"](https://eprint.iacr.org/2010/538.pdf) (PDF). *International Association for Cryptologic Research*: 6–7. [Archived](https://web.archive.org/web/20250820233459/https://eprint.iacr.org/2010/538.pdf) (PDF) from the original on 20 August 2025. Retrieved 20 August 2025.

v t e Block ciphers (security summary) Common algorithms AES Blowfish DES (internal mechanics, Triple DES) Serpent SM4 Twofish Less common algorithms ARIA Camellia CAST-128 GOST IDEA LEA RC5 RC6 SEED Skipjack TEA XTEA Other algorithms 3-Way Adiantum Akelarre Anubis Ascon BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi Kalyna KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Kuznyechik Ladder-DES LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Prince Q QARMA RC2 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES xmx XXTEA Zodiac Design Feistel network Key schedule Lai–Massey scheme Product cipher S-box P-box SPN Confusion and diffusion Round Avalanche effect Block size Key size Key whitening (Whitening transformation) Attack (cryptanalysis) Brute-force (EFF DES cracker) MITM Biclique attack 3-subset MITM attack Algebraic Cube attack Gröbner attack Linear (Piling-up lemma) Differential Impossible Truncated Higher-order Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Side-channel Timing Power-monitoring Electromagnetic Acoustic Differential-fault XSL Interpolation Partitioning Rubber-hose Black-bag Davies Rebound Weak key Tau Chi-square Time/memory/data tradeoff Standardization AES process CRYPTREC NESSIE NSA Suite B CNSA Utilization Initialization vector Mode of operation Padding v t e Cryptography General History of cryptography Outline of cryptography Classical cipher Cryptographic protocol Authentication protocol Cryptographic primitive Cryptanalysis Cryptocurrency Cryptosystem Cryptographic nonce Cryptovirology Hash function Cryptographic hash function Key derivation function Secure Hash Algorithms Digital signature Kleptography Key (cryptography) Key exchange Key generator Key schedule Key stretching Keygen Machines Ransomware Random number generation Cryptographically secure pseudorandom number generator (CSPRNG) Pseudorandom noise (PRN) Secure channel Insecure channel Subliminal channel Encryption Decryption End-to-end encryption Harvest now, decrypt later Information-theoretic security Plaintext Codetext Ciphertext Shared secret Trapdoor function Trusted timestamping Key-based routing Onion routing Garlic routing Kademlia Mix network Mathematics Cryptographic hash function Block cipher Stream cipher Symmetric-key algorithm Authenticated encryption Public-key cryptography Quantum key distribution Quantum cryptography Post-quantum cryptography Message authentication code Random numbers Steganography Category

This cryptography-related article is a stub. You can help Wikipedia by adding missing information.

- [v](https://en.wikipedia.org/wiki/Template:Crypto-stub)
- [t](/source/Template_talk%3ACrypto-stub)
- [e](https://en.wikipedia.org/wiki/Special:EditPage/Template:Crypto-stub)

---
Adapted from the Wikipedia article [Rotational cryptanalysis](https://en.wikipedia.org/wiki/Rotational_cryptanalysis) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Rotational_cryptanalysis?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.