© The Institution of Engineering and Technology
A novel technique for cryptanalysis of the stream cipher Grain-v1 is given. In a particular setting, the algorithms proposed in this study provide recovery of an internal state of Grain-v1 with the expected time complexity of only 254 table look-up operations employing a memory of dimension ∼270, assuming availability of 234 keystream sequences each of length 238 generated for different initial values, and the pre-processing time complexity of ∼288. These figures appear as significantly better in comparison with the previously reported ones. The proposed approach for cryptanalysis primarily depends on the order of normality of the employed Boolean function in Grain-v1. Accordingly, in addition to the security evaluation insights of Grain-v1, the results of this study are also an evidence of the cryptographic significance of the normality criteria of Boolean functions.
References
-
-
1)
-
M. Hell ,
T. Johansson
.
Cryptanalysis of Achterbahn-128/80.
IET Inf. Secur.
,
47 -
52
-
2)
-
eSTREAM Portfolio of ECRYPT project. Available at: http://www.ecrypt.eu.org/stream/announcements.html, accessed September 2011.
-
3)
-
Agren, M., Hell, M., Johansson, T., Meier, W.: `A New Version of Grain-128 with Authentication', Proc. 2011 Symmetric Key Encryption Workshop – SKEW 2011, 16–17 February 2011, Copenhagen, Denmark, E-Proceedings (19 p.). Available at: http://skew2011.mat.dtu.dk/proceedings, accessed September 2011.
-
4)
-
Saarinen, M.J.O.: `Chosen-iv statistical attacks on estream ciphers', Proc. Int. Conf. on Security and Cryptography, SECRYPT 2006, 7–10 August 2006, Setúbal, Portugal, p. 260–266.
-
5)
-
Englund, H., Johansson, T., Turan, M.S.: `A framework for chosen IV statistical analysis of stream ciphers', Proc. Progress in Cryptology – INDOCRYPT 2007, Eighth Int. Conf. on Cryptology in India, 9–13 December 2007, Chennai, India, p. 268–281, (LNCS, 4859).
-
6)
-
Hell, M., Johansson, T., Maximov, A., Meier, W.: `A stream cipher proposal: grain-128', Proc. 2006 IEEE Int. Symp. on Information Theory – ISIT 2006, 9–14 July 2006, Seattle, WA, USA, p. 1614–1618.
-
7)
-
Lee, Y., Jeong, K., Sung, J., Hong, S.: `Related-key chosen IV attacks on Grain-v1 and Grain-128', Proc. Information Security and Privacy, 13th Australasian Conf., ACISP 2008, 7–9 July 2008, Wollongong, Australia, p. 321–335, (LNCS, 5107).
-
8)
-
V. Velichkov ,
V. Rijmen ,
B. Preneel
.
Algebraic cryptanalysis of a small-scale version of stream cipher Lex.
IET Inf. Secur.
,
49 -
61
-
9)
-
Biryukov, A., Shamir, A.: `Cryptanalytic time/memory/data tradeoffs for stream ciphers', Proc. Advances in Cryptology – ASIACRYPT 2000, Sixth Int. Conf. on Theory and Application of Cryptology and Information Security, 3–7 December 2000, Kyoto, Japan, p. 1–13, (LNCS, 1976).
-
10)
-
Dobbertin, H.: `Construction of bent functions and balanced Boolean functions with high nonlinearity', Proc. Fast Software Encryption: Second Int. Workshop, 14–16 December 1994, 1995, Leuven, Belgium, p. 61–74, (LNCS, 1008)FSE 1994, .
-
11)
-
Dinur, I., Shamir, A.: `Breaking Grain-128 with dynamic cube attacks', Proc. Fast Software Encryption – 18th Int. Workshop, FSE 2011, 13–16 February 2011, Lyngby, Denmark, p. 167–187, (LNCS, 6733).
-
12)
-
O. Dunkelman ,
N. Keller
.
Treatment of the initial value in time-memory-data tradeoff attacks on stream ciphers.
Inf. Proc. Lett.
,
133 -
137
-
13)
-
H. Ahmadi ,
T. Eghlidos
.
Heuristic guess-and-determine attacks on stream ciphers.
IET Inf. Secur.
,
66 -
73
-
14)
-
ECRYPT: ‘The eSTREAM Project – Phase 3’. Available at: http://www.ecrypt.eu.org/stream/grainpf.html, accessed September 2011.
-
15)
-
Barbain, C., Gilbert, H., Maximov, A.: `Cryptanalysis of Grain', Proc. Fast Software Encryption, 13th Int. Workshop, FSE 2006, 15–17 March 2006, Graz, Austria, p. 15–29, (LNCS, 4047).
-
16)
-
M.E. Hellman
.
A cryptanalytic time-memory trade-off.
IEEE Trans. Inf. Theory
,
401 -
406
-
17)
-
M. Hell ,
T. Johansson ,
W. Meier
.
Grain – a stream cipher for constrained environments.
-
18)
-
Biryukov, A., Shamir, A., Wagner, D.: `Real time cryptanalysis of A5/1 on a PC', Proc. Fast Software Encryption, eighth Int. Workshop, FSE 2001, 2–4 April 2001, Yokohama, Japan, p. 37–44, (LNCS, 2002, 1978).
-
19)
-
Carlet, C.: `The complexity of Boolean functions from cryptographic viewpoint', Dagstuhl Seminar Proceedings 06111: Complexity of Boolean Functions, 2006, paper #604, 15 p 2006. Available at: http://drops.dagstuhl.de/opus/volltexte/2006/604, accessed September 2011.
-
20)
-
T.E. Bjørstad
.
(2008)
Cryptanalysis of grain using time/memory/data tradeoffs.
-
21)
-
Fischer, S., Khazaei, S., Meier, W.: `Chosen IV statistical analysis for key recovery attacks on stream ciphers', Proc. Progress in Cryptology – AFRICACRYPT 2008, First Int. Conf. on Cryptology in Africa, 11–14 June 2008, Casablanca, Morocco, p. 236–245, (LNCS, 5023).
-
22)
-
M. Hell ,
T. Johansson ,
A. Maximov ,
W. Meier
.
The grain family of stream ciphers.
New Stream Ciphers Design
,
179 -
190
-
23)
-
M. Hell ,
T. Johansson ,
W. Meier
.
Grain – a stream cipher for constrained environments.
Int. J. Wirel. Mobile Comput. – Spec. Issue Secur. Comput. Netw. Mobile Syst.
,
86 -
93
-
24)
-
P. Charpin
.
Normal Boolean functions.
J. Complexity
,
245 -
265
-
25)
-
Zhang, H., Wang, X.: `Cryptanalysis of stream cipher grain family', IACR E-print Archiv, Report # 109, 2009, Available at http://eprint.iacr.org/2009/109.pdf, accessed September 2011.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2011.0107
Related content
content/journals/10.1049/iet-ifs.2011.0107
pub_keyword,iet_inspecKeyword,pub_concept
6
6