Salsa20

Salsa20

The Salsa quarter-round function. Four parallel copies make a round.
General
Designers	Daniel J. Bernstein
First published	2007 (designed 2005)
Related to	Rumba20, ChaCha
Certification	eSTREAM portfolio
Cipher detail
Key sizes	256 bits
State size	512 bits
Structure	ARX
Rounds	20
Speed	3.91 cpb on an Intel Core 2 Duo
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.

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 block of the key stream (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 key stream in constant time. It offers speeds of around 4–14 cycles per 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.

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

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

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. Then the array is mixed as follows.

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.