Question

Give an explicit description of the column-round operation in Salsa20 using the
quarter-round map.

Answer 1

The basic nonlinear operation of Salsa20 is the quarterround function. Each quarterround(a, b, c, d) consists of four ARX rounds, each of which comprises of one addition (A), one cyclic left rotation (R) and one XOR (X) operation as given below.

b = b ⊕ ((a + d) ≪ 7),

c = c ⊕ ((b + a) ≪ 9),

d = d ⊕ ((c + b) ≪ 13),

a = a ⊕ ((d + c) ≪ 18)

Each columnround works as four quarterrounds on each of the four columns of the state matrix and each rowround works as four quarterrounds on each of the four rows of the state matrix. In Salsa20 (one can call it Salsa20/20), ten times the columnround and ten times the rowround are applied alternatively on the initial state. One may note that this can be considered as application of the columnround and transpose of the state matrix [6] twenty times. This helps in understanding the cipher better as in this case every round of Salsa20 becomes identical. To be precise, in each round, we first apply quarterround on all the four columns in the following order: quarterround(x0, x4, x8, x12), quarterround(x5, x9, x13, x1), quarterround(x10, x14, x2, x6), and quarterround(x15, x3, x7, x11), and then a transpose(X) as considering it as a 4×4 matrix. By X(r) , we mean that r rounds have been applied on the initial state X. Hence X(0) is the same as the initial state X. Finally, after R rounds we have X(R) . Then a keystream block of 16 words or 512 bits is obtained as Z = X + X(R) . For Salsa20, R = 20. However, the one accepted in eStream [9] software portfolio is Salsa20/12, where R = 12. Naturally, more rounds will provide better security and less rounds will provide higher speed. One may note that each Salsa20 round is reversible as the state-transition operations are reversible. In other words, if X(r+1) = round(X(r) ), then X(r) = reverseround(X(r+1)), where reverseround is the inverse of round and consists of first transposing the state and then applying the inverse of quarterround for each column as follows.

a = a ⊕ ((d + c) ≪ 18),

d = d ⊕ ((c + b) ≪ 13),

c = c ⊕ ((b + a) ≪ 9),

b = b ⊕ ((a + d) ≪ 7).

Consider that one obtains a state X(1) after one round of Salsa20. Now to know whether it is a valid state after one round, one needs to come back by one reverse round and then check whether the constants in the diagonal elements are indeed the specified ones. This is the constraint for 256-bit Salsa20. However, for 128- bit Salsa20, one needs to have another constraint related to the key words apart from matching the constants. That is, we need to have ki = ki+4, for 0 ≤ i ≤ 3.