I heard encryption based purely on XOR and Rotation is inherently weak. The paper Rotational Cryptanalysis of ARX says:
It is also easy to prove that omitting addition or rotation is devastating, and such systems (XR and AX) can always be broken.
But I am not able to find any information on how to actually do it. Can anyone give a hint?
(Update:)
@CodesInChaos pointed out: "You can describe each output bit as the XOR of a fixed set of input/key bits. This results in a few hundred linear equations modulo $2$, which can be solved efficiently." For simple XR cipher, I understand how it works. But there are issues for me for more complex ones. Illustrated as follows:
Suppose a toy XOR/Rotation based cipher (cipher 1) which encrypts a 4 bit plaintext $P$ to a 4 bit ciphertext $C$ with a 4 bit key $K$. The encryption process is as follows (with example $p = 1001$, $k= 1000$, and $c = 1110$, all additions are modulo $2$ additions):
- $E_1$. Right rotate $P$ by 2 bits, producing $M$ ($1001 \rightarrow 0110$),
- $E_2$. XOR $M$ with $K$, producing $C$ ($0110 + 1000 = 1110$)
The corresponding decryption process:
- $D_1$. XOR $C$ with $K$, producing $M$ ($1110 + 1000 = 0110$)
- $D_2$. Left rotate $M$ by 2 bits, producing $P$ ($0110 \rightarrow 1001$)
Following @CodesInChaos 's advice, I can convert the decryption to the following linear equation system :
c1 + k1 = p3 1 + k1 = 1 k3 = 1
c0 + k0 = p2 ==> 0 + k0 = 0 ==> k2 = 0 (A)
c3 + k3 = p1 1 + k3 = 0 k1 = 0
c2 + k2 = p0 1 + k2 = 1 k0 = 0
So far so good. But what if the rotation bits in the above step $E_2$ is not a constant 2, but changes with the input plaintext? For example, let's modify the above cipher a little bit to this (cipher 2):
- $E_1$. Right rotate $P$ by $n$ bits, producing $M$. In which $n$ = the upper 2 bits of $P$ ($1001 \rightarrow 0110$),
- $E_2$. XOR $M$ with $K$, producing $C$ ($0110 + 1000 = 1110$)
I cannot convert this cipher to a simple linear equation system. Because there is no longer a fixed function for each output bit as of key & input bits.
So my questions is: Is cipher 2 still qualified as a "pure XR" system? Is there still a generic way to break it?