1
$\begingroup$

Is it possible to recompute the Salsa20 or ChaCha20 key in a realistic time if the keystream and the nonce are given to an attacker? Or is the keystream generation one-way, like a cryptographic hash function?

$\endgroup$
  • 4
    $\begingroup$ The nonce may be public knowledge. So is the key stream, as encrypting a stream of all zeros would already present an attacker with the key stream. Following that reasoning, the answer should be clear. $\endgroup$ – Maarten - reinstate Monica Apr 27 '15 at 9:41
  • 1
    $\begingroup$ A keystream generation algorithm which key, assumed unknown and uniformly random, can realistically be found from the output keystream and input other than key, is broken by definition of key per Kerckhoffs's principles, and/or of the security objectives of a keystream generator/CSPRNG. $\endgroup$ – fgrieu Apr 27 '15 at 10:09
  • $\begingroup$ @MaartenBodewes There is no way for us to know if that is the keystream. $\endgroup$ – Melab Jan 23 '18 at 21:32
  • $\begingroup$ @Melab What good ol' fashioned chosen plaintext attack? $\endgroup$ – Ella Rose Jan 23 '18 at 21:48
3
$\begingroup$

Yes, the Salsa20/ChaCha20 keystream generation is one-way, in the sense that no, it is not possible to recompute the Salsa20 or ChaCha20 key in a realistic time if the keystream and the nonce are given to an attacker, to the best of current knowledge.

We have no proof of that, but strong arguments:

  • Salsa20 (and ChaCha20) are considered unbroken keystream ciphers after a decade of exposure (in particular of the reduced-round version Salsa20/12 in eStream);
  • sound design principles, tried and tested for the last 40 years, are used.

In summary, Salsa20 is "a hash function in counter mode"; in more detail:

  • It is defined a $\operatorname{doubleround}$ function over the set of 16 words each 32-bit, that is a reversible and efficiently computable function, built from 32 times a sequence of addition, fixed rotation, and xor, applied to 32-bit words; $\operatorname{doubleround}$ is expected to be a mildly good random public fixed permutation, and iterating it $10$ times is expected to be more than enough (perhaps $20/8$ times enough since Salsa20/8 is unbroken) to make $\operatorname{doubleround}^{10}(x)$ an excellent random public fixed permutation, except for negligibly few oddities, including that $\operatorname{doubleround}^{10}(x)=0$.
  • It is defined $\operatorname{Salsa20}(x)=x+\operatorname{doubleround}^{10}(x)$ where $+$ is addition of 16 individual 32-bit words $\pmod{2^{32}}$. Combining back with the input is expected to make a one-way function, behaving like a random function except for negligibly few oddities, including that $\operatorname{Salsa20}(0)=0$, and $x\to\operatorname{Salsa20}(x)-x$ is a permutation for obvious definition of $-$.
  • It is defined a keystream generator (and from that built a stream cipher), as follows
    • $x$ is setup as a mixture of 256-bit key (or twice a 128-bit key), 128-bit rather arbitrary non-zero constants (dependent on key length), 128-bit nonce typically split into 64-bit nonce input and 64-bit counter setup to zero;
    • repeatedly, $\operatorname{Salsa20}(x)$ is computed, the output used as a 512-bit keystream chunk, and the counter part of $x$ incremented.

It is hoped that the non-zero constants avoids exploitation of any oddity $\operatorname{Salsa20}$ inherits from $\operatorname{doubleround}^{10}$, and security follows from that (including impossibility to get back at the key knowing all other input and output, which follows from the more general property that the output can't be distinguished from random).

Note: one notable operational drawback of Salsa20 (as in the eStream reference code) is the shortness of its $64$-bit nonce input, which can't be comfortably fed with a random number. Nonce reuse obviously breaks security, but does not compromise the key.

$\endgroup$
4
$\begingroup$

Nobody should be able to retrieve the key from the IV + key stream. If that would be possible then the stream cipher would be broken. Both the IV and key stream can be considered public knowledge (by performing a known plaintext attack, for instance using all zero's). Retrieving the key from information that may be known to an attacker constitutes the strongest attack possible, so any stream or block cipher should protect against that situation.

Or, as fgrieu already states without making it an answer:

A keystream generation algorithm which key, assumed unknown and uniformly random, can realistically be found from the output keystream and input other than key, is broken by definition of key per Kerckhoffs's principles, and/or of the security objectives of a keystream generator/CSPRNG.

$\endgroup$
1
$\begingroup$

The function $\text{Salsa20}(x)$ is equivalent to running $x$ through $x+\text{doubleround}(x)$ twenty times, where the plus sign means adding corresponding bytes in the two sequences modulo 256. $\text{doubleround}(x)$ is invertible. Adding $x$ to the result makes it non-invertible.

$\endgroup$
  • 2
    $\begingroup$ The last two sentences are correct, but do not answer the question. Based on definition of Salsa20, $Salsa20(x)$ is an un-keyed (conjectured-one-way) function used to build the Salsa20 cipher, hence this answer does not touch the question of if the key can be found. Also three errors crept in the first sentence; actually $Salsa20(x)=x+doubleround^{10}(x)$ where $+$ is addition skipping carry every $32$ bit, and we have $1$ such addition and $10$ chained $doubleround$, rather than a chaining of $20$ times (different) additions and $doubleround$ as stated. $\endgroup$ – fgrieu Apr 27 '15 at 21:28

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.