Salsa20 and the closely related ChaCha are
stream ciphers developed by
Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the
eSTREAM
eSTREAM is a project to "identify new stream ciphers suitable for widespread adoption", organised by the EU ECRYPT network. It was set up as a result of the failure of all six stream ciphers submitted to the NESSIE project. The call for primi ...
European Union cryptographic validation process by Bernstein. ChaCha is a modification of Salsa20 published in 2008. It uses a new round function that increases diffusion and increases performance on some architectures.
Both ciphers are built on a
pseudorandom function based on
add-rotate-XOR (ARX) operations — 32-bit addition, bitwise addition (XOR) and
rotation operations. The core function maps a 256-
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
key, a 64-bit
nonce, and a 64-bit counter to a 512-bit block of the key stream (a Salsa version with a 128-bit key also exists). This gives Salsa20 and ChaCha the unusual advantage that the user can efficiently seek to any position in the key stream in constant time. Salsa20 offers speeds of around 4–14
cycles per byte
Encryption software is software that uses cryptography to prevent unauthorized access to digital information. Cryptography is used to protect digital information on computers as well as the digital information that is sent to other computers over t ...
in software on modern
x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was intr ...
processors, and reasonable hardware performance. It is not patented, and Bernstein has written several
public domain
The public domain (PD) consists of all the creative work to which no exclusive intellectual property rights apply. Those rights may have expired, been forfeited, expressly waived, or may be inapplicable. Because those rights have expired, ...
implementations optimized for common architectures.
Structure
Internally, the cipher uses bitwise addition ⊕ (
exclusive OR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
), 32-bit addition
mod 2
32 ⊞, 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 attack
In cryptography, a timing attack is a side-channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and ...
s in software implementations. The internal state is made of sixteen 32-bit words arranged as a 4×4 matrix.
The initial state is made up of eight words of key, two words of stream position, two words of nonce (essentially additional stream position bits), and four fixed words:
The constant words spell "expand 32-byte k" in ASCII (i.e. the 4 words are "expa", "nd 3", "2-by", and "te k"). This is an example of a
nothing-up-my-sleeve number. The core operation in Salsa20 is the quarter-round
QR(a, b, c, d)
that takes a four-word input and produces a four-word output:
b ^= (a + d) <<< 7;
c ^= (b + a) <<< 9;
d ^= (c + b) <<< 13;
a ^= (d + c) <<< 18;
Odd-numbered rounds apply
QR(a, b, c, d)
to each of the four columns in the 4×4 matrix, and even-numbered rounds apply it to each of the four rows. Two consecutive rounds (column-round and row-round) together are called a double-round:
// Odd round
QR( 0, 4, 8, 12) // column 1
QR( 5, 9, 13, 1) // column 2
QR(10, 14, 2, 6) // column 3
QR(15, 3, 7, 11) // column 4
// Even round
QR( 0, 1, 2, 3) // row 1
QR( 5, 6, 7, 4) // row 2
QR(10, 11, 8, 9) // row 3
QR(15, 12, 13, 14) // row 4
An implementation in C/C++ appears below.
#include
#define ROTL(a,b) (((a) << (b)) , ((a) >> (32 - (b))))
#define QR(a, b, c, d)( \
b ^= ROTL(a + d, 7), \
c ^= ROTL(b + a, 9), \
d ^= ROTL(c + b,13), \
a ^= ROTL(d + c,18))
#define ROUNDS 20
void salsa20_block(uint32_t out 6 uint32_t const in 6
In the last line, the mixed array is added, word by word, to the original array to obtain its 64-byte key stream block. This is important because the mixing rounds on their own are ''invertible''. In other words, applying the reverse operations would produce the original 4×4 matrix, including the key. Adding the mixed array to the original makes it impossible to recover the input. (This same technique is widely used in hash functions from
MD4
The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms. The initialism "MD" s ...
through
SHA-2
SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression ...
.)
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
[Since the majority of the work consists of performing the repeated rounds, the number of rounds is inversely proportional to the performance. That is, halving the number of rounds roughly doubles the performance. Reduced-round variants are thus appreciably faster.] in the eSTREAM benchmarks than Salsa20, though with a correspondingly lower security margin.
XSalsa20 with 192-bit nonce
In 2008, Bernstein proposed a variant of Salsa20 with 192-bit nonces called XSalsa20. XSalsa20 is
provably secure if Salsa20 is secure, but is more suitable for applications where longer nonces are desired. XSalsa20 feeds the key and the first 128 bits of the nonce into one block of Salsa20 (without the final addition, which may either be omitted, or subtracted after a standard Salsa20 block), and uses 256 bits of the output as the key for standard Salsa20 using the last 64 bits of the nonce and the stream position. Specifically, the 256 bits of output used are those corresponding to the non-secret portions of the input: indexes 0, 5, 10, 15, 6, 7, 8 and 9.
eSTREAM selection of Salsa20
Salsa20 has been selected as a Phase 3 design for Profile 1 (software) by the
eSTREAM
eSTREAM is a project to "identify new stream ciphers suitable for widespread adoption", organised by the EU ECRYPT network. It was set up as a result of the failure of all six stream ciphers submitted to the NESSIE project. The call for primi ...
project, receiving the highest weighted voting score of any Profile 1 algorithm at the end of Phase 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, 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.
Cryptanalysis of Salsa20
, there are no published attacks on Salsa20/12 or the full Salsa20/20; the best attack known
breaks 8 of the 12 or 20 rounds.
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". 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 related-key attack on Salsa20/7 with estimated time complexity of 2
217.
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 2
255 operations, using 2
11.37 keystream pairs. However, this attack does not seem to be competitive 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 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 128-bit key.
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 2
109 and Salsa20/8 (256-bit key) to 2
250.
In 2013, Mouha and Preneel published a proof 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.
The Aumasson et al. paper also attacks ChaCha, achieving one round fewer: for 256 bits ChaCha6 with complexity 2
139 and ChaCha7 with complexity 2
248. 128 bits ChaCha6 within 2
107, but claims that the attack fails to break 128 bits ChaCha7.
Like Salsa20, ChaCha's initial state includes a 128-bit constant, a 256-bit key, a 64-bit counter, and a 64-bit nonce (in the original version; as described later, a version of ChaCha from is slightly different), arranged as a 4×4 matrix of 32-bit words.
But ChaCha re-arranges some of the words in the initial state:
The constant is the same as Salsa20 ("expand 32-byte k"). ChaCha replaces the Salsa20 quarter-round
QR(a, b, c, d)
with
a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;
Notice that this version updates each word twice, while Salsa20's quarter round updates each word only once. In addition, the ChaCha quarter-round diffuses changes more quickly. On average, after changing 1 input bit the Salsa20 quarter-round will change 8 output bits while ChaCha will change 12.5 output bits.
The ChaCha quarter round has the same number of adds, xors, and bit rotates as the Salsa20 quarter-round, but the fact that two of the rotates are multiples of 8 allows for a small optimization on some architectures including x86. Additionally, the input formatting has been 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. Like Salsa20, ChaCha arranges the sixteen 32-bit words in a 4×4 matrix. If we index the matrix elements from 0 to 15
Then a double round in ChaCha is:
// Odd round
QR(0, 4, 8, 12) // 1st column
QR(1, 5, 9, 13) // 2nd column
QR(2, 6, 10, 14) // 3rd column
QR(3, 7, 11, 15) // 4th column
// Even round
QR(0, 5, 10, 15) // diagonal 1 (main diagonal)
QR(1, 6, 11, 12) // diagonal 2
QR(2, 7, 8, 13) // diagonal 3
QR(3, 4, 9, 14) // diagonal 4
ChaCha20 uses 10 iterations of the double round. An implementation in C/C++ appears below.
#define ROTL(a,b) (((a) << (b)) , ((a) >> (32 - (b))))
#define QR(a, b, c, d) ( \
a += b, d ^= a, d = ROTL(d,16), \
c += d, b ^= c, b = ROTL(b,12), \
a += b, d ^= a, d = ROTL(d, 8), \
c += d, b ^= c, b = ROTL(b, 7))
#define ROUNDS 20
void chacha_block(uint32_t out 6 uint32_t const in 6
ChaCha is the basis of the
BLAKE hash function, a finalist in the
NIST hash function competition
The NIST hash function competition was an open competition held by the US National Institute of Standards and Technology (NIST) to develop a new hash function called SHA-3 to complement the older SHA-1 and SHA-2. The competition was formally an ...
, and its faster successors BLAKE2 and BLAKE3. It also defines a variant using sixteen 64-bit words (1024 bits of state), with correspondingly adjusted rotation constants.
XChaCha
Although not announced by Bernstein, the security proof of XSalsa20 extends straightforwardly to an analogous ''XChaCha'' cipher. Use the key and the first 128 bits of the nonce (in input words 12 through 15) to form a ChaCha input block, then perform the block operation (omitting the final addition). Output words 0–3 and 12–15 (those words corresponding to non-key words of the input) then form the key used for ordinary ChaCha (with the last 64 bits of nonce and 64 bits of block counter).
ChaCha20 adoption
Google
Google LLC () is an American Multinational corporation, multinational technology company focusing on Search Engine, search engine technology, online advertising, cloud computing, software, computer software, quantum computing, e-commerce, ar ...
had selected ChaCha20 along with Bernstein's
Poly1305
Poly1305 is a universal hash family designed by Daniel J. Bernstein for use in cryptography.
As with any universal hash family, Poly1305 can be used as a one-time message authentication code to authenticate a single message using a key shared b ...
message authentication code in
SPDY
SPDY (pronounced "speedy") is an obsolete open-specification communication protocol developed for transporting web content. SPDY became the basis for HTTP/2 specification. However, HTTP/2 diverged from SPDY and eventually HTTP/2 subsumed all u ...
, which was intended as a replacement for
TLS over
TCP. In the process, they proposed a new
authenticated encryption
Authenticated Encryption (AE) and Authenticated Encryption with Associated Data (AEAD) are forms of encryption which simultaneously assure the confidentiality and authenticity of data.
Programming interface
A typical programming interface for ...
construction combining both algorithms, which is called
ChaCha20-Poly1305
ChaCha20-Poly1305 is an authenticated encryption with additional data (AEAD) algorithm, that combines the ChaCha20 stream cipher with the Poly1305 message authentication code. Its usage in IETF protocols is standardized in RFC 8439. It has fast ...
. ChaCha20 and Poly1305 are now used in the
QUIC-protocol, which replaces
SPDY
SPDY (pronounced "speedy") is an obsolete open-specification communication protocol developed for transporting web content. SPDY became the basis for HTTP/2 specification. However, HTTP/2 diverged from SPDY and eventually HTTP/2 subsumed all u ...
and is used by
HTTP/3.
Shortly after Google's adoption for TLS, both the ChaCha20 and Poly1305 algorithms were also used for a new
chacha20-poly1305@openssh.com
cipher in
OpenSSH
OpenSSH (also known as OpenBSD Secure Shell) is a suite of secure networking utilities based on the Secure Shell (SSH) protocol, which provides a secure channel over an unsecured network in a client–server architecture.
Network Working Gro ...
. Subsequently, this made it possible for OpenSSH to avoid any dependency on
OpenSSL, via a compile-time option.
ChaCha20 is also used for the
arc4random
random number generator in
FreeBSD,
OpenBSD, and
NetBSD operating systems, instead of the broken
RC4
In cryptography, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, ren ...
, and in
DragonFly BSD
DragonFly BSD is a free and open-source Unix-like operating system forked from FreeBSD 4.8. Matthew Dillon, an Amiga developer in the late 1980s and early 1990s and FreeBSD developer between 1994 and 2003, began working on DragonFly BSD in ...
for the
CSPRNG
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely kno ...
subroutine of the kernel. Starting from version 4.8, the Linux kernel uses the ChaCha20 algorithm to generate data for the nonblocking
/dev/urandom
In Unix-like operating systems, and are special files that serve as cryptographically secure pseudorandom number generators. They allow access to environmental noise collected from device drivers and other sources. typically blocked if ther ...
device.
An implementation reference for ChaCha20 has been published in . The
IETF's implementation modified Bernstein's published algorithm by changing 64-bit nonce and 64-bit block counter to 96-bit nonce and 32-bit block counter, The name was not changed when the algorithm was modified, as it is cryptographically insignificant (both form what a cryptographer would recognize as a 128-bit nonce), but the interface change could be a source of confusion for developers. Because of the reduced block counter, the maximum message length that can be safely encrypted by the IETF's variant is 2
32 blocks of 64 bytes (256
GiB
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable unit ...
). For applications where this is not enough, such as file or disk encryption, proposes using the original algorithm with 64-bit nonce.
Use of ChaCha20 in
IKE
Ike or IKE may refer to:
People
* Ike (given name), a list of people with the name or nickname
* Dwight D. Eisenhower (1890–1969), Supreme Commander of the Allied forces in Europe during World War II and President of the United States Surname
...
and
IPsec
In computing, Internet Protocol Security (IPsec) is a secure network protocol suite that authenticates and encrypts packets of data to provide secure encrypted communication between two computers over an Internet Protocol network. It is used in ...
have been proposed for standardization in . Proposed standardization of its use in TLS is published as .
ChaCha20 usually offers better performance than the more prevalent
Advanced Encryption Standard
The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.
AES is a varian ...
(AES) algorithm on systems where the CPU does not feature AES acceleration (such as the
AES instruction set
An Advanced Encryption Standard instruction set is now integrated into many processors. The purpose of the instruction set is to improve the speed and security of applications performing encryption and decryption using Advanced Encryption Standard ...
for x86 processors). As a result, ChaCha20 is sometimes preferred over AES in certain use cases involving
mobile device
A mobile device (or handheld computer) is a computer small enough to hold and operate in the hand. Mobile devices typically have a flat LCD or OLED screen, a touchscreen interface, and digital or physical buttons. They may also have a physica ...
s, which mostly use
ARM
In human anatomy, the arm refers to the upper limb in common usage, although academically the term specifically means the upper arm between the glenohumeral joint (shoulder joint) and the elbow joint. The distal part of the upper limb between th ...
-based CPUs.
In 2018, RFC 7539 was obsoleted by .
ChaCha20 is the exclusive algorithm used by the
WireGuard VPN system, as of protocol version 1.
See also
*
Speck
Speck can refer to a number of European cured pork products, typically salted and air-cured and often lightly smoked but not cooked.
In Germany, speck is pickled pork fat with or without some meat in it. Throughout much of the rest of Europe a ...
– an add-rotate-xor cipher developed by the NSA
*
ChaCha20-Poly1305
ChaCha20-Poly1305 is an authenticated encryption with additional data (AEAD) algorithm, that combines the ChaCha20 stream cipher with the Poly1305 message authentication code. Its usage in IETF protocols is standardized in RFC 8439. It has fast ...
– an AEAD scheme combining ChaCha20 with the Poly1305 MAC
Notes
References
External links
Snuffle 2005: the Salsa20 encryption functionSalsa20 specification(
PDF)
Salsa20/8 and Salsa20/12(PDF)
Implementation and Didactical Visualization of the ChaCha Cipher Family in CrypTool 2
{{Cryptography navbox, stream
Internet Standards
Stream ciphers
Public-domain software with source code