9
$\begingroup$

Both Salsa20 and ChaCha basically work like this:

  1. Put the key, the nonce, the sequence number and a constant into a 4x4 matrix of 32-bit words.
  2. Transform the matrix invertibly with a number of ARX rounds.
  3. Add the initial matrix into the current state to produce the output block.

Now, as discussed e.g. in this currently featured question, the final addition is required to prevent simple backwards computation from revealing the key. However, my question is: why is the whole initial matrix added in, rather than only the key part?

It seems that the addition of the rest of the matrix is mostly wasted effort, since they are publicly known numbers that an attacker with a known plaintext can simply subtract again.

On the other hand, there is a clear downside of extra memory and computation required. The latter is probably negligible compared to the whole cipher, but the former could be important, especially for hardware implementations. If only the key was added, the nonce and the sequence number would not need to be accessed again, saving a sixth of the state required (if you ignore constants).

$\endgroup$
5
$\begingroup$

Note that, in Salsa20, the loads and additions of the key words ($x_1$, $x_2$, $x_3$, $x_4$, $x_{11}$, $x_{12}$, $x_{13}$, $x_{14}$) are critical for security, since the double-round function is trivially invertible. One might think that the remaining loads and additions could be skipped without sacrificing security, achieving almost half of the HSalsa20 savings. However, this change would interfere with the vector loads and vector additions used in many high-speed Salsa20 implementations.

from D. J. Bernstein - Extending the Salsa20 nonce

Since you need to supply the nonce/counter to pass them to the next block, you need to keep track of them anyways, eliminating the space savings.

$\endgroup$
  • 2
    $\begingroup$ Ok, that answers the question for Salsa20, but not ChaCha, which has the key words conveniently in successive words. The space savings would still exist for one-block messages, in hardware units meant to work in parallel, etc. $\endgroup$ – otus Jul 26 '15 at 10:52

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.