Why are bitwise rotations used in cryptography?

Question

Any understanding I have of cryptography stops right around the cipher level. As such, I'm just curious as to why bit shifts and moreover circular bit shift are so prevalent in cryptography.

Answer 1

A bit rotation of a $w$-bit word by $r$ bits to the right transforms a $w$-bit word $X=(x_{w-1},x_{w-2},\dots,x_1,x_0)$ into the $w$-bit word $\operatorname{ROTR}(X,r)=(x_{r+w-1\bmod w},x_{r+w-2\bmod w},\dots,x_{r+1\bmod w},x_{r\bmod w})$. Depending on context, $r$ is arbitrary in $\mathbb Z$, or constrained to some interval thereof, e.g. $0\le r<w$. Rotation to the left can be defined as $\operatorname{ROTL}(X,r)=\operatorname{ROTR}(X,(-r\bmod w))$.

For any fixed $r$, $X\mapsto \operatorname{ROTR}(X,r)$ is a bit permutation. Under function composition, bit permutations of $w$-bit words form a finite group of $w!$ elements, of which bit rotations of $w$-bit words for fixed values of $r$ form a commutative subgroup of $w$ elements, isomorphic to $(\mathbb Z_w,+)$.

Bit permutations of $w$-bit words, including bit rotations by a fixed $r$, are not by themselves useful cryptographic transformations, because the above groups are so small subgroups of the group of bijections over $w$-bit words (which has $(2^w)!$ elements), or of the monoid of functions over $w$-bit words (which has $2^{w\cdot 2^w}$ elements).

However, bit rotations are useful in cryptography when combined with other common operations on $w$-bit words, such as other bitwise operations ($\operatorname{AND}$, $\operatorname{OR}$, $\operatorname{XOR}$, $\operatorname{NAND}$, $\operatorname{NOR}$..), and addition modulo $2^w$. That's for a number of reasons:

• Rotation combined with other operation(s) allows to build arbitrary transformations of $w$-bit words. For example, by combining (a sufficient number of) $\operatorname{ROTR}$ (with $r=1$), $\operatorname{NAND}$, and some fixed constants, any function over $w$-bit words can be constructed (thus including any bijection, thus any bit permutation). By contrast, when $w>1$, this can not be achieved using any combination of $\operatorname{AND}$, $\operatorname{OR}$, $\operatorname{XOR}$, $\operatorname{NAND}$, $\operatorname{NOR}$, and addition modulo $2^w$ (because none of these operations can make bit $x_1$ on input influence bit $x_0$ on output). Stated otherwise: rotation is one of few ways to achieve diffusion from high to lower-order bits (right-shift, division, and table lookup are others).
• More generally, rotation allows a cipher designer to create diffusion, at will, among bits of different rank in computer words, as emphasized in this other answer. Shifts allow that too, but when shifting by more than a few bits are too strongly surjective have too many distinct inputs reaching the same output for many cryptographic uses. Other techniques are used to create diffusion among different computer words.
• Availability, speed and low cost: on many CPUs, rotation is the only bit permutation available as a single native CPU instruction (discounting the possibility to implement a permutation by a table read for small $w$). All modern computer CPUs, and many modern embedded CPUs, have a dedicated barrel shifter that can rotate over its natively supported word size(s) $w$, for any $r$, as fast as any other data manipulation goes. Rotation for other width $w$ not supported in hardware can be efficiently constructed in software. In hardware, rotation by a fixed $r$ requires no gate at all (like any bit permutation) thus is extremely fast and cheap.
• No timing dependency: on all CPUs, rotation for fixed $r$ has duration independent of the data manipulated; this extends to variable $r$ when there is a barrel shifter. By contrast, table-lookup (another popular way to achieve diffusion to the right) often exhibit timing dependency, due to cache misses or memory alignment, which might allow timing attacks.

Many symmetric cryptographic primitives (hashes, block ciphers..) make heavy use of rotation by a fixed $r$, for the above reasons. Some (notably RC5) use variable rotation, though I have not seen this trend catching. I guess that could be (rightly) for fear of timing dependencies and other side-channels on CPUs without a barrel shifter supporting the rotation's width.

Answer 2

In Shannon's landmark paper Communication Theory of Secrecy Systems, published in 1949, he discussed two traits of secure ciphers: confusion and diffusion. Loosely speaking, confusion means that the relationship between the symmetric key and ciphertext should be complex.

Diffusion, on the other hand, focuses on the relationship between the plaintext and the ciphertext. Roughly, a cipher that exhibits good diffusion will produce completely different ciphertexts even with very similar plaintexts. For example, if you flip a single bit in a block encrypted with AES, it is completely garbled when decrypted. As a concept, you can think of diffusion as the "diffusing" of bits of the plaintext throughout the ciphertext.

Bitshifts and especially rotations are so widely used because they promote good diffusion. Many (most?) modern-day cryptographic constructs are built on the concept of rounds, where you take the plaintext and execute many rounds of some operations on it.

If those rounds include rotations, then bits of the plaintext are directly carried to other locations. Once they are in their new locations, other operations take place which further increase diffusion, such as modular addition. Other operations may add security, like XORing a piece of a derived key with a buffer. And then when the rounds continue, the rotations continue, and the bits from the plaintext end up "spread out" throughout the ciphertext.

For instance, MD5 is an example of a construction which uses rotation heavily (even going so far as to have per-round rotation amounts). If you change even a single bit in the input to MD5, the resultant hash is entirely different. That is diffusion in action. For example,

md5("test") = 098f6bcd4621d373cade4e832627b4f6
md5("Test") = 0cbc6611f5540bd0809a388dc95a615b

(ASCII uppercase and lowercase characters differ only by a single bit.)

If you would like to know more about addition, rotation, and XOR systems (ARX systems), I'd recommend the paper Rotational Cryptanalysis of ARX which also has some references on the subject. Sections one and two, especially with the context given in this post, should be relatively intelligible. Another link worth looking at is the avalanche effect, which is directly related to diffusion.