1
$\begingroup$

When you know the Salsa20's keystream, how do you know the next keystream?

In other words, can I infer the next keystream when I don't know the Key and IV of Salsa20, but the keystream is 0x100000?

If you have any related attack papers, please recommend it.

Or, I'd like to ask for some search keywords.

$\endgroup$
3
$\begingroup$

It is impossible for computationally bounded adversaries

What you are looking for is impossible in modern stream ciphers. If ever one finds to break a stream cipher in this way, you will see in the cryptographic news!

but the keystream is 0x100000?

First of all, the keystream is too small to extract the key and IV, even there is an attack. There is a lot of occurrence of this keystream on the period of the Salsa20's keystream but you cannot reach them in your lifetime.

The expected period of Salsa20 (Oversimplified!):

The Salsa20's core function maps a 256-bit key, a 64-bit nonce, and a 64-bit counter to a 512-bit block of the keystream. So we have 384-bit random input and 512-bit output. If we assume that the output of the Salsa20 is a pseudo-random sequence with an output size of $n=512$-bit the expected period length will be $\sum_{i=1}^n i/n = (n + 1)/2 \approx 2^{511}$ with the Harris' 1960 work. Salsa20, however, limited with the counter 64-bit. So can simply say that, a key with a nonce will not be periodic.

What is the expected occurrence on a pseudo-random sequence of size $2^{64}$? It is $2^{64}/2^{24} = 2^{40}$. So, for a single (key,nonce) pair, there is around $2^{40}$ occurrence of your string randomly sitting somewhere on the keystream. What is the following as the next bit? Nobody knows. For how many (key,nonce) pair you can store this to attack? And how you will be lucky that your target will be hot on your tiny list?

The next-bit test

This is more formal in the The next-bit test;

In cryptography and the theory of computation, the next-bit test is a test against pseudo-random number generators. We say that a sequence of bits passes the next bit test for at any position $i$ in the sequence, if any attacker who knows the $i$ first bits (but not the seed) cannot predict the $(i+1)$st with reasonable computational power.

If one computationally bounded entity can predict the next bit from the given bits, then this is a big problem for any stream cipher. There is no known such attack on Salsa20.

And, note that next-bit test is not sufficient, a non-Pseudo-Random-Sequence can pass the test.

Attacks on Salsa20

The best attack on the Salsa20

The other attacks;

  • in 2005, The paper Truncated differential cryptanalysis of five rounds of Salsa20 by Paul Crowley won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis"

  • in 2006, Fischer et al. in the paper Non-randomness in eSTREAM Candidates Salsa20 and TSC-4 demonstrated an attack on Salsa20/6 with estimated time complexity $\approx 2^{177}$. They also showed a related-key attack on Salsa20/7 with estimated time complexity $\approx 2^{217}$. The related key attacks are not important for the encryption, since the keys are selected randomly, it is important when uses in hash constructions.

  • in 2007, there is an attack on 8 rounds of Salsa20 in the paper Differential Cryptanalysis of Salsa20/8 by Tsunoo et al. This attack has no improvement over the brute force since they have $2^{255}$ complexity. In the same paper, they have also shown a related-key attack on the 7 rounds of the Salsa20 with $2^{117}$ complexity.

  • in 2012, Shi et al. improved the attack of Aumasson et al. on the paper Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha. Note that the improvement is on 128-bit keyed Salsa20/7 with $2^{109}$ complexity time and on 256-bit keyed Salsa20/8 with complexity $2^{250}$.

  • in 2013, Mouha and Preneel gave proof on differential cryptanalysis. Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20. They showed that 15 rounds of Salsa20 are 128-bit secure against differential cryptanalysis. Their work proved that Salsa20 has no differential characteristic with higher probability than $2^{130}$, as a result, the differential cryptanalysis would be more difficult than 128-bit key exhaustive key search.

  • in 2018, it is shown that the Salsa20 has no integral distinguisher after 6 rounds, Finding Integral Distinguishers with Ease by Eskandari et al.

  • in 2020, Improved Related-Cipher Attack on Salsa20 Stream Cipher by Lin Ding. They demonstrated an attack on the use of two different IVs on the same key for Salsa20/12 and Salsa20/8 They can recover the 256-bit secret key with time complexity of about $2^{193.58}$. This is an improvement on the existing attack by a factor of $2^{30.42}$ This seems the best-realated cipher attack.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your kind response! $\endgroup$ – Giyoon kim Oct 17 at 10:58

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.