Portal de Periódicos da CAPES

Conditional differential attacks on Grain‐128a stream cipher

2016; Institution of Engineering and Technology; Volume: 11; Issue: 3 Linguagem: Inglês

10.1049/iet-ifs.2016.0060

1751-8717

Zhen Ma, Tian Tian, Wen‐Feng Qi,

Physical Unclonable Functions (PUFs) and Hardware Security

IET Information SecurityVolume 11, Issue 3 p. 139-145 Research ArticleFree Access Conditional differential attacks on Grain-128a stream cipher Zhen Ma, Zhen Ma National Digital Switching System Engineering and Technological Research Center, P.O. Box 407, 62 Kexue Road, Zhengzhou, 450001 People's Republic of China State Key Laboratory of Cryptology, P.O. Box 5159, Beijing, 100878 People's Republic of ChinaSearch for more papers by this authorTian Tian, Tian Tian National Digital Switching System Engineering and Technological Research Center, P.O. Box 407, 62 Kexue Road, Zhengzhou, 450001 People's Republic of ChinaSearch for more papers by this authorWen-Feng Qi, Corresponding Author Wen-Feng Qi wenfeng.qi@263.net National Digital Switching System Engineering and Technological Research Center, P.O. Box 407, 62 Kexue Road, Zhengzhou, 450001 People's Republic of ChinaSearch for more papers by this author Zhen Ma, Zhen Ma National Digital Switching System Engineering and Technological Research Center, P.O. Box 407, 62 Kexue Road, Zhengzhou, 450001 People's Republic of China State Key Laboratory of Cryptology, P.O. Box 5159, Beijing, 100878 People's Republic of ChinaSearch for more papers by this authorTian Tian, Tian Tian National Digital Switching System Engineering and Technological Research Center, P.O. Box 407, 62 Kexue Road, Zhengzhou, 450001 People's Republic of ChinaSearch for more papers by this authorWen-Feng Qi, Corresponding Author Wen-Feng Qi wenfeng.qi@263.net National Digital Switching System Engineering and Technological Research Center, P.O. Box 407, 62 Kexue Road, Zhengzhou, 450001 People's Republic of ChinaSearch for more papers by this author First published: 01 May 2017 https://doi.org/10.1049/iet-ifs.2016.0060Citations: 8AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract 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. 1 Introduction Conditional differential cryptanalysis on non-linear feedback shift register based (NFSR-based) cryptosystems was first introduced by Knellwolf et al. at Asiacrypt 2010 [1]. Inspired by the message modification techniques introduced in [2] for hash function cryptanalysis, the basic idea of the conditional differential attack on NFSR-based cryptosystems is to trace the differences round by round and identify conditions on the internal variables that control the propagations of the difference through the first few rounds in the initialisation process. The attackers derive IVs that satisfy the conditions and enable them to detect a bias in the output difference. Simple conditions that assign certain IV bits to fixed values 0 or 1 are called Type 0 conditions, while conditions that are relations between IV bits and secret key bits are called Type 1 conditions. In a chosen IV scenario, Type 0 conditions can be easily satisfied and Type 1 conditions can be used to recover secret key expressions. Conditional differential cryptanalysis has been successfully applied to many NFSR-based stream ciphers. It targets the initialisation process of stream ciphers and consists in analysing the distribution of output differences on specifically chosen initial values (IVs). In [1], an extended version of which is presented in [3], Knellwolf et al. presented conditional differential attacks on Grain v1 and Grain-128. They retrieved four secret key expressions for reduced Grain v1 with 104 out of 160 rounds and derived a distinguishing attack on reduced Grain-128 up to 215 out of 256 rounds. In [4], the author revisited Knellwolf's attacks on Grain v1 and provided a theoretical framework to prove the correctness of these attacks. In [5], Lehmann and Meier proposed a conditional differential cryptanalysis of Grain-128a. They found a significant bias of the output difference at 177 out of 256 rounds with only conditions on IV bits and presented a distinguisher on 189-round Grain-128a with a class of weak keys. In [6], Knellwolf et al. improved their techniques using automatic tools to find and analyse the involved conditions, and presented a distinguishing attack on reduced Trivium up to 961 of 1152 rounds with a class of weak keys. In [7], Banik presented a conditional differential attack on 105-round Grain v1 and retrieved six secret key expressions. A distinguisher on 106-round Grain v1 was introduced by Sarkar in [8]. These results show that conditional differential attack is a versatile and important tool for the cryptanalysis on NFSR-based stream ciphers. In this paper, we focus on the conditional differential attack against Grain-128a. The stream cipher Grain-128 [9] was proposed as a variant of Grain v1 [10] with 128-bit secret key. While Grain v1 is chosen as one of seven finalists by European eSTREAM project, Grain-128 is vulnerable against several attacks [11-14]. In particular, Dinur et al. [14] presented a full key recovery attack on the full version of Grain-128 faster than exhaustive search by a factor of about 238. As a response, the designers proposed a new version of Grain-128 with optional authentication, named Grain-128a [15]. The new version modified the IV padding and adopted a different non-linear update function to increase the security level. Except for some fault attacks [16-18], and related key attacks [19, 20], so far conditional differential cryptanalysis is the only published single-key attack on Grain-128a [5]. In this paper, we shall show some new results on the conditional differential attacks against Grain-128a. First, we derive a new differential engine ΔGrain-128a to correctly track the differential trails of Grain-128a during the whole initialisation process. Second, we focus on retrieving secret key expressions for reduced Grain-128a with only conditions on IV bits in attack A. Note that the previous attack on reduced Grain-128a with only conditions on IV bits introduced in [5] adopted a cube of order 33, and for each difference, the attackers controlled only one propagation by imposing Type 0 conditions. Since the expressions of the subsequent propagations include only secret key bits, they could not control more propagations. Consequently, they could not obtain Type 1 conditions and so they could not retrieve secret key expressions. In our attack, we identify the differences whose first few propagations can be effectively controlled with only conditions on IV bits and more importantly, with respect to which Type 1 conditions can be imposed which enables us to retrieve secret key expressions. Moreover, the definition of effective difference is introduced to characterise the difference which will result in a non-zero bias in the output difference without conditions on secret key bits, and algorithms to search the effective differences are proposed. As a result, we successfully retrieve 18 secret key expressions for 169-round Grain-128a. Third, in attack B, since in a weak-key setting conditions can be also imposed on secret key bits, a completely different difference-searching strategy than that in attack A is derived. For a given round r, the strategy targets finding an appropriate difference with respect to which a significant bias in the output difference of r -round Grain-128a can be found in a weak-key setting. Using the strategy, we successfully distinguish Grain-128a up to 195 rounds. Thus far, attack A is the first attack known to retrieve secret key expressions for reduced Grain-128a, and attack B is the best known attack for reduced Grain-128a in a weak-key setting as far as the number of rounds attacked is concerned. The paper is organised as follows. Some preliminaries are presented in Section 2. The differential engine ΔGrain-128a is introduced in Section 3. Two conditional differential attacks against reduced Grain-128a are detailedly described in Section 4. Finally, we conclude the paper in Section 5. In this paper, the operations '+' and '−' denote the ordinary integer addition and subtraction, respectively, while the operation '' denotes the addition modulo 2. The finite field of two elements is denoted by and for a positive integer n, the n -dimensional vector space over is denoted by . 2 Preliminaries and notations Here we briefly describe Grain-128a, introduce the frequency test to a random Boolean function, and discuss its application in our analysis. Please refer subsection 2.2 in [1] for the definition of derivatives of Boolean functions. 2.1 Description of Grain-128a Grain-128a consists of a mechanism that produces a pre-output stream, and two different modes of operation: with or without authentication. Authentication is mandatory when iv0 = 1, and forbidden when iv0 = 0. In our analysis, iv0 is assumed to be 0 and the authentication mode is ignored. Grain-128a accepts a 128-bit secret key and a 96-bit . The pre-output generator of Grain-128a consists of three main building blocks, namely a 128-bit LFSR, a 128-bit NFSR, and a pre-output function. A general overview of the design is given in Fig. 1. Fig. 1Open in figure viewerPowerPoint Overview of Grain-128a's keystream generation algorithm Let us denote the state of Grain-128a at round t by St = [Bt ||Lt], where denotes the content of the NFSR and denotes the content of the LFSR. The registers are initialised as where the IV padding refers to the padding that the LFSR state bits l96, …, l126 are set to 0 and l127 is set to 1. For t ≥ 0, the update functions of the NFSR and the LFSR are where g is a 29-variable non-linear Boolean function of degree 4 and f is a 6-variable linear Boolean function. The pre-output function is defined as (1)where A = {2, 15, 36, 45, 64, 73, 89} and (2)In the mode without authentication, the output function is simply defined as zt = yt, t ≥ 0, which means all pre-output bits are used directly as keystream. Since the authentication mode is ignored in our analysis, we always take this as the output function in the following paper. Before generating keystreams, Grain-128a goes through an initialisation process. During the initialisation process, the cipher is clocked 256 times without producing any keystream. Instead, the output function is fed back and xored with the input, both to the NFSR and to the LFSR. The initialisation process of Grain-128a is presented in Fig. 2. Fig. 2Open in figure viewerPowerPoint Overview of Grain-128a's initialisation process The updates of the NFSR and the LFSR in the initialisation process, i.e. bits l128+t and b128+t, are called the internal variables and St is called the internal state for t ≥ 0. Next, we introduce some useful notations with respect to differential cryptanalysis on Grain-128a. Let us denote one-bit difference inserted in the i th position of IV by ei, 0 ≤ i ≤ 95. Then at round t ≥ 0, the corresponding states of Grain-128a with respect to ei are St and , the updates of the NFSR/LFSR loaded with B0 /L0 and are denoted by bt+128 /lt+128 and , respectively, and the output bits are zt and , respectively. The symbol 'Δ' denotes bit difference as well as vector difference. For example, the difference of lt and lt′ is denoted by Δlt. Furthermore, the bias ε in the output difference at round t is defined as the deviation of its distribution from 1/2, i.e. If we consider round-reduced variants of Grain-128a with r initialisation rounds (r -round Grain-128a for short), the feedback of the output stops after r rounds and the first keystream bit is zr. For r ≥ 0, the differential trails of r -round Grain-128a is defined as three integer arrays, i.e. ΔNFSR = [Δb0, Δb1, …, Δbr +127], ΔLFSR = [Δl0, Δl1, …, Δlr +127] and Δoutput = [Δz0, Δz1, …, Δzr]. 2.2 Random Boolean functions and frequency test Let D be a non-empty subspace of . Let f be a Boolean function on D and c1, c2, …, cN be the outputs of f on the set {x1, …, xN } ⊆ D. Let be the sum of the outputs. Suppose f is random on D and let . Then the law of large numbers says that for a sufficiently large N, the value y approximately follows a standard normal distribution (see [21], Chapter 2). Then the Boolean function f is said to pass the frequency test on D at a significance level α if where Φ is the standard normal distribution. If f fails to pass the frequency test on D at the significance level α, i.e. (3)then we say f passes the bias test with the significance level α. It is well known that a random Boolean function passes the bias test with probability 2α. Therefore, the smaller the α is, the higher probability that one can distinguish random functions from non-random ones. In practice, the significance level is often taken as 0.01 or 0.001. Now we introduce an application of the frequency test to Boolean functions, i.e. a method to estimate the number of IVs needed to detect a bias ε in Δzr. Suppose we need Nα pairs of IVs to detect the bias with significance level α. Let Δzr, j be the output difference of r -round Grain-128a with respect to the j th pair of IVs. Let us denote and . Then the expected values of U and y are and , respectively. According to the frequency test, to detect this bias with the significance level α, the number y must satisfy (3). Substitute y by its expected value in (3) and we obtain the estimation of Nα that (4)where uα satisfies . This implies that we need at least pairs of IVs to detect the bias. If the effective IV space, i.e. free IVs, is larger than Nα, then we can detect the bias with the significance level α; otherwise we fail. 3 Differential Engine ΔGrain-128a To compute the bias in the output difference at some round t ≥ 0, we devise a tool ΔGrain-128a that will keep track of the differential trails of Grain-128a during the initialisation process. The tool is an improvement of the engine ΔGrain proposed in [4]. While ΔGrain incorrectly computed the items of the differential trails at some rounds, our improved engine computes the differential trails correctly during the whole initialisation process. For an inserted difference ei, the major task of Algorithm ΔGrain-128a (see Fig. 3) is to ascertain the differences between St and for t ≥ 0. The algorithm takes two inputs, i.e. the position of the difference i and the number of rounds r, and returns the differential trails of Grain-128a, i.e. two integer arrays ΔNFSR, ΔLFSR of 128 + r items and an integer array Δoutput of r items. Note that the items in the differential trails could be 0, 1 or 2. Value 0 or 1 indicates the difference of the corresponding items in St and is certain and always 0 or 1. Value 2 indicates the difference of the corresponding items in St and is uncertain and probabilistically either 0 or 1, and the exact value depends on the value of secret key and IV. Fig. 3Open in figure viewerPowerPoint Algorithm 1 ΔGrain-128a We have the following explanations for Algorithm ΔGrain-128a: Algorithm ΔGrain-128a determines the differences Δzt (or Δlt, Δbt) to be 0, 1 or 2 according to: (a) if there exists a non-zero difference in any variable appearing in the non-linear terms of the output function (or the update functions), then output 2; (b) else if there exists a difference 2 in any independent linear variable, i.e. the linear variable does not appear in any non-linear term of the output function (or the update functions), then output 2; (c) else output the sum modulo 2 of all the differences of independent linear variables in the output function (or the update functions). It appears that the original function ht has no independent linear variable, but this is not always true. In fact, the function ht has 20 distinct forms at different rounds due to the IV padding. In particular, the actual function ht has independent linear variables at certain rounds during the initialisation process which are listed in Table 1. Algorithm ΔGrain-128a specially handles these situations in lines from 11 to 14. Table 1. Independent linear variables of ht Round t 17–36 49–66 76–82 108–113 Independent linear variable lt +60 lt +79 lt +13 lt +20 4 Conditional differential attacks on Grain-128a In this section, we will present two conditional differential attacks on reduced versions of Grain-128a, i.e. attack A and attack B. In attack A, we will show that secret key expressions can be retrieved for reduced Grain-128a with only conditions on IV bits, while the previous attacks failed to do so. In attack B, we will present a distinguisher on Grain-128a up to 195 rounds in a weak-key setting. The framework of our attacks on reduced Grain-128a can be divided into the following steps. Step 1 Searching the appropriate difference. For attack A and attack B, we propose different difference-searching strategies, respectively. These strategies are detailedly described in the following section. In general, one-bit differences propagate slower than multi-bit differences, and thus we only consider one-bit differences ei where i ∈ [1, 95]. Step 2 Imposing conditions on IV or secret key bits. Note that in the previous attacks, conditions were only imposed to control the first few differential propagations, while in our attack, conditions are also imposed to directly modify the output difference to further raise its bias. In attack A, conditions are only imposed on IV bits, while in attack B, conditions are also imposed on secret key bits. Step 3 Calculating the bias in the output difference. We take the help of the differential engine ΔGrain-128a and use the theoretical framework proposed in [4] to compute the bias in the output difference. Note that conditions imposed at step 2 to control the propagations should be added to ΔGrain-128a. For instance, if the propagation at round t1 is controlled, then a clause 'if t = t1 then Δzt ← 0' should be inserted at the third line from the bottom. Step 4 Estimating the number of needed IVs. Estimate the number of IVs needed to detect the bias with a given significance level α. If the effective IV space is larger than the estimation, then the attack succeeds with a constant probability; otherwise the attack fails. Note that iv0 is not free since it is set to be 0 to forbid the authentication mode. Suppose in total we impose n conditions on IV bits, then the effective IV space is reduced to 295−ω −n, where ω is the order of the inserted difference. Before presenting attack A and attack B, we first show some crucial observations on Grain-128a. 4.1 Observations on Grain-128a In the following, we call the differential propagation whose expression includes only secret key bits Type A propagation. It is clear that one cannot control Type A propagations with only conditions on IV bits. A further calculation shows that the value of the expression of Type A propagation is balanced for the most cases. As a result, the occurrence of Type A propagation in the first few (usually five) propagations will result in zero-bias in the output difference with a large probability. Thus to control the subsequent propagations is of little meaning and to retrieve secret key expressions is impossible since Type 1 conditions could not be obtained. Since we try to retrieve secret key expressions with only conditions on IV bits in attack A, the difference whose Type A propagation occurs in the first five propagations should be avoided. Therefore, in this subsection, we first identify the differences whose Type A propagation occurs later than the first five propagations and then obtain the differences whose first five propagations can be effectively controlled with only conditions on IV bits. Observation 1.Let . Then the first propagation of the difference ei with i ∈ TAP1 is a Type A propagation. Moreover, for the differences with positions in , the expressions of the first propagation is a single secret key bit and for the differences e94 and e95, the expressions are a product of two secret key bits. Proof.First, for the difference ei with i ∈ [8, 12], the first propagation occurs when the difference goes into the LFSR state variable lt +8 of the output function at round t = i − 8 and its expression is bt +12. Since t + 12 < 128, bt +12 is a secret key bit. Second, for difference ei with i ∈ [42, 74], the first propagation occurs at round t = i − 42 when the difference goes into the LFSR state variable lt +42 of the output function and its expression is bt +95. Since t + 95 < 128, bt +95 is a secret key bit. Last, for differences e94 and e95, the first propagation occurs when the difference goes into the LFSR state variable lt +94 of the output function at rounds t = 0 and t = 1 respectively and its expression is bt +12 bt +95. Since t + 95 < 128, bt +12 bt +95 is a product of two secret key bits. □ Observation 2.Let TAP2 = [13, 19] and TAP3 = [20, 41]. Then the second propagation of the difference ei with i ∈ TAP2 is a Type A propagation, and the third propagation of the difference ei with i ∈ TAP3 is a Type A propagation. Proof.The second propagation of the difference ei with i ∈ TAP2 and the third propagation of the difference ei with i ∈ TAP3 occur both when the difference goes into the LFSR state variable lt +8 of the output function at round t = i − 8 and the expression is bt +12, which is obvious a secret key bit. □ Observation 3.Let TAP4 = {1, 93}. Then we cannot control the first propagation of the difference e1 or the second propagation of the difference e93 with only conditions on IV bits although the expressions include both IV and secret key bits. Proof.The first propagation of the differences e1 and the second propagation of e93 are as follows: If one wants to nullify either of the propagations, say the first propagation of e93, then the conditions '' and '' must be imposed, which implies the equations 'b121 b125 b126 = 0' and 's75 = 1' must be satisfied. However, with only conditions on IV bits, the first equation cannot be satisfied all the time. Similarly, the results can be proved for e1. □ The following proposition presents the differences whose first five propagations can be effectively controlled with only conditions on IV bits. Proposition 1.There are in total 25 one-bit differences that one can control at least the first five propagations without conditions on secret key bits. The positions of these differences belong to the set .The results can be verified by detailedly analysing the first five propagations of these differences one by one. 4.2 Attack A In this subsection, we will present a conditional differential attack on 169-round Grain-128a with only conditions on IV bits. It will be shown that 18 secret key expressions can be retrieved in this attack. From Section 4.1, we know that, if we only impose conditions on IV bits, then we should choose differences provided by Proposition 1. However, for a specific attack on round r, whether these candidate differences are really 'appropriate' in the sense that the output difference of r -round Grain-128a shows an evident bias still needs checking. Suppose one inserts the difference ei into IV. Denote Then from (1) and the pilling up lemma, we have (5)where εΔx denotes the bias in the difference of x. Let us denote and Note that we use theoretical framework proposed in [4] to compute the bias in the differences of the internal variables and the output bit. It can be seen from (5) that if any of the factor bias is zero, then is zero and all the computations are in vain. Therefore, we introduce the definition of the effective difference which is a necessary condition for a successful attack. Definition 1.An effective difference for attack A on r -round Grain-128a (an effective difference for round r for short) is the difference resulting in non-zero biases in all the differences in ΔOr without conditions on secret key bits. The following proposition tells us that there is no need to specially take care of the value since most of the differences will guarantee a non-zero . Recall the function ht is given in (2). Proposition 2.Even if the biases in the differences Δlt +42, Δlt +60, Δlt +79, Δlt +94 and Δbt +95 are all zeros, Δht still has an obvious bias 1/32 as long as the differences Δst +8, Δst +13, Δst +20 and Δbt +12 are all zeros. Proof.One can compute the distribution of Δht as follows where 'i1, i2, i3, i4, i5' denotes 'Δlt +42 = i1, Δlt +60 = i2, Δlt +79 = i3, Δlt +94 = i4, Δbt +95 = i5'. With the assumption that all the internal variables are independent from each other and uniformly distributed, the probability can be substituted by 1/25. Then one can easily compute the value □ Since uncertain differences in the variables st +8, st +13, st +20 and bt +12 can be easily nullified due to their small tap positions, Proposition 2 implies that most of the differences will guarantee an obvious . Next, we design Algorithm Select effective difference to automatically search effective differences which guarantee the biases in the other seven differences in ΔOt to be non-zero. First we introduce some useful notations. Denote and where the items can be 0, 1 or '2'. Of all the variables in the update function of bt, we denote BUt the vector including all the variables whose differences are uncertain and BCt the vector including those whose differences are certain. Similarly we denote LUt and LCt. The vectors including the differences of the items in these vectors are denoted by ΔBUt, ΔBCt, ΔLUt and ΔLCt. Now we explain the basic idea of the algorithm by an example. Let us consider whether e69 is an effective difference for the attack on 177-round Grain-128a. Set r = 177 and the position 69 to be the input of the differential engine ΔGrain-128a. Then we can obtain the vector LO177 from the output of the engine that ΔLO177 = [2, 0, 2, 2, 2, 2, 2]. It can be seen that the differences in ΔLO177 are all uncertain except for Δb179. Let us calculate the bias in the difference Δb192. In the update function of b192, b155 is an independent linear variable and it can be calculated that Δb155 = b122. Due to the random distribution of b122, we have and it follows that . This implies that the bias is zero and thus, e69 is not an effective difference. Based on this observation, we have the following proposition about the difference ei. Proposition 3.If the expression of any difference in ΔLOr includes an independent linear secret key bit, then ei is not an effective difference for round r. More generally, if the expression of any difference in ΔLOr includes an independent linear variable whose difference has no bias and cannot be nullified, then ei is not an effective difference for round r. On the basis of Proposition 3, Algorithm Detect uncertain difference (see Fig. 4) recursively detects whether an uncertain difference has no bias and cannot be nullified, and finally Algorithm Select effective difference determines whether a difference is effective for a specific round. We run Algorithm Select effective dsifference (see Fig. 5) to search the effective differences from the candidate differences given in Proposition 1. Experimental data show that for any given round r, only a small number of differences are effective and for some rounds even no effective difference exists. Part of the experimental results are listed in Table 2. Fig. 4Open in figure viewerPowerPoint Algorithm 2 Detect uncertain difference Fig. 5Open in figure viewerPowerPoint Algorithm 3 Select effective difference Table 2. Effective differences for some rounds r 165 166 167 168 169 170 171 172 174 175 i 76,87,89,92 77,88,90 75,78,89,91 76,79,90,92 80,91 92 75 76,92 75 76,92 For r > 160, we try all the effective differences in the conditional differential attacks on r -round Grain-128a and the highest round we could attack with only conditions on IV bits is 169 rounds with respect to e80. To obtain an obvious bias in the output difference, we need to impose conditions on IV bits to control the differential propagations of e80. In total, we control ten rounds of propagations. The differential propagations at these rounds are as follows: Furthermore, we also impose conditions on IV bits to modify the output difference to get a bigger bias. To sum up, 65 conditions are imposed on IV bits, including 47 Type 0 conditions and 18 Type 1 conditions. In specific, IV bits imposed to 0 are as follows: and IV bits imposed to 1 are l33, l87 and l93. Type 1 conditions are derived by imposing the following internal variables to 0: Among these Type 1 conditions, only 1 condition is a linear equation, that is, and the others are non-linear equations. Then the effective IV space is 295−1−65 = 229. Next, with all the conditions imposed, we compute the bias in the output difference and obtain that According to (4), the bias can be detected with the significance level 0.001 using 227.25 pairs of IVs. This implies that in the attack on 169-round Grain-128a, we could retrieve 18 secret key expressions with success probability about 0.998. The whole attack consists of guessing 18 secret key expressions and detect the bias with 227.25 IV bits and thus, the complexity is 218+1+27.25 ≃ 246.25 evaluations of the 169-round Grain-128 initialisation process. Since some wrong guesses may also show a distinguishing feature, the values of secret key expressions should be determined using Mastermind method [See http://en.wikipedia.org/wiki/Mastermind_(board_game)]. This method was also used in [3]. In specific, for each of the 218 guesses of the 18 secret key expressions, Nα = 227.25 pairs of IVs are used to check whether it can pass the bias test with significance level 0.001, and record it as a candidate guess if it passes the test. Suppose in total y guesses pass the bias test (usually about 2α · Nα guesses will pass the bias test). By counting the number of '1' in the candidate guesses of each secret key expression, we determine the value to be 1 if the number excesses y /2 and otherwise to be 0. A prerequisite for Mastermind method is that the correct guess passes the bias test. Since the whole complexity of the attack is beyond our computation capability, we only examine whether the correct value will pass the bias test with significance level 0.001. We test 512 randomly generated secret keys to see their probability to pass the test. Thus the complexity of our experiment is 227.25+1+9 = 237.25 evaluations of the 169-round Grain-128a initialisation process. The result shows that 504 secret keys pass the bias test. Then the success probability is 504/512 = 98.4% for this experiment. 4.3 Attack B In this section, we present a conditional differential attack on 195-round Grain-128a in a weak-key setting. Since in a weak-key setting we can impose conditions on secret key bits, the difference-choosing strategy is completely different than that in attack A. In specific, for any given round r and any difference ei, the following vectors can be obtained from the outputs of the ΔGrain-128a with the input i and r : Since the random behaviours of the uncertain differences of the input variables will contribute to the random behaviour of the difference of the output bit (or the internal variables), the difference ei is chosen based on the principle that the total number of '2' in the above vectors is minimum. Note that the minimum number of '2' in the vector ΔLOr is not sufficient to select an appropriate difference since a large number of '2' in the other eight vectors will cost lots of IV bits during the condition-imposing phase. We design an algorithm to automatically search the appropriate differences for a given round r based on the above principle, and compute the bias in the output difference. The experimental data show that the highest round of Grain-128a we could attack is 195 with respect to the difference e69. In this attack, 63 conditions are imposed on IV bits and 9 conditions are imposed on secret key bits. In specific, Type 0 conditions are where IV bits are all imposed to 0. Type 1 conditions are derived by imposing the following internal variables to 0: The secret key bits b62, b73, b77, b87, b96, b108, b109, b111, b112, b122 are imposed to 0.With all these conditions satisfied, we compute the bias and obtain that According to (4), the bias can be detected with significance level 0.001 using 230.25 pairs of IVs, which is smaller than the effective IV space 231. 5 Conclusions In this paper, we study the conditional differential attacks on the stream cipher Grain-128a. In comparison with the previous conditional differential attacks proposed in [5], our main contributions include three respects. First, a differential engine ΔGrain-128a is devised to keep track of the differential trails of Grain-128a. Second, based on some observations on the structural characteristics of Grain-128a and the crucial technique of searching the effective difference, we successfully retrieve 18 secret key expressions with only conditions on IV bits in attack A. While the previous attacks could not retrieve any secret key information. Third, we further extend the conditional differential attack on Grain-128a with conditions on IV bits as well as on secret key bits from 189 rounds in [5] up to 195 rounds in attack B. Based on our analysis, these attacks are the best found using our approach. Hopefully, our reflections on the design of Grain-128a provide insights on such compact stream ciphers. 6 Acknowledgments This work was supported by the National Natural Science Foundations of China under grant nos. 61272042, 61521003, and 61309017. This work was also supported by the National 863 Program of China under grant no. 2015AA01A708. 7 References 1Knellwolf, S., Meier, W., Naya-Plasencia, M.: 'Conditional differential cryptanalysis of NLFSR-based cryptosystems'. Proc. 16th Conf. Theory and Application of Cryptology and Inform. Security (ASIACRYPT 2010), Singapore, 2010, pp. 130– 145 2Wang, X., Yu, H.: 'How to break MD5 and other hash functions'. Proc. 24th Conf. Theory and Application of Cryptographic Techniques (EUROCRYPT 2005), Aarhus, Denmark, 2005, pp. 19– 35 3Knellwolf, S.: ' Cryptanalysis of hardware-oriented ciphers, The Knapsack Generator, and SHA-1'. PhD thesis, ETH Zurich University, 2012 4Banik, S.: 'Some insights into differential cryptanalysis of Grain v1'. Proc. Information Security and Privacy – 19th Australasian Conf. (ACISP 2014), Wollongong, NSW, Australia, 2014, pp. 34– 49 5Lehmann, M., Meier, W.: 'Conditional differential cryptanalysis of Grain-128a'. Proc. 11th Int. Conf. Cryptology and Network Security (CANS 2012), Darmstadt, Germany, 2012, pp. 1– 11 6Knellwolf, S., Meier, W., Naya-Plasencia, M.: 'Conditional differential cryptanalysis of Trivium and KATAN'. Proc. 18th Int. Workshop on Selected Areas in Cryptography (SAC 2011), Toronto, Ontario, Canada, 2011, pp. 200– 212 7Banik, S.: ' Conditional differential cryptanalysis of 105 round Grain v1'. Cryptography Communication DOI: 10.1007/s12095-015-0146-5 ( Springer, Heidelberg, 2015) 8Sarkar, S.: 'A new distinguisher on Grain v1 for 106 rounds'. Proc. 11th Int. Conf. Information System Security, Kolkata, India, 2015, pp. 334– 344 9Hell, M., Johansson, T., Maximov, A. et al: 'A stream cipher proposal: Grain-128'. Proc. 2nd Conf. Information Theory, Washington, DC, USA, 2006, pp. 1614– 1618 10Hell, M., Johansson, T., Meier, W.: 'Grain: a stream cipher for constrained environments'. New Stream Cipher Designs, (LNCS 4986), 2008, pp. 179– 190 11Aumasson, J.P., Dinur, I., Henzen, L. et al: ' Efficient FPGA implementations of high-dimensional cube testers on the stream cipher Grain-128'. Available at http://eprint.iacr.org/2009/218.pdf, accessed 26 January 2016 12Stankovski, P.: 'Greedy distinguishers and nonrandomness detectors'. Proc. 11th Int. Conf. Cryptology in India (INDOCRYPT 2010), Hyderabad, India, 2010, pp. 210– 226 13Miodrag, J.M., Sugata, G., Goutam, P. et al: 'Generic cryptographic weakness of K-normal Boolean functions in certain stream ciphers and cryptanalysis of Grain-128', Periodica Mathematica Hungarica, 2012, 65, (2), pp. 205– 227 14Dinur, I., Güneysu, T., Paar, C. et al: 'An experimentally verified attack on full Grain-128 using dedicated reconfigurable hardware'. Proc. 17th Conf. Theory and Application of Cryptology and Information Security (ASIACRYPT 2011), Seoul, South Korea, 2011, pp. 327– 343 15Ågren, M., Hell, M., Johansson, T. et al: 'Grain-128a: a new version of Grain-128 with optional authentication', Int. J. Wireless Mob. Comput., 2011, 5, (1), pp. 48– 59 16Banik, S., Maitra, S., Sarkar, S.: 'A Differential Fault Attack on Grain-128a Using MACs'. Proc. Security, Privacy, and Applied Cryptography Engineering, (LNCS 7644), 2012, pp. 111– 125 17Banik, S., Maitra, S., Sarkar, S.: 'A differential fault attack on the grain family under reasonable assumptions'. Proc. 13th Int. Conf. Cryptology in India, Kolkata, India, 2012, pp. 191– 208 18Banik, S., Maitra, S., Sarkar, S.: 'Differential fault attack against grain family with very few faults and minimal assumptions', IEEE Trans. Comput., 2014, 64, (6), pp. 1647– 1657 19Ding, L., Guan, J.: 'Related key chosen IV attack on Grain-128a stream cipher', IEEE Trans. Inf. Forensics Sec., 2013, 8, (5), pp. 803– 809 20Banik, S., Maitra, S., Sarkar, S. et al: 'A chosen IV related key attack on Grain-128a'. Proc. Information Security and Privacy – 18th Australasian Conf. (ACISP 2013), Brisbane, Australia, 2013, pp. 13– 26 21Robert, V.H., Elliot, A.T.: ' Probability and statistical inference' ( Macmillan Publishing Co., Inc., 1977) Citing Literature Volume11, Issue3May 2017Pages 139-145 FiguresReferencesRelatedInformation