# Quantum Time-Memory-Data Tradeoff Attacks on the SNOW-V Stream Cipher
## 2 Brief Description of SNOW-V  
The SNOW-V stream cipher supports a 256-bit key and a 128-bit initialization vector (IV). It has a large internal state size of 896 bits and outputs 128 bits at each clock. It is built around two components, i.e., two linear feedback shift registers of length 16, over the field \(GF\big{(}2^{16}\big{)}\), and a non-linear finite-state machine (FSM), with three 128-bit registers. Figure 1 gives a diagrammatic representation of the SNOW-V stream cipher. In Figure 1, the symbol \(\oplus\) denotes a bitwise XOR operation, and the symbol \(\boxplus_{32}\) denotes a parallel application of four additions modulo \(2^{32}\) over each sub-word. It should be noted that, in the operation \(\boxplus_{32}\), the four 32-bit parts of the 128-bit words are added with carry, but the carry from a lower 32-bit word to a higher is discarded. The two LFSRs are named LFSR-A and LFSR-B, both of length 16 and with a cell size of 16 bits. They use different irreducible polynomials, each feeding into the other. Denote the states of the LFSR-A and LFSR-B as \(\left(a_{15}^{(t)},\cdots,a_{0}^{(t)}\right)\) and \(\left(b_{15}^{(t)},\cdots,b_{0}^{(t)}\right)\), respectively, at time \(t\geq 0\). The update functions of LFSR-A and LFSR-B are given as follows. \[a_{15}^{(t+1)}=b_{0}^{(t)}\oplus aa_{0}^{(t)}\oplus a_{1}^{(t)}\oplus\alpha^{- 1}a_{8}^{(t)}\]  
\[a_{i}^{(t+1)}=a_{i+1}^{(t)},i=0,1,\cdots,14\]  
\[b_{15}^{(t+1)}=a_{0}^{(t)}\oplus b_{0}^{(t)}\oplus b_{3}^{(t)}\oplus\beta^{-1} b_{8}^{(t)}\]  
\[b_{i}^{(t+1)}=b_{i+1}^{(t)},i=0,1,\cdots,14\]  
where \(\alpha\) and \(\beta\) are roots of two different primitive polynomials over \(GF\big{(}2^{16}\big{)}\), and the notations \(\alpha^{-1}\) and \(\beta^{-1}\) are the inverses in the respective implemented fields. At each time, SNOW-V updates the two LFSRs eight times, i.e., 256 bits of the total 512-bit state will be updated in a single step. The FSM contains three 128-bit registers, denoted as \(R1^{(t)},R2^{(t)},R3^{(t)}\), at time \(t\geq 0\), which takes two blocks, \(T1\) and \(T2\), from the two LFSRs as inputs and produces a 128-bit keystream as output. The update expressions of FSM are defined as below. \[R1^{(t+1)}=\sigma\Big{(}R2^{(t)}\oplus_{32}\Big{(}R3^{(t)}\oplus T2^{(t)} \Big{)}\Big{)}\]  
\[R2^{(t+1)}=AES^{R}\Big{(}R1^{(t)},C1\Big{)}\]  
\[R3^{(t+1)}=AES^{R}\Big{(}R2^{(t)},C2\Big{)}\]  
where the block \(T2^{(t)}\) is a 128-bit word denoted as \(T2^{(t)}=\left(a_{7}^{(8t)},\cdots,a_{0}^{(8t)}\right)\), \(\sigma\) is a byte-oriented permutation given by \(\sigma\) = [ 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]. \(AES^{R}(IN,key)\) denotes the AES encryption round function, and \(C1\) and \(C2\) are two round-key constants, with values that are both fixed to be zero. Figure 1: Diagrammatic representation of the SNOW-V stream cipher. The 128-bit keystream, \(z^{(t)}\) at time \(t\geq 0\), is outputted by the following expression  
\[z^{(t)}=\left(R1^{(t)}\boxplus_{32}T1^{(t)}\right)\oplus R2^{(t)}\]  
where the block \(T1^{(t)}\) is a 128-bit word denoted as \(T1^{(t)}=\left(b_{15}^{(8)},\cdots,b_{8}^{(8t)}\right)\). The SNOW-V (Algorithm 1) stream cipher has a 256-bit key \(K\) and a 128-bit initialization vector \(IV\) as inputs. Denote the key and IV as \(K=(k_{15},\cdots,k_{0})\) and \(IV=(iv_{7},\cdots,iv_{0})\), and each \(k_{i}(0\leq i\leq 15)\) and \(iv_{j}(0\leq j\leq 7)\) is a 16-bit vector. The first step of the initialization is to load the key and IV into the two LFSRs, by assigning \(\left(a_{15}^{(0)},\cdots,a_{0}^{(0)}\right)=(k_{7},\cdots,k_{0},iv_{7},\cdots,iv_{0})\) and \(\left(b_{15}^{(0)},\cdots,b_{0}^{(0)}\right)=(k_{15},\cdots,k_{8},0,\cdots,0)\). Then, the cipher is clocked 16 times in the same way as in the running-key mode, with the exception being that the 128-bit output \(z^{(t)}\) is not outputted while XORed into LFSR-A at each clock. Note that at the two last clocks of initialization, the key is XORed into the \(R1\) register, again.