Purpose of repeating a 16-byte key for Salsa20

Question

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.

Answer 1

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.

Answer 2

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.