Crypto-IT

• Key length = 32 bytes

Salsa20 is a modern and efficient stream symmetric cipher. It was designed in 2005 by Daniel Bernstein, research professor of Computer Science at the University of Illinois at Chicago.

Salsa20 is a cipher that was submitted to eSTREAM project, running from 2004 to 2008, which was supposed to promote development of stream ciphers. It is considered to be a well-designed and efficient algorithm. There aren't any known and effective attacks on the family of Salsa20 ciphers.

Salsa20 is a stream cipher that works on data blocks of size of 64 bytes.

For each 64-byte data block, the algorithm uses the Salsa20 expansion function. The input to the function is the secret key (which can have either 32 or 16 bytes) and an 8-byte long nonce concatenated with an additional block number, which values change from 0 to 2⁶⁴-1 (it is also stored on 8 bytes). Every call to the expansion function increases the block number by one.

The core of Salsa20 encryption algorithm is a hash function which receives the 64-byte long input data from the Salsa20 expansion function, mixes it, and eventually returns the 64-byte long output. The Salsa20 hash function works on the received sequence of bytes, which consists of:

• the secret key.
• the nonce with the block number.
• four constant vectors received from the expansion function, which values depend on the size of the secret key.

The hash function operates on data divided into words. Every word contains 4 bytes and can have values from 0 to 2³²-1. Therefore, the input data is 16-word long, a key contains 8 or 4 words, and the nonce has 2 words.

The output from the Salsa20 expansion function is added XOR to the 64-byte block of data. The result is a 64-byte block of ciphertext.

The same algorithm should be used during decryption. The data should be divided into parts of the same size.

The output from the Salsa20 expansion function should be added XOR to the 64-byte block of ciphertext. The result is a 64-byte block of plaintext.

There are also some other ciphers, which are based on the Salsa20 algorithm but differ in details.

• Salsa20/8 and Salsa20/12 - they work exactly as the original Salsa20 algorithm but instead of 10 doublerounds inside the hash function, they perform 4 or respectively 6 doublerounds.
• ChaCha family - published by Bernstein in 2008. They provide better security than the original Salsa20 cipher, by using slightly better hash functions. The hash function input data was rearranged, to allow to implement the algorithm in a more efficient way.

Scheme of Salsa20 algorithm

The operations for Salsa20 algorithm are presented in the order from the low-level functions, to the more complex functions, which use the functions described above them.

The addition of two 4-byte words is denoted in the algorithm description as a + b. The result is divided modulo by 2³² (so, by the maximum value that can be stored in one word).

The sum of two words a and b is equal to a+b mod 2³². The result is a valid 4-byte long word.

The Exclusive-Or of two 4-byte words is denoted in the algorithm description as a XOR b.

To perform XOR addition, two words are compared bit by bit, and XOR addition is performed for each pair. The result is also a valid proper 4-byte long word.

The a-bit left rotation of a 4-byte word w is denoted in the algorithm as w <<< a. The leftmost a bits move to the rightmost positions.

A rotation of bits to the left w <<< a of a 4-byte word w may be represented as the multiplication:
2^a·w mod(2³²-1)
The result is a valid 4-byte long word.

The Quarterround Function takes 4 words as input and returns another 4-word sequence.

If x is a 4-word input:
    x = (x₀, x₁, x₂, x₃)
then the function can be defined as follow:
    quarterround(x) = (y₀, y₁, y₂, y₃)
where:
    y₁ = x₁ XOR ((x₀ + x₃) <<< 7)
    y₂ = x₂ XOR ((y₁ + x₀) <<< 9)
    y₃ = x₃ XOR ((y₂ + y₁) <<< 13)
    y₀ = x₀ XOR ((y₃ + y₂) <<< 18)

The Quarterround Function can be performed in place, without the need of allocating any additional memory. First, x₁ changes to y₁, then x₂ changes to y₂, next x₃ changes to y₃, then x₀ changes to y₀. The Quarterround Function is invertible because all the modifications above are invertible.

The Rowround Function takes 16 words as input, transforms them, and returns 16-word sequence.

This function is very similar to the Columnround Function but it operates on the words in a different order.

If x is a 16-word input:
    x = (x₀, x₁, x₂, ..., x₁₅)
then the function can be defined as follow:
    rowround(x) = (y₀, y₁, y₂, ..., y₁₅)
where:
    (y₀, y₁, y₂, y₃) = quarterround(x₀, x₁, x₂, x₃)
    (y₅, y₆, y₇, y₄) = quarterround(x₅, x₆, x₇, x₄)
    (y₁₀, y₁₁, y₈, y₉) = quarterround(x₁₀, x₁₁, x₈, x₉)
    (y₁₅, y₁₂, y₁₃, y₁₄) = quarterround(x₁₅, x₁₂, x₁₃, x₁₄)

The 16-word input can be presented as a square matrix:

The rows in the matrix can be changed in parallel. Each of them is modified by the Quarterround Function.

In the first row, the words are changed in the following order:

1. x₁
2. x₂
3. x₃
4. x₀

In the second row, the words are changed in the following order:

1. x₆
2. x₇
3. x₄
4. x₅

In the third row, the words are modified in the order:

1. x₁₁
2. x₈
3. x₉
4. x₁₀

Finally, in the last, fourth row, the words are changed in the order:

1. x₁₂
2. x₁₃
3. x₁₄
4. x₁₅

The Columnround Function takes 16 words as input and returns 16-word sequence.

This function is very similar to the Rowround Function but operates on the words in different order.

If x is a 16-word input:
    x = (x₀, x₁, x₂, ..., x₁₅)
then the function can be defined as follow:
    columnround(x) = (y₀, y₁, y₂, ..., y₁₅)
where:
    (y₀, y₄, y₈, y₁₂) = quarterround(x₀, x₄, x₈, x₁₂)
    (y₅, y₉, y₁₃, y₁) = quarterround(x₅, x₉, x₁₃, x₁)
    (y₁₀, y₁₄, y₂, y₆) = quarterround(x₁₀, x₁₄, x₂, x₆)
    (y₁₅, y₃, y₇, y₁₁) = quarterround(x₁₅, x₃, x₇, x₁₁)

The 16-word input can be presented as a square matrix:

The columns in the matrix can be changed in parallel. Each of them is modified by the Quarterround Function.

In the first column, the words are changed in the following order:

1. x₄
2. x₈
3. x₁₂
4. x₀

In the second column, the words are modified in the following order:

1. x₉
2. x₁₃
3. x₁
4. x₅

In the third column, the words are changed in the order:

1. x₁₄
2. x₂
3. x₆
4. x₁₀

In the last fourth column, the words are modified in the order:

1. x₃
2. x₇
3. x₁₁
4. x₁₅

The Doubleround Function takes 16 words as input and returns 16-word sequence.

If x is a 16-word input, then the Doubleround Function can be defined as follow:
    doubleround(x) = rowround(columnround(x))

The Littleendian Function changes the order of a 4-byte sequence.

If b is a sequence of four bytes:
    b = (b₀, b₁, b₂, b₃)
then the function is defined as:
    littleendian(b) = b₀ + 2⁸b₁ + 2¹⁶b₂ + 2²⁴b₃

The Littleendian Function is invertible. It just simply changes the order of bytes in a word.

The Salsa20 Hash Function takes 64 bytes as input and returns a 64-byte sequence.

First, the Hash Function creates 16 words from the received 64-byte input. If input is a sequence of 64 bytes:
    input =(b₀, b₁, b₂, ..., b₆₃)
then 16 words are created as below:
    w₀ = littleendian(b₀, b₁, b₂, b₃)
    w₁ = littleendian(b₄, b₅, b₆, b₇)
    [...]
    w₁₅ = littleendian(b₆₀, b₆₁, b₆₂, b₆₃)

Then, all 16 words are modified by 10 iterations of the Doubleround Function:
    (x₀, x₁, ..., x₁₅) = doubleround¹⁰(w₀, w₁, ..., w₁₅)

Finally, the 16 words received as input are added (as described above) to the modified 16 words and changed to 64 new bytes using the Littleendian Function. The bytes are output from the Salsa20 Hash Function:
    output = littleendian^-1(x₀+w₀) + littleendian^-1(x₁+w₁) + ... + littleendian^-1(x₁₅+w₁₅)

The Salsa20 Expansion Function takes two sequences of bytes. The first sequence can have either 16 or 32 bytes and the second sequence (n) is always 16-byte long. The function returns another sequence of 64 bytes.

If the first sequence is 32-bytes long, then it is divided into two shorter sequences of 16 bytes (k₀ and k₁). The Salsa20 Expansion Function is defined by using the Salsa20 Hash Function, as shown below:
    Salsa20Expansion_{k0, k1}(n) = Salsa20Hash(a₀, k₀, a₁, n, a₂, k₁, a₃)
where:
    a₀ = (101, 120, 112, 97)
    a₁ = (110, 100, 32, 51)
    a₂ = (50, 45, 98, 121)
    a₃ = (116, 101, 32, 107)

If the first sequence is 16-bytes long (k), then the Salsa20 Expansion Function is defined by using the Salsa20 Hash Function as below:
    Salsa20Expansion_k(n) = Salsa20Hash(b₀, k, b₁, n, b₂, k, b₃)
where:
    b₀ = (101, 120, 112, 97)
    b₁ = (110, 100, 32, 49)
    b₂ = (54, 45, 98, 121)
    b₃ = (116, 101, 32, 107)

The constant values of the vector (a₀, a₁, a₂, a₃) mean 'expand 32-byte k' in ASCII code. Similarly, the constant values of the second vector (b₀, b₁, b₂, b₃) mean 'expand 16-byte k' in ASCII.