Recent Results on Some Word Oriented Stream Ciphers: SNOW 1.0, SNOW 2.0 and SNOW 3G

Abstract

In this chapter, we have studied three word-oriented stream ciphers SNOW 1.0, SNOW 2.0 and SNOW 3G in a detailed way. The detailed description includes the working principles of each cipher, security vulnerabilities and implementation issues. It also helps us to study the challenges in each cipher. As SNOW 3G is used as a confidentiality and integrity component in 3G, 4G and 5G communications, the after study of this article may instigate the reader to find the fixes from different cryptanalysis and also find a new suitable design in Mobile telephony security.

1. Introduction

In modern era of communication, mobile devices, tablets, computers are developed with huge processing power, memory and storage. When one mobile device communicates with a remote server or another mobile device, the communication always takes place in a secret way. For any bank transaction or any online purchase through PC, we always require communication link between the source and the server which ensures the authentication, confidentiality and integrity of the channel. Before the year 1999, Block ciphers was the only way to provide confidentiality in any kind of communication in word oriented environment. AES, DES, 3-DES, BlowFish, Serpent, Twofish are some of the common used block cipher algorithms. The problems associated with block ciphers are mainly processing power, throughput in comparison to stream cipher. Stream cipher works very efficiently in hardware due to its simple design and good statistical properties. But it lacks in software based applications. But is it possible to make a word-oriented cipher which will be faster than Block cipher, at least gives security of AES [1] (Advance Encryption Standard) and suits in software as well as hardware? This initiate the design and analysis of word-oriented stream cipher. The basic building block of word oriented stream cipher is designed by LFSR (Linear Feedback Shift Register) with multi input multi output (MIMO) delay blocks and a Nonlinear function. In this kind of design, LFSR plays the role of generating sequence with uniform distribution. It generates $m-$sequence. As, sequence from LFSR can be easily cryptanalyzed by Barleycamp Massey Algorithm [2], Nonlinear maps are used along with LFSR to increase the linear complexity as well as nonlinearity of the output sequence. Generally, S-box, Addition modulo $2^n$($⊞$), Subtraction modulo $2^n$($\boxminus$) are used as Nonlinear function. Word-based Cipher acts as a pseudorandom number generator (PRNG) which produces vector in each clock cycle as keystreams. Plaintext block and keystream block are encrypted with bitwise EXOR operator and it creates cipher text block. In the receiving end, cipher text block and the same keystream generator produces the plaintext block using the same bitwise exor operator. In the next subsection, we discuss about some existing word-based LFSR.

1.1 Related work

The research on word-based stream cipher was coined by Bart Preneel in FSE 1994. In NESSIE (New European Schemes for Signature, Integrity, and Encryption) competition (2000–2003), six stream ciphers (BMGL, Leviathan, LILI-128, SNOW [3], SOBER-t16 [4] and SOBER-t32 [5]) were submitted. Among which SNOW 1.0, SOBER-t16 and SOBER t-32 were found as word oriented stream ciphers. In 2002, SNOW, SOBER-t16 and SOBER t-32 were found with security flaws with certain cryptographic attacks (Distinguishing attack, Guess and Determine attack and Linear cryptanalysis). In 2002, SNOW 2 [6] was proposed by Ekdahl and Johansson, the same author published SNOW 1.0. But two cryptographic attacks, Algebraic attack and Linear Distinguishing attack made SNOW 2.0 vulnerable. After SNOW 2.0, in 2006 SNOW 3G and in 2008 Sosemanuk [7] (as a Estream finalist) came into the literature. SNOW 3G was selected as 3GPP Confidentiality and Integrity Algorithms UEA2 and UIA2. It was also analyzed by Fault Analysis attack [8] in 2009. Sosemanuk cipher is an modified of version of SNOW 2.0. There are some attacks on Sosemanuk like Linear masking method [9], byte based guess and determine attack [10]. Ekdahl et al. recently proposed SNOW-V [11] stream cipher with the feature of 256-bit security and huge throughput in 5G environment. Still, we find fast correlation attack [12] with $2^{251.93}$ complexity and improved guess and determining attack [13] with $2^{406}$ complexity on SNOW-V.

In this literature, we are trying to present detailed study of SNOW 1.0, SNOW 2.0 and SNOW 3G and discuss the basic problems related to it.

2. Symbols used and their meaning

The following mathematical symbols will be used in this article (Table 1).

Symbol	Meaning
${\mathbb{F}}_{b^n}$	Finite field of cardinality $p^n$, where b is a prime number
${\mathbb{F}}_p^n$	$n$-dimensional vector space over ${\mathbb{F}}_p$
$\mathit{GF}\left(P\right)$	Galois field with elements $\in \left\{0,1,\cdots ,p-1\right\}$
$v^T$	A vector $v$ with transposed form $v=\left(v_1,v_2,\cdots ,v_n\right)$
$\oplus$	XOR
$⊞$	Addition modulo $2^{32}$
$M^{n\times n}$	Matrix M with $n$ rows and $n$ columns
$x⋘$	Cyclic shift of x to 7 step left
$M_m\left(F_2\right)$	Matrix Ring of $m\times m$ matrices over Finite Field $F_2$

Table 1.

Symbol and their meaning.

3. Preliminaries

In this section, we present some definitions and related concepts useful to understand the context of next sections.

Primitive polynomial: A polynomial that generates all elements in an extension field over a base field is called Primitive Polynomial. It is also irreducible polynomial. There are $\frac{\varphi \left(q^n-1\right)}{n}$ primitive polynomials of degree $n$ in $\mathcal{G}\mathcal{F}\left(q\right)\left[X\right]$, where $\varphi$ is the Euler phi function.

Example 1.$x^4+x+1$ and $x^4+x^3+1$ are two primitive polynomials of $\mathcal{G}\mathcal{F}\left(2^4\right)$.

Linear feedback shift register (LFSR): LFSR is an important source of PRNG in stream cipher design. It is very fast and easy to implement in hardware. It consists of some D flip flops and a feedback polynomial. If $f$ is the primitive polynomial of degree $n$ and $\left\{x_1,x_2,\cdots ,x_n\right\}$ where each $x_i\in {\mathbb{F}}_2$, is the state of the LFSR, the state update function of the LFSR $L$ is defined:

$$L:\left\{x_1,x_2,\cdots ,x_n\right\}\to \left\{f\left(x_1,x_2,\cdots ,x_n\right),x_2,\cdots ,x_{n-1}\right\}$$E1

If the feedback polynomial of a LFSR is primitive, it can generate all the nonzero states in its period. But LFSR based PRNG is vulnerable to Barleycamp Massey attack. It finds the initial state and the feedback polynomial of the LFSR if $2\times n$ keystream can be accessed from the LFSR state. So, various forms of nonlinear feedback shift register (NLFSR) like Nonlinear combiner generator, Nonlinear feedforward generator, Clock control generator are used as a keystream generator to resist BMA attack. But LFSRs are slow in smartphone, PC, embedded system applications with respect to word oriented operation. So word oriented PRNG’s like RC4, SOBER, SNOW, SNOW 2.0 etc. came to the market to serve the purpose of PRNG. The important factor in word oriented LFSR is primitive polynomial over extension field. These papers [14, 15, 16] are a good source of materials to study primitive polynomials over extension field.

Let $b$ be the number of $m$ input output delay blocks ($D_0,D_1,\cdots ,D_b$ where each $D_i\in {\mathbb{F}}_2^m$) and gain matrices $B_0,B_1,\cdots ,B_{b-1}\in {\mathbb{F}}_2^{m\times m}$ of a multi-input multi-output LFSR(MIMO LFSR). Initial state of the MIMO LFSR is of $\mathit{mb}$ bits. The state update function of a $\sigma -$LFSR, $A_{\mathit{mb}}$ is defined as:

$$A_{\mathit{mb}}=\left[\begin{array}{ccccc}0& I& 0& \cdots & 0\\ 0& 0& I& \cdots & 0\\ ⋮& ⋮& ⋮& \cdots & ⋮\\ 0& 0& 0& \cdots & I\\ B_0& B_1& B_2& \cdots & B_{b-1}\end{array}\right]\in {\mathbb{F}}_2^{\mathit{mb}\times \mathit{mb}}$$

where $0,I\in {\mathbb{F}}_2^{m\times m}$ are all zero and identity matrix respectively. The characteristic polynomial of $A_{\mathit{mb}}$,

$$f\left(x\right)=x^n+B_{b-1}{x}^{n-1}+B_{b-2}{x}^{n-2}+\cdots +B_0$$E2

is called a primitive polynomial over ${\mathbb{F}}_{2^m}$ if periodicity of the polynomial is $2^{\mathit{mb}}-1$. Primitive MIMO LFSR is a good PRNG as the keystreams generated from it satisfy balancedness, span-n, 2-level autocorrelation property according to Golomb’s randomness criterion. But only LFSR cannot be used as a PRNG due to small linear complexity. Linear complexity is the length of the smallest linear feedback shift register which can generate the sequence. To increase the linear complexity, nonlinear functions are used in PRNG along with LFSR (Figure 1).

Figure 1.

Word oriented LFSR based Encryption.

Substituation Box (S-Box): An S-Box or substitution box $f$ is a vectorial Boolean function [17] which is defined as follows:

$$f:{\mathbb{F}}_{2^n}\to {\mathbb{F}}_{2^n}$$

It is nothing but the permutation of $n$ elements from one set to another. We can represent $f$ as ($f_1,f_2,\cdots ,f_n$) where each $f_i$ is the component Boolean function [18] of the S-box.

$$f_i:V_n\to {\mathbb{F}}_2$$

There are $n!$ S-box’es for a set of $n$ elements. We can categorize S-boxes into two section.

1. Affine S-box: If all the component functions are affine functions.

2. Non Affine S-box: If at least one component function is nonlinear function.

In cryptology, researchers are interested on Non affine S-boxes whose all component functions are nonlinear. S-box should have good cryptographic characteristics such as balancedness, good nonlinearity, resiliency, optimal algebraic immunity, good differential uniformity [19].

Example 2. One of the S-boxes used in DES(Data Encryption Standard) is:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7

There are four boolean function with respect to this S-box. Their Algebraic Normal Form(ANF) are:

1. $f_1:$$y{0}^{\ast }y{1}^{\ast }y3+y{0}^{\ast }y2+y{0}^{\ast }y3+y1+y3$

2. $f_2:$$y{0}^{\ast }y1+y{0}^{\ast }y{2}^{\ast }y3+y{0}^{\ast }y2+y{0}^{\ast }y3+y0+y{1}^{\ast }y{2}^{\ast }y3+$$y{1}^{\ast }y2+y{1}^{\ast }y3+y1+y{2}^{\ast }y3+1$

3. $f_3:$$y{0}^{\ast }y{1}^{\ast }y3+y{0}^{\ast }y1+y{0}^{\ast }y{2}^{\ast }y3+y0+y{1}^{\ast }y{2}^{\ast }y3+$$y{1}^{\ast }y2+y{1}^{\ast }y3+y{2}^{\ast }y3+y3+1$

4. $f_4:$$y{0}^{\ast }y{1}^{\ast }y3+y{0}^{\ast }y1+y{0}^{\ast }y2+y{1}^{\ast }y3+y2+y3+1$

4. SNOW 1.0 KSG

In this section, we demonstrate SNOW 1.0 Keystream generator and various attacks possible on it (Figure 2).

Figure 2.

Block Diagram of SNOW 1.0.

SNOW 1.0 consists of two parts as LFSR part and FSM part. The LFSR of SNOW 1.0 has 16 delay blocks ${\mathit{St}}_i$, each can store 32 values. It means ${\mathit{St}}_i\in {\mathbb{F}}_{2^{32}}$. The LFSR has a primitive feedback polynomial over ${\mathbb{F}}_{2^{32}}$ which is

$$p\left(y\right)=y^{16}+y^{13}+y^7+\alpha$$E3

where $\alpha$ is the generating element of ${\mathbb{F}}_{2^{32}}$. The irreducible polynomial $f\left(y\right)$ used to generate ${\mathbb{F}}_{2^{32}}$ as an ideal is $f\left(y\right)=y^{32}+y^{29}+y^{20}+y^{15}+y^{10}+y+1$ such that $f\left(\alpha \right)=0.$

$${\mathbb{F}}_{2^{32}}=\raisebox{1ex}{${\mathbb{F}}_2\left[y\right]$}\!\left/ \!\raisebox{-1ex}{$f\left(y\right)$}\right.$$

The FSM (Finite State Machine) part comprised of registers $\mathit{Reg}1$, $\mathit{Reg}2\in {\mathbb{F}}_{2^{32}}$ and substitution box $S$,

$$\begin{array}{c}\mathit{Fm}:{\left\{0,1\right\}}^{32}\times {\left\{0,1\right\}}^{32}\to {\left\{0,1\right\}}^{32}\\ {\mathit{Fm}}_t=\left({\mathit{St}}_{t+i}⊞\mathit{Reg}{1}_t\right)\oplus \mathit{Reg}{2}_t\end{array}$$E4

Here, $⊞$ operator is integer addition modulo $2^{32}$ such as $x⊞y=\left(x+y\right)\left(mod{2}^{32}\right)$. In the FSM the registers are updated as follows.

$$\begin{array}{c}\mathit{Reg}{1}_{t+1}=\left(\left(\mathit{Fm}⊞\mathit{Reg}{2}_t\right)⋘\right)\oplus \mathit{Reg}{1}_t\end{array}$$E5

$$\mathit{Reg}{2}_{t+1}=S\left(\mathit{Reg}{1}_t\right)$$E6

The S-box $S$ operation acts as follows (Figure 3). The input y is broken into 4 bytes. Each of the bytes are changed to another byte by a nonlinear mapping from 8 to 8 bits. The nonlinear mapping is

Figure 3.

Block Diagram of SNOW 2.0.

$$x=Y^7\oplus {\beta }^2\oplus \beta \oplus 1$$E7

where x is output of nonlinear map, Y is the input and both considered to be representing elements $\in {\mathbb{F}}_{2^8}$ with the polynomial basis $\left\{{\beta }^7\cdots \beta ,1\right\}$. $\beta$ is the root of the irreducible polynomial $h\left(y\right)=y^8+y^5+y^3+y+1$ such that $h\left(\beta \right)=0$. The nonlinear mapping followed by a permutation of the bits in the output word.

4.1 SNOW 1.0 algorithm

In this section, we demonstrate the working nature of SNOW 1.0. It starts with Initialization, LFSRupdate, FSMupdate and finally ends with SNOW 1.0 algorithm.

Algorithm 1: Initialization().

Input: Key $K=\left(k_1,\cdots ,k_8\right)\in {\mathbb{F}}_{2^{256}}$ where each $k_i\in {\mathbb{F}}_{2^{32}}$ and Initialization vector $\mathit{IV}=\left({\mathit{IV}}_2,{\mathit{IV}}_1\right)\in {\mathbb{F}}_{2^{64}}$ where each ${\mathit{IV}}_2,{\mathit{IV}}_1\in {\mathbb{F}}_{2^{32}}$.

1: $\left({\mathit{St}}_t,\cdots ,{\mathit{St}}_{t+15}\right)\leftarrow (k_1\oplus {\mathit{IV}}_1,k_2,k_3,k_4\oplus {\mathit{IV}}_2,k_5,k_6,k_7,k_8,k_1\oplus 1,k_2\oplus 1,k_3\oplus 1,k_4\oplus 1,$

$k_5\oplus 1,k_6\oplus 1,k_7\oplus 1,k_8\oplus 1)$

2: $\left(\mathit{Reg}{1}_t,\mathit{Reg}{2}_t\right)\leftarrow \left(0,0\right)$

3: for all$t\leftarrow 1$ to $32$do

4: ${\mathit{Fm}}_t\leftarrow \left(\mathit{Reg}{1}_t⊞{\mathit{St}}_t\right)\oplus \mathit{Reg}{2}_t$

5: $\mathit{\text{FSMupdate}}\left(\right)$

6: $\mathit{\text{LFSRupdate}}\left(\right)$

7: $\left({\mathit{St}}_t,\cdots ,{\mathit{St}}_{t+15}\right)\leftarrow \left({\mathit{St}}_t,\cdots ,{\mathit{St}}_{t+15}\right)\oplus {\mathit{Fm}}_t$

8: end for

Algorithm 2: FSMupdate().

Input:${\mathit{St}}_t,{\mathit{Fm}}_t$

Output: Output of the FSM ${\mathit{Fm}}_t$ at time $t$. [19]

1: ${\mathit{Fm}}_t\leftarrow \left(\mathit{Reg}{1}_t⊞{\mathit{St}}_t\right)\oplus \mathit{Reg}{2}_t$

2: $\mathit{Reg}{1}_{t+1}=\left(\left({\mathit{Fm}}_t⊞\mathit{Reg}{2}_t\right)⋘\right)\oplus \mathit{Reg}{1}_t$

3: $\mathit{Reg}{2}_{t+1}=S\left(\mathit{Reg}{1}_t\right)$

4: $\mathit{Reg}{1}_t=\mathit{Reg}{1}_{t+1}$

5: $\mathit{Reg}{2}_t=\mathit{Reg}{2}_{t+1}$

Algorithm 3: LFSRupdate()

1: $\mathit{\text{temp}}=\alpha \left({\mathit{St}}_t\oplus {\mathit{St}}_{t+3}\oplus {\mathit{St}}_{t+9}\right)$

2: $\left({\mathit{St}}_t,\cdots ,{\mathit{St}}_{t+15}\right)\leftarrow \left(\mathit{\text{temp}},{\mathit{St}}_t,\cdots ,{\mathit{St}}_{t+14}\right)$

Algorithm 4 SNOW 1.0().

Input:$K,\mathit{IV}$

Output: Keystream $z_t$ at time t.

1: $\mathit{\text{Initialization}}\left(K,\mathit{IV}\right)$

2: $t\leftarrow 1$

3: while$t\le \mathit{\text{GivenNumber}}$do

4: $z_t={\mathit{Fm}}_t\oplus {\mathit{St}}_t$

5: $\mathit{\text{FSMupdate}}\left(\right)$

6: $\mathit{\text{LFSRUpdate}}\left(\right)$

7: Output $z_t$

8: $t\leftarrow t+1$

9: end while

4.2 Weaknesses in SNOW 1.0

1. Guess and determine attack: It is one type of key recovery attack. It [20] utilizes the relationship between internal values (recurrence relation in a shift register) and the relationship used to establish the key-stream values from the registers values. In this attack, value of some registers are guessed and then the relationships are utilized to find other internal values.

   The problem in SNOW 1.0 is the recurrence relation

   $${\mathit{St}}_{t+16}=\alpha \left({\mathit{St}}_t\oplus {\mathit{St}}_{t+3}\oplus {\mathit{St}}_{t+9}\right)$$E8

   If we square Eq. (1),

   $${\mathit{St}}_{t+32}={\alpha }^2\left({\mathit{St}}_t\oplus {\mathit{St}}_{t+6}\oplus {\mathit{St}}_{t+18}\right)$$E9

   We can find out the distance of three words between ${\mathit{St}}_t$ and ${\mathit{St}}_{t+3}$, and the distance of 6 words between ${\mathit{St}}_{t+3}$ and ${\mathit{St}}_{t+9}$. So the attacker can use $\left({\mathit{St}}_{t+i}\oplus {\mathit{St}}_{t+6+i}\right)$ as a single input to both the equation. Another aspect the use of $⋘$ operator (Circular shift operator) helps in finding relation between FSM and Reg2 (Table 2).

2. Distinguishing attack: In this kind of attack linear approximation of the nonlinear part is done first and combined with the linear part. Coppersmith et al. [21] observed that only $\alpha$ present which in ${\mathbb{F}}_{2^{32}}$. Using Frobenious automorphism ($\varphi :y\to y^{2^{32}}$) they eliminated $\alpha$ and gave a new linear relation over $\mathit{GF}\left(2\right)$.

	Data complexity	Process complexity
Guess-and-determine attack (method 1)	$\mathcal{O}\left(2^{64}\right)$	$\mathcal{O}\left(2^{256}\right)$
Guess-and-determine attack (method 2)	$\mathcal{O}\left(2^{95}\right)$	$\mathcal{O}\left(2^{100}\right)$

Table 2.

GD attack complexity.

$$p{\left(y\right)}^{2^{32}}+p\left(y\right)=y^{16\times 2^{32}}+y^{13\times 2^{32}}+y^{7\times 2^{32}}+y^{16}+y^{13}+y^7$$E10

The best linear approximation of the two consecutive round input outputs of the FSM from the following.

$$\delta ={\left({\mathit{St}}_t\right)}_{15}\oplus {\left({\mathit{St}}_t\right)}_{16}\oplus {\left({\mathit{St}}_{t+1}\right)}_{22}\oplus {\left({\mathit{St}}_{t+1}\right)}_{23}\oplus {\left({\mathit{Fm}}_t\right)}_{15}\oplus {\left({\mathit{Fm}}_{t+1}\right)}_{23}$$E11

where ${\left({\mathit{St}}_t\right)}_k$ signify k th bit of ${\mathit{St}}_0$ state of the LFSR at time $t$. The bias of the linear approximation evaluated was at least $2^{-9.3}$. And the author calculated $2^{101.6}$ rounds keystream requirement for distinguishing the output sequence from SNOW 1.0 and the sequences from true random bit generator.

5. SNOW 2.0 KSG

This section discusses all about SNOW 2.0 Keystream generator. We also mention about some cryptographic attacks on SNOW 2.0.

SNOW 2.0 is the updated KSG over SNOW 1.0. Here, the primitive polynomial over $\mathit{GF}\left(2^{32}\right)$ is chosen by studying the weakness of the primitive polynomial in SNOW 1.0. Let $\delta$ be the generating element of the primitive polynomial $f\left(y\right)=y^8+y^7+y^5+y^3+1$, such that $f\left(\delta \right)=0$ and $\alpha$ be the generator of the primitive polynomial $g\left(y\right)=y^4+{\delta }^{23}{y}^3+{\delta }^{245}{y}^2+{\delta }^{48}y+{\delta }^{239}$ such that $g\left(\alpha \right)=0$. We can represent each element in ${\mathbb{F}}_{2^{32}}$ with the help of the basis $\left\{{\alpha }^3,{\alpha }^2,\alpha ,1\right\}$. Using the above 2 extension fields the generator polynomial of SNOW 2.0

$$H\left(y\right)=\alpha y^{16}+y^{14}+{\alpha }^{-1}{y}^5+1\in {\mathbb{F}}_{2^{32}}\left[Y\right]$$E12

is calculated and the recurrence relation of $H\left(y\right)$ is as follows:

$${\mathit{St}}_{t+15}={\alpha }^{-1}{\mathit{St}}_{t+11}+{\mathit{St}}_{t+2}+\alpha {\mathit{St}}_t$$E13

where ${\mathit{St}}_t\in {\mathbb{F}}_{2^{32}}$ is the state of the first delay block in clock time $t$.

The FSM part of SNOW 2.0 is same as SNOW 1.0, except ${\mathit{St}}_{t+5}$ is used as a input to the FSM. It makes more dependency of state vectors to the FSM. We can evaluate the FSM ${\mathit{Fm}}_t$ as:

$${\mathit{Fm}}_t=\left({\mathit{St}}_{t+15}⊞\mathit{Reg}{1}_t\right)\oplus \mathit{Reg}{2}_t$$E14

and the keystream $z_t$ is given by

$$z_t={\mathit{Fm}}_t\oplus {\mathit{St}}_t$$E15

The updation of registers $\mathit{Reg}{1}_{t+1}$, $\mathit{Reg}{2}_{t+1}$ from $\mathit{Reg}{1}_t$, $R{2}_t$ are related as follows:

$$\mathit{Reg}{1}_{t+1}={\mathit{St}}_{t+4}⊞\mathit{Reg}{2}_t$$E16

$$\mathit{Reg}{2}_{t+1}=S\left(\mathit{Reg}{1}_t\right)$$E17

Here S is the S-box which takes 4 bytes ($b_0,b_1,b_2,b_3$) as input and uses AES S-box followed by mixcolumn operation to output 4 bytes.

$$\left[\begin{array}{c}{b}_0^{t+1}\\ b_1^{t+1}\\ b_2^{t+1}\\ b_3^{t+1}\end{array}\right]=\left[\begin{array}{cccc}X& X+1& 1& 1\\ 1& X& X+1& 1\\ 1& 1& X& X+1\\ X+1& X& 1& 1\end{array}\right]\left[\begin{array}{c}S\left(b_0^t\right)\\ S\left(b_1^t\right)\\ S\left(b_2^t\right)\\ S\left(b_3^t\right)\end{array}\right]$$E18

In the above equation, the matrix used is for Mixcolumn operation where the value in $X\in F_{2^8}$ and the S-box $S:{\mathbb{F}}_{2^8}\to {\mathbb{F}}_{2^8}$ is a permutation function used in SubByte step defined as:

$$S\left(y\right)=\left\{\begin{array}{ll}0,& \mathbf{\text{if}}y=0\\ y^{-1},& \forall y\in {\mathbb{F}}_2^8-\left\{0\right\}\end{array}\right.$$

5.1 Key initialization

In SNOW 2.0128 bits or 256 bits key (K) and a initialization vector IV (public) is used. The $\mathit{IV}\in \left\{0,1,\cdots ,2^{128}-1\right\}$ and the two memory registers are set to 0. The cipher is then clocked 32 times where no keystream is produced and the FSM output is feeded as following:

$${\mathit{St}}_{t+15}={\alpha }^{-1}{\mathit{St}}_{t+11}\oplus {\mathit{St}}_{t+2}\oplus \alpha {\mathit{St}}_t\oplus {\mathit{Fm}}_t$$E19

The cipher is then switched into the normal mode, but the first output of the keystream is discarded. After $2^{50}$ keystream the cipher’s key $K$ is changed to a new value for resisting from cryptanalysis.

5.2 SNOW 2.0 algorithm

In this section, we describe the working principle of SNOW 2.0 algorithm which consists of Initialization, LFSRupdate, FSMupdate.

Algorithm 5: Initialization().

Input: Key $K=\left(k_0,\cdots ,k_7\right)\in {\mathbb{F}}_{2^{256}}$ where each $k_i\in {\mathbb{F}}_{2^{32}}$ and Initialization vector $\mathit{IV}=\left({\mathit{IV}}_3,{\mathit{IV}}_2,{\mathit{IV}}_1,{\mathit{IV}}_0\right)\in {\mathbb{F}}_{2^{128}}$ where each ${\mathit{IV}}_i\in {\mathbb{F}}_{2^{32}}$.

1: $\left({\mathit{St}}_t,\cdots ,{\mathit{St}}_{t+15}\right)\leftarrow (k_0\oplus 1,k_1\oplus 1,k_2\oplus 1,k_3\oplus 1,k_4\oplus 1,k_5\oplus 1,k_6\oplus 1,k_7\oplus 1,k_0,k_1\oplus {\mathit{IV}}_3,$

$k_2\oplus {\mathit{IV}}_2,k_3,k_4\oplus {\mathit{IV}}_1,k_5,k_6,k_7\oplus {\mathit{IV}}_0)$

2: $\left(\mathit{Reg}{1}_t,\mathit{Reg}{2}_t\right)\leftarrow \left(0,0\right)$

3: for all$t\leftarrow 1$ to $32$do

4: ${\mathit{Fm}}_t\leftarrow \left(\mathit{Reg}{1}_t⊞{\mathit{St}}_{t+15}\right)\oplus \mathit{Reg}{2}_t$

5: $\mathit{\text{FSMupdate}}\left(\right)$

6: $\mathit{\text{LFSRupdate}}\left(\right)$

7: $\left({\mathit{St}}_t,\cdots ,{\mathit{St}}_{t+15}\right)\leftarrow \left({\mathit{St}}_t,\cdots ,{\mathit{St}}_{t+15}\right)\oplus {\mathit{Fm}}_t$

8: end for

Algorithm 6: FSMupdate()

(Input)${\mathit{St}}_{t+15},{\mathit{St}}_{t+5}$

Output: Output of the FSM ${\mathit{Fm}}_t$ at time $t$.

1: ${\mathit{Fm}}_t\leftarrow \left(\mathit{Reg}{1}_t⊞{\mathit{St}}_{t+15}\right)\oplus \mathit{Reg}{2}_t$

2: $\mathit{Reg}{1}_{t+1}={\mathit{St}}_{t+5}⊞\mathit{Reg}{2}_t$

3: $\mathit{Reg}{2}_{t+1}=\mathit{St}\left(\mathit{Reg}{1}_t\right)$

4: $\mathit{Reg}{1}_t=\mathit{Reg}{1}_{t+1}$

5: $\mathit{Reg}{2}_t=\mathit{Reg}{2}_{t+1}$

Algorithm 7: LFSRupdate()

1: $\mathit{\text{temp}}={\alpha }^{-1}{\mathit{St}}_{t+11}\oplus {\mathit{St}}_{t+2}\oplus \alpha {\mathit{St}}_t$

2: $\left({\mathit{St}}_{t+15},\cdots ,{\mathit{St}}_t\right)\leftarrow \left(\mathit{\text{temp}},{\mathit{St}}_{t+15},\cdots ,{\mathit{St}}_{t+1}\right)$

Algorithm 8: SNOW 2.0()

Input:$K,\mathit{IV}$

Output: Keystream $z_t$ at time t.

1: $\mathit{\text{Initialization}}\left(K,\mathit{IV}\right)$

2: $t\leftarrow 1$

3: while$t\le 2^{50}$do

4: $z_t=F_t\oplus S_t$

5: $\mathit{\text{FSMupdate}}\left(\right)$

6: $\mathit{\text{LFSRUpdate}}\left(\right)$

7: Output $z_t$

8: $t\leftarrow t+1$

9: end while

5.3 Cryptographic attack on SNOW 2.0

5.3.1 Distinguishing attack

In this kind of attack a distinguisher algorithm is constructed to distinguish the output keystream from a PRNG and same length output from a true random number generator. If the distinguishing algorithm complexity is less than the brute force search algorithm, this is called an attack on the cipher.

1. Watanabe et al. [21] 2003 used linear masking method to distinguish the output of SNOW 2.0 from a TRNG. Basically it tries to find out linear relation between the output of the keystream with FSM and LFSR. SO to serve this purpose we need to find a mask $\mathcal{T}\in {\mathbb{F}}_{2^{32}}$ with high bias such that

   $$\mathcal{T}{\mathit{St}}_{t+16}\oplus \left(\mathcal{T}.{\alpha }^{-1}\right).{\mathit{St}}_{t+11}\oplus \mathcal{T}{\mathit{St}}_{t+2}\oplus \left(\mathcal{T}\alpha \right).{\mathit{St}}_t=0$$E20

   holds. The 2 rounds approximation of FSM

   $${\mathcal{T}}_0{\mathit{St}}_t\oplus {\mathcal{T}}_1{\mathit{St}}_{t+1}{\mathcal{T}}_5{\mathit{St}}_{t+5}\oplus {\mathcal{T}}_{15}{\mathit{St}}_{t+15}\oplus {\mathcal{T}}_{16}{\mathit{St}}_{t+16}={\mathcal{T}}_0{z}_t\oplus {\mathcal{T}}_1{z}_{t+1}$$E21

   with assumption that all the masks values are same, becomes possible of two nonlinear approximation such as S-box and the three $⊞$ operator,

   $$\mathcal{T}S\left(X\right)=\mathcal{T}X$$E22
   $$\mathcal{T}\left(X⊞y\right)=\mathcal{T}X\oplus \mathcal{T}y$$E23

   The bias of the total approximation can be found with complexity $\mathcal{O}\left(2^{-112.25}\right)$. So we need about $2^{225}$ words to distinguish SNOW 2.0 from true random bit sequence.

2. In 2006 FSE, Nyberg et al. [22] improved this attack by approximating FSM (Finite state machine) and output of the cipher with different linear mask ($\mathcal{T},\lambda \in {\mathbb{F}}_2^{32}$)

$$\mathcal{T}F\left(x\right)=\mathit{\lambda x}$$E24

$$\mathcal{T}\left(z_{t+16}\oplus z_{t+2}\right)\oplus \mathcal{T}\alpha .z_t\oplus \mathcal{T}{\alpha }^{-1}.z_{t+11}\oplus \lambda \left(z_{t+17}\oplus z_{t+3}\right)\oplus \mathit{\lambda \alpha }.z_{t+1}\oplus {\mathit{\lambda \alpha }}^{-1}.z_{t+12}=0$$E25

measured the bias of the above relation with correlation ($\mathcal{T},\lambda$) which is defined as:

$$\mathit{\text{correlation}}\left(\mathcal{T},\lambda \right)=\left(\#\left\{x\in {\mathbb{F}}_2^{32}:\mathcal{T}F\left(x\right)=\mathit{\lambda x}\right\}-\#\left\{x\in {\mathbb{F}}_2^{32}:\mathcal{T}F\left(x\right)!=\mathit{\lambda x}\right\}\right)$$E26

They also investigated the diffusion property of Mixcolumn, improved the search complexity of linear distinguishing attack.

5.3.2 Correlation attack

In correlation attack [23] over extension field, the correlation of output keystream with the LFSR output is calculated for a particular $N$ (# available words). If the correlation or bias value is far greater than $\frac{1}{2^n}$, we find linear relation between input and output and also find out the initial state of the LFSR. It is also one kind of key recovery attack. Another kind of correlation attack is Fast Correlation attack [24] where the each output of a keystream $z_i$ is written as:

$$z_i=u_i+e_i$$E27

$u_i$ is the output of the LFSR and $e_i$ is considered as error in the discrete memoryless channel which is the nonlinear function attached with LFSR. So, finding initial state of the LFSR is equivalent of solving the decoding problem in error correcting code. We consider LFSR as $\left(N,l\right)$ linear code, where $l$ is the size of the LFSR.

1. In 2008, Lee et al. [9], in Asiacrypt 2008 presented more improved result with second LFSR derivation technique to mount correlation attack with time complexity $\mathcal{O}\left(2^{212.38}\right)$, space complexity $\mathcal{O}\left(2^{202.83}\right)$ bits and data complexity $\mathcal{O}\left(2^{197.77}\right)$ bits to find out the initial state of SNOW 2.0 LFSR.

2. In 2015, Bin Zhang et al. [25] published paper on Fast correlation attack on SNOW 2.0 over extension field to find out the initial state of the LFSR with data complexity $\mathcal{O}\left(2^{163.59}\right)$, time complexity $\mathcal{O}\left(2^{164.15}\right)$ which is $2^{49}$ times faster than the previous one.

3. In 2018, Funabiki et al. [26] updated the FCA attack on SNOW 2.0 by using a MILP aided search for the linear mask very efficiently. It also uses the k-tree algorithm in [25] to find the key of SNOW 2.0 in data complexity $\mathcal{O}\left(2^{162.34}\right)$ and time complexity $\mathcal{O}\left(2^{162.92}\right)$.

4. In 2020, Gond et al. [27] published their work on FCA on SNOW 2.0 by slightly modifying the idea of k-tree algorithm. It finds the key of SNOW 2.0 in data complexity $\mathcal{O}\left(2^{159.62}\right)$ and time complexity $\mathcal{O}\left(2^{162.86}\right)$.

Theorem 6.1 The carry bit $c_i$ in the addition $X⊞Y=Z$ is equal to zero with probability $\frac{1}{2}+\frac{1}{2^{i+1}}$.

5.3.3 Algebraic attack

Any stream cipher can be expressed with respect to algebraic equations where the variables of the equations are nothing but the initial state of the LFSR. We know that the challenge is to solving system of nonlinear equations with respect to the keystreams available to the us. It is well known to us that Solving such system of nonlinear equations over finite field is NP-Hard problem. But there are some approaches in the literature to mount algebraic attack like linearization, Grobner basis, Finding low degree annihilators [28] of a Boolean function etc.

In 2005, [29] Olivier Billet et. el cryptanalyzed SNOW 2.0 with algebraic attack like following:

1. Assuming $⊞$ in the cipher as $\oplus$ operation, the equations at time stamp $t$ help in mounting algebraic attack:

$$\mathit{Reg}{2}_t=\mathit{Reg}{2}_0+\sum _{i=0}^t{z}^i+\sum _{i=0}^t\left({\mathit{St}}_{4+i}+{\mathit{St}}_{15+i}+{\mathit{St}}_i\right)$$E28

where only known information is output keystreams($z$).

$$\mathit{Reg}{2}_{t+1}=S\left(\mathit{Reg}{1}_t\right)$$E29

$$=S\left(\mathit{Reg}{2}_t+z^t+{\mathit{St}}_{15+t}+{\mathit{St}}_t\right)$$E30

From each S-boxes we can find 39 linearly independent equations, So total $39\times 4=156$ quadratic equations can be found from equation (11) for one keystream. The authors took linearization as a tool to make ${\sum }_{i=0}^2\left(\begin{array}{c}544\\ i\end{array}\right)\approx 2^{17}$ many unknown variables. The equations can be solved using Graobner basis with the help of about less than 17 keystreams. It results to find the initial state of the cipher with time complexity $\mathcal{O}\left(2^{51}\right)$.

5.3.4 Guess and determining attack

In this kind of attack, the attacker first assumes the value of some registers and determine the value of the rest registers following the guesses. Later, keystream is generated from the cipher. If the keystream is equal to the keystream found by known keystream, the guess is a valid one. The terminology for the minimum guessed values of the cipher is called guessed basis. First systematic algorithm was proposed by Ahmadi et al. [30] which was a Viterbi like algorithm. Guessed basis for this algorithm was 8 and time complexity of the algorithm is $\mathcal{O}\left(2^{265}\right)$. The next updated result is found from the article [31] which uses two auxiliary equations. Moreover, the guessed basis for this result is 6 and time complexity of the algorithm is $\mathcal{O}\left(2^{192}\right)$.

5.4 KDFC SNOW

To resist from Algebraic attack, another version of SNOW 2.0 called Key dependent feedback configuration (KDFC) SNOW is proposed in [32]. It replaces the LFSR over ${\mathcal{F}}_{2^{32}}$ by $\sigma -$LFSR over $M_{32}\left(F_2\right)$. Moreover, it also implements the idea of different feedback matrices [33] for the $\sigma -$LFSR based on the key of the cipher. The whole process of changing the existing feedback matrix is done on the initialization phase of the cipher (Figure 4).

Figure 4.

Block diagram of KDFC-SNOW.

KDFC Scheme hides the feedback matrix of the $\sigma -$LFSR which helps the SNOW 2.0 to resist from some known plaintext attacks like Algebraic attack, Distinguishing Attack, Some Fast correlation attacks, Guess and Determining Attacks.

6. SNOW 3G KSG

SNOW 3G is an updated version of SNOW 2G. To get resistance from Algebraic Attack on SNOW 2.0, this cipher is proposed. It is used in mobile telephony for 4G and 5G communication as authenticated encrypted word oriented stream cipher in UEA2 and UIA2. The basic building block of SNOW 3G is as follows (Figure 5):

Figure 5.

Block diagram of SNOW 3G.

The LFSR configuration of SNOW 3G is as same as SNOW 2.0. The only changes are in the FSM configuration. One extra register R3 and extra Sbox is proposed by the designer. We discuss only the FSM construction of SNOW 3G in the following paragraph.

FSM: The FSM of SNOW 3G consists of two input words ${\mathit{St}}_{15}$ and ${\mathit{St}}_5$. It generates a 32-bit output word FW.

$$\mathit{Fw}=\left({\mathit{St}}_{15}⊞R1\right)\oplus {\mathit{St}}_5$$E31

On the next step, the registers are updated. To do so, we calculate one value $r$ like following:

$$r=R2⊞\left(R3\oplus {\mathit{St}}_5\right)$$E32

Next, we update the registers

$$R3=\mathit{\text{SBox}}2\left(R2\right)$$E33

$$R2=\mathit{\text{SBox}}1\left(R1\right)$$E34

$$R1=r$$E35

SBox1: This Sbox is same as the Sbox described in SNOW 2.0.

SBox2: The SBox2 (S2 in Eq. (23)) is constructed using the Dickson polynomial. It is defined as an element of $\mathit{GF}\left(2^8\right)$ which is generated by $x^8+x^6+x^5+x^3+1$. Suppose $b_i\in \mathit{GF}\left(2^8\right)$, using that we find an $32-$bits inputs $b=b_1\Vert b_2\Vert b_3\Vert b_4$ which is given as a input to the SBox2. It works as the following:

$$\left[\begin{array}{c}{b}_0^{t+1}\\ b_1^{t+1}\\ b_2^{t+1}\\ b_3^{t+1}\end{array}\right]=\left[\begin{array}{cccc}Y& Y+1& 1& 1\\ 1& Y& Y+1& 1\\ 1& 1& Y& Y+1\\ Y+1& Y& 1& 1\end{array}\right]\left[\begin{array}{c}S2\left(b_0^t\right)\\ S2\left(b_1^t\right)\\ S2\left(b_2^t\right)\\ S2\left(b_3^t\right)\end{array}\right]$$E36

Here, $Y\in \mathit{GF}\left(2^8\right)$ and the matrix of Y and 1 is used for mixcolumn transformation.

6.1 Cryptographic attack on SNOW 3G

6.1.1 Fault attack on SNOW 3G

In this attack [8, 34] the attacker has a access of the physical device and it can cause transient fault attack on the device. In this kind of fault attack, the attacker can reset the device to its original state and apply a fault to the same device to get new keystream. The attacker can find the secret key of the cipher by verifying the faulty keystream and the actual keystream.

In SNOW 3G KSG, fault is injected between two computations of the following registers:

• Register $R{1}^t$.

• Register $R{2}^t$.

• LFSR state ${\mathit{St}}_0^t$.

We need to keep track that we consider the memory locations of $R{1}^{t+1}$, $R{2}^{t+1}$, ${\mathit{St}}_{15}^{t+1}$ after computation of a new word. Next we can find out $X_t\oplus X_{t^{\prime }}$ which can give value either 1 or 0 for a certain fault injected positions, where $X_t$ denotes the value the above mentioned registers in RAM and $X_{t^{\prime }}$ is the faulty valued of the registers. We also verify the $Z_t\oplus Z_{t^{\prime }}$ value to get the confirmation of the fault occurrence. Finally, the state of the LFSR of SNOW 3G can be found by at least 24 fault injections and solving 512 linear equation by Gaussian elimination.

Note: Besides, all the attacks on SNOW 2.0 written before except algebraic attacks are also performed on SNOW 3G. It results SNOW 3G as a 128-bit secure cipher.

In Table 3, we enlist the attacks possible on SNOW 1.0, SNOW 2.0 and SNOW 3G.

	Distinguishing attack	Algebraic attack	Fast correlation attack	Guess and determining attack	Fault attack
SNOW 1.0	✓	$X$	$X$	✓	$X$
SNOW 2.0	✓	✓	✓	✓	✓
SNOW 3G	✓	$X$	✓	✓	✓

Table 3.

Various attacks on SNOW 1.0, SNOW 2.0, SNOW 3G.

7. Implementation issues

7.1 Vector-vector multiplication over ${\mathcal{F}}_{2^{32}}$

Whole SNOW family of ciphers use LFSR with $y^{\ast }\beta$ operation over ${\mathcal{F}}_{2^{32}}$ where $\beta$ is a primitive element of $\mathcal{G}\mathcal{F}\left(2^{32}\right)$. SNOW 2.0 and SNOW 3G uses the following approach:

$$y.\beta =\left(y\ll 8\right)\oplus \mathit{\text{Table}}\left(y\gg 24\right)$$E37

Here, Table(x) function takes 8-bit vector as input and return 32-bit vector as output. It can be described as follows:

$$\mathit{\text{Table}}\left(x\right)=F_1\left(x\mathrm{,23,0}\mathit{xA}9\right)\Vert F_1\left(x\mathrm{,245,0}\mathit{xA}9\right)\Vert F_1\left(x\mathrm{,48,0}\mathit{xA}9\right)\Vert F_1\left(x\mathrm{,239,0}\mathit{xA}9\right)$$E38

where $0\mathit{xA}9$ is the hexadecimal representation of the primitive polynomial $x^8+x^7+x^5+x^3+1$ over ${\mathcal{F}}_2$, $F_1$ is a function which takes 16 bit inputs and positive integer $i$ to 8-bit vector. $F_1\left(W,i,x\right)=W$ if $i==0$ and $F_1\left(W,i,x\right)=F_2\left(F_1\left(W,i-1,x\right),x\right)$, otherwise, where $W,x\in {\mathcal{F}}_2^8$. And $F_2\left(W,x\right)=\left(W{\ll }_{8}1\right)\oplus x$ if leftmostbit(W)==1, else $F_2\left(W,x\right)=\left(W{\ll }_{8}1\right)$. $F_2$ is a function which takes two $8-$ bit inputs and gives 8- bit output. This whole procedure reduces the time complexity of vector-vector multiplication over finite field to $\mathcal{O}\left(1\right)$ complexity.

7.2 Addition modulo $2^{32}(⊞$)

Let us take two vectors $P,Q\in {\mathcal{F}}_2^{32}$ and addition modulo $2^{32}$ is defined as follows:

$$P⊞Q=\left(P+Q\right)\left(mod{2}^{32}\right)=\left(P+Q\right)\&\left(0\mathit{\text{xFFFFFFFF}}\right)$$E39

Here, $+$ is normal addition and & is bitwise AND-operator.

8. Conclusion

In this article, we can observe that SNOW 1.0 has problems in its design regarding the ${⋘}_7$ shift operator. The interaction between the ${⋘}_7$ shift operator and the S-box is one of the reasons for the large correlation in the FSM. Besides, the S-box used in SNOW 1.0 is not up to the mark. So, changing the S-box with Rijndael improves its power [35] against Guess and Distinguishing attack. In this context, SNOW 2.0 is better than SNOW 1.0 with respect to the design issues and cryptographic attacks. Still, it is susceptible to several attacks. Among all the attacks, the best-known attack is Algebraic Attack [29] which is taken care in the upgraded version SNOW 3G. A new S-Box and another Register are introduced in SNOW 3G to circumvent the problems in SNOW 2.0. Besides, the only practical attack possible for SNOW 2.0 and SNOW 3G is Fault Attack [8, 34] which is possible if someone access the memory location of the SNOW algorithm. This results SNOW 3G to be used in mobile telephony with 128 bit security. Though, KDFC-SNOW is another approach which is also potential candidate to resist some known plaintext attacks on SNOW 2.0, it requires some research on the implementation issue in the initialization phase. Besides, KDFC-SNOW cannot resist the recent fast correlation attack by Gond et al. [27] on SNOW 2.0. A possible research towards the improvement of SNOW family may be the finding an word LFSR with 64- or 128-bit block size with 256 bit key security which would be beneficial in 5G communication. Also, resistance of Fast Correlation Attack may be another kind of research which can be taken as future study.