Generic cryptographic weakness of k -normal Boolean functions in certain stream ciphers and cryptanalysis of grain-128
- PDF / 209,229 Bytes
- 23 Pages / 595 x 842 pts (A4) Page_size
- 68 Downloads / 210 Views
GENERIC CRYPTOGRAPHIC WEAKNESS OF k-NORMAL BOOLEAN FUNCTIONS IN CERTAIN STREAM CIPHERS AND CRYPTANALYSIS OF GRAIN-128 ´1 , Sugata Gangopadhyay2 , Goutam Paul3 Miodrag J. Mihaljevic and Hideki Imai4 1
Serbian Academy of Sciences and Arts, Belgrade, Serbia & Research Institute for Secure Systems, National Institute for Advanced Industrial Science and Technologies, Tsukuba, Japan E-mail: [email protected] 2
3
Department of Mathematics, Indian Institute of Technology Roorkee Roorkee 247667, India E-mail: [email protected]
Department of Computer Science and Engineering, Jadavpur University Kolkata 700 032, India E-mail: [email protected] 4
Chuo University, Faculty of Science and Engineering, Tokyo, Japan & Research Institute for Secure Systems, National Institute for Advanced Industrial Science and Technologies Tsukuba, Japan (Received September 30, 2011; Accepted March 3, 2012)
Abstract This paper considers security implications of k-normal Boolean functions when they are employed in certain stream ciphers. A generic algorithm is proposed for cryptanalysis of the considered class of stream ciphers based on a security weakness of k-normal Boolean functions. The proposed algorithm yields a framework for mounting cryptanalysis against particular stream ciphers within the considered class. Also, the proposed algorithm for cryptanalysis implies certain design guidelines for avoiding certain weak stream cipher constructions. A particular objective of this paper is security evaluation of stream cipher Grain-128 employing the developed generic algorithm. Contrary to the best known attacks against Grain-128 which provide complexity of a secret key recovery lower than exhaustive search only over a subset of secret keys which is just a fraction (up to 5%) of all possible secret keys, Mathematics subject classification number : 94A60. Key words and phrases: stream cipher, cryptanalysis, k-normal Boolean functions, timememory-data trade-off, Grain-128. 0031-5303/2012/$20.00 c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
206
´ S. GANGOPADHYAY, G. PAUL and H. IMAI M. J. MIHALJEVIC,
the cryptanalysis proposed in this paper provides significantly lower complexity than exhaustive search for any secret key. The proposed approach for cryptanalysis primarily depends on the order of normality of the employed Boolean function in Grain-128. Accordingly, in addition to the security evaluation insights of Grain-128, the results of this paper are also an evidence of the cryptographic significance of the normality criteria of Boolean functions.
1. Introduction Stream ciphers are an important class of encryption techniques and Boolean functions are a traditional component of stream ciphers (see, [9], [18], [26] and [28], for example). If a Boolean function is constant over a k-dimensional flat then it is said to be a k-normal Boolean function. This paper considers the security implications of the main feature of k-normal Boolean functions when they are employed in certain stream ciphers. A generi
Data Loading...
