Abstract
In [6], Biryukov presented a new methodology of stream cipher design, called leak extraction. The stream cipher LEX, based on this methodology and on the AES block cipher, was selected to phase 3 of the eSTREAM competition. The suggested methodology seemed promising, and LEX, due to its elegance, simplicity and performance was expected to be selected to the eSTREAM portfolio.
In this paper we present a key recovery attack on LEX. The attack requires about 236.3 bytes of key-stream produced by the same key (possibly under many different IVs), and retrieves the secret key in time of 2112 simple operations. Following a preliminary version of our attack, LEX was discarded from the final portfolio of eSTREAM.
Chapter PDF
Similar content being viewed by others
Keywords
References
Babbage, S.H., Dodd, M.: Specification of the Stream Cipher Mickey 2.0, submitted to eSTREAM (2006), http://www.ecrypt.eu.org/stream/p3ciphers/mickey/mickey_p3.pdf
Babbage, S.H: Improved “exhaustive search” attacks on stream ciphers. In: IEE European Convention on Security and Detection, IEE Conference publication, vol. 408, pp. 161–165. IEE (1995)
Bernstein, D.J.: Personal communication (2008)
Biham, E., Shamir, A.: Differential Cryptanalysis of the Data Encryption Standard. Springer, Heidelberg (1993)
Biham, E., Shamir, A.: Differential Fault Analysis of Secret Key Cryptosystems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 513–525. Springer, Heidelberg (1997)
Biryukov, A.: The Design of a Stream Cipher LEX. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 67–75. Springer, Heidelberg (2007)
Biryukov, A.: A New 128-bit Key Stream Cipher LEX, ECRYPT stream cipher project report 2005/013, http://www.ecrypt.eu.org/stream
Biryukov, A.: The Tweak for LEX-128, LEX-192, LEX-256, ECRYPT stream cipher project report 2006/037, http://www.ecrypt.eu.org/stream
Biryukov, A., Mukhopadhyay, S., Sarkar, P.: Improved Time-Memory Tradeoffs with Multiple Data. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 245–260. Springer, Heidelberg (2006)
Biryukov, A., Shamir, A.: Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 1–13. Springer, Heidelberg (2000)
Blum, M., Micali, S.: How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM Journal of Computation 13(4), 850–864 (1984)
Boneh, D., DeMillo, R.A., Lipton, R.J.: On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract). In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997)
Daemen, J., Rijmen, V.: AES Proposal: Rijndael, NIST AES proposal (1998)
Daemen, J., Rijmen, V.: The design of Rijndael: AES — the Advanced Encryption Standard. Springer, Heidelberg (2002)
Dunkelman, O., Keller, N.: Treatment of the Initial Value in Time-Memory-Data Tradeoff Attacks on Stream Ciphers. Information Processing Letters 107(5), 133–137 (2008)
ECRYPT, Call for Stream Cipher Primitives, version 1.3 (April 12, 2005), http://www.ecrypt.eu.org/stream/call/
Englund, H., Hell, M., Johansson, T.: A Note on Distinguishing Attacks. In: Preproceedings of State of the Art of Stream Ciphers workshop (SASC 2007), Bochum, Germany, pp. 73–78 (2007)
Ferguson, N., Kelsey, J., Lucks, S., Schneier, B., Stay, M., Wagner, D., Whiting, D.: Improved Cryptanalysis of Rijndael. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 213–230. Springer, Heidelberg (2001)
Goldreich, O., Levin, L.A.: A Hard-Core Predicate for all One-Way Functions. In: Proceedings of 21st STOC, pp. 25–32. ACM, New York (1989)
Golic, J.D.: Cryptanalysis of Alleged A5 Stream Cipher. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 239–255. Springer, Heidelberg (1997)
Håstad, J., Näslund, M.: BMGL: Synchronous Key-stream Generator with Provable Security. NESSIE project (submitted, 2000), http://www.nessie.eu.org
National Institute of Standards and Technology, Advanced Encryption Standard, Federal Information Processing Standards Publications No. 197 (2001)
Wu, H., Preneel, B.: Attacking the IV Setup of Stream Cipher LEX, ECRYPT stream cipher project report 2005/059, http://www.ecrypt.eu.org/stream
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dunkelman, O., Keller, N. (2008). A New Attack on the LEX Stream Cipher. In: Pieprzyk, J. (eds) Advances in Cryptology - ASIACRYPT 2008. ASIACRYPT 2008. Lecture Notes in Computer Science, vol 5350. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89255-7_33
Download citation
DOI: https://doi.org/10.1007/978-3-540-89255-7_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89254-0
Online ISBN: 978-3-540-89255-7
eBook Packages: Computer ScienceComputer Science (R0)