distinguishing attack. In a recent paper by Coppersmith, Halevi and Jutla [1], they find such a correlation and for the resulting distinguishing attack they need about $2^{95}$$2^{95}$2^(95)2^{95} words of output and the computational complexity is about $2^{100}$$2^{100}$2^(100)2^{100}. By computer search we have also found other smaller correlations, often involving similar bit positions. The strong correlations seem to be caused by an interaction between the permutation in the S-box and the cyclic shift by 7 in the FSM.
区分攻击。在 Coppersmith、Halevi 和 Jutla 最近的一篇论文中，他们发现了这样的相关性，对于由此产生的区分攻击，他们需要大约 $2^{95}$$2^{95}$2^(95)2^{95} 个输出字，并且计算复杂度约为 $2^{100}$$2^{100}$2^(100)2^{100} 。通过计算机搜索，我们还发现了其他较小的相关性，通常涉及类似的位位置。强相关性似乎是由 S 盒中的置换与 FSM 中的 7 位循环移位之间的相互作用引起的。

Even if this indeed is a security flaw unpredicted by the authors, one could argue about the relevance of such a distinguishing attack. Using e.g. AES (or any other block cipher with block length 128 bits) in counter mode, there is an almost trivial distinguishing attack after seeing about $2^{64}$$2^{64}$2^(64)2^{64} ciphertext blocks. However, as we regard security as the outmost important design criteria, we addressed all known weaknesses in SNOW 1.0 and propose a slightly modified design, SNOW 2.0.
即使这确实是作者未预见的安全漏洞，也可以对这种区分攻击的相关性进行辩论。使用例如 AES（或任何其他块长度为 128 位的块密码）在计数模式下，在看到大约 $2^{64}$$2^{64}$2^(64)2^{64} 个密文块后，几乎可以进行一个微不足道的区分攻击。然而，由于我们将安全性视为最重要的设计标准，我们解决了 SNOW 1.0 中所有已知的弱点，并提出了稍微修改的设计 SNOW 2.0。

As we now turn to describe the new version SNOW 2.0, we want to emphasize that the notations from the previous sections are no longer valid and will be redefined in the following. The new version is schematically a small modification of the original construction, see Figure 2 The word size is unchanged (32 bits) and the LFSR length is again 16, but the feedback polynomial has been changed. The Finite State Machine (FSM) has two input words, taken from the LFSR, and the running key is formed as the XOR between the FSM output and the last element of the LFSR, as done in SNOW 1.0. The operation of the cipher is as follows. First, a key initialization is performed. This operation provides the LFSR with a starting state as well as giving the internal FSM registers $R1$$R1$R1R 1 and $R2$$R2$R2R 2 there initial values. Next the cipher is clocked once and the first keystream symbol is read out11. Then the cipher is clocked again and the second keystream symbol is read, etcetera.
当我们现在转向描述新版本 SNOW 2.0 时，我们想强调之前部分的符号不再有效，并将在以下内容中重新定义。新版本在结构上是对原始构造的小修改，见图 2。字长保持不变（32 位），LFSR 长度再次为 16，但反馈多项式已被更改。有限状态机（FSM）有两个输入字，来自 LFSR，运行密钥是 FSM 输出与 LFSR 最后一个元素之间的异或，和 SNOW 1.0 中的做法相同。密码的操作如下。首先，执行密钥初始化。此操作为 LFSR 提供了一个起始状态，并为内部 FSM 寄存器 $R1$$R1$R1R 1 和 $R2$$R2$R2R 2 提供了初始值。接下来，密码时钟一次，读取第一个密钥流符号。然后再次时钟密码，读取第二个密钥流符号，依此类推。

Let us give a detailed description of the cipher, starting with the LFSR. The main reason for the specific feedback polynomial chosen in SNOW 1.0, was to have a fast realization in software. By choosing a multiplication with the same primitive element as the base is constructed from, we can realize the multiplication with just one left shift and a possible XOR with a known pattern. However, this choice opens up possible weaknesses, as discussed in Section 3 In SNOW 2.0, we have two different elements involved in the feedback loop, $\alpha$$\alpha$alpha\alpha and ${\alpha }^{-1}$${\alpha }^{-1}$alpha^(-1)\alpha^{-1}, where $\alpha$$\alpha$alpha\alpha now is a root of a primitive polynomial of degree 4 over ${\mathbb{F}}_{2^8}$${\mathbb{F}}_{2^8}$F_(2^(8))\mathbb{F}_{2^{8}}. To be more precise, the feedback polynomial of SNOW 2.0 is given by
让我们详细描述这个密码，首先从 LFSR 开始。在 SNOW 1.0 中选择特定反馈多项式的主要原因是为了在软件中实现快速。通过选择与构造基础相同的原始元素进行乘法，我们可以仅通过一次左移和可能与已知模式的异或来实现乘法。然而，这一选择也带来了可能的弱点，如第 3 节所讨论的。在 SNOW 2.0 中，我们在反馈循环中涉及两个不同的元素， $\alpha$$\alpha$alpha\alpha 和 ${\alpha }^{-1}$${\alpha }^{-1}$alpha^(-1)\alpha^{-1} ，其中 $\alpha$$\alpha$alpha\alpha 现在是 ${\mathbb{F}}_{2^8}$${\mathbb{F}}_{2^8}$F_(2^(8))\mathbb{F}_{2^{8}} 上 4 度原始多项式的根。更准确地说，SNOW 2.0 的反馈多项式为

where $\alpha$$\alpha$alpha\alpha is a root of $x^4+{\beta }^{23}{x}^3+{\beta }^{245}{x}^2+{\beta }^{48}x+{\beta }^{239}\in {\mathbb{F}}_{2^8}[x]$$x^4+{\beta }^{23}{x}^3+{\beta }^{245}{x}^2+{\beta }^{48}x+{\beta }^{239}\in {\mathbb{F}}_{2^8}[x]$x^(4)+beta^(23)x^(3)+beta^(245)x^(2)+beta^(48)x+beta^(239)inF_(2^(8))[x]x^{4}+\beta^{23} x^{3}+\beta^{245} x^{2}+\beta^{48} x+\beta^{239} \in \mathbb{F}_{2^{8}}[x], and $\beta$$\beta$beta\beta is a root of $x^8+x^7+x^5+x^3+1\in {\mathbb{F}}_2[x]$$x^8+x^7+x^5+x^3+1\in {\mathbb{F}}_2[x]$x^(8)+x^(7)+x^(5)+x^(3)+1inF_(2)[x]x^{8}+x^{7}+x^{5}+x^{3}+1 \in \mathbb{F}_{2}[x].
其中 $\alpha$$\alpha$alpha\alpha 是 $x^4+{\beta }^{23}{x}^3+{\beta }^{245}{x}^2+{\beta }^{48}x+{\beta }^{239}\in {\mathbb{F}}_{2^8}[x]$$x^4+{\beta }^{23}{x}^3+{\beta }^{245}{x}^2+{\beta }^{48}x+{\beta }^{239}\in {\mathbb{F}}_{2^8}[x]$x^(4)+beta^(23)x^(3)+beta^(245)x^(2)+beta^(48)x+beta^(239)inF_(2^(8))[x]x^{4}+\beta^{23} x^{3}+\beta^{245} x^{2}+\beta^{48} x+\beta^{239} \in \mathbb{F}_{2^{8}}[x] 的一个根，而 $\beta$$\beta$beta\beta 是 $x^8+x^7+x^5+x^3+1\in {\mathbb{F}}_2[x]$$x^8+x^7+x^5+x^3+1\in {\mathbb{F}}_2[x]$x^(8)+x^(7)+x^(5)+x^(3)+1inF_(2)[x]x^{8}+x^{7}+x^{5}+x^{3}+1 \in \mathbb{F}_{2}[x] 的一个根。

Fig. 2. A schematic picture of SNOW 2.0
图 2. SNOW 2.0 的示意图

Let the state of the LFSR at time $t\ge 0$$t\ge 0$t >= 0t \geq 0 be denoted $(s_{t+15},s_{t+14},\dots ,s_t),s_{t+i}\in$$\left(s_{t+15},s_{t+14},\dots ,s_t\right),s_{t+i}\in$(s_(t+15),s_(t+14),dots,s_(t)),s_(t+i)in\left(s_{t+15}, s_{t+14}, \ldots, s_{t}\right), s_{t+i} \in ${\mathbb{F}}_{2^{32}},i\ge 0$${\mathbb{F}}_{2^{32}},i\ge 0$F_(2^(32)),i >= 0\mathbb{F}_{2^{32}}, i \geq 0. The element $s_t$$s_t$s_(t)s_{t} is the rightmost element (or first element to exit) as indicated in Figure 2 and the sequence produced by the LFSR is $(s_0,s_1,s_2,\dots )$$\left(s_0,s_1,s_2,\dots \right)$(s_(0),s_(1),s_(2),dots)\left(s_{0}, s_{1}, s_{2}, \ldots\right). By time $t=0$$t=0$t=0t=0, we mean the time instance directly after the key initialization. Then the cipher is clocked once before producing the first keystream symbol, i.e., the first keystream symbol, denoted $z_1$$z_1$z_(1)z_{1}, is produced at time $t=1$$t=1$t=1t=1. The produced keystream sequence is denoted $(z_1,z_2,z_3,\dots )$$\left(z_1,z_2,z_3,\dots \right)$(z_(1),z_(2),z_(3),dots)\left(z_{1}, z_{2}, z_{3}, \ldots\right).
让 LFSR 在时间 $t\ge 0$$t\ge 0$t >= 0t \geq 0 的状态表示为 $(s_{t+15},s_{t+14},\dots ,s_t),s_{t+i}\in$$\left(s_{t+15},s_{t+14},\dots ,s_t\right),s_{t+i}\in$(s_(t+15),s_(t+14),dots,s_(t)),s_(t+i)in\left(s_{t+15}, s_{t+14}, \ldots, s_{t}\right), s_{t+i} \in ${\mathbb{F}}_{2^{32}},i\ge 0$${\mathbb{F}}_{2^{32}},i\ge 0$F_(2^(32)),i >= 0\mathbb{F}_{2^{32}}, i \geq 0 。元素 $s_t$$s_t$s_(t)s_{t} 是最右边的元素（或第一个退出的元素），如图 2 所示，LFSR 产生的序列为 $(s_0,s_1,s_2,\dots )$$\left(s_0,s_1,s_2,\dots \right)$(s_(0),s_(1),s_(2),dots)\left(s_{0}, s_{1}, s_{2}, \ldots\right) 。我们所说的时间 $t=0$$t=0$t=0t=0 是指密钥初始化后直接的时间实例。然后在产生第一个密钥流符号之前，密码被时钟一次，即第一个密钥流符号，表示为 $z_1$$z_1$z_(1)z_{1} ，是在时间 $t=1$$t=1$t=1t=1 产生的。产生的密钥流序列表示为 $(z_1,z_2,z_3,\dots )$$\left(z_1,z_2,z_3,\dots \right)$(z_(1),z_(2),z_(3),dots)\left(z_{1}, z_{2}, z_{3}, \ldots\right) 。

The Finite State Machine (FSM) has two registers, denoted $R1$$R1$R1R 1 and $R2$$R2$R2R 2, each holding 32 bits. The value of the registers at time $t\ge 0$$t\ge 0$t >= 0t \geq 0 is denoted $R{1}_t$$R{1}_t$R1_(t)R 1_{t} and $R{2}_t$$R{2}_t$R2_(t)R 2_{t} respectively. The input to the FSM is $(s_{t+15},s_{t+5})$$\left(s_{t+15},s_{t+5}\right)$(s_(t+15),s_(t+5))\left(s_{t+15}, s_{t+5}\right) and the output of the FSM, denoted $F_t$$F_t$F_(t)F_{t}, is calculated as
有限状态机（FSM）有两个寄存器，分别表示为 $R1$$R1$R1R 1 和 $R2$$R2$R2R 2 ，每个寄存器保存 32 位。时间 $t\ge 0$$t\ge 0$t >= 0t \geq 0 时寄存器的值分别表示为 $R{1}_t$$R{1}_t$R1_(t)R 1_{t} 和 $R{2}_t$$R{2}_t$R2_(t)R 2_{t} 。FSM 的输入为 $(s_{t+15},s_{t+5})$$\left(s_{t+15},s_{t+5}\right)$(s_(t+15),s_(t+5))\left(s_{t+15}, s_{t+5}\right) ，FSM 的输出，表示为 $F_t$$F_t$F_(t)F_{t} ，计算为

and the keystream is given by
密钥流由以下给出

Here we use the notation $⊞$$⊞$⊞\boxplus for integer addition modulo $2^{32}$$2^{32}$2^(32)2^{32} and $\oplus$$\oplus$o+\oplus for bitwise addition (XOR). The registers $R1$$R1$R1R 1 and $R2$$R2$R2R 2 are updated with new values according to
在这里，我们使用符号 $⊞$$⊞$⊞\boxplus 表示整数加法模 $2^{32}$$2^{32}$2^(32)2^{32} ，使用 $\oplus$$\oplus$o+\oplus 表示按位加法（异或）。寄存器 $R1$$R1$R1R 1 和 $R2$$R2$R2R 2 根据新值进行更新。

The S-box, denoted by $S(w)$$S(w)$S(w)S(w), is a permutation on ${\mathbb{Z}}_{2^{32}}$${\mathbb{Z}}_{2^{32}}$Z_(2^(32))\mathbb{Z}_{2^{32}} based on the round function of Rijndael [4]. Let $w=(w_3,w_2,w_1,w_0)$$w=\left(w_3,w_2,w_1,w_0\right)$w=(w_(3),w_(2),w_(1),w_(0))w=\left(w_{3}, w_{2}, w_{1}, w_{0}\right) be the input to the S-box, where $w_i,i=0\dots 3$$w_i,i=0\dots 3$w_(i),i=0dots3w_{i}, i=0 \ldots 3 is the four bytes of $w$$w$ww. Assume $w_3$$w_3$w_(3)w_{3} to be the most significant byte. Let
S 盒，记作 $S(w)$$S(w)$S(w)S(w) ，是基于 Rijndael [4]的轮函数对 ${\mathbb{Z}}_{2^{32}}$${\mathbb{Z}}_{2^{32}}$Z_(2^(32))\mathbb{Z}_{2^{32}} 的一个置换。设 $w=(w_3,w_2,w_1,w_0)$$w=\left(w_3,w_2,w_1,w_0\right)$w=(w_(3),w_(2),w_(1),w_(0))w=\left(w_{3}, w_{2}, w_{1}, w_{0}\right) 为 S 盒的输入，其中 $w_i,i=0\dots 3$$w_i,i=0\dots 3$w_(i),i=0dots3w_{i}, i=0 \ldots 3 是 $w$$w$ww 的四个字节。假设 $w_3$$w_3$w_(3)w_{3} 是最高有效字节。

be a vector representation of the input to the S-box. First we apply the Rijndael S-box, denoted $S_R$$S_R$S_(R)S_{R} to each byte, giving us the vector
成为输入到 S-box 的向量表示。首先，我们将 Rijndael S-box（记作 $S_R$$S_R$S_(R)S_{R} ）应用于每个字节，从而得到向量。

In the MixColumn transformation of Rijndael’s round function, each 4 byte word is considered a polynomial in $y$$y$yy over ${\mathbb{F}}_{2^8}$${\mathbb{F}}_{2^8}$F_(2^(8))\mathbb{F}_{2^{8}}, defined by the irreducible polynomial $x^8+x^4+x^3+x+1\in {\mathbb{F}}_2[x]$$x^8+x^4+x^3+x+1\in {\mathbb{F}}_2[x]$x^(8)+x^(4)+x^(3)+x+1inF_(2)[x]x^{8}+x^{4}+x^{3}+x+1 \in \mathbb{F}_{2}[x]. Each word can be represented by a polynomial of at most degree 3 . Next we consider the vector in (12) as representing a polynomial over ${\mathbb{F}}_{2^8}$${\mathbb{F}}_{2^8}$F_(2^(8))\mathbb{F}_{2^{8}} and multiply with a fixed polynomial $c(y)=(x+1)y^3+y^2+y+x\in {\mathbb{F}}_{2^8}[y]$$c(y)=(x+1)y^3+y^2+y+x\in {\mathbb{F}}_{2^8}[y]$c(y)=(x+1)y^(3)+y^(2)+y+x inF_(2^(8))[y]c(y)=(x+1) y^{3}+y^{2}+y+x \in \mathbb{F}_{2^{8}}[y] modulo $y^4+1\in {\mathbb{F}}_{2^8}[y]$$y^4+1\in {\mathbb{F}}_{2^8}[y]$y^(4)+1inF_(2^(8))[y]y^{4}+1 \in \mathbb{F}_{2^{8}}[y]. This polynomial multiplication can (as done in Rijndael) be computed as a matrix multiplication,
在 Rijndael 的轮函数的 MixColumn 变换中，每个 4 字节的字被视为在 ${\mathbb{F}}_{2^8}$${\mathbb{F}}_{2^8}$F_(2^(8))\mathbb{F}_{2^{8}} 上的 $y$$y$yy 中的多项式，由不可约多项式 $x^8+x^4+x^3+x+1\in {\mathbb{F}}_2[x]$$x^8+x^4+x^3+x+1\in {\mathbb{F}}_2[x]$x^(8)+x^(4)+x^(3)+x+1inF_(2)[x]x^{8}+x^{4}+x^{3}+x+1 \in \mathbb{F}_{2}[x] 定义。每个字最多可以表示为一个 3 度的多项式。接下来，我们考虑(12)中的向量作为在 ${\mathbb{F}}_{2^8}$${\mathbb{F}}_{2^8}$F_(2^(8))\mathbb{F}_{2^{8}} 上的多项式，并与固定多项式 $c(y)=(x+1)y^3+y^2+y+x\in {\mathbb{F}}_{2^8}[y]$$c(y)=(x+1)y^3+y^2+y+x\in {\mathbb{F}}_{2^8}[y]$c(y)=(x+1)y^(3)+y^(2)+y+x inF_(2^(8))[y]c(y)=(x+1) y^{3}+y^{2}+y+x \in \mathbb{F}_{2^{8}}[y]