Salsa20

From Wikipedia, the free encyclopedia

Salsa20 is a stream cipher submitted to eSTREAM by Daniel Bernstein. It is built on a pseudorandom function based on 32-bit addition, bitwise addition (XOR) and rotation operations, which maps a 256-bit key, a 64-bit nonce, and a 64-bit stream position to a 512-bit output (a version with a 128-bit key also exists). This gives Salsa20 the unusual advantage that the user can efficiently seek to any position in the output stream. It offers speeds of around 8–14 cycles/byte in software on modern x86 processors, and reasonable hardware performance. It is not patented, and Bernstein has written several public domain implementations optimized for common architectures [1].

Internally, the cipher uses bitwise addition (exclusive OR), 32-bit addition mod 2³², and constant-distance rotation operations on an internal state of 16 32-bit words. This choice of operations avoids the possibility of timing attacks in software implementations.

Salsa20 performs 20 rounds of mixing on its input. However, reduced round variants Salsa20/8 and Salsa20/12 using 8 and 12 rounds respectively have also been introduced. These variants were introduced to complement the original Salsa20, not to replace it, and perform even better in the eSTREAM benchmarks than the already competitive Salsa20.

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 [2]. 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 [3], 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 [4].

In 2005, Paul Crowley reported an attack on Salsa20/5 with an estimated time complexity of 2¹⁶⁵, and won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis" ^[1]. 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 2¹⁷⁷, and a related-key attack on Salsa20/7 with estimated time complexity of 2^{217 [2]}.

As of 2008, Aumasson, Fischer, Khazaei, Meier, and Rechberger ^[3] reported a cryptanalytic attack against Salsa20/7 with a time complexity of 2¹⁵¹, and they reported the first attack against Salsa20/8 with an estimated time complexity of 2²⁵¹. 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. There are no published attacks on Salsa20/12 or Salsa20.

[edit] References

1. ^ Paul Crowley, Truncated differential cryptanalysis of five rounds of Salsa20
2. ^ Simon Fischer, Willi Meier, Côme Berbain, Jean-Francois Biasse, Matt Robshaw, Non-Randomness in eSTREAM Candidates Salsa20 and TSC-4, Indocrypt 2006
3. ^ Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger, New Features of Latin Dances

[edit] External links

• Salsa20 home page
• Specification (PDF)
• Salsa20/8 and Salsa20/12 (PDF)
• eStream page on Salsa20

v • d • e   Stream ciphers Algorithms:A5/1 | A5/2 | E0 | FISH | Grain | HC-256 | ISAAC | MUGI | Panama | Phelix | Pike | Py | QUAD  | Rabbit | RC4 | Salsa20 | Scream | SEAL | SOBER | SOBER-128 | SOSEMANUK | Trivium | VEST | WAKE Theory: Shift register | LFSR | NLFSR | Shrinking generator | T-function | IV Standardization: eSTREAM v • d • e   Cryptography History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers | Steganography