6
$\begingroup$

I have been hearing about Salsa20 from quite some time. It is even the favorite cipher in the ransomware world. Some ransomware used this cipher, probably because of speed.

I want to know how secure this cipher is when compared to AES. How much has it has been reviewed by cryptanalysts?

|improve this question
$\endgroup$
  • $\begingroup$ Note that, while Salsa20 is quite secure, ChaCha20 (based on it) is even better. $\endgroup$ – forest Dec 26 '18 at 4:55
9
$\begingroup$

Pulling information from the wikipedia entry on Salsa20:

eSTREAM selection

Salsa20 has been selected as a Phase 3 design for Profile 1 (software) by the eSTREAM project, receiving the highest weighted voting score of any Profile 1 algorithm at the end of Phase 2.[6] Salsa20 had previously been selected as Phase 2 Focus design for Profile 1 (software) and as a Phase 2 design for Profile 2 (hardware) by the eSTREAM project,[7] but was not advanced to Phase 3 for Profile 2 because eSTREAM felt that it was probably not a good candidate for extremely resource constrained hardware environments.[8]

Cryptanalysis

As of 2015, there are no published attacks on Salsa20/12 or the full Salsa20/20; the best attack known[3] breaks 8 of the 12 or 20 rounds.

In 2005, Paul Crowley reported an attack on Salsa20/5 with an estimated time complexity of 2165, and won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis".[9] This attack, and all subsequent attacks are based on truncated differential cryptanalysis. In 2006, Fischer, Meier, Berbain, Biasse, and Robshaw reported an attack on Salsa20/6 with estimated time complexity of 2177, and a related-key attack on Salsa20/7 with estimated time complexity of 2217.[10]

In 2007, Tsunoo et al. announced a cryptanalysis of Salsa20 which breaks 8 out of 20 rounds to recover the 256-bit secret key in 2255 operations, using 211.37 keystream pairs.[11] However, this attack does not seem to be comparative with the brute force attack.

In 2008, Aumasson, Fischer, Khazaei, Meier, and Rechberger reported a cryptanalytic attack against Salsa20/7 with a time complexity of 2153, and they reported the first attack against Salsa20/8 with an estimated time complexity of 2251. This attack makes use of the new concept of probabilistic neutral key bits for probabilistic detection of a truncated differential. The attack can be adapted to break Salsa20/7 with a 128-bit key.[3]

In 2012 the attack by Aumasson et al. was improved by Shi et al. aainst Salsa20/7 (128-bit key) to a time complexity of 2109 and Salsa20/8 (256-bit key) to 2250.[12]

In 2013, Mouha and Preneel published a proof[13] that 15 rounds of Salsa20 was 128-bit secure against differential cryptanalysis. (Specifically, it has no differential characteristic with higher probability than 2−130, so differential cryptanalysis would be more difficult than 128-bit key exhaustion.)

Salsa20 is about as secure and analyzed as one could reasonably ask for. It is one of the few alternatives to AES that a knowledgeable cryptographer could comfortably suggest for usage in the real world.

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks. I checked that post. From the above mentioned excerpt: "In 2005, Paul Crowley reported an attack on Salsa20/5 with an estimated time complexity of 2^165", what does this mean? Are these attacks theoretical? How this time complexity is calculated? Is this time complexity based on a normal PC or any super computer used by government? :) $\endgroup$ – RPK Oct 8 '16 at 19:18
  • 3
    $\begingroup$ @RPK A time complexity of 2 ^ 165 means the attack would require 2 ^ 165 invocations of the algorithm. The actual amount of seconds this will require will vary depending on the machine(s) performing the task, which is why we use the quantity of algorithm invocations as the measurement of time. Performing more then 2 ^ 80 operations is considered infeasible with current technology, so 2 ^ 165 invocations is certainly impossible, so yes, the attacks are just theoretical. $\endgroup$ – Ella Rose Oct 8 '16 at 20:00
  • $\begingroup$ Addendum to my previous comment: 2^80 operations can not be said to be infeasible any more $\endgroup$ – Ella Rose Sep 4 '18 at 22:03
1
$\begingroup$

In addition to @ Ella Rose answer , in term of integral cryptanalysis , The Salsa20 has no longer integral distinguisher in 7 rounds (ref).

PS: salsa20 has been used in Petya ransomware.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Why is its use in ransomware relevant? $\endgroup$ – forest Dec 27 '18 at 4:54
  • 1
    $\begingroup$ This is a great question , it opened my mind, I did some search to answer your question, according to blog.cryptographyengineering.com/2012/10/09/… , the Salsa20/12 to be 2-3x as fast as a heavily optimized AES-CTR and my assumption is also related to timing resistant attacks. $\endgroup$ – hardyrama Dec 27 '18 at 7:27
  • $\begingroup$ Iam interested if you have a different perspective in this. $\endgroup$ – hardyrama Dec 27 '18 at 7:28
  • $\begingroup$ It's true, Salsa20/12 can be a lot faster than AES. However when hardware accelerated AES is available (AES-NI), then AES is faster. But not every CPU supports hardware acceleration. $\endgroup$ – forest Dec 27 '18 at 7:32

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.