On the uniqueness of a type of cascade connection representations for NFSRs

Abstract

Cascade connection architectures of nonlinear feedback shift registers (NFSRs) have been widely used in cryptography. In particular, the Grain family of stream ciphers uses the cascade connection architecture of an LFSR into an NFSR. A cascade connection representation is not always unique. The nonuniqueness of the representation may threat the security of a cipher. Inspired by the Grain family of stream ciphers, in this paper, we focus on cascade connections of an LFSR into an NFSR. A necessary and sufficient condition for the uniqueness of this class of cascade connection representations is provided under a reasonable condition that the involved NFSR has only trivial cascade connection decompositions. In particular, as a direct application of new results, it is theoretically proved that the cascade connection representation of a Grain-like structure, an n-bit primitive LFSR into an n-bit NFSR with a positive integer n, is unique not considering some trivial distinct representations if the involved n-bit NFSR satisfies the condition. Besides, it is verified that all the main registers used in the Grain family of stream ciphers satisfy the condition.

Appendices

Appendix A

Let

$$\begin{aligned} f_1= & {} x_2\oplus x_1 \oplus x_0, \\ f_2= & {} x_3\oplus x_1x_2 \oplus x_0, \\ f_3= & {} x_4 \oplus x_1x_3\oplus x_0 \oplus 1. \end{aligned}$$

Then

$$\begin{aligned}&f_1 *f_2 *f_3 \\&\quad = f_1 *D(f_2) *(f_3\oplus 1) \\&\quad = D(f_1) *(D(f_2)\oplus 1) *(f_3\oplus 1)\\&\quad = (x_2\oplus x_1 \oplus x_0\oplus 1)*(x_3\oplus x_1x_2\oplus x_1\oplus x_2 \oplus x_0) *(x_4 \oplus x_1x_3\oplus x_0). \end{aligned}$$

Appendix B

In this section, we shall verify that the main registers of Grain, Grain-128, and Grain-128a all satisfy the condition of Theorem 4, respectively.

1.1 Notations

Let f be a Boolean function.

• sub(f): The set of subscripts of all variables appearing in the ANF of f.

• $f_{[d]}$: The summation of all terms in T(f) with degree d. Take $g = x_0\oplus x_1x_2\oplus x_2x_3\oplus x_2x_3x_4\oplus x_5$ for example. Then $g_{[2]} = x_1x_2\oplus x_2x_3$ and $sub(g_{[2]})=\{1,2,3\}$.

• $f_{\ge [d]}$: The summation of all terms in T(f) with degree not smaller than d. For example, $g_{\ge [2]} = x_1x_2\oplus x_2x_3\oplus x_2x_3x_4$.

• $\frac{f}{x_i}$: The Boolean function p such that the summation of all terms in T(f) divisible by $x_i$ is equal to $px_i$. For example, $\frac{g}{x_3} = x_2 \oplus x_2x_4$.

1.2 Auxiliary lemmas

Lemma 4

Let $f\in \mathbb {B}^{*}$ with $\deg (f) >1$ and $g \in \mathcal {C}^{*}$. Suppose $f = f_{[1]} \oplus r \oplus s\cdot x_n$ where $n = \mathrm {ord}(f_{\ge [2]})$, $f_{\ge [2]} = r \oplus s\cdot x_n$, and $\mathrm {ord}(r)<n$. Then

$$\begin{aligned} \frac{(f*g)_{\ge [d+1]}}{x_{n+m}} = (s*g)_{\ge [d]} \end{aligned}$$

(29)

where $d = \deg (g)$ and $m=\mathrm {ord}(g)$.

Proof

Let $g = x_0\oplus g'(x_1,\ldots , x_{m-1})\oplus x_m$. Then we have

$$\begin{aligned} f*g = f_{[1]}*g \oplus r*g \oplus (s*g) \cdot (x_n \oplus g'(x_{n+1},\ldots , x_{n+m-1})\oplus x_{n+m}). \end{aligned}$$

Let us denote

$$\begin{aligned} p = r*g \oplus (s*g) \cdot (x_n \oplus g'(x_{n+1},\ldots , x_{n+m-1})\oplus x_{n+m}), \end{aligned}$$

(30)

and so

$$\begin{aligned} f*g = f_{[1]}*g \oplus p. \end{aligned}$$

Since $\deg (f_{[1]}*g)= d$ if $f_{[1]}*g\ne 0$, it follows that

$$\begin{aligned} (f*g)_{\ge [d+1]} = p_{\ge [d+1]}. \end{aligned}$$

(31)

By Corollary 3, we know that $r*g,s*g\ne 0$ if $r,s\ne 0$. Since $\mathrm {ord}(r) < n$, it follows that if $r\ne 0$, then $\mathrm {ord}(r*g) < n+m$. This and (30) lead to

$$\begin{aligned} \frac{p_{\ge [d+1]}}{x_{n+m}} = (s*g)_{\ge [d]}. \end{aligned}$$

(32)

Taking (32) into (31) completes the proof. $\square$

One may think it is possible that $(s*g)_{\ge [d]}$ in (29) equals zero. The following lemma implies that $(s*g)_{\ge [d]}=0$ will never happen and provides a useful upper bound on the degree of a right $*$-factor.

Lemma 5

Let $f\in \mathbb {B}^{*}$ and $g \in \mathcal {C}^{*}$. Then $\deg (f*g) \ge \deg (g)$ and the equality holds if and only if f is linear.

Proof

We use mathematical induction on the degree of f. If f is linear, then we have $f*g \ne 0$ by Proposition 2, and it is clear that $\deg (f*g) = \deg (g)$. Let $k\ge 2$, and suppose $\deg (f*g) \ge \deg (g)$ hold for every function $f\in \mathbb {B}^{*}$ with $\deg (f) < k$.

Next we consider the case $\deg (f)=k$. Let us write

$$\begin{aligned} f = f_{[1]} \oplus f_{\ge [2]} =f_{[1]} \oplus r \oplus s \cdot x_n, \end{aligned}$$

where $r,s\in \mathbb {B}^{*}$ and $n = \mathrm {ord}(f_{\ge [2]})$. Then by Lemma 4, we have

$$\begin{aligned} \frac{(f*g)_{\ge [d+1]}}{x_{n+m}} = (s*g)_{\ge [d]},\quad \text { where }\quad d = \deg (g)\quad \text { and }\quad m=\mathrm {ord}(g). \end{aligned}$$

(33)

Since $1\le \deg (s)<\deg (f)$, the induction hypothesis implies that

$$\begin{aligned} \deg (s*g) \ge d \end{aligned}$$

(34)

and so $(s*g)_{\ge [d]} \ne 0$. Hence (33) and (34) immediately imply that

$$\begin{aligned} \deg (f*g) \ge d+1. \end{aligned}$$

This completes the proof. $\square$

Let f, s, g be as described in Lemma 4. By Lemma 5 we know $\deg (s*g) \ge d$, and so $(s*g)_{\ge [d]}\ne 0$. Since it can be seen that $\mathrm {ord}(p_{\ge [d+1]}) = n+m$ in the proof of Lemma 4, it follows from (31) that $\mathrm {ord}((f*g)_{\ge [d+1]}) = n+m$. This indicates that Lemma 4 could also be described in the following way.

Lemma 6

Let f, s, g be as described in Lemma 4. Then

$$\begin{aligned} \frac{(f*g)_{\ge [d+1]}}{x_{u}} = (s*g)_{\ge [d]}, \end{aligned}$$

where $d = \deg (g)$ and $u=\mathrm {ord}((f*g)_{\ge [d+1]})$.

If we focus on $\min sub(f_{\ge [2]})$ not on $\max sub(f_{\ge [2]})$ (which is also $\mathrm {ord}(f_{\ge [2]})$), then quite similar arguments could yield the following result.

Lemma 7

Let $f\in \mathbb {B}^{*}$ with $\deg (f) >1$ and $g \in \mathcal {C}^{*}$. Suppose $f = f_{[1]} \oplus r' \oplus s'\cdot x_v$ where $v = \min sub(f_{\ge [2]})$, $f_{\ge [2]} = r' \oplus s'\cdot x_v$, and $x_v$ does not appear in $r'$. Then

$$\begin{aligned} \frac{(f*g)_{\ge [d+1]}}{x_{v}} = (s' *g)_{\ge [d]}, \end{aligned}$$

where $d = \deg (g)$.

Finally, when we analyze Grain and Grain-128a in the following subsections, we shall often meet the special case that $l*g$ is a one term function where l is a linear Boolean function and $g\in \mathbb {B}^{*}$. In such case, the following lemma will be useful.

Lemma 8

Let l be a linear Boolean function and $g\in \mathbb {B}^{*}$. If $l*g = x_{i_1}x_{i_2}\cdots x_{i_d}$, then

• (1) $|T(l)|=1$ and $|T(g)|=1$, i.e., l is a single variable and g is a one term function;

• (2) $g=x_{a}x_{a-i_1+i_2}\cdots x_{a-i_1+i_k}$ for some nonnegative integer a not larger than $i_1$.

Proof

Let us write

$$\begin{aligned} l= & {} x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_u}, i_1<i_2<\cdots <i_u \text { and } \\ g= & {} t_1 \oplus t_2 \oplus \cdots \oplus t_k, t_1 \prec t_2 \prec \cdots \prec t_k. \end{aligned}$$

Suppose either $|T(l)|>1$ or $|T(g)|>1$. Then it can be seen that $x_{i_1}*t_1$ and $x_{i_u} *t_k$ are two distinct terms of $l*g$, which is a contradiction to $|T(l*g)|=1$. Hence, we have $|T(l)|=1$ and $|T(g)|=1$. Consequently, we know $l=x_{j}$ for some integer $0\le j \le i_1$. It follows from $l*g = x_{i_1}x_{i_2}\cdots x_{i_d}$ that $g = x_{i_1-j}x_{i_2-j}\cdots x_{i_d-j}$. Let $a = i_1-j$. Then we get $g = x_ax_{a-i_1+i_2}\cdots x_{a-i_1+i_d}$. $\square$

1.3 Grain v1

In this subsection, we shall prove that the 80-bit NFSR involved in Grain v1 is $*$-irreducible.

Recall that the characteristic function of the 80-bit NFSR$(f^{80})$ in Grain v1 is given by

$$\begin{aligned} f^{80}= & {} x_{21}x_{28}x_{33}x_{37}x_{45}x_{52}\oplus x_9 x_{15}x_{21}x_{28}x_{33}\oplus x_{37}x_{45}x_{52}x_{60}x_{63}\oplus x_{33}x_{37}x_{52}x_{60} \\&\oplus \, x_9 x_{28} x_{45} x_{63}\oplus x_{15} x_{21} x_{60} x_{63}\oplus x_{21} x_{28} x_{33}\oplus x_{45} x_{52} x_{60}\oplus x_9 x_{15}\oplus x_{33} x_{37}\\&\oplus \, x_{60}x_{63}\oplus x_0\oplus x_9\oplus x_{14}\oplus x_{21}\oplus x_{28}\oplus x_{33}\oplus x_{37}\oplus x_{45}\\&\oplus \, x_{52}\oplus x_{60}\oplus x_{62} \oplus x_{80}. \end{aligned}$$

Note that $\deg (f^{80}) = 6$. By Lemma 5, if $f^{80}$ could be factored into $f^{80} = p*g$ for some $p,g\in \mathcal {C}^{*}$, then $\deg (g)\le 6$. Hence we divide our discussions into the following six cases according to the algebraic degree of g.

Case 1 Suppose $\deg (g)=6$. It follows from Proposition 4 that $p=x_0$.

Case 2 Suppose $\deg (g)=5$. On one hand, it follows from Lemma 6 that

$$\begin{aligned} x_{21}x_{28}x_{33}x_{37}x_{45} = \frac{(f^{80})_{\ge [6]}}{x_{52}} = (s*g)_{\ge [5]} \end{aligned}$$

for some function $s\in \mathbb {B}^{*}$. Since $\deg (g)=5$, it is necessary that s is linear by Lemma 5, and so in fact we have

$$\begin{aligned} s*g_{[5]} = x_{21}x_{28}x_{33}x_{37}x_{45}. \end{aligned}$$

Then it follows from Lemma 8 that

$$\begin{aligned} g_{[5]} = x_{a}x_{a-21+28}x_{a-21+33}x_{a-21+37}x_{a-21+45} \end{aligned}$$

(35)

for some nonnegative integer a. On the other hand, it follows from Lemma 7 that

$$\begin{aligned} x_{28}x_{33}x_{37}x_{45}x_{52} = \frac{(f^{80})_{\ge [6]}}{x_{21}} = (s'*g)_{\ge [5]} \end{aligned}$$

for some function $s'\in \mathbb {B}^{*}$. Similarly, we have

$$\begin{aligned} g_{[5]} = x_{b}x_{b-28+33}x_{b-28+37}x_{b-28+45}x_{b-28+52} \end{aligned}$$

(36)

for some nonnegative integer b. It can be seen that (35) is a contradiction to (36). Hence, this case is impossible.

Case 3 Suppose $\deg (g)=4$. On one hand, it follows from Lemma 6 that

$$\begin{aligned} x_{37} x_{45} x_{52} x_{60} = \frac{(f^{80})_{\ge [5]}}{x_{63}} = (s*g)_{\ge [4]} \end{aligned}$$

for some function $s\in \mathbb {B}^{*}$. Since $\deg (g)=4$, it is necessary that s is linear by Lemma 5, and so in fact we have

$$\begin{aligned} s*g_{[4]} =x_{37} x_{45} x_{52} x_{60}. \end{aligned}$$

Then it follows from Lemma 8 that

$$\begin{aligned} g_{[4]} = x_{a} x_{a-37+45} x_{a-37+52} x_{a-37+60} \end{aligned}$$

(37)

for some nonnegative integer a. On the other hand, it follows from Lemma 7 that

$$\begin{aligned} x_{15} x_{21} x_{28} x_{33} = \frac{(f^{80})_{\ge [5]}}{x_{9}} = (s'*g)_{\ge [4]} \end{aligned}$$

for some function $s'\in \mathbb {B}^{*}$. Similarly, we have

$$\begin{aligned} g_{[4]} = x_{b} x_{b-15+21} x_{b-15+28} x_{b-15+33} \end{aligned}$$

(38)

for some nonnegative integer b. It can be seen that (38) is a contradiction to (37). Hence, this case is impossible.

Case 4 Suppose $\deg (g)=3$. To show this case is impossible either, the basic idea is the same as that used in the previous two cases except that we need to use Lemmas 6 and 7 twice respectively.

On one hand, it follows from Lemma 6 that

$$\begin{aligned} x_{37} x_{45} x_{52} x_{60}\oplus x_9 x_{28} x_{45} \oplus x_{15} x_{21} x_{60} = \frac{(f^{80})_{\ge [4]}}{x_{63}} = (s*g)_{\ge [3]} \end{aligned}$$

(39)

for some function $s\in \mathbb {B}^{*}$. Let us denote $h = s*g$. Then based on the equality

$$\begin{aligned} h_{\ge [3]}= x_{37} x_{45} x_{52} x_{60}\oplus x_9 x_{28} x_{45} \oplus x_{15} x_{21} x_{60}, \end{aligned}$$

Lemma 6 implies that

$$\begin{aligned} x_{37} x_{45} x_{52} = \frac{h_{\ge [4]}}{x_{60}} = (s_1*g)_{\ge [3]} \end{aligned}$$

for some function $s_1\in \mathbb {B}^{*}$. Consequently, $g_{[3]}$ could only be of the form

$$\begin{aligned} g_{[3]} = x_{a} x_{a-37+45} x_{a-37+52} \end{aligned}$$

(40)

for some nonnegative integer a.

On the other hand, using Lemma 7 twice, we obtain

$$\begin{aligned} (s_1'*g)_{\ge [3]} = x_{21} x_{28} x_{33} \end{aligned}$$

for some function $s_1'\in \mathbb {B}^{*}$. Consequently, we have

$$\begin{aligned} g_{[3]} = x_{b} x_{b-21+28} x_{b-21+33} \end{aligned}$$

(41)

for some nonnegative integer b. It can be seen that (41) is a contradiction to (40). Hence, this case is impossible.

Case 5 Suppose $\deg (g)= 2$. Recursively using Lemma 6 three times leads to

$$\begin{aligned} (s*g)_{\ge [2]} = x_{37} x_{45} \end{aligned}$$

(42)

for some function $s\in \mathbb {B}^{*}$, while recursively using Lemma 7 three times leads to

$$\begin{aligned} (s'*g)_{\ge [2]} = x_{28} x_{33} \end{aligned}$$

(43)

for some function $s'\in \mathbb {B}^{*}$. Consequently, it follows from (42) that $g_{[2]}$ should be of the form $g_{[2]} = x_ax_{a-37+45}$ for some nonnegative integer a, while it follows from (43) that $g_{[2]}$ should be of the form $g_{[2]} = x_bx_{b-28+33}$ for some nonnegative integer b, a contradiction. Hence, this case is impossible.

Case 6 Suppose $\deg (g)= 1$. It follows from [11, Corollary 1] that $g = x_0$.

In all, the six cases show that $f^{80}$ only has trivial $*$-factorizations, and so $f^{80}$ is $*$-irreducible.

1.4 Grain-128

In this subsection, we shall prove that the 128-bit NFSR involved in Grain-128 is $*$-irreducible.

Recall that the characteristic function of the 128-bit NFSR$(f^{128})$ in Grain-128 is given by

$$\begin{aligned} f^{128}= & {} x_{68}x_{84}\oplus x_{61}x_{65}\oplus x_{40}x_{48}\oplus x_{27}x_{59}\oplus x_{17}x_{18}\oplus x_{11}x_{13}\oplus x_{3}x_{67} \\&\oplus \, x_{0}\oplus x_{26}\oplus x_{56}\oplus x_{91}\oplus x_{96}\oplus x_{128}. \end{aligned}$$

Note that $\deg (f^{128}) = 2$, and so by Lemma 5, if $f^{128}$ could be factored into $f^{128} = p*g$ for some $p,g\in \mathcal {C}^{*}$, then $\deg (g)$ is equal to 1 or 2. If $\deg (g)=1$, then it follows from [11, Corollary 1] that $g = x_0$. If $\deg (g)=2$, then p is linear by Lemma 5 and it follows from Proposition 4 that $p=x_0$. Hence, $f^{128}$ is $*$-irreducible.

1.5 Grain-128a

In this subsection, we shall prove that the 128-bit NFSR involved in Grain-128a is $*$-irreducible.

Recall that the characteristic function of the 128-bit NFSR$(f^{128a})$ in Grain-128a is given by

$$\begin{aligned} f^{128a}= & {} x_{88} x_{92} x_{93} x_{95}\oplus x_{22} x_{24} x_{25}\oplus x_{70} x_{78} x_{82}\oplus x_3 x_{67}\oplus x_{11} x_{13}\\&\oplus \, x_{17} x_{18}\oplus x_{27} x_{59}\oplus x_{40} x_{48}\oplus x_{61} x_{65}\oplus x_{68} x_{84}\\&\oplus \, x_{128}\oplus x_{26}\oplus x_{56}\oplus x_{91}\oplus x_{96}\oplus x_0. \end{aligned}$$

Note that $\deg (f^{128a}) = 4$. By Lemma 5, if $f^{128a}$ could be factored into $f^{128a} = p*g$ for some $p,g\in \mathcal {C}^{*}$, then $\deg (g)\le 4$. Hence we divide our discussions into the following four cases according to the algebraic degree of g.

Case 1 Suppose $\deg (g)=4$. It follows from Proposition 4 that $p=x_0$.

Case 2 Suppose $\deg (g)=3$. Using Lemma 6 once leads to

$$\begin{aligned} (s*g)_{\ge [3]} = x_{88}x_{92}x_{93} \end{aligned}$$

for some function $s\in \mathbb {B}^{*}$. This implies that

$$\begin{aligned} g_{[3]} = x_{a}x_{a-88+92}x_{a-88+93} \end{aligned}$$

(44)

for some nonnegative integer a. Using Lemma 7 once leads to

$$\begin{aligned} (s'*g)_{\ge [3]} = x_{92} x_{93}x_{95} \end{aligned}$$

for some function $s'\in \mathbb {B}^{*}$. This implies that

$$\begin{aligned} g_{[3]} = x_{b}x_{b-92+93}x_{b-92+95} \end{aligned}$$

(45)

for some integer b. It can be seen that (44) is a contradiction to (45). Hence this case is impossible.

Case 3 Suppose $\deg (g)=2$. Using Lemma 6 twice leads to

$$\begin{aligned} (s*g)_{\ge [2]} = x_{88}x_{92} \end{aligned}$$

for some function $s\in \mathbb {B}^{*}$. This implies that $g_{[2]}$ should be of the form

$$\begin{aligned} g_{[2]} = x_{a}x_{a-88+92} \end{aligned}$$

(46)

for some nonnegative integer a. Using Lemma 7 once leads to

$$\begin{aligned} (s'*g)_{\ge [2]} = x_{24} x_{25} \end{aligned}$$

for some function $s'\in \mathbb {B}^{*}$. This implies that $g_{[2]}$ should be of the form

$$\begin{aligned} g_{[2]} = x_{b}x_{b-24+25} \end{aligned}$$

(47)

for some integer b. It can be seen that (46) is a contradiction to (47). Hence this case is impossible.

Case 4 Suppose $\deg (g)=1$. It follows from [11, Corollary 1] that $g = x_0$.

In all, the four cases show that $f^{128a}$ only has trivial $*$-factorizations, and so $f^{128a}$ is $*$-irreducible.