5
$\begingroup$

The core of the Salsa20 family of stream ciphers is a hash function that takes a 64-byte block, using it to generate a pseudorandom 64-byte output. The 64 bytes contain space for

  • a 32-byte key
  • a 16-byte constant
  • an 8-byte counter
  • an 8-byte nonce

These ciphers are intended to be used with 32 byte keys, but they can also be used with smaller keys. Using a 16 byte key involves changing the constant so there are no equivalent keys between the different sizes, and repeating the 16-byte key so it fits into 32 bytes (i.e. the input is $k \mathbin\| k$ for a 16-byte $k$ and just $k$ for a 32-byte $k$).

Why is this done? Why is the key not simply zero-padded? If cryptanalysis (but not exhaustive search) of the keystream can be made easier when a key without uniform distribution is used, the scheme is broken.

From section 4.1 of The Salsa20 family of stream ciphers:

The diagonal constants are the same for every block, every nonce, and every 32-byte key. As an extra (non-recommended) option, Salsa20 can use a 16-byte key, repeated to form a 32-byte key; in this case the diagonal constants change to 0x61707865, 0x3120646e, 0x79622d36, 0x6b206574.

$\endgroup$
  • 2
    $\begingroup$ Does the downvoter care to explain the issue with my question? Anonymous downvotes help no one. $\endgroup$ – forest Mar 26 '18 at 1:48
4
$\begingroup$

If we fix the second half of the key to all zeros we have at least 2 potential issues:

  1. The zero-bits offer no additional diffusion effect, whereas repeating the key increases the diffusion effect.

  2. Normally the adversary would know $1/2$ of the input and control $1/4$, but with $16$ more static known bytes, the adversary now knows $3/4$ of the input. This might give the adversary enough control to mount more attacks that may have not yet been analyzed; though likely only with a reduced round chacha.

Without doing the expensive analysis, I can only conjecture that the static zero bytes would only weaken chacha. I do not know by how much, but I do doubt it'll be enough to break the full 20-round chacha.

$\endgroup$
  • $\begingroup$ I suspected #1 at least, but considered that the cipher would have to be pretty broken if that were the case (if I recall, DJB conjectured that there are no classes of weak keys). $\endgroup$ – forest Mar 26 '18 at 4:52
  • $\begingroup$ With fewer rounds it may be relevant. At the full 20-rounds, shouldn't make any difference. So yes, it would have to be pretty broken. But why risk it when you've got the bits and it is really cheap? $\endgroup$ – cypherfox Mar 26 '18 at 4:55
  • $\begingroup$ Ah, so it's purely done because it can't hurt and because it might help slightly in a worst-case scenario? $\endgroup$ – forest Mar 26 '18 at 4:57
  • $\begingroup$ As far as I know and can tell, yes. $\endgroup$ – cypherfox Mar 26 '18 at 4:59
1
$\begingroup$

You say,

If cryptanalysis (but not exhaustive search) of the keystream can be made easier when a key without uniform distribution is used, the scheme is broken.

But this is outside the security conjecture of Salsa20:

If the Salsa20 key $k$ is uniform random…the random function $n \mapsto \operatorname{Salsa20}_k(n)$ from $\{0, 1, \dots, 255\}^{16}$ to $\{0, 1, \dots, 255\}^{64}$ is conjectured to be indistinguishable from uniform random.

In particular, related-key attacks are explicitly excluded from consideration:

The standard solutions to all the standard cryptographic problems—encryption, authentication, etc.—are protocols that do not allow related-key attacks on the underlying primitives. I see no evidence that we can save time by violating this condition. The reader might guess that Salsa20 is highly resistant to related-key attacks; but I simply don't care.

That said, the Salsa20 family technically supports 80-bit keys too—which are zero-padded up to 128 bits and then repeated as if with 128-bit keys, but with, again, a different constant. (I've never heard of anyone using this; 80-bit keys are ridiculous!)

Neither of these decisions—repeating vs. zero-padding the key—appears to be discussed in any of the design documents. It seems unlikely to me that the choice of one or the other makes much of a difference to security, but you'll have to talk to a real cryptanalyst, not a pseudonymous carrion bird who plays one on the internet.

$\endgroup$
  • $\begingroup$ The 80-bit keys are zero-padded only because it is not a multiple of 256-bit keys. I guess I should read up more to see if anyone has done any analysis on whether or not related key attacks are applicable to Salsa20/ChaCha, considering DJB "simply doesn't care" (that statement took me by surprise when I first read the paper). $\endgroup$ – forest Apr 5 '18 at 3:47
  • $\begingroup$ @forest Most cryptographers don't care about related-key attacks. Only exotic or badly designed protocols rely on resistance to them. $\endgroup$ – Squeamish Ossifrage Apr 5 '18 at 4:02
  • $\begingroup$ But clearly a partially attacker-controlled key was taken into account for the cipher's threat model, as σ exists specifically to reduce that risk. $\endgroup$ – forest Apr 5 '18 at 5:39

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.