Salsa20

Salsa20
The Salsa quarterround function. Four parallel copies make a round.General Related to Rumba20, ChaCha Certification eSTREAM portfolio Cipher detail Key sizes 256 bits State size 512 bits Rounds 20 Speed 4.25 cpb on Intel Woodcrest^{[1]} Best public cryptanalysis 2008 cryptanalysis breaks 8 out of 20 rounds to recover the 256bit secret key in 2^{251} operations, using 2^{31} keystream pairs.^{[2]} Salsa20 is a stream cipher submitted to eSTREAM by Daniel Bernstein. It is built on a pseudorandom function based on 32bit addition, bitwise addition (XOR) and rotation operations, which maps a 256bit key, a 64bit nonce (number used once), and a 64bit stream position to a 512bit output (a version with a 128bit 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 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]}
Contents
Structure
Internally, the cipher uses bitwise addition (exclusive OR), 32bit addition mod 2^{32}, and constantdistance rotation operations on an internal state of 16 32bit words. This choice of operations avoids the possibility of timing attacks in software implementations.
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.
Each round consists of four quarterround operations, performed on either the columns or the rows of the 16word state, arranged as a 4×4 matrix. Every 2 rounds, the pattern repeats. Pseudocode for two rounds is as follows. ⊞ is addition modulo 2^{32}, <<< is the leftrotate operation, and ^ is exclusiveor.
x ^= y
is an abbreviation forx = 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;
These operations can be performed very efficiently using the x86 SSE2 instruction set.
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.
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.^{[5]} 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 ^{[6]}, 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.^{[7]}
Cryptanalysis
In 2005, Paul Crowley reported an attack on Salsa20/5 with an estimated time complexity of 2^{165}, and won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis".^{[8]} 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^{177}, and a relatedkey attack on Salsa20/7 with estimated time complexity of 2^{217}.^{[9]}
In 2007, Tsunoo et al. announced a cryptanalysis of Salsa20 which breaks 8 out of 20 rounds to recover the 256bit secret key in 2^{255} operations, using 2^{11.37} keystream pairs.^{[10]}. However, this attack does not seem to be comparative with the brute force attack.
As of 2008^{[update]}, Aumasson, Fischer, Khazaei, Meier, and Rechberger^{[2]} reported a cryptanalytic attack against Salsa20/7 with a time complexity of 2^{153}, and they reported the first attack against Salsa20/8 with an estimated time complexity of 2^{251}. 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 128bit key. There are no published attacks on Salsa20/12 or the full Salsa20/20.
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 greater performance.^{[11]} The Aumasson et al. paper also attacks ChaCha, achieving one round less: ChaCha6 with complexity 2^{140} and ChaCha7 with complexity 2^{231}.^{[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 quarterround 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 2operand instruction sets (like x86), this updates each word twice per quarterround.
The fact that two of the rotates are multiple of 8 allows some optimization.^{[12]} 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.^{[13]}
ChaCha is the basis of the BLAKE hash function, a finalist in the NIST hash function competition.
References
 ^ Daniel J. Bernstein. "Salsa 20 speed; Salsa20 software". http://cr.yp.to/snuffle.html#speed.
 ^ ^{a} ^{b} ^{c} JeanPhilippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger, New Features of Latin Dances
 ^ Salsa20 home page
 ^ Speed of Salsa20
 ^ http://www.ecrypt.eu.org/stream/endofphase2.html
 ^ http://www.ecrypt.eu.org/stream/endofphase1.html
 ^ http://www.ecrypt.eu.org/stream/PhaseIIreport.pdf
 ^ Paul Crowley, Truncated differential cryptanalysis of five rounds of Salsa20
 ^ Simon Fischer, Willi Meier, Côme Berbain, JeanFrancois Biasse, Matt Robshaw, NonRandomness in eSTREAM Candidates Salsa20 and TSC4, Indocrypt 2006
 ^ Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki and Hiroki Nakashima (20070102). Differential Cryptanalysis of Salsa20/8. http://www.ecrypt.eu.org/stream/papersdir/2007/010.pdf.
 ^ ChaCha home page
 ^ Neves, Samuel (20091007), Faster ChaCha implementations for Intel processors, http://eden.dei.uc.pt/~sneves/chacha/chacha.html, retrieved 20110220, "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"
 ^ Bernstein, D. J. (20080128) (pdf), ChaCha, a variant of Salsa20, p. 4, Document ID: 4027b5256e17b9796842e6d0f68b0b5e, http://cr.yp.to/chacha/chacha20080128.pdf, retrieved 20110220
External links
 Salsa20 home page
 Specification (PDF)
 Salsa20/8 and Salsa20/12 (PDF)
 eStream page on Salsa20
 The ChaCha family of stream ciphers
Stream ciphers Theory: Shift register · LFSR · NLFSR · Shrinking generator · Tfunction · IV
Attacks: Correlation attack · Correlation immunity
Cryptography Categories: Stream ciphers
Wikimedia Foundation. 2010.
Look at other dictionaries:
Salsa20 — Salsa20 система поточного шифрования разработанная Daniel J. Bernstein. Алгоритм был представлен на конкурсе eSTREAM, целью которого было создание европейских стандартов для поточных систем шифрования. Алгоритм стал победителем конкурса в… … Википедия
Salsa20 — Pour les articles homonymes, voir Salsa (homonymie) et 20 (nombre). Salsa20 est un chiffrement de flux proposé au projet eSTREAM par Daniel Bernstein. Il est architecturé autour d une fonction pseudo aléatoire basée sur des opérations d addition… … Wikipédia en Français
Truncated differential cryptanalysis — In cryptography, truncated differential cryptanalysis is a generalization of differential cryptanalysis, an attack against block ciphers. Lars Knudsen developed the technique in 1994. Whereas ordinary differential cryptanalysis analyzes the full… … Wikipedia
eSTREAM — eSTREAM проект по выявлению новых поточных шифров, пригодных для широкого применения, организованный ЕС. Был начат после взлома всех 6 шифров, предложенных в проекте NESSIE. Условия приёма алгоритмов впервые были опубликованы в… … Википедия
Stream cipher — The operation of the keystream generator in A5/1, a LFSR based stream cipher used to encrypt mobile phone conversations. In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher… … Wikipedia
Daniel J. Bernstein — Daniel Bernstein Born October 29, 1971 (1971 10 29) (age 40) East Patchogue, New York[ … Wikipedia
Comparison of operating system kernels — A kernel is the core component of every computer operating system. While kernels are highly technical in nature, and may be hidden from the user under many layers of software and applications, they do have distinguishing or characteristic… … Wikipedia
ECRYPT — European Network of Excellence for Cryptology ECRYPT (European Network of Excellence for Cryptology) est une initiative d une durée de quatre ans lancée par des experts européens en cryptologie. Son but est d améliorer la collaboration entre les… … Wikipédia en Français
European Network of Excellence for Cryptology — ECRYPT (European Network of Excellence for Cryptology) est un Réseau d excellence d une durée de quatre ans lancé par des experts européens en cryptologie. Son but est d améliorer la collaboration entre les spécialistes de la sécurité… … Wikipédia en Français
Obfuscated TCP — (ObsTCP) was a proposal for a transport layer protocol which implements opportunistic encryption over TCP. It was designed to prevent mass wiretapping and malicious corruption of TCP traffic on the internet, with lower implementation cost and… … Wikipedia