# Role of xor in ARX construction

In ARX construction like Salsa 20, why xor operation is required? That is why AR is not sufficient? Note that xor is a linear operation.

## 1 Answer

Xor is the "addition" operator for algebra with boolean operators, while AND is the "multiplication" operator for boolean operators. "Regular" addition and multiplication are the addition/multiplication operators for integers. So speaking of "linearity" in the sense of algebraic compatibility, XOR and integer addition are non-linear. I feel like this question/answer(s) sums it up pretty well.

As for why xor is required/why AR is not sufficient, technically, AR is equivalent to ARX, but less efficient. See the paper Rotational Cryptanalysis of ARX . There are some details to it:

We also show that the AR systems , that do not use XOR, are theoretically equivalent to ARX systems. However, we prove that they are less secure with the same number of operations, because of the linear mod 2**n approximation. It is also easy to prove that omitting addition or rotation is devastating, and such systems (XR and AX) can always be broken.

• "Xor is a linear operation with respect to AND" Are you sure? AND+ROT+XOR are certainly sufficient for constructing secure ARX-like ciphers as an example compare NORX with ChaCha. But since I'm not sure about how linearity is defined in this context, you might still be right. Dec 19 '16 at 20:42
• Also, the quote says that AR is sufficient, just less efficient than ARX. Dec 19 '16 at 20:43
• @CodesInChaos I meant linearity as in algebraic compatibility, if that makes any sense? I updated my answer to hopefully clarify what I meant. NORX uses a half-adder like function if I recall correctly, which would imply that while it is implemented in XOR+ROT+AND, it is still basically performing integer addition. Dec 19 '16 at 22:17