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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Dec 19, 2016 at 20:28
-
$\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$ Commented Dec 19, 2016 at 20:42
-
$\begingroup$ Also, the quote says that AR is sufficient, just less efficient than ARX. $\endgroup$ Commented Dec 19, 2016 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$ Commented Dec 19, 2016 at 22:17