5
$\begingroup$

Explaining the choice of the Salsa20 constant Bernstein explains:

[...] shifting the entire Salsa20 hash-function input array along the diagonal has exactly the same effect on the output.

The Salsa20 expansion function eliminates this shift structure by limiting the attacker’s control over the hash-function input. In particular, the input diagonal is always 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574, which is different from all its nontrivial shifts. In other words, two distinct arrays with this diagonal are always in distinct orbits under the shift group.

What is the meaning of the terms nontrivial shifts and distinct orbits under the shift group?

$\endgroup$
2
4
$\begingroup$

The Salsa20 core is defined on a $4\times4$ matrix $x$ of 32-bit words by $\operatorname{Salsa20}(x) = \pi(x) + x$, where $\pi$ is a permutation.

Consider a matrix:

\begin{equation} x = \begin{pmatrix} A_0 & B_0 & C_0 & D_0 \\ A_1 & B_1 & C_1 & D_1 \\ A_2 & B_2 & C_2 & D_2 \\ A_3 & B_3 & C_3 & D_3 \end{pmatrix}. \end{equation}

If we transform it into the matrix

\begin{equation} S(x) = \begin{pmatrix} D_3 & D_2 & D_1 & D_0 \\ C_3 & A_0 & B_0 & C_0 \\ B_3 & A_1 & B_1 & C_1 \\ A_3 & A_2 & B_2 & C_2 \end{pmatrix}, \end{equation}

that is move every cell downward and to the right along the diagonal, then it turns out that $\pi(S(x)) = S(\pi(x))$, for the particular $\pi$ used in Salsa20; consequently, since $S(x + y) = S(x) + S(y)$, the Salsa20 core has the property that $$\operatorname{Salsa20}(S(x)) = \pi(S(x)) + S(x) = S(\pi(x) + x) = S(\operatorname{Salsa20}(x)).$$ This transformation $S$ is called a shift, and it is invertible, so the space of all transformations $S \circ \cdots \circ S$ forms a group called the shift group; there are, of course, only four distinct shifts, since shifting four times is the same as not shifting at all. The orbit of an element $x$ under the shift group is the set $\{x, S(x), S(S(x)), S(S(S(x)))\}$.

Similarly, consider a 32-bit integer $A \in \mathbb Z/2^{32}\mathbb Z$ of the form $$A = a_0 + 2 a_1 + 4 a_2 + 8 a_3 + \cdots + 2^{31} a_{31}.$$ Define the 32-bit integer $$R(A) = a_{31} + 2 a_0 + 4 a_1 + 8 a_2 + \cdots + 2^{31} a_{30},$$ and for a $4\times4$ matrix $x$ of 32-bit integers define $R(x)$ elementwise; that is,

\begin{equation} R(x) = \begin{pmatrix} R(A_0) & R(B_0) & R(C_0) & R(D_0) \\ R(A_1) & R(B_1) & R(C_1) & R(D_1) \\ R(A_2) & R(B_2) & R(C_2) & R(D_2) \\ R(A_3) & R(B_3) & R(C_3) & R(D_3) \end{pmatrix}. \end{equation}

It turns out that, again, $$\operatorname{Salsa20}(R(x)) = R(\operatorname{Salsa20}(x)).$$ The transformation $R$ is called a rotation, and it too is invertible, so the space of all transformations $R \circ \cdots \circ R$ forms a group called the rotation group; there are, of course, 32 distinct rotations. Again, the orbit of an element $x$ under the rotation group is the set $\{x, R(x), R(R(x)), \dots\}$.

We can also consider shifts and rotations, like $S(R(R(x))$. As it happens, this is the same as $R(S(R(x))$ and $R(R(S(x))$, because $S$ only affects the matrix structure while leaving the elements intact, while $R$ only affects the elements and leaves the matrix structure intact—it doesn't matter which order you shift or rotate, so you can always uniquely write a composition of shifts and rotations as $R^\nu \circ S^\mu$ for some $\nu, \mu$, forming the shift/rotation group; as before, the orbit of an element $x$ under this group is the set $\{R^\nu(S^\mu(x))\}_{\nu,\mu}$.

These symmetries spell trouble if we use the Salsa20 core directly with arbitrary matrices—cryptography is normally about destroying structure so an adversary can't recover it, but shifts and rotations pass through the Salsa20 core unscathed. Fortunately, we don't use the Salsa20 core that way. When we use it with a key $k$ to generate the $n^{\mathit{th}}$ block $\operatorname{Salsa20}_k(n)$ of pad material for encryption, we encode the 8-word (32-byte) key $k$, the 4-word (16-byte) nonce/counter $n$, and a constant $\sigma$ (4-word/16-byte) into the matrix $x$:

\begin{equation} \operatorname{Salsa20}_k(n) = \operatorname{Salsa20}(x), \quad\text{where}\quad x = \begin{pmatrix} \sigma_0 & k_0 & k_1 & k_2 \\ k_3 & \sigma_1 & n_0 & n_1 \\ n_2 & n_3 & \sigma_2 & k_4 \\ k_5 & k_6 & k_7 & \sigma_3 \end{pmatrix}. \end{equation}

This form has the property that there is no rotation or shift $R^\nu(S^\mu(x))$ that has the same form $$\begin{pmatrix} \sigma_0 & \cdots \\ \vdots & \sigma_1 \\ & & \sigma_2 \\ & & & \sigma_3 \end{pmatrix},$$ except when $\nu = \mu = 0$, i.e. the trivial shift and rotation that leaves the matrix unchanged. That is, under the shift/rotation group, the orbit of $x$ in $\operatorname{Salsa20}_k(n)$ is entirely distinct from the orbit of $x'$ in $\operatorname{Salsa20}_{k'}(n')$ when $(k, n) \ne (k', n')$—there is no amount of shifting and rotating you can do to get from $x$ to $x'$. So no amount of control over the inputs to Salsa20 encryption—not control of the nonce, not control of the message, and not even control of the key!—enables an attacker to exploit the shift and rotational symmetry of the Salsa20 core.

This depends, of course, on the particular string $\sigma$. Had we chosen, say, $\sigma_0 = \sigma_1 = \sigma_2 = \sigma_3$, then the Salsa20 stream cipher might be vulnerable to attacks exploiting shifts, because $S(\operatorname{diag}(\sigma)) = \sigma$. Had we chosen, say, $\sigma_0 = 1 + 2^{16}$, $\sigma_1 = 2 + 2^{17}$, $\sigma_2 = 4 + 2^{18}$, and $\sigma_3 = 8 + 2^{19}$, then the Salsa20 stream cipher might be vulnerable to attacks exploiting rotations, because $R^{16}(\sigma_i) = \sigma_i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.