World Library  
Flag as Inappropriate
Email this Article


Article Id: WHEBN0002701329
Reproduction Date:

Title: Salsa20  
Author: World Heritage Encyclopedia
Language: English
Subject: SOSEMANUK, LEVIATHAN (cipher), Stream cipher, WikiProject Cryptography, DNSCurve
Collection: Internet Standards, Stream Ciphers
Publisher: World Heritage Encyclopedia


The Salsa quarter-round function. Four parallel copies make a round.
Designers Daniel J. Bernstein
Related to Rumba20, ChaCha
Certification eSTREAM portfolio
Cipher detail
Key sizes 256 bits
State size 512 bits
Rounds 20
Speed 3.91 cpb on an Intel Core 2 Duo[1]
Best public cryptanalysis
2008 cryptanalysis breaks 8 out of 20 rounds to recover the 256-bit secret key in 2251 operations, using 231 keystream pairs.[2]

Salsa20 is a stream cipher submitted to eSTREAM by Daniel J. Bernstein. It is built on a pseudorandom function based on add-rotate-xor (ARX) operations — 32-bit addition, bitwise addition (XOR) and rotation operations. Salsa20 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 in constant time. It offers speeds of around 4–14 cycles per byte in software on modern x86 processors,[3] and reasonable hardware performance. It is not patented, and Bernstein has written several public domain implementations optimized for common architectures.[4] Salsa20 has been submitted to eSTREAM.

A related cipher, ChaCha, which has similar features but a different round function, was published by Bernstein in 2008.


  • Structure 1
  • eSTREAM selection 2
  • Cryptanalysis 3
  • ChaCha variant 4
    • ChaCha20 adoption 4.1
  • See also 5
  • References 6
  • External links 7


Internally, the cipher uses bitwise addition ⊕ (exclusive OR), 32-bit addition mod 232 ⊞, and constant-distance rotation operations (<<<) on an internal state of sixteen 32-bit words. This choice of operations avoids the possibility of timing attacks in software implementations. The basic Salsa20 round primitive R(a,b,c,k) is

b ⊕= (a ⊞ c) <<< k;

The initial state is made up of 8 words of key, 2 words of stream position, 2 words of nonce (essentially additional stream position bits), and 4 fixed words. 20 rounds of mixing produce 16 words of stream cipher output.

A quarter-round takes a four-word input and produces a four-word output. The internal 16-word state is arranged as a 4x4 matrix; even-numbered rounds apply the quarter-round operation to each of the four rows, while odd-numbered rounds apply the quarter-round operation to each of the four columns. Two consecutive rounds (a row-round and column-round) together are called a double-round.

A more precise specification appears below as pseudocode, although in this form the row/column pattern is more difficult to see. ⊞ is addition modulo 232, <<< is the left-rotate operation, and ⊕ is exclusive-or. x ⊕= y is an abbreviation for x = x ⊕ y.

x[ 4] ⊕= (x[ 0] ⊞ x[12])<<<7;    x[ 9] ⊕= (x[ 5] ⊞ x[ 1])<<<7;
x[14] ⊕= (x[10] ⊞ x[ 6])<<<7;    x[ 3] ⊕= (x[15] ⊞ x[11])<<<7;
x[ 8] ⊕= (x[ 4] ⊞ x[ 0])<<<9;    x[13] ⊕= (x[ 9] ⊞ x[ 5])<<<9;
x[ 2] ⊕= (x[14] ⊞ x[10])<<<9;    x[ 7] ⊕= (x[ 3] ⊞ x[15])<<<9;
x[12] ⊕= (x[ 8] ⊞ x[ 4])<<<13;   x[ 1] ⊕= (x[13] ⊞ x[ 9])<<<13;
x[ 6] ⊕= (x[ 2] ⊞ x[14])<<<13;   x[11] ⊕= (x[ 7] ⊞ x[ 3])<<<13;
x[ 0] ⊕= (x[12] ⊞ x[ 8])<<<18;   x[ 5] ⊕= (x[ 1] ⊞ x[13])<<<18;
x[10] ⊕= (x[ 6] ⊞ x[ 2])<<<18;   x[15] ⊕= (x[11] ⊞ x[ 7])<<<18;

x[ 1] ⊕= (x[ 0] ⊞ x[ 3])<<<7;    x[ 6] ⊕= (x[ 5] ⊞ x[ 4])<<<7;
x[11] ⊕= (x[10] ⊞ x[ 9])<<<7;    x[12] ⊕= (x[15] ⊞ x[14])<<<7;
x[ 2] ⊕= (x[ 1] ⊞ x[ 0])<<<9;    x[ 7] ⊕= (x[ 6] ⊞ x[ 5])<<<9;
x[ 8] ⊕= (x[11] ⊞ x[10])<<<9;    x[13] ⊕= (x[12] ⊞ x[15])<<<9;
x[ 3] ⊕= (x[ 2] ⊞ x[ 1])<<<13;   x[ 4] ⊕= (x[ 7] ⊞ x[ 6])<<<13;
x[ 9] ⊕= (x[ 8] ⊞ x[11])<<<13;   x[14] ⊕= (x[13] ⊞ x[12])<<<13;
x[ 0] ⊕= (x[ 3] ⊞ x[ 2])<<<18;   x[ 5] ⊕= (x[ 4] ⊞ x[ 7])<<<18;
x[10] ⊕= (x[ 9] ⊞ x[ 8])<<<18;   x[15] ⊕= (x[14] ⊞ x[13])<<<18;

Salsa20 performs 20 rounds of mixing on its input, then adds the final array to the original array to obtain its 64-byte output block.[5] 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 Salsa20, though with a correspondingly lower security margin.

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]


As of 2015, there are no published attacks on Salsa20/12 or the full Salsa20/20; the best attack known[2] 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.[2]

In 2012 the attack by Aumasson et al. was improved by Shi et al. against 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.)

ChaCha variant

In 2008, Bernstein published the closely related "ChaCha" family of ciphers, which aim to increase the diffusion per round while achieving the same or slightly better performance.[14] The Aumasson et al. paper also attacks ChaCha, achieving one round fewer: for 256 bits ChaCha6 with complexity 2139 and ChaCha7 with complexity 2248. 128 bits ChaCha6 within 2107, but claims that the attack fails to break 128 bits ChaCha7.[2]

ChaCha replaces the basic Salsa20 round primitive R(a,b,c,k)

b ⊕= (a ⊞ c) <<< k;

with the modified computation:

b ⊞= c;
a ⊕= b;
a <<<= k;

The rotation amounts are also updated. A full quarter-round, QR (a,b,c,d) becomes:

a ⊞= b; d ⊕= a; d <<<= 16;
c ⊞= d; b ⊕= c; b <<<= 12;
a ⊞= b; d ⊕= a; d <<<= 8;
c ⊞= d; b ⊕= c; b <<<= 7;

In addition to being more efficient on 2-operand instruction sets (like x86), this updates each word twice per quarter-round.

The fact that two of the rotates are multiple of 8 allows some optimization.[15] Additionally, the input formatting is rearranged to support an efficient SSE implementation optimization discovered for Salsa20. Rather than alternating rounds down columns and across rows, they are performed down columns and along diagonals.[16] So a double round in ChaCha is

QR (0, 4, 8, 12)
QR (1, 5, 9, 13)
QR (2, 6, 10, 14)
QR (3, 7, 11, 15)
QR (0, 5, 10, 15)
QR (1, 6, 11, 12)
QR (2, 7, 8, 13)
QR (3, 4, 9, 14)

where the numbers are the indexes of the sixteen 32-bit state words. ChaCha20 uses 10 iterations of the double round.[17]

ChaCha is the basis of the BLAKE hash function, a finalist in the NIST hash function competition, and BLAKE2 successor tuned for even higher speed. It also defines a variant using sixteen 64-bit words (1024 bits of state), with correspondingly adjusted rotation constants.

ChaCha20 adoption

Google has selected ChaCha20 along with Bernstein's Poly1305 message authentication code as a replacement for RC4 in OpenSSL, which is used for Internet security.[18] Google's initial implementation secures https (TLS/SSL) traffic between the Chrome browser on Android phones and Google's websites.[19]

Shortly after Google's adoption for TLS, both the ChaCha20 and Poly1305 algorithms were also used for a new cipher in OpenSSH.[20][21] Subsequently, this made it possible for OpenSSH to avoid any dependency on OpenSSL, via a compile-time option.[22]

ChaCha20 is also used for the arc4random random number generator in OpenBSD[23] and NetBSD[24] operating systems, instead of the "broken" RC4, and in DragonFly BSD[25] for the CSPRNG subroutine of the kernel.[26][27]

ChaCha20 has been standardized in RFC 7539.

See also

  • Speck – an add-rotate-xor cipher developed by the NSA


  1. ^ Daniel J. Bernstein. "Salsa 20 speed; Salsa20 software". 
  2. ^ a b c d Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger, New Features of Latin Dances
  3. ^ Salsa20 home page
  4. ^ Speed of Salsa20
  5. ^
  6. ^
  7. ^
  8. ^
  9. ^ Paul Crowley, Truncated differential cryptanalysis of five rounds of Salsa20
  10. ^ Simon Fischer, Willi Meier, Côme Berbain, Jean-Francois Biasse, Matt Robshaw, Non-Randomness in eSTREAM Candidates Salsa20 and TSC-4, Indocrypt 2006
  11. ^ Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki and Hiroki Nakashima (2007-01-02). "Differential Cryptanalysis of Salsa20/8" (PDF). 
  12. ^ Zhenqing Shi, Bin Zhang, Dengguo Feng, Wenling Wu (2012): „Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha“. Information Security and Cryptology – ICISC 2012. Springer Verlag, 2013, pp. 337-351
  13. ^ Nicky Mouha, Bart Preneel (2013). "A Proof that the ARX Cipher Salsa20 is Secure against Differential Cryptanalysis" (PDF). 
  14. ^ ChaCha home page
  15. ^ Neves, Samuel (2009-10-07), Faster ChaCha implementations for Intel processors, retrieved 2011-02-20, two of these constants are multiples of 8; this allows for a 1 instruction rotation in Core2 and later Intel CPUs using the pshufb instruction 
  16. ^  
  17. ^ ChaCha20 and Poly1305 for IETF protocols, Internet-Draft , Y. Nir, Check Point, A. Langley, Google Inc., November 9, 2014
  18. ^ draft-ietf-tls-chacha20-poly1305 The ChaCha20-Poly1305 AEAD Cipher for Transport Layer Security
  19. ^ Google Swaps Out Crypto Ciphers in OpenSSL, InfoSecurity, April 24, 2014
  20. ^ Miller, Damien (2013-12-02). "ssh/PROTOCOL.chacha20poly1305". BSD Cross Reference, OpenBSD src/usr.bin/. Retrieved 2014-12-26. 
  21. ^ Murenin, Constantine A. (2013-12-11). Unknown Lamer, ed. "OpenSSH Has a New Cipher — Chacha20-poly1305 — from D.J. Bernstein".  
  22. ^ Murenin, Constantine A. (2014-04-30). Soulskill, ed. "OpenSSH No Longer Has To Depend On OpenSSL".  
  23. ^  
  24. ^ riastradh, ed. (2014-11-16). "libc/gen/arc4random.c". BSD Cross Reference, NetBSD src/lib/. Retrieved 2015-01-13. Legacy arc4random(3) API from OpenBSD reimplemented using the ChaCha20 PRF, with per-thread state. 
  25. ^ "kern/subr_csprng.c". BSD Cross Reference, DragonFly BSD src/sys/. Retrieved 2015-01-13. chacha_encrypt_bytes 
  26. ^ "ChaCha Usage & Deployment". 
  27. ^ "arc4random - NetBSD Manual Pages". Retrieved 6 January 2015. 

External links

  • Salsa20 home page
  • Specification (PDF)
  • Salsa20/8 and Salsa20/12 (PDF)
  • eStream page on Salsa20
  • The ChaCha family of stream ciphers
  • Salsa20 Usage & Deployment
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.