GAO Juntao, LI Xuelian. Security Analysis of A Stream Cipher with Proven Properties[J]. Chinese Journal of Electronics, 2021, 30(2): 210-218. DOI: 10.1049/cje.2021.01.002
Citation:
GAO Juntao, LI Xuelian. Security Analysis of A Stream Cipher with Proven Properties[J]. Chinese Journal of Electronics, 2021, 30(2): 210-218. DOI: 10.1049/cje.2021.01.002
GAO Juntao, LI Xuelian. Security Analysis of A Stream Cipher with Proven Properties[J]. Chinese Journal of Electronics, 2021, 30(2): 210-218. DOI: 10.1049/cje.2021.01.002
Citation:
GAO Juntao, LI Xuelian. Security Analysis of A Stream Cipher with Proven Properties[J]. Chinese Journal of Electronics, 2021, 30(2): 210-218. DOI: 10.1049/cje.2021.01.002
LI Xuelian was born in 1979. She received the D.E. degree in cryptography from Xidian University. She is now an associate professor. Her research interests include Boolean function and cryptography. (Email: xlli@mail.xidian.edu.cn)
Corresponding author:
GAO Juntao (corresponding author) was born in 1979. He received the D.E. degree in cryptography from Xidian University. He is now an associate professor. His research interests include stream cipher and pseudorandom sequence. (Email: jtgao@mail.xidian.edu.cn)
Si and Ding proposed a stream cipher with two keys (the first and the second key) and an expected security strength. To further measure the security, we analyze the stream cipher by considering the selective discrete Fourier spectra attack and the fast selective discrete Fourier spectra attack. The two attacks reveal a fact that the second key is more important than the first key, that is, if the second key is leaked out, the first key can be obtained with a lower time complexity than that of the expected security. In addition, we analyze the ability of the stream cipher to resist the guess-anddetermine attack. The results show an attacker is able to gain the two keys with an exponentially improved time complexity and a polynomial data complexity. It implies that we need a securer permutation over finite fields to design a new binary additive stream cipher to achieve the expected security level.
Stream ciphers usually are produced by a pseudorandom sequence generator, which has wide application in communication[1-4] and cryptography[5-9]. Due to simple implementation and large throughput, stream ciphers have received much attention in modern cryptography. There are various ideas about the design of stream ciphers, such as, the traditional combination generator, the filter generator and the shrinking generator, and so on. As the development of the cryptanalytic techniques, the traditional designs can not satisfy the security requirements in communication systems any longer, therefore, some new design ideas continuously spring up, such as, the Grain[6], Trivium[7], Sosemanuk[8], HC-128[9] and so on.
In Ref.[10], Cusick et al. gave a simple design of stream ciphers based on a permutation over a finite field. The stream cipher consists of a generator over the finite field F2n, a permutation over F2n with good nonlinearity and a linear function from F2n to F2. In Ref.[11], based on the idea of Cusick et al., W. Si and C. Ding proposed a towards practical stream cipher with the key k=(a,b), a,b∈F2n and an initial value IV. The stream cipher is referred to as the binary additive stream cipher based on the inverse permutation. They analyzed the linear complexity stability, autocorrelation and cross-correlation of the keystream. Besides, they showed that the stream cipher is secure with respect to several attacks, such as, algebraic attacks and guess-and-determine attacks. For gaining further insight into the stream cipher, Si and Ding invited the reader to more intensively analyze whether there are efficient attacks for the binary additive stream cipher based on the inverse permutation[12, 13].
In this paper, we analyze the security of the stream cipher by employing three cryptanalytic methods, spectra attacks, fast spectra attacks and guess-and-determine attacks. For the first two attacks of the three methods, we show that the key b is more important than another key a, that is, if the key b is leaked out, the stream cipher can be compromised with a complexity much less than the brute-force attack, whereas, if the key a is leaked out, the stream cipher is still secure for spectra attacks and fast spectra attacks. Furthermore, we find an efficient guess-and-determine attack with a time complexity of O(2nn2lognlog2nlog2log2n) and a data complexity of O(3.47n). The stream cipher is not able to achieve the claimed security O(22n) under our guess-and-determine attacks.
This paper is organized as follows, Section Ⅱ gives some basic definitions and preparations. Section Ⅲ introduces spectra attacks and fast spectra attacks, which are proposed to analyze the filter generator[14, 15]. We modify the two attacks and apply them to the binary additive stream cipher based on the inverse permutation. We give an upper bound on the spectrum immunity of the keystream, and prove that the stream cipher can resist the two attacks. However, if the key b is leaked out, we show the key a can be obtained with a much lower complexity than the brute-force attack. Section Ⅳ puts forward a new guess-and-determine attack by guessing the value of ab−1. The attack has a time complexity of O(2nn2lognlog2nlog2log2n) and a data complexity of O(3.47n). Finally, we give a conclusion in Section Ⅴ.
Ⅱ.
Background
In the following, we give some notations[12, 13] which will be used throughout this paper.
∙F2n denotes a finite field with 2n elements. F∗2n is the multiplicative group with 2n−1 elements.
∙α is a primitive element in F∗2n.
∙F2[x] denotes the polynomial ring with coefficients in F2.
∙IV∈[0,2n−1) is an initial value for stream cipher. Usually, IV is public.
∙Trn1(x), or Tr(x) for short, denotes the trace function from F2n to F2, i.e., Tr(x)=x+x2+⋯+x2n−1. Obviously, Tr(x) is a linear function from F2n to F2.
∙{ω1,ω2,⋯,ωn} denotes a basis of F2n over F2, where each ωi is an element of F2n. ∀x∈F2n, x has a unique expansion of the form x=x1ω1+x2ω2+⋯+xnωn, where xi∈F2.
∙Ck={k2i(mod2n−1)|i=0,1,⋯,nk−1} denotes the cyclotomic coset on the coset leader k, where nk|n is the size of Ck.
∙ For any polynomial f(x)∈F2[x], we can write f(x)=f(x1ω1+x2ω2+⋯+xnωn). Therefore, any polynomial function f(x)∈F2[x] can be viewed as an n-variable Boolean function f(x1,x2,⋯,xn) with respect to the basis {ω1,ω2,⋯,ωn} and vice versa.
∙ Any polynomial function f(x) (or any n-variable Boolean function f(x1,x2,⋯,xn)) can be uniquely expressed as (f(0),f(1),f(α),⋯,f(α2n−2)). The sequence
s=(f(1),f(α),⋯,f(α2n−2),⋯)
determined by the truth table of f(x) except for the f(0) is called the corresponding sequence of f(x) or f(x1,x2,⋯,xn). Conversely, f(x) or f(x1,x2,⋯,xn), ignoring the f(0), is referred to as the corresponding function of s.
∙ Let s=s0s1s2⋯ denote the keystream sequence, and m=m0m1m2⋯ and c=c0c1c2⋯ denote the plaintext and ciphertext respectively.
In Ref.[10], Cusick, Ding and Renvall gave a construction of stream ciphers, which consist of a generator over F2n, a permutation function over F2n with good nonlinearity and a linear function from F2n to F2. The encryption process is implemented by performing the bitwise XOR operation between the keystream and the plaintext. The decryption process is the same as the encryption process. Although the authors in Ref.[10] gave the framework of the stream cipher, they didn't assign specific parameters to the permutation function and the linear function. In Ref.[11], Si and Ding proposed a specific stream cipher based on the framework. The inverse function x−1 over F2n is used for the permutation function and the trace function Tr(x) from F2n to F2 is used for the linear function in the stream cipher. The k = (a,b), where a,b∈F2n is chosen as the secret key of the stream cipher. Hence the stream cipher has an expected security strength of O(22n), which is also the complexity of the brute-force attack on the stream cipher. Before encrypting the plaintext, two users set an initial vector IV∈[0,2n−1) and α over F2n. Using the cyclic counter, the users can produce all elements of F∗2n in order of αIV, α1+IV, ⋯, α2n−2+IV cyclically. Obviously, the initial value IV and the primitive element α are public, and the key k=(a,b) is private. If we find a cryptanalytic method with a time complexity significantly less than O(22n), we think the stream cipher to be compromised.
Ⅲ.
Two Spectra Attacks on the Stream Cipher Based on Guessing the Key b
According to specific parameters in the stream cipher, any entry si in the keystream s=s0s1s2⋯ can be expressed as
si=Tr[(aαi+IV+b)−1]
where a,b∈F∗2n, and IV is an initial value which is known for attackers. We can rewrite si as
si=Tr[b−1(ab−1αi+IV+1)−1]
Let a=αea and b=αeb. Then si can also be expressed as
si=Tr[α−eb(αi+IV+ea−eb+1)−1]
In this section, by guessing the value of b, we apply the selective discrete Fourier spectra attack (spectra attack for short) and fast selective discrete Fourier spectra attack (fast spectra attack for short) to find the remained key a. The spectra attack is a new attack on the filter generator. It is introduced firstly by Rϕnjom and Helleseth[15]. Gong, Rϕnjom, Helleseth and Hu proposed the fast spectra attack by considering the linear complexities of product sequences of the keystream in Ref.[14]. The spectra attack's complexity is directly proportional to the linear complexity of the keystream produced by the filter generator, while the fast spectra attack's complexity is directly proportional to the linear complexity of the product sequence of the keystream.
1
Discrete Fourier transform of binary sequences with odd period
Given a binary sequence s=s0s1s2⋯ with the period N, where N is an odd. We can uniquely write the entry si as si=F(γi), where F(x)=∑N−1k=0Skxk is a polynomial over F2n, and γ is a primitive element in F2n. The coefficient Sk of the F(x) can be determined by the Discrete Fourier transform (DFT) as follows
Sk=N−1∑i=0siγ−ik,k=0,1,⋯,N−1
Similarly, the entry si can be acquired by the inverse DFT
si=N−1∑k=0Skγki,i=0,1,⋯,N−1
We call the sequence {Sk}N−1k=0 a DFT spectral sequence of s with respect to γ.
2
Shift sequences and its DFT
We consider a new sequence u=u0u1⋯, where
ui=Tr[b−1(αi+IV+1)−1]
(1)
The DFT of u is given as follows
Uk=N−1∑i=0uiγ−ik
Obviously, the sequence u is a (ea−eb)-shift sequence of s, and
Sk=Ukγ(ea−eb)k
Lemma 1[14] Let g(x)=∑N−1i=0gixi be a polynomial over F2 and deg(g(x)) = d. Let {Vk}N−1k=0 and {Sk}N−1k=0 be the DFT spectral sequences of the sequence s and v respectively, where v=g(L)s and L denotes the left cyclically shift operator. Then Vk=Skg(γk), 0≤k<N.
3
Modified spectra attack
Let
Ku={k|Uk≠0,kisacosetleader(modN)}
¯Ku={k|Uk≠0}
and
Ks={k|Sk≠0,kisacosetleader(modN)}
¯Ks={k|Sk≠0}
Because the sequence u=u0u1u2⋯ is a shift sequence of s=s0s1s2⋯, we have Ku=Ks. Note that ui=Tr[b−1(αi+IV+1)−1] in Eq.(1). By guessing the value of b, we can obtain the corresponding sequence u and its spectra sequence {Uk}N−1k=0. The main idea of modified spectra attacks is to employ the given Uk and a part of keystream to achieve the αea−eb or a spectral term of s. In the following, we give the concrete procedure of modified spectra attacks.
Algorithm 1 Modified spectra attack
Input: l(s) consecutive bits of the sequence s=s0s1⋯,
where l(s) denotes the linear complexity of s;
Output: αea−eb=ab−1 or Sj, a spectral term of s.
Precomputation
1:
Select a positive integer z satisfying gcd(z,N)=1 and let α=γz;
2:
Select a j∈Ks with |Cj|=n;
3:
Guess b and compute u, where ui=Tr[b−1(αi+IV+1)−1];
4:
Compute Uj, where Uj=∑N−1i=0uiγ−ij;
5:
Compute g(x)=p(x)/pj(x)=∑l(s)−ni=0cixi, where p(x) is the minimal polynomial of s, pj(x) is the minimal polynomial of γj.
Remark 1 Since α=γz and gcd(z,N)=1, we know γ is also a primitive element in F2n. Therefore, we are able to compute the spectral sequence of u with respect to γ. On the other hand, s is a shifted sequence of u, we know that the two corresponding spectral sequences satisfy Sj=Ujγ(ea−eb)j.
Remark 2 For a coset leader j∈Ks, {1,γj, γ2j,⋯,γ(n−1)j} is a basis of F2n over F2. Therefore, the unknown ω can be expressed as ω=xj,0+xj,1γj+⋯+xj,n−1γ(n−1)j, where xj,i∈F2. The Eq.(2) can be rewritten as vt=∑n−1i=0xj,iTr(γjiγtj),t=0,1,⋯,n−1. The complexity to solve the above equation is O(n2log(n)log2(n)log2log2(n))[14].
Remark 3 In the precomputation, we need to calculate p(x), pj(x), g(x), g(γj) and Uj. According to the complexity analysis in Ref.[14], the complexity to calculate p(x), pj(x), g(x), g(γj) is O(l(s)[n(logn)2+(logl(s))3+nlog2nlog2log2n]). Moreover, we also need to guess the value of b and compute a spectral term Uj for any a guessed b. It implies that the precomputation needs to be performed 2n times. Therefore, the total complexity of the precomputation is
O(22n+l(s)[n(logn)2+(logl(s))3+nlog2nlog2log2n])
(3)
In Algorithm 1, the modified spectra attack requires l(s) consecutive keystream bits of s. From Ref.[11], we know that l(s)≥2n−1. It means that we need more than half of one period keystream to implement the modified spectra attack. Besides, although the modified spectra attack has a complexity of O(n2log(n)log2(n)log2log2(n)) in the procedure, it has a larger complexity than that of the brute-force attack (O(22n)) in the precomputation. Therefore, the binary additive stream cipher based on inverse permutation can resist the modified spectra attack. On the other hand, we observe that most of time is spent on guessing all possible values of b's and computing the corresponding Uj for each b. If the key b is leaked out, the time complexity of the precomputation can be significantly reduced, and, in this case, the precomputation is performed only once.
Remark 4 If we don't consider the complexity of computing the Uj and b is given, the time complexity of the precomputation in Algorithm 1 is able to be significantly reduced from Eq.(3) to
O(l(s)[n(logn)2+(logl(s))3+nlog2nlog2log2n])
This is a similar case as in the spectra attack and the fast spectra attack on the filter generator[14].
4
Modified fast spectra attack
Spectra attacks can be improved by introducing two sequences with relatively small linear complexities, that is, by finding two sequences s(1) and s(2) satisfying s(2)=s⋅s(1), where s(2)i=sis(1)i, for i=0,1,⋯ and l(s(1))+l(s(2))<l(s), the required keystream bits can be cut down from l(s) to l(s(1))+l(s(2)). The data complexity will be largely reduced if l(s(1))+l(s(2))<<l(s). The improved spectra attack is referred to as fast selective DFT attack (fast spectra attack for short). To measure the ability of stream cipher to resist fast spectra attacks, Gong et al. proposed an index similar to algebraic immunity, called the spectral immunity[14], which is defined as follows.
Definition 1 Suppose that s is a binary sequence with a period N. Let
SIs=mins′∈FN2{l(s′)|s⋅s′=0or(s+1)⋅s′=0,s′≠0}
Then SIs is referred to as the spectral immunity of s.
In the following, we will give a modified fast spectra attack in Algorithm 2. Modified fast spectra attacks need much less keystream bits and can obtain the key with a lower time complexity than that of modified spectra attacks. In addition, we will give an upper bound on the spectral immunity of the keystream s. To describe the Algorithm 2, we need to give the following lemma, which is given in Ref.[14] by Gong et al..
Lemma 2[14] Suppose that Ks(2)⊄Ks(1), let s(2)=s⋅s(1) and q(x)=∑Ks(2)∖Ks(1)pk(x)=∑ri=0cixi, where pk(x) is the minimal polynomial of αk and r=|¯Ks(2)∖¯Ks(1)|. Let ft(x)=∑ri=0cisi+txi for t=0,1,⋯,l(s(1))−1. We have
where t=0,1,⋯,l(s(1))−1, and {S(1)k} and {S(2)k} denote the DFT spectra of s(1) and s(2). If q(x) is the minimal polynomial of s(2), then we have
∑k∈Ks(1)Tr(S(1)kft(αk)αtk)=0
According to the complexity analysis in Ref.[14], we know that, in the precomputation, the complexity of Step 4 is O(l(s(4))[n(logn)2+(logl(s(4)))3+nlog2nlog2log2n]). The complexity of calculating ft(x) is O(l(s(4)). The complexity of solving the the Eq.(4) is O(l(s(3))2logl(s(3))log2l(s(3))log2log2l(s(3))) in F2. Besides, the attacker needs to guess the value of b with a complexity of O(2n). If we consider the complexity of calculating the DFT of the sequences u, s(1) and s(2), then the total complexity will be more than the brute-force attack. It implies that the stream cipher is able to resist the modified fast spectra attack.
The Algorithm 2 works on condition that there are two specific sequences s(1) and s(2) such that s(2)=s⋅s(1), and can return αea−eb or α(ea−eb)k for k∈Ks(3) by using at most l(s(1))+l(s(2)) key stream bits. In the following, we prove that, for an s, there exist two potential sequences which can play the roles of s(1) and s(2).
From Definition 1, we know that SIs denotes the lowest linear complexity of the binary annihilators of s. In Ref.[16], Wang, Chen and Zhu presented that it is not an easier task to decide the (non)existence of the low weight annihilator than the algebraic attack. Wang et al. also proved that the spectral immunity is upper bounded by half of the period of s when the corresponding Boolean function of s has an odd number of variables. In Ref.[17], Wu, Qi, and Chen gave a sharp upper bound on spectral immunities of periodic sequences.
Algorithm 2 Modified fast spectra attack
Input: m consecutive bits of s=s0s1⋯, where m<l(s);
Output: αea−eb=ab−1 or Sj, a spectral term of s;
Precomputation
1:
Generate u=u0u1⋯, where ui=Tr[b−1(αi+IV+1)−1] by guessing b and choosing the identical Ⅳ of s;
2:
Choose s(3) and s(4) such that s(4)i=uis(3)i for i=0,1,⋯, and l(s(3))+l(s(4))<l(u);
3:
Let s(1) be a shift of s(3) and s(2) be a shift of s(4) with the same as s from u;
4:
Compute q(x)=ms(4)(x)=∑l(s(4))i=0qixi, where q(x) is the minimal polynomial of s(4);
Precedure
1:
Compute ft(αk)=∑l(s(4))i=0qisi+txi, where k∈Ns(3), and t=0,1,⋯,ls(3)−1;
2:
Solve the following equation with the unknown α(ea−eb)
∑k∈Ks(3)Tr(α(ea−eb)kS(3)kft(αk)αtk)=0(4)
for t=0,1,⋯,l(s(3))−1;
3:
If there exits a k∈Ks(3) such that gcd(k,N)=1, then
Theorem 1[17] Let n>1 be an odd positive integer and s be a binary sequence with the period T|2n−1. We have
SIs≤T+12
Moreover, this upper bound is sharp, that is, there exists a sequence s such that SIs=T+12.
Theorem 2[17] Let n>1 be an even positive integer and s be a binary sequence with the period T|2n−1. We have
SIs≤T+n−12
We refer to the periodic sequence achieving the sharp upper bound in Theorem 1 or Theorem 2 as the sequence with optimal spectral immunity. In addition, Wu et al. proved that the sequence with optimal spectral immunity is corresponding to a Boolean function with optimal algebraic immunity. It implies that a Boolean functions with non-optimal algebraic immunity is corresponding to a periodic sequence with non-optimal spectral immunity. In Ref.[18], Feng and Gong proved that the trace inverse function over finite fields with characteristic two is not a Boolean function with the optimal algebraic immunity.
Theorem 3[18] Let Tr(λx−1) be the trace inverse function over finite fields F2n, where n≥2, λ∈F2n and λ≠0. We have
AI(Tr(λx−1))=⌊√n⌋+⌈n⌊√n⌋⌉−2=⌈2√n⌉−2
where AI(Tr(λx−1)) denotes the algebraic immunity of Tr(λx−1).
From Theorem 3 as above, we see that Tr(λx−1) is not a Boolean function with the optimal algebraic immunity ⌊n2⌋. Note that x↦ax+b is a linear transformation over F2n, so we have AI(Tr[(ax+b)−1]) also equals to ⌈2√n⌉−2. If we can find some specific annihilators of Tr[(ax+b)−1] and these annihilators have corresponding sequences with low linear complexities, then these sequences can be used to attack the stream cipher in Algorithm 2. This inspires us to look for the specific annihilator of Tr[(ax+b)−1]. In Ref.[19], Nawaz and Gong investigated the algebraic immunity of the monomial polynomial over F2n. Their methods can be used for estimating the spectral immunity of Tr[(ax+b)−1].
Lemma 3[19] Let f(x)=Trn1(βxt), and g(x)=Trm1(γxr), where x,β∈F2n, γ∈F2m and t and r are the coset leaders of cosets Ct and Cr respectively. The sizes of Ct and Cr are n and m respectively, m|n. Then we have deg(f(x)g(x))=max0≤i<mH(r+t2−i), where deg(⋅) denotes the degree of polynomial and H(⋅) denotes the Hamming weight of the binary representation of the value.
Lemma 4[19] Let k=n−⌊n⌊√n⌋⌋⌊√n⌋, and f(x)=Trn1(βxt), where x,β∈F2n, and t is the coset leader of coset Ct. Let g(x)=Trm1(xr) where
Lemma 5[19] Let f(x)=Trn1(βx−1), and g(x)=Trm1(xr). Then deg(f(x)g(x))≤⌊√n⌋+⌈n⌊√n⌋⌉−2, where β, r and m are the same as defined in Lemma 4.
We recall the relation between linear complexity and the DFT of a binary sequence s. Let s=s0s1⋯ be a sequence over F2 with a period of N. Each entry si can be uniquely written as
si=N∑j=0Sjαji,0≤i<N
(5)
where Sj∈F2n for j=0,1,⋯,N−1. Defining the indicator set J={j|Sj≠0,j=0,1,⋯,N−1}, we have the linear complexity l(s)=|J|. Note that
where a,b∈F2n, m and r are defined as Lemma 4. We consider (ax+b)'s exponents r2j−2i for i=0,1,⋯,n−1 and j=0,1,⋯,m−1. If r2j−2i<0, then we substitute r2j−2i for 2n−1−r2j+2i>0. Hence all of exponents of (ax+b) can be viewed as a positive integer. Combining Theorem 3 and Lemma 5, we know there exists a polynomial Trm1[(ax+b)r] such that deg(Trn1[(ax+b)−1]Trm1[(ax+b)r])=2⌈√n⌉−2. In this case, we have
max0≤i≤n−1,0≤j≤m−1H(r2j−2i)=2⌈√n⌉−2
It implies that there exist at most n2(22⌈√n⌉−2−1) different powers of x in Trn1[(ax+b)−1]Trm1[(ax+b)r]. Suppose that the corresponding sequence of Trn1[(ax+b)−1]Trm1[(ax+b)r] is s(2)=s(2)0s(2)1⋯, where s(2)i=Trn1[(aαi+b)−1]Trm1[(aαi+b)r] for i=0,1,⋯. According to the relation between the linear complexity and DFT in Eq.(5), we know the linear complexity of s(2) is at most n2(22⌈√n⌉−2−1), i.e.,
l(s(2))≤n2(22⌈√n⌉−2−1)
(6)
On the other hand, suppose that the corresponding sequence of Trm1[(ax+b)r] is s(1)=s(1)0s(1)1⋯ where s(1)i=Trm1[(aαi+b)r] for i=0,1,⋯. Observe the parameter r in Lemma 4, we know that there exist at most 2⌈√n⌉+1 different powers of x in Trm1[(ax+b)r]. Therefore, we have
l(s(1))≤2⌈√n⌉+1
If all of terms in Trn1[(ax+b)−1]Trm1[(ax+b)r]+Trm1[(ax+b)r] can not be combined (the worst case), then we have the linear complexity of s(1)+s(2) is upper bounded by
l(s(1)+s(2))≤n2(22⌈√n⌉−2−1)+2⌈√n⌉+1
Theorem 4 Assume that the binary sequence s=s0s1⋯, where si=Trn1[(aαi+b)−1]. We can find a sequence s(1)=s(1)0s(1)1⋯, such that the sequence s⋅s(1)+s(1) has a linear complexity upper bounded by n2(22⌈√n⌉−2−1)+2⌈√n⌉+1, where s(1)i=Trm1[(aαi+b)r] for i=0,1,⋯, and m, r are defined as Lemma 4.
Theorem 4 shows that there exists some potential annihilator (s+1)⋅s(1) of s. In this case, the required keystream are at most n2(22⌈√n⌉−2−1)+2⌈√n⌉+1 bits, which is significantly less than 2n−1[11].
If the key b is leaked out under fast spectra attacks, then the key a can be obtained with a lower complexity and fewer keystream bits than the spectra attack. Consequently, when the key b is leaked out, the stream cipher suffers from spectra attacks and fast spectra attacks. Instead, if the key a is leaked out, we can not obtained b with a low complexity by using spectra attacks or fast spectra attacks. It shows that the key b is more important than the key a for the stream cipher under spectra attacks and fast spectra attacks.
5
The prerequisite to implement two attacks
In the following, we present a prerequisite for finding two keys (a,b) of s under spectra attacks and fast spectra attacks respectively. The prerequisite was ever proposed in Ref.[14] for the filter generator.
1) Applications of Algorithm 1. In this case, the secret key (a,b) can be calculated directly if
a) There exists a j∈Ku such that gcd(j,N) = 1, or
b) there exist t indexes j1, j2, ⋯, jt∈Ku such that gcd(∑ti=1diji,N) = 1, where di are nonzero integers.
When N is a prime, a) can be satisfied directly. If N is not a prime and there does not exist j such that gcd(j,N) = 1, then we can look for the j1, j2, ⋯, jt∈Ku such that gcd(∑ti=1diji,N) = 1 instead.
2) Applications of Algorithm 2. In this case, the secret key (a,b) can be calculated if
a) There are two sequences s(1) and s(2) such that s(2)=s⋅s(1) and l(s(1))+l(s(2))<l(s), and
b) there exists a k∈Ks(3) such that gcd(k,N) = 1 or we can obtain all of k∈Ks(3).
From Theorem 4, we know that the sequence s has a relatively low spectral immunity. It implies that we can find the potential sequences to largely cut down the required keystream bits.
Ⅳ.
Guess-and-Determine Attack on the Stream Cipher
Except for a and b, we can guess other value, for example, ab−1, to attack the stream cipher. In this case, the stream cipher can be compromised with a complexity much less than O(22n). Note that si can be written as si=Tr[α−eb(αi+IV+ea−eb+1)−1]. If ab−1=αea−eb is obtained by the attacker, then the stream cipher can be attacked with some short keystream bits. Assume that the attacker has obtained the following equations
where 0≤i(1)<i(2)<⋯<i(m). It means that the consecutive keystream bits are not necessary in this guess-and-determine attack. The attacker only need to obtain some keystream segment and know their locations.
Since {ω1,ω2,⋯,ωn} denotes a basis of F2n over F2, we can express each inverse element as,
where each coefficient vi(j)k = 0 or 1, for j=1,2,⋯,m and k=0,1,⋯,n. Note that all the vi(j)ks are known by the attacker because ab−1 is guessed.
Let {θ1,θ2,⋯,θn} be the corresponding dual basis of {ω1,ω2,⋯,ωn}, that is, θ1,θ2,⋯,θn and {ω1,ω2,⋯,ωn} satisfy
Tr(θiωj)=1,i=jTr(θiωj)=0,i≠j
The element b−1∈F2n has a unique representation as follows,
b−1=u1θ1+u2θ2+⋯+unθn
where uj = 0 or 1, for j=1,2,⋯,n. According to the properties of the trace function and dual basis, we know that each equation in Eq.(7) is a linear equation with unknowns u1, u2, ⋯, un. The attacker only requires to find n linearly independently equations from the m equations and solve these equations. In the following, we express the equations in Eq.(7) by a matrix form, that is,
We need to determine the rank of M(u) to solve the Eq.(8). Note that the binary representation of (ab−1αi(j)+IV+1)−1, for j=1,2,⋯,m, is nearly random under the basis of {ω1,ω2,⋯,ωn}, that is, the probability of the entry v(i(j))k=0 equals that of v(i(j))k=1 in the vector {v(i(j))1,v(i(j))2,⋯,v(i(j))n} for j=1,2,⋯,m and k=1,2,⋯,n. Therefore, the matrix M(j) can be viewed as an approximately random generated m×n binary matrix. The following lemma can be found in Ref.[13].
Lemma 6 The probability that a random generated m×n binary matrix has rank l(1≤l≤min(m,n)) is
Pl=2l(m+n−l)−mnl−1∏i=0(1−2i−l)(1−2i−n)(1−2i−l)
(9)
Note that we need a matrix M(u) with the rank n for finding all of unknowns u1, u2, ⋯, un in the Eq.(8). Let l=n in Eq.(9). In this case, Pn=∏n−1i=0(1−2i−n). We make an estimation of the rank of the matrix M(u) from a probability point of view. We need about m=nPn keystream bits to find n linearly independent rows in the matrix M(u). Therefore, we have the following theorem,
Theorem 5 By guessing the value of ab−1, an attacker can obtain the secret keys a and b with a time complexity O(2nn2lognlog2nlog2log2n), and a data complexity of O(3.47n).
Proof Since ab−1∈F2n, an attacker needs to guess the value of ab−1 with a complexity of O(2n). For each guessed value, the attacker can obtain a corresponding matrix M(u), and the attacker can obtain the values of u1, u2, ⋯, un by solving the Eq.(7) with a complexity of O(n2lognlog2nlog2log2n). Combining b−1 and the guessed ab−1, we are able to obtain a and b. On the other hand, we need about
O(n∏n−1i=0(1−2i−n))
keystream bits to find n linearly independent rows in the matrix M(u). Note that the 1∏n−1i=0(1−2i−n) is convergent when n→+∞. By a numerical evaluation, we know that
limn→+∞1∏n−1i=0(1−2i−n)≈3.47
The total keystream bits required is O(3.47n). As desired.
In Ref.[11], Si and Ding considered the guess-and-determine attack on the stream cipher. They guessed a or b and then determined the remained key. Note that guessing ab−1 has the same complexity as guessing a or b. However, the resulting complexities are very different. From the analysis as above, we are able to launch a guess-and-determine attack on the stream cipher with a complexity much less than the brute-force attack. The following is a toy example.
Example 1 Let n=5, and the generating polynomial of F25 be x5+x3+1. Let α satisfy α5+α3+1=0. Obviously, {1,α,α2,α3,α4} is a basis of F25. The dual basis of {1,α,α2,α3,α4} is {1,α30,α29,α2,α}. According to the definition of trace function, we get Tr(1)=1, Tr(α)=Tr(α2)=Tr(α4)=0, and Tr(α3)=0. Now two users choose the secret keys a, b and IV=3, the primitive element α. In the general attack model, the IV and α are known by the attacker. Suppose the attacker has known the ab−1=α25, then the i-th keystream bit si can be expressed as si=Tr[b−1(αi+3+25+1)−1]. Under the known plaintext attack, the attacker can obtain some short keystream bits, say, s=s0s1s2s3s4s5s6s7s8=001001100 and the binary expression of each (αi+28+1)−1 under the basis {1,α,α2,α3α4}. Let
It follows that (u1,u2,u3,u4,u5)T = (1,1,1,1,1)T, and b−1=1+α30+α29+α2+α=α18. Therefore, the attacker gets a=α7, b=α13.
Remark 5 From the example 1, we know the attacker is not necessary to employ the consecutive keystream bits. Only some keystream segments are enough to obtain the secret key. On the other hand, other keystream bits can also be used to solve the secret keys a and b only if the rank of the matrix M(u) achieves n.
Ⅴ.
Conclusions
This paper focuses on the security of the binary additive stream cipher based on the inverse permutation. We investigated the stream cipher's ability to resist three cryptanalytic methods, i.e., spectra attacks, fast spectra attacks and guess-and-determine attacks. For the first two of three attacks, the attacker has to guess b−1 and compute the corresponding DFT transforms of the initial sequences for each b−1 in the precomputation. Besides, the required keystream bits are related to the linear complexity of the keystream or its annihilator. All of these lead to a high time and data complexity beyond the brute-force attack. Though the stream cipher is able to resist the two attacks, we find a potential weakness of the stream cipher. For example, once the key b is leaked out, the time complexity of fast spectra attacks will be significantly reduced from O(22n) to O(l(s(3))2logl(s(3))log2l(s(3))log2log2l(s(3))+l(s(4))), and the DFT transforms of the corresponding u, s(1) and s(2) are computed only once in the precomputation. Conversly, if a is leaked out, the stream cipher is still able to resist the two attacks. Therefore, for the users, the key b is more important than the key a.
Our investigation also enlarges the application range of spectra attacks and fast spectra attacks. The two attacks were proposed for the filter generator. This paper shows that they also apply to the binary additive stream cipher based on permutation. Actually, provided that we give an initial sequence which is a shifted sequence of the stream cipher(shifted number is unknown for the attacker), the two attacks will possibly work for the stream cipher.
If we guess the value of ab−1 other than a or b, then the attack complexity can be reduced from O(22n) to O(2nn2lognlog2nlog2log2n). And only O(3.47n) keystream bits are required in the attack. Therefore, the binary additive stream cipher based on the inverse permutation has a small security margin. It implies that a simple inverse permutation is not enough to ensure the security of the stream cipher. A securer permutation should be employed in the stream cipher.
P. Ke, Z. Ye, S. Zhang, et al., "On the cross-correlation distribution of d-ary generalized Legendre-Sidelnikov sequences", Chinese Journal of Electronics, Vol. 27, No. 2, pp. 287–291, 2018. DOI: 10.1049/cje.2017.12.004
[2]
C. Zhao, W. Ma and T. Yan, "Linear complexity of least significant bit of polynomial quotients", Chinese Journal of Electronics, Vol. 26, No. 3, pp. 573–578, 2017. DOI: 10.1049/cje.2016.10.008
[3]
J. Gao, Y. Hu and X. Li, "Linear span of the optimal frequency hopping sequences from irreducible cyclic codes", Chinese Journal of Electronics, Vol. 24, No. 4, pp. 818–823, 2015. DOI: 10.1049/cje.2015.10.026
[4]
W. Liang, X. Zeng and Y. Xu, "The periods of a class of nonlinear feedback shift register sequences", Chinese Journal of Electronics, Vol. 25, No. 2, pp. 296–303, 2016. DOI: 10.1049/cje.2016.03.016
[5]
Y. Zhang, "A chaotic system based image encryption scheme with identical encryption and decryption algorithm". Chinese Journal of Electronics, Vol. 26, No. 5, pp. 1022–1031, 2017. DOI: 10.1049/cje.2017.08.022
T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Revised edition, The North-Holland Mathematical Library, Elsevier, Amsterdam, Nederland, 1998.
R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, London, England, 1996.
[13]
Z. Wan, Geometry of Classical Groups over Finite Fields, Chartwell Bratt Publishing Training Ltd, New York, USA, 1993.
[14]
G. Gong, S. Rϕnjom, T. Helleseth, et al., "Fast discrete Fourier spectra attacks on atream ciphers", IEEE Transactions on Information Theory, Vol. 57, No. 8, pp. 5555–5565, 2011. DOI: 10.1109/TIT.2011.2158480
[15]
S. Rϕnjom and T. Helleseth, "A new attack on the filter generator", IEEE Transactions on Information Theory, Vol. 53, No. 5, pp. 1752–1758, 2007. DOI: 10.1109/TIT.2007.894690
[16]
J. Wang, K. Chen and S. Zhu, "Annihilators of fast discrete Fourier spectra attacks", 7th International Workshop on Security, IWSEC 2012, Fukuoka, Japan, pp. 182–196, 2012.
[17]
D. Wu, W. Qi, H. Chen, "On the spectral immunity of periodic sequences restricted to binary annihilators", Designs, Codes and Cryptography, Vol. 78, No. 2, pp. 533–545, 2016. DOI: 10.1007/s10623-014-0019-5
[18]
X. Feng and G. Gong, "On Algebraic Immunity of Trace Inverse Functions over Finite Fields with Characteristic Two", http://eprint.iacr.org/2013/585.pdf, 2013-12-12.
[19]
Y. Nawaz, G. Gong, and K. C. Gupta, "Upper bounds on algebraic immunity of boolean power functions", Fast software encryption 2006, Graz, Austria, pp. 375–389, 2006.
Zheng, Y., Gao, J., Li, X. et al. A polynomial system for bit-based division property solving by quantum algorithm. Quantum Information Processing, 2023, 22(12): 448.
DOI:10.1007/s11128-023-04179-8