How to break an arbitrary XOR and Rotation based encryption?

Question

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 this 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):

• E1. Right rotate p by 2 bits, producing m ( 1001 --> 0110),
• E2. XOR m with k, producing c (0110 + 1000 = 1110)

The corresponding decryption process:

• D1. XOR c with k, producing m (1110 + 1000 = 0110)
• D2. Left rotate m by 2 bits, producing p ( 0110 --> 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 E2 is not a constant 2, but changes with the input plain text? For example, let's modify the above cipher a little bit to this (cipher 2):

• E1. Right rotate p by n bits, producing m. In which n = the upper 2 bits of p( 1001 --> 0110),
• E2. 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?

Answer 1

XOR operations, fixed bit movements (as in taking the 2 topmost bits or concatenating bits etc.) and data dependent rotations form a functional complete set of operations. This means that you can realize any function between fixed length binary strings, including all possible blockciphers, using them.

To show that these operations form a functional complete set one can show that all operations of another functional complete set can be realized. For example the set {NOT, AND}:

• Realizing a NOT operation is easy, since this is only a XOR operation with a 1 constant.
• Realizing an AND operation requires the data dependent rotations. Given the inputs $a$ and $b$ construct the value $v = RotLeft_{a}(0b)$. The leftmost bit of $v$ is now the result of the AND operation of $a$ and $b$. This can be verified by looking at the possible input values: If $a$ is zero the rotation is does nothing and the leftmost bit stays zero. If $a$ is one the rotation will move the value of $b$ to the leftmost bit and the result is one exactly if $b$ is also one.

This would turn any algorithm that could break any cipher based on these oprations efficiently into an algorithm that breaks any arbitrary cipher efficiently, unlikely to exist and certainly not known.

Nevertheless I would not assume that most or even many of the ciphers constructed from these premitives are secure. For example if there are only few data dependent rotations and it is feasible to enumerate all possible rotation count combinations, the system can be broken by just trying to solve the resulting linear system for each combination.