Fast computation of linear approximation over certain composition functions and applications to SNOW 2.0 and SNOW 3G

Abstract

In this paper, we study the linear approximation of certain composition functions, with applications to SNOW 2.0 and SNOW 3G. We first propose an efficient algorithm to compute the linear approximation of certain composition functions with parallel operations, which has a linear-time complexity for any given mask tuple, and thus allows for a wide range of search for linear approximations. Naturally, we apply this algorithm to compute the linear approximations of the FSM of both SNOW 2.0 and SNOW 3G. For SNOW 2.0, we compute the linear approximation of the FSM for a wide range of linear masks, and obtain some results which enable us to slightly improve the data complexity of the known fast correlation attacks, by using multiple linear approximations and combining a small technique when applying the k-tree algorithm. For SNOW 3G, we make a careful search for the linear approximations of the FSM and obtain many mask tuples which yield high correlations. Using these linear approximations, we mount a fast correlation attack on SNOW 3G and recover the initial state of the LFSR with the total time complexity $2^{222.33}$ and memory complexity $2^{221.74}$, given $2^{220.74}$ keystream words. Our attack does not pose a threat to the claimed 128-bit security of SNOW 3G.

Appendices

Appendix A: Computing the mask ${\varLambda }'$ from the given mask ${\varLambda }$ such that ${\varLambda }'\cdot x={\varLambda }\cdot (M_1x)$

Let $lin: \mathbf{F }_{2^{32}}\rightarrow \mathbf{F }_{2^{32}}$ be a linear transformation with ${\varLambda }'=lin({\varLambda })$ being the linear mask computed from ${\varLambda }$ by combining the MixColumn matrix $M_1$, i.e., ${\varLambda }'\cdot x={\varLambda }\cdot (M_1x)$. Let us briefly describe how to compute ${\varLambda }'$ from ${\varLambda }$. For $\lambda =(\lambda _0\parallel \lambda _1\parallel \lambda _2\parallel \lambda _3\parallel \lambda _4\parallel \lambda _5\parallel \lambda _6\parallel \lambda _7)\in \mathbf{F }_{2^8}$, define $\lambda '=trans(\lambda )=(\lambda '_0\parallel \lambda '_1\parallel \lambda '_2\parallel \lambda '_3\parallel \lambda '_4\parallel \lambda '_5\parallel \lambda '_6\parallel \lambda '_7)$ as:

$$\begin{aligned} \left\{ \begin{array}{l} {\lambda '_i} = {\lambda _{i + 1}},\quad i = 0,1,...,6\\ {\lambda '_7} = \underline{{\lambda _0} \oplus {\lambda _1} \oplus {\lambda _3} \oplus {\lambda _4}}. \end{array} \right. \end{aligned}$$

Write ${\varLambda }=({\varLambda }_0\parallel {\varLambda }_1\parallel {\varLambda }_2\parallel {\varLambda }_3)$, ${\varLambda }'=({\varLambda }_0'\parallel {\varLambda }_1'\parallel {\varLambda }_2'\parallel {\varLambda }_3')$, where ${\varLambda }_j\in \mathbf{F }_{2^8}$, ${\varLambda }_j'\in \mathbf{F }_{2^8}$, we have $({\varLambda }_0'\parallel {\varLambda }_1'\parallel {\varLambda }_2'\parallel {\varLambda }_3')=lin({\varLambda }_0\parallel {\varLambda }_1\parallel {\varLambda }_2\parallel {\varLambda }_3)$ such that

$$\begin{aligned} \begin{aligned}&{\varLambda }_0'=\textit{trans}({\varLambda }_0)\oplus {\varLambda }_1\oplus {\varLambda }_2\oplus {\varLambda }_3\oplus \textit{trans}({\varLambda }_3).\\&{\varLambda }_1'=\textit{trans}({\varLambda }_1)\oplus {\varLambda }_2\oplus {\varLambda }_3\oplus {\varLambda }_0\oplus \textit{trans}({\varLambda }_0),\\&{\varLambda }_2'=\textit{trans}({\varLambda }_2)\oplus {\varLambda }_3\oplus {\varLambda }_0\oplus {\varLambda }_1\oplus \textit{trans}({\varLambda }_1),\\&{\varLambda }_3'=\textit{trans}({\varLambda }_3)\oplus {\varLambda }_0\oplus {\varLambda }_1\oplus {\varLambda }_2\oplus \textit{trans}({\varLambda }_2).\\ \end{aligned} \end{aligned}$$

(11)

Appendix B: Computing the mask ${\varLambda }''$ from the given mask ${\varLambda }$ such that ${\varLambda }''\cdot x={\varLambda }\cdot (M_2x)$

Let $lin': \mathbf{F }_{2^{32}}\rightarrow \mathbf{F }_{2^{32}}$ be another linear transformation with ${\varLambda }''=lin'({\varLambda })$ being the linear mask computed from ${\varLambda }$ by combining the MixColumn matrix $M_2$, i.e., ${\varLambda }''\cdot x={\varLambda }\cdot (M_2 x)$. We now describe how to compute ${\varLambda }''$ from ${\varLambda }$. For $\lambda =(\lambda _0\parallel \lambda _1\parallel \lambda _2\parallel \lambda _3\parallel \lambda _4\parallel \lambda _5\parallel \lambda _6\parallel \lambda _7)\in \mathbf{F }_{2^8}$, define $\lambda ''=trans'(\lambda )=(\lambda ''_0\parallel \lambda ''_1\parallel \lambda ''_2\parallel \lambda ''_3\parallel \lambda ''_4\parallel \lambda ''_5\parallel \lambda ''_6\parallel \lambda ''_7)$ as:

$$\begin{aligned} \left\{ \begin{array}{l} {\lambda ''_i} = {\lambda _{i + 1}},\quad i = 0,1,...,6\\ {\lambda ''_7} = \underline{{\lambda _0} \oplus {\lambda _3} \oplus {\lambda _5} \oplus {\lambda _6}}. \end{array} \right. \end{aligned}$$

Writing ${\varLambda }=({\varLambda }_0\parallel {\varLambda }_1\parallel {\varLambda }_2\parallel {\varLambda }_3)$, ${\varLambda }''=({\varLambda }_0''\parallel {\varLambda }_1''\parallel {\varLambda }_2''\parallel {\varLambda }_3'')$, where ${\varLambda }_j\in \mathbf{F }_{2^8}$, ${\varLambda }_j''\in \mathbf{F }_{2^8}$, we have $({\varLambda }_0''\parallel {\varLambda }_1''\parallel {\varLambda }_2''\parallel {\varLambda }_3'')=lin'({\varLambda }_0\parallel {\varLambda }_1\parallel {\varLambda }_2\parallel {\varLambda }_3)$ such that

$$\begin{aligned} \begin{aligned}&{\varLambda }_0''=\textit{trans}'({\varLambda }_0)\oplus {\varLambda }_1\oplus {\varLambda }_2\oplus {\varLambda }_3\oplus trans'({\varLambda }_3),\\&{\varLambda }_1''=\textit{trans}'({\varLambda }_1)\oplus {\varLambda }_2\oplus {\varLambda }_3\oplus {\varLambda }_0\oplus trans'({\varLambda }_0),\\&{\varLambda }_2''=\textit{trans}'({\varLambda }_2)\oplus {\varLambda }_3\oplus {\varLambda }_0\oplus {\varLambda }_1\oplus trans'({\varLambda }_1),\\&{\varLambda }_3''=\textit{trans}'({\varLambda }_3)\oplus {\varLambda }_0\oplus {\varLambda }_1\oplus {\varLambda }_2\oplus \textit{trans}'({\varLambda }_2). \end{aligned} \end{aligned}$$