6
$\begingroup$

Block ciphers mix key material into the permutation through XOR. Also do pre and post whitening this way.

Chacha/Salsa finishes by 32-bit modular adding key and iv material (among other bits but since reversing them is trivial that doesn't matter) into permutation output.

What is the rationale behind using 32-bit modular addition instead of XOR for that final step? MD hashes which have the exact same problem solve it with XOR and not modulus > 2 addition.

Improve this question
$\endgroup$
  • $\begingroup$ But XOR is addition modulo 2. $\endgroup$ – forest Nov 15 '18 at 22:07
  • $\begingroup$ @forest salsa20 uses 32-bit additions, inside of quarter round that will be as non-linear $\endgroup$ – kelalaka Nov 15 '18 at 22:08
  • $\begingroup$ @kelalaka Sure, I'm just nitpicking that XOR is addition, just modulo 2. $\endgroup$ – forest Nov 15 '18 at 22:10
  • $\begingroup$ @kelalaka Inside the round is fine, I want to know why it finishes with the same. $\endgroup$ – user63513 Nov 15 '18 at 22:11
  • $\begingroup$ a possible duplicate of Why is the whole initial state used in the final addition of Salsa20 and ChaCha? $\endgroup$ – kelalaka Nov 15 '18 at 22:16
0
$\begingroup$

MD hashes which have the exact same problem solve it with XOR and not modulus > 2 addition.

is correct in the Merkle-Damgård + Davies-Meyer theory, but practice differs: MD5, SHA-1, SHA-2 (which implement that theory) all use word-wise modular addition as the final step of the round function, rather than XOR.

My guess is that's because

  1. Modular addition has markedly more diffusion that XOR. Thus absent other reason to chose one or the other, addition is the default practitionner's choice (OTOH Occam's razor would pick XOR). For the same reason, in ARX ciphers, it is common to have slightly more ADD than XOR.
  2. Using addition rather than XOR costs next to nothing in software (it might even generate marginally faster/denser code than XOR in some architectures).
  3. MD5 paved the way.
Improve this answer
$\endgroup$
  • $\begingroup$ the link I posted yesterday, isn't an answer? $\endgroup$ – kelalaka Nov 16 '18 at 11:32
  • $\begingroup$ @kelalaka: I think that this link addresses why there is the final addition, but not why it is not used XOR instead, which is my reading of what the question asks. $\endgroup$ – fgrieu♦ Nov 16 '18 at 11:36
  • $\begingroup$ But he simply says that keep it in this way ( uniform implementation) so that high-speed implementation can benefit. SO you can remove, or use x-or, but this will cause non-uniform implementation. $\endgroup$ – kelalaka Nov 16 '18 at 11:38
1
$\begingroup$

Either operation works as long as one operand (or both) is unpredictable and the two operands are (practically) statistically independent. Normally XOR is used because it requires fewer transistors and less time than modular addition in hardware based implementations.

In software both operations run in one cycle for data that fits a register size. This gives addition an advantage over plain XOR operations. Differences in inputs to the steps of the permutation propagate faster with additions because carry bits influence the probability that an output bit may change.

ChaCha is primarily meant to be used in software implementations on machines with native support for 32-bit modular addition. Replacing the final additions with XORs is very unlikely to effect security, so the choice may be arbitrary.

Improve this answer
$\endgroup$
0
$\begingroup$

in addition to @Future Security answers.

$\boxplus$ is a nonlinear process as shown in the following equation: $x \boxplus y = ( x \oplus y)\, \boxplus \,2(x \wedge y) \quad (mod \, 2^n)$

I assume that the nonlinear part make it hard to reverse it in the final step.

for further read of cryptographic properties of $\boxplus$

Improve this answer
$\endgroup$

Your Answer

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