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.


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.

| improve this answer | |
  • $\begingroup$ "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. $\endgroup$ – CodesInChaos Dec 19 '16 at 20:42
  • $\begingroup$ Also, the quote says that AR is sufficient, just less efficient than ARX. $\endgroup$ – CodesInChaos Dec 19 '16 at 20:43
  • $\begingroup$ @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. $\endgroup$ – Ella Rose Dec 19 '16 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.