[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Conditional differential cryptanalysis of 105 round Grain v1

  • Published:
Cryptography and Communications Aims and scope Submit manuscript

Abstract

In this paper we propose conditional differential cryptanalysis of 105 round Grain v1. This improves the attack proposed on 97 round Grain v1 by Knellwolf et al at Asiacrypt 2010. We take the help of the tool ΔGrain KSA, to track the differential trails introduced in the internal state of Grain v1 by any difference in the IV bits. We prove that a suitably introduced difference in the IV leads to a distinguisher for the output bit produced in the 105th round. This helps determine the values of 6 expressions in the Secret Key bits. Using the above attack as a subroutine, we propose a method that determines 9 Secret Key bits explicitly. Thus, the complexity for the Key recovery is proportional to 271 operations, which is faster than exhaustive search by 29.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. The ECRYPT Stream Cipher Project. eSTREAM Portfolio of Stream Ciphers (2008)

  2. Ågren, M., Hell, M., Johansson, T., Meier, W.: A New Version of Grain-128 with Authentication. Symmetric Key Encryption Workshop, 2011, DTU, Denmark

  3. Banik, S.: Some Insights into Differential Cryptanalysis of Grain v1. In: ACISP 2014, LNCS, vol. 8544, pp. 34–49 (2014)

  4. Banik, S., Maitra, S., Sarkar, S.: A Differential Fault Attack on Grain family under reasonable assumptions. In: Indocrypt 2012, LNCS, vol. 7668, pp. 191–208 (2012)

  5. Banik, S., Maitra, S., Sarkar, S.: A Differential Fault Attack on the Grain Family of Stream Ciphers. In: CHES 2012, LNCS, 7428, pp 122–139 (2012)

  6. Banik, S., Maitra, S., Sarkar, S., Turan, M.S.: A Chosen IV Related Key Attack on Grain-128a. In: ACISP 2013, LNCS, vol. 7959, pp. 13–26 (2013)

  7. Berbain, C., Gilbert, H., Maximov, A., Cryptanalysis of Grain. In: FSE 2006, LNCS, vol. 4047, pp. 15–29 (2006)

  8. Berzati, A., Canovas, C., Castagnos, G., Debraize, B., Goubin, L., Gouget, A., Paillier, P., Salgado, S.: Fault Analysis of Grain-128. In: IEEE International Workshop on Hardware-Oriented Security and Trust, pp. 7–14 (2009)

  9. Bjørstad, T.E.: Cryptanalysis of Grain using Time/Memory/Data tradeoffs (v1.0 / 2008-02-25). Available at, http://www.ecrypt.eu.org/stream

  10. De Cannière, C., Küçük, O., Preneel, B.: Analysis of Grain’s Initialization Algorithm. In: AFRICACRYPT 2008, LNCS, vol. 5023, pp. 276–289 (2008)

  11. Dinur, I., Güneysu, T., Paar, C., Shamir, A., Zimmermann, R.: An Experimentally Verified Attack on Full Grain-128 Using Dedicated Reconfigurable Hardware. In: ASIACRYPT 2011, LNCS, vol. 7073, pp. 327–343 (2011)

  12. Dinur, I., Shamir, A.: Grain-128 with Dynamic Cube. In: Breaking 2011, Attacks FSE, LNCS, vol. 6733, pp. 167–187 (2011)

  13. Dinur, I., Shamir, A.: Cube Attacks on Tweakable Black Box Polynomials. In: EUROCRYPT 2009, LNCS, vol. 5479, pp. 278–299 (2009)

  14. Dinur, I., Shamir, A.: Applying cube attacks to stream ciphers in realistic scenarios. Crypt. Commun. 4(3-4), 217–232 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Englund, H., Johansson, T., Turan, M.S.: A framework for chosen IV statistical analysis of stream ciphers. In: INDOCRYPT 2007, LNCS, vol. 4859, pp. 268–281 (2007)

  16. Fischer, S., Khazaei, S., Meier, W.: Chosen IV statistical analysis for key recovery attacks on stream ciphers. In: AFRICACRYPT 2008, LNCS, vol. 5023, pp. 236–245 (2008)

  17. Hell, M., Johansson, T., Meier, W.: Grain - A Stream Cipher for Constrained Environments. ECRYPT Stream Cipher Project Report 2005/001, 2005. Available at, http://www.ecrypt.eu.org/stream

  18. Hell, M., Johansson, T., Meier, W.: A Stream Cipher Proposal: Grain-128. In: IEEE International Symposium on Information Theory (ISIT, 2006) (2006)

  19. Khazaei, S., Hassanzadeh, M., Kiaei, M.: Distinguishing Attack on Grain. ECRYPT Stream Cipher Project Report 2005/071, 2005. Available at, http://www.ecrypt.eu.org/stream

  20. Khoo, K., Tan, C.: New time-memory-data trade-off attack on the estream finalists and modes of operation of block ciphers. In: 7th ACM Symposium on Information, Computer and Communications Security, pp. 20–21. ASIACCS (2012)

  21. Knellwolf, S.: Cryptanalysis of Hardware-Oriented Ciphers, The Knapsack Generator, and SHA-1. PhD Dissertation, 2012. Available at, http://e-collection.library.ethz.ch/eserv/eth:5999/eth-5999-02.pdf

  22. Knellwolf, S., Meier, W., Naya-Plasencia, M.: Conditional Differential Cryptanalysis of NLFSR-based Cryptosystems. In: ASIACRYPT 2010, LNCS, vol. 6477, pp. 130–145 (2010)

  23. Knellwolf, S., Meier, W., Naya-Plasencia, M.: Conditional Differential Cryptanalysis of Trivium and KATAN. In: SAC 2011, LNCS, vol. 7118, pp. 200–212 (2011)

  24. Lee, Y., Jeong, K., Sung, J., Hong, S.: Related-Key Chosen IV Attacks on Grain-v1 and Grain-128. In: ACISP 2008, LNCS, vol. 5107, pp. 321–335 (2008)

  25. Lehmann, M., Meier, W.: Conditional Differential Cryptanalysis of Grain-128a. In: CANS 2012, LNCS, vol. 7712, pp. 1–11 (2012)

  26. Rahimi, M., Barmshory, M., Mansouri, M.H., Reza Aref, M.: Dynamic Cube Attack on Grain-v1. In: IACR eprint archive. Available at, http://eprint.iacr.org/2013/268

  27. Stankovski, P.: Greedy Distinguishers and Nonrandomness Detectors. In: INDOCRYPT 2010, LNCS, vol. 6498, pp. 210-226 (2010)

  28. Stein, W.: SageMathematics Software. Free Software Foundation, Inc., 2009. Available at http://www.sagemath.org (Open source project initiated by W. Stein and contributed by many)

  29. Vielhaber, M.: AIDA Breaks BIVIUM (A&B) in 1 Minute Dual Core CPU Time. In: IACR eprint archive. Available at, http://eprint.iacr.org/2009/402

Download references

Author information

Authors and Affiliations

  1. DTU Compute, Technical University of Denmark, Lyngby, Denmark

    Subhadeep Banik

Authors
  1. Subhadeep Banik
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Subhadeep Banik.

Additional information

Section 2.4 of this work has been taken from the paper “Some Insights into the Differential Cryptanalysis of Grain v1 [3]” accepted in ACISP 2014 and published in LNCS 8544, pp. 34-49, 2014.

Appendix A: Computing the distribution of \(z_{105}\oplus z_{105}^{\phi }\) for ϕ = 61 if all C 1, C 2,…,C 6 are satisfied

Appendix A: Computing the distribution of \(z_{105}\oplus z_{105}^{\phi }\) for ϕ = 61 if all C 1, C 2,…,C 6 are satisfied

We will prove the bias in the distribution of \(z_{105}\oplus z_{105}^{\phi }\) along similar lines of the proof of the bias of \(z_{97}\oplus z_{97}^{37}\) reported in [3]. The probability values we calculate are computed over the randomness due to the Key bits and the those IV bits not assigned by the Type 1, 2 relations. However, these results also hold, even if the Key is fixed, and the randomness comes only from the IV bits. First we state a straightforward lemma without proof.

Lemma 2

Let F be an i-variable Boolean function, with wt(F)=w. If the vector X is chosen uniformly from {0,1} i then \(\textsf {Pr}[ F(X) =0] =1- \frac {\textsf {w}}{2^{i}}\).

We begin by inspecting the output of Δ61−Grain KSA at round t = 105, in which the difference is nullified at rounds t = 15,36,39,42. At t = 105, we have

$$\chi_{105} =[v_{106}=1, v_{107}=0, v_{109}=0, v_{115}=0, v_{136}=0, v_{148}=2, v_{161}=2] $$
$${\Upsilon}_{105} =[u_{108}=1, u_{130}=1, u_{151}=2, u_{169}=2, v_{168}=2] $$

This implies that of all the bits of \(S_{105}, S_{105}^{\phi }\) involved in the computation of z 105 and \(z_{105}^{\phi }\) respectively, the relations between only i) \(x_{148},x_{148}^{\phi }\) ii) \(x_{161},x_{161}^{\phi }\) iii) \(y_{151},y_{151}^{\phi }\) iv) \(y_{169},y_{169}^{\phi }\) v) \(x_{168},x_{168}^{\phi }\) are probabilistic. Therefore we have

$$\begin{array}{@{}rcl@{}} z_{105}\oplus z_{105}^{\phi} &=& 1 \oplus \left[x_{148}\oplus x_{148}^{\phi} \right] \oplus \left[x_{161}\oplus x_{161}^{\phi}\right] \oplus\\ &&[ h(y_{108} , y_{130} , y_{151} , y_{169} , x_{168} ) \oplus\\ &&{\kern5pt} h(1\oplus y_{108} , 1\oplus y_{130} , y_{151}^{\phi} , y_{169}^{\phi} , x_{168}^{\phi} ) ] \end{array} $$

We assume that the random variables \(x_{148} \oplus x_{148}^{\phi }\), \(x_{161}\oplus x_{161}^{\phi }\), \(y_{151} \oplus y_{151}^{\phi }\), \(y_{169} \oplus y_{169}^{\phi }\) and \(x_{168}\oplus x_{168}^{\phi }\) are statistically mutually independent of one another. It is difficult to prove this assumption theoretically but extensive computer simulations have shown that one can make this assumption.

1.1 Calculating \(\textsf {Pr}[x_{148} \oplus x_{148}^{\phi }=0]\)

To find this distribution we need to look at the state of our modified Δ61−Grain KSA at t = 148 − 80 = 68. At this we have u 68 = 0, Υ68 = 0, \(\mathcal {G}_{lin,68}=[v_{68}=0,v_{82}=0, v_{130}=1],\mathcal {G}_{nlin,68}=\mathbf {0} \), and

$$\chi_{68}=[ v_{69}=0, v_{70}=0, v_{72}=0 , v_{78}=0, v_{99}=0, v_{111}=0, v_{124}=2]$$

So we have

$$\begin{array}{@{}rcl@{}} x_{148} \oplus x_{148}^{\phi} &=& [g(X_{68}) \oplus y_{68} \oplus z_{68}] \oplus [g(X_{68}^{\phi}) \oplus y_{68}^{\phi} \oplus z_{68}^{\phi}]\\ &=& 1 \oplus (x_{124}\oplus x_{124}^{\phi}) \end{array} $$

So in order to compute the above probability we need to compute the distribution of \((x_{124}\oplus x_{124}^{\phi })\) first. At t = 124−80=44, we have \(u_{44}=0, {\Upsilon }_{44}=[u_{47}=0, u_{69}=0, u_{90}=1,u_{108}=1,v_{107}=0], \chi _{44}=\mathbf {0}, \mathcal {G}_{lin,44}=[v_{44}=0,v_{58}=0,v_{106}=1], \mathcal {G}_{nlin,68}=\mathbf {0}\). Note that y 47 = ν 47 = 0 according to one of the Type 1 conditions, and y 69 = 1 as defined by the padding rule of Grain v1. So we have

$$\begin{array}{@{}rcl@{}} x_{124} \oplus x_{124}^{\phi} &=& [g(X_{44}) \oplus y_{44} \oplus z_{44}] \oplus [g(X_{44}^{\phi}) \oplus y_{44}^{\phi} \oplus z_{44}^{\phi}]\\ &=& 1 \oplus h(y_{47}, y_{69}, y_{90},y_{108},x_{107})\oplus h(y_{47}, y_{69}, 1\oplus y_{90},1\oplus y_{108},x_{107})\\ &=& x_{107} \oplus y_{90}\cdot x_{107} \oplus y_{90} \oplus y_{108}\cdot x_{107} \oplus y_{108} \end{array} $$

Since x 107 ⊕ y 90⋅x 107 ⊕ y 90 ⊕ y 108⋅x 107 ⊕ y 108 is a Boolean Function of weight 6, assuming independence of the component variables we have \({\textsf {Pr}}\left [x_{124} \oplus x_{124}^{\phi }=0\right ] = 1-\frac {6}{8}=\frac {1}{4}\). This implies that \({\textsf {Pr}}\left [x_{148} \oplus x_{148}^{\phi }=0\right ] = \frac {3}{4}\).

1.2 Calculating \(\textsf {Pr}[y_{151} \oplus y_{151}^{\phi }=0]\)

To find this distribution we need to look at the state of our modified Δ61−Grain KSA at t = 151−80=71. At this we have Υ71 = [u 74 = 0,u 96 = 0,u 117 = 0,u 135 = 2,v 134 = 2], \(\mathcal {F}_{71}=\mathbf {0}, \chi _{71}=\mathbf {0}\). So we have

$$\begin{array}{@{}rcl@{}} y_{151} \oplus y_{151}^{\phi} &=& \left[f(Y_{71}) \oplus z_{71}\right] \oplus \left[f(Y_{71}^{\phi}) \oplus z_{71}^{\phi}\right]\\ &=& h(y_{74},y_{96},y_{117},y_{135},x_{134}) \oplus h\left( y_{74},y_{96},y_{117},y_{135}^{\phi},x_{134}^{\phi}\right) \end{array} $$

Define the set of functions h i j = h(y 74, y 96, y 117, y 135, x 134)⊕h(y 74, y 96, y 117, y 135 ⊕ i, x 134 ⊕ j), for i, j ∈ {0, 1}. Now assuming independence or the random variables involved, we can write,

$$ \textsf{Pr}[y_{151} \oplus y_{151}^{\phi}=0]= \sum\limits_{i,j} \textsf{Pr}[h_{ij}=0]\cdot \textsf{ Pr}\left[y_{135}\oplus y_{135}^{\phi}=i\right]\cdot \textsf{Pr}\left[x_{134}\oplus x_{134}^{\phi}=j\right] $$
(9)

To compute this probability, we would need to calculate the individual probabilities \(\textsf {Pr}\left [y_{135}\oplus y_{135}^{\phi }=0\right ]\) and \(\textsf {Pr}\left [x_{134}\oplus x_{134}^{\phi }=0\right ]\). At t = 135−80=55, we have \(\mathcal {F}_{55}=[u_{55}=0, u_{68}=0, u_{78}=0,u_{93}=0, u_{106}=1,u_{117}=0]\), χ 55 = 0, Υ55 = [u 58 = 0,u 80 = 0,u 101 = 0,u 119 = 1,v 118 = 0]. So we have

$$\begin{array}{@{}rcl@{}} y_{135} \oplus y_{135}^{\phi} &=& [f(Y_{55}) \oplus z_{55}] \oplus \left[f(Y_{55}^{\phi}) \oplus z_{55}^{\phi}\right]\\ &=& 1\oplus h(y_{58},y_{80},y_{101},y_{119},x_{118}) \oplus h(y_{58},y_{80},y_{101},1\oplus y_{119},x_{118}) \\ &=& 1\oplus y_{58} y_{101} \oplus y_{58} \oplus y_{101} x_{118} \oplus y_{101} \oplus x_{118} \end{array} $$

This represents a Boolean Function of weight 2, and hence we have \(\textsf {Pr}[y_{135}\oplus y_{135}^{\phi }=0]= 1- \frac {2}{8}=\frac {3}{4}\). Now at t = 134−80=54, we have \(\chi _{54}=\mathbf {0}, \mathcal {G}_{lin,54}=\mathbf {0}, u_{54}=0, {\Upsilon }_{54}= [u_{57}=0, u_{79}=0,u_{100}=0, u_{118}=1,v_{117}=0]\)and all elements of \(\mathcal {G}_{nlin,54}\) are zeros except v 106 = 1. So we have

$$\begin{array}{@{}rcl@{}} x_{134} \oplus x_{134}^{\phi} &=& [g(X_{54}) \oplus y_{54} \oplus z_{54}] \oplus [g(X_{54}^{\phi}) \oplus y_{54}^{\phi} \oplus z_{54}^{\phi}]\\ &=& [g(\ldots,x_{106},\ldots)\oplus g(\ldots,1\oplus x_{106},\ldots)] \oplus \\ &&\,[h(y_{57}, y_{79},y_{100}, y_{118},x_{117})\oplus h(y_{57}, y_{79},y_{100}, 1\oplus y_{118},x_{117})] \end{array} $$

We have to set x 99 = 1, in the above equation since it is one of the conditions imposed at t = 36 to nullify a difference. Hence we have \(\textsf {Pr}[y_{135} \oplus y_{135}^{\phi }=0] = \frac {35}{64}\). Now turning back to our original problem, we know that \(\textsf {Pr}[h_{00}=0]=1, \textsf {Pr}[h_{01}=0]=\frac {1}{2}, \textsf {Pr}[h_{10}=0]=\frac {1}{4}, \textsf {Pr}[h_{11}=0] = \frac {1}{2} \). Putting these values in (9), we get \(\textsf {Pr}[y_{151} \oplus y_{151}^{\phi }=0]\approx 0.6709\).

1.3 Calculating \(\textsf {Pr}[y_{169} \oplus y_{169}^{\phi }=0]\), \(\textsf {Pr}[x_{168} \oplus x_{168}^{\phi }=0]\) and \({\textsf {Pr}}[x_{161} \oplus x_{161}^{\phi }=0]\)

To compute these probabilities, we will need to look at outputs of Δ61−Grain KSA at t = 81,88,89. However at these rounds both χ t and Υ t have many elements equal to 2 and hence at this point we have to delve into several lower KSA rounds and compute the distributions of several intermediate variables and work our way up from there. Since this is slightly tedious, we omit extensive analysis of these two distributions and simply state the results.

$$\begin{array}{@{}rcl@{}} \textsf{Pr}[y_{169} \oplus y_{169}^{\phi}&=&0]= 0.5015, \textsf{Pr}[x_{168} \oplus x_{168}^{\phi}=0] = 0.5,\\ &\textsf{Pr}&[x_{161} \oplus x_{161}^{\phi}=0] = 0.495 \end{array} $$

1.4 Calculating \(\textsf {Pr}[h(y_{108} , y_{130} , y_{151} , y_{169} , x_{168} )\oplus h(1\oplus y_{108} , 1\oplus y_{130} , y_{151}^{\phi } , y_{169}^{\phi } ,\) \( x_{168}^{\phi })=0]\)

For the sake of conciseness, let this expression be denoted by the symbol H, and define the Boolean Functions \(\mathcal {H}_{ijk}= h(y_{108} , y_{130} , y_{151} , y_{169} , x_{168} )\oplus h(1\oplus y_{108} , 1\oplus y_{130} , i \oplus y_{151} ,j\oplus y_{169} ,k\oplus x_{168})\), for all i, j, k ∈ {0, 1}. Assuming independence, it is easy to see that Pr[H = 0] equals

$$\sum\limits_{i,j,k} \textsf{Pr}[\mathcal{H}_{ijk}=0]\cdot \textsf{Pr}[y_{151}\oplus y_{151}^{\phi}=i] \cdot \textsf{ Pr}[y_{169}\oplus y_{169}^{\phi}=j] \cdot {\textsf{Pr}}[ x_{168} \oplus x_{168}^{\phi} =k]$$

As it turns out, all the functions \(\mathcal {H}_{ijk}\) are balanced except \(\mathcal {H}_{011}\) and \({\textsf {Pr}}[\mathcal {H}_{011}=0]=\frac {3}{4}\). By plugging these values into the above equation we get Pr[H = 0]≈0.542.

1.5 Calculating \(\textsf {Pr}[z_{105}\oplus z_{105}^{\phi } =0]\)

From (9), we can write \(\textsf {Pr}[z_{105}\oplus z_{105}^{\phi } =0 ]\) equal to the following:

$$\begin{array}{@{}rcl@{}} &=& 1 - \sum\limits_{i\oplus j \oplus k=0} \textsf{Pr}[x_{148}\oplus x_{148}^{\phi} =i]\cdot \textsf{Pr}[x_{161}\oplus x_{161}^{\phi} =j]\cdot {\textsf{Pr}}[H=k] \\ &\approx& 0.5002 \end{array} $$

This concludes our proof for the distribution of \(z_{105}\oplus z_{105}^{\phi } =0\). This has also been verified by independent computer simulations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Banik, S. Conditional differential cryptanalysis of 105 round Grain v1. Cryptogr. Commun. 8, 113–137 (2016). https://doi.org/10.1007/s12095-015-0146-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12095-015-0146-5

Keywords

Mathematics Subject Classification (2010)

Search

Navigation