How to break an arbitrary XOR and Rotation based encryption? 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  ==&gt;  0 + k0 = 0  ==&gt;  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 &amp; 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?
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
operations 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 primitives 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.