Cube attacks are an important type of key recovery attacks against nonlinear feedback shift register (NFSR)‐based cryptosystems. The key step in cube attacks closely related to key recovery is recovering superpolies. However, in the previous cube attacks including original, division property based and correlation cube attacks, the algebraic normal form of superpolies could hardly be shown to be exact due to an unavoidable failure probability or a requirement of large time complexity. In this study, the authors propose an algebraic method aiming at recovering the exact algebraic normal forms of superpolies practically. The proposed method is developed based on the degree of evaluation method proposed by Liu in Crypto 2017. As an illustration, the authors apply the proposed method to Trivium. As a result, they recover the algebraic normal forms of some superpolies for the 818‐, 835‐, 837‐ and 838‐round Trivium. Based on these superpolies, the authors could mount key‐recovery attacks on 818‐, 835‐, 837‐ and 838‐round Trivium with the worst complexity slightly lower than a brute‐force attack. Besides, for the cube proposed by Liu in Crypto 2017 as a zero‐sum distinguisher for the 838‐round Trivium, it is proved that its superpoly is not zero‐constant. Hopefully, the proposed method would provide some new insights on cube attacks against NFSR‐based ciphers.

In this paper, a new and efficient method for solving affine sub-families included in a family of nonlinear feedback shift register (NFSR) sequences is proposed. The linear case is focused on since the affine case is an analogy. Let f(x0,x1,...,xn) = x0⊕f1(x1,...,xn-1)⊕xnbe a characteristic function of an n-stage NFSR, where n is a positive integer. Let deg(f) = d > 1 and f[d]be the summation of all terms in the algebraic normal form of f whose degrees attain the maximum d. First, it is proved that every linear sub-family of G(f) is a sub-family of linear feedback shift register sequences generated by a characteristic polynomial of the form Σi∈Scixi, where ci∈ F2and S consists of all subscripts of variables appearing in f[d]. That is to say, every linear sub-family of G( f ) is a factor of some polynomial Σi∈Scixiover the finite field F2. This result is a well generalization of linear recurring sequences theory since it also holds if d = 1. Based on this result, a candidate set of linear sub-families could be obtained by polynomial factorizations over F2. Second, we propose a new method to verify a linear sub-family whose memory requirement and time complexity are clearer than the previous method. For instance, all affine sub-families of the 160-bit main register used in Grain v1 could be determined within two seconds by a PC using the new method in this paper, which is unobtainable for previous algorithms.

Grain-128 is a hardware oriented stream cipher based on the cascade connection of a 128-bit linear feedback shift register into a 128-bit quadratic nonlinear feedback shift register (NFSR). Its main register is in essence a quadratic NFSR, however its affine sub-families could not be solved by the previous methods. In this paper, it is shown that the family of sequences generated by the main register of Grain-128 includes no affine sub-families except a small one of order three. To achieve this goal, a new method is proposed for solving affine sub-families of general quadratic NFSRs. Let NFSR(f) be an NFSR with a quadratic characteristic function f . It is proved that the characteristic function of a linear sub-family of the NFSR(f) divides a linear combination of variables appearing in the quadratic terms of f , where the division can be seen as the univariate polynomial division over the finite field F2. This facilitates picking up a candidate set of linear sub-families through univariate polynomial factorization over F2. The affine case is an analogy. Besides, a useful new upper bound on the orders of affine sub-families of a quadratic NFSR is given.

Conditional differential cryptanalysis on NFSR‐based cryptosystems was first proposed by Knellwolf et al . in Asiacrypt 2010 and has been successfully used to attack reduced variants of Grain v1. In this paper, we greatly improve conditional differential attacks on Grain v1 in the following four aspects. First, a new differential engine is derived to correctly track the differential trails of Grain v1. Second, we propose a new difference‐searching strategy which serves to find suitable differences for the conditional differential attack on a given reduced variant of Grain v1. Third, a highly IV‐saving condition‐imposing strategy is presented. Last, we propose a further bias‐increasing strategy. In particular, the improvements on the difference‐searching strategy and the condition‐imposing strategy are crucial to mount conditional differential attacks on the variants of Grain v1 with more than 106 rounds. It is shown that the improved conditional differential attacks could retrieve 31 distinct secret key expressions for 107‐round Grain v1 and could retrieve 15 distinct secret key expressions for 110‐round Grain v1. Both the attacks succeed with constant probabilities. Thus far, our results are the best known for the reduced variants of Grain v1 as far as the number of rounds attacked is concerned.

The well‐known stream cipher Grain‐128a is the new version of Grain‐128. While Grain‐128 is vulnerable against several introduced attacks, Grain‐128a is claimed to be secure against all known attacks and observations on Grain‐128. So far the only published single‐key attack on Grain‐128a is the conditional differential cryptanalysis proposed by Michael Lehmann et al . at CANS 2012. In their analysis, a distinguishing attack on 189‐round Grain‐128a in a weak‐key setting was proposed. In this study, the authors present two new conditional differential attacks on Grain‐128a, i.e. attack A and attack B. In attack A, the authors successfully retrieve 18 secret key expressions for 169‐round Grain‐128a. To the best of our knowledge, attack A is the first attack to retrieve secret key expressions for reduced Grain‐128a. In attack B, the authors extend the distinguishing attack against Grain‐128a up to 195 rounds in a weak‐key setting. Thus far, attack B is the best known attack for reduced Grain‐128a as far as the number of rounds attacked is concerned. Hopefully, the authors’ reflections on the design of Grain‐128a provide insights on such compact stream ciphers.

The well‐known stream cipher Grain v1 is one of the finalists of European eSTREAM project. In this study, a novel guess‐and‐determine attack on Grain v1 is introduced. The attack primarily employs a new conditional BSW sampling technique and the main creative idea is that the conditions are set not only on state bits but also on the updates of the registers for the BSW sampling technique. It is shown that using this technique we can further reduce the sampling resistance of Grain v1 to which is the best result so far. The attack leads to an efficient internal state recovery of Grain v1 with only online time employing a memory of , requiring keystreams each of length and preprocessing time. It is shown that these figures are obviously better compared with the previous results. This is also the first attempt to control the updates of the registers of Grain v1 in the guess‐and‐determine attack and hopefully this provides new insights for cryptanalysis on such compact stream ciphers.

The Feistel‐2 cipher is a type of Feistel ciphers proposed by Isobe and Shibutani at Asiacrypt 2013. Its round functions consist of a public F ‐function and a subkey XORed before the F ‐function. Recently, a variation of the Feistel‐2 cipher, in which the subkey is XORed after the F ‐function, has been widely used in proposals such as SIMON and Simeck. The authors denote this type of Feistel ciphers as Feistel‐2. In this study, they study the security of Feistel‐2* ciphers. First, they propose the differential function reduction technique. Then, they present all‐subkeys‐recovery attacks against Feistel‐2* ciphers based on this technique. Let z be the key size to block size ratio of block ciphers. It is shown that their attacks can break up 6, 8 and 10 rounds of the Feistel‐2* cipher for z = 1, 3/2 and 2, respectively. Thanks to the meet‐in‐the‐middle approach, their attacks only need a few chosen plaintexts. Moreover, with higher‐data complexity, all attacks can be improved by one round. This implies that a secure Feistel‐2* cipher should at least iterate 8, 10 and 12 rounds for z = 1, 3/2 and 2, respectively.

Nonlinear feedback shift registers (NFSRs) are widely used in stream cipher design as building blocks. In this paper, we study the problem of decomposing an NFSR into the cascade connection of an NFSR into a linear feedback shift register (LFSR), which is a kind of concatenation of an NFSR and LFSR. A necessary and sufficient condition for such decomposition is provided and other algebraic properties about such decomposition are also studied. Based on these theoretical results, a binary decision diagram (BDD)-based algorithm for such decomposition is proposed. Compared with the previous algorithm proposed by Ma et al., our algorithm can find more accurate candidate LFSR and the algebraic properties presented in this paper guarantee that the memory requirement during our verification is linear in the size of the BDD of the NFSRs characteristic function.

Letnbe a positive integer. An NFSR ofnstages is called irreducible if the family of output sequences of any NFSR of stages less thannis not included in that of the NFSR. In this paper, we prove that the density of the irreducible NFSRs ofnstages is larger than 0.39. This implies that it is expected to find an irreducible NFSR ofnstages among three randomly chosen NFSRs ofnstages.

LetMbe a square-free odd integer andZ/(M) the integer residue ring moduloM. This paper studies the distinctness of primitive sequences overZ/(M) modulo 2. Recently, for the case ofM=pq, a product of two distinct prime numberspandq, the problem has been almost completely solved. As for the case thatMis a product of more prime numbers, the problem has been quite resistant to proof. In this paper, a partial proof is given by showing that a class of primitive sequences of order 2n'+1 overZ/(M) is distinct modulo 2, wheren'is a positive integer. Besides as an independent interest, this paper also involves two distribution properties of primitive sequences overZ/(M), which are related closely to our main results.

Let p be an odd prime number, e an integer greater than 1, and Z/(pe) the integer residue ring modulo pe. In this paper, we obtain an improved result of the previous paper (IEEE Trans. Inf. Theory, 56(1) (2010) 555-563) on distribution properties of compressing sequences derived from primitive sequences over Z/(pe). It is shown that two primitive sequences α and b generated by a strongly primitive polynomial f(x) over Z/(pe) are the same, if there exist s∈ Z/(p) and k∈ Z(p)* such that the distribution of in their compressing sequences ae-1+η(a0,⋯.ae-2) and be-1+η(b0,⋯,be-2) is coincident at the positions t with α(t)=k, where η(x0,⋯,xe-2) is an (e-)-variable polynomial over Z/(p) with the coefficient of xe-2p-1⋯x1p-1x0p-1not equal to (-1)e· (p+1)/2 and α is an m-sequence over Z/(p)determined by f(x) and a. Compared with the previous result, this gives a more precise characterization on the positions of a compressing sequence, i.e., of the form ae-1+η(a0,⋯,ae-2), derived from a primitive sequence a over Z/(pe) that completely determines a. In particular, the result is also true for the highest level sequence ae-1by taking η(x0,⋯,xe-2)=0.

Although 2 -adic complexity was proposed more than ten years ago, even form-sequences which are thought of as the most important linear recurring sequences, no theoretical results about their 2-adic complexity has been presented. In this paper, it is shown that for a binarym-sequence, its 2-adic complexity attains the maximum, which implies that no feedback with carry shift registers (FCSRs) with connection integer less than22n-1- 1 can generatem-sequences of ordern.

It has long been open whether all pairs of proper decimations of l-sequences based on primes are cyclically distinct. By determining the nontrivial maximal autocorrelation of l-sequences, this paper presents a partial proof of the distinctness problem. Since the proof idea is completely different from former ones, the set of decimations that are known to be cyclically distinct is further enlarged. On the basis of convincing experimental data, the proof seems to ensure that more than 79% of l-sequences based on different primes satisfy the fact that every pair of proper decimations is cyclically distinct. In particular, a complete proof is provided for l-sequences based on primes of the form $2\cdot r+1$, where r is an odd prime number.

Let Zopf/(pe) be the integer residue ring with odd prime p and integer eges2. For a sequence a_ over Zopf/(pe), one has a unique p-adic expansion a_=a_0+a_1.p+...+a_(e-1).pe-1, where a_ican be regarded as a sequence over Zopf/(p) for 0lesilese-1. Let f(x) be a strongly primitive polynomial over Zopf/(pe) and G'(f(x), pe) be the set of all primitive sequences generated f(x) by over Zopf/(pe). Recently, the authors, Xuan-Yong Zhu and Wen-Feng Qi, have proved that for a function phi(x0,...,xe-1)=g(xe-1)+eta(x0,...,xe-2)over Zopf/(p) and a_,b_isinG'f(x),pe), where 2lesdeg glesp-1, phi(a_0,a_1...,a_e-1)=phi(b_0,b_1...,b_e-1) if and only if a_=b_. To further complete their work, we show that such injectivity also holds for deg g=1. That is for a function phi(x0,...,xe-1)=xe-1+eta(x0,...,xe-2)over Zopf/(p) and a_,b_isinG'f(x),pe), phi(a_0,a_1...,a_e-1)=phi(b_0,b_1...,b_e-1) if and only if a_=b_.

In this correspondence, we investigate feedback with carry shift register (FCSR) memory sequences. For an -sequence generated by an FCSR with connection integer and initial memory , we prove that for , where and is the memory sequence. Generally speaking, the period of a memory sequence is a factor of that of the FCSR output binary sequence. We show there are a large number of connection integers, with which an FCSR can generate sequences that have the same period as their memory sequences, especially including all connection integers for -sequences.