Why are bitwise rotations used in cryptography? 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.
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&lt;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&gt;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.