Abstract
The iterated Even-Mansour (EM) scheme is a generalization of the original 1-round construction proposed in 1991, and can use one key, two keys, or completely independent keys. In this paper, we methodically analyze the security of all the possible iterated Even-Mansour schemes with two n-bit keys and up to four rounds, and show that none of them provides more than n-bit security. Our attacks are based on a new cryptanalytic technique called multibridge which splits the cipher to different parts in a novel way, such that they can be analyzed independently, exploiting its self-similarity properties. After the analysis of the parts, the key suggestions are efficiently joined using a meet-in-the-middle procedure.
As a demonstration of the multibridge technique, we devise a new attack on 4 steps of the LED-128 block cipher, reducing the time complexity of the best known attack on this scheme from 296 to 264. Furthermore, we show that our technique can be used as a generic key-recovery tool, when combined with some statistical distinguishers (like those recently constructed in reflection cryptanalysis of GOST and PRINCE).
Chapter PDF
Similar content being viewed by others
References
Aerts, W., Biham, E., De Moitie, D., De Mulder, E., Dunkelman, O., Indesteege, S., Keller, N., Preneel, B., Vandenbosch, G.A.E., Verbauwhede, I.: A Practical Attack on KeeLoq. J. Cryptology 25(1), 136–157 (2012)
Andreeva, E., Bogdanov, A., Dodis, Y., Mennink, B., Steinberger, J.P.: On the Indifferentiability of Key-Alternating Ciphers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 531–550. Springer, Heidelberg (2013)
Aoki, K., Sasaki, Y.: Preimage Attacks on One-Block MD4, 63-Step MD5 and More. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 103–119. Springer, Heidelberg (2009)
Bogdanov, A., Knudsen, L.R., Leander, G., Standaert, F.-X., Steinberger, J.P., Tischhauser, E.: Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations - (Extended Abstract). In: Pointcheval, Johansson (eds.) [27], pp. 45–62
Borghoff, J., Canteaut, A., Güneysu, T., Kavun, E.B., Knezevic, M., Knudsen, L.R., Leander, G., Nikov, V., Paar, C., Rechberger, C., Rombouts, P., Thomsen, S.S., Yalçin, T.: PRINCE - A Low-Latency Block Cipher for Pervasive Computing Applications - Extended Abstract. In: Wang, Sako (eds.) [30], pp. 208–225
Daemen, J.: Limitations of the Even-Mansour Construction. In: Imai, et al. (eds.) [15], pp. 495–498
Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 719–740. Springer, Heidelberg (2012)
Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Cryptanalysis of iterated even-mansour schemes with two keys. Cryptology ePrint Archive, Report 2013/674 (2013), http://eprint.iacr.org/
Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Key Recovery Attacks on 3-round Even-Mansour, 8-step LED-128, and Full AES2. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 337–356. Springer, Heidelberg (2013)
Dunkelman, O., Keller, N., Shamir, A.: Minimalism in Cryptography: The Even-Mansour Scheme Revisited. In: Pointcheval, Johansson (eds.) [27], pp. 336–354
Even, S., Mansour, Y.: A construction of a cioher from a single pseudorandom permutation. In: Imai, et al. (eds.) [15], pp. 210–224
Fouque, P.-A., Joux, A., Mavromati, C.: Multi-user collisions: Applications to Discrete Logs, Even-Mansour and Prince. Cryptology ePrint Archive, Report 2013/761 (2013), http://eprint.iacr.org/
Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED Block Cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326–341. Springer, Heidelberg (2011)
Hellman, M.E.: A Cryptanalytic Time-Memory Trade-Off. IEEE Transactions on Information Theory 26(4), 401–406 (1980)
Matsumoto, T., Imai, H., Rivest, R.L. (eds.): ASIACRYPT 1991. LNCS, vol. 739. Springer, Heidelberg (1993)
Isobe, T., Shibutani, K.: Security Analysis of the Lightweight Block Ciphers XTEA, LED and Piccolo. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol. 7372, pp. 71–86. Springer, Heidelberg (2012)
Kara, O.: Reflection Cryptanalysis of Some Ciphers. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 294–307. Springer, Heidelberg (2008)
Lampe, R., Patarin, J., Seurin, Y.: An Asymptotically Tight Security Analysis of the Iterated Even-Mansour Cipher. In: Wang, Sako (eds.) [30], pp. 278–295
Luby, M., Rackoff, C.: How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM J. Comput. 17(2), 373–386 (1988)
Mandal, A., Patarin, J., Seurin, Y.: On the Public Indifferentiability and Correlation Intractability of the 6-Round Feistel Construction. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 285–302. Springer, Heidelberg (2012)
Mendel, F., Rijmen, V., Toz, D., Varici, K.: Differential Analysis of the LED Block Cipher. In: Wang, Sako (eds.) [30], pp. 190–207
Merkle, R.C., Hellman, M.E.: On the Security of Multiple Encryption. Commun. ACM 24(7), 465–467 (1981)
Nikolić, I., Wang, L., Wu, S.: Cryptanalysis of Round-Reduced LED. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 112–130. Springer, Heidelberg (2014)
Patarin, J.: Improved security bounds for pseudorandom permutations. In: Graveman, R., Janson, P.A., Neumann, C., Gong, L. (eds.) ACM Conference on Computer and Communications Security, pp. 142–150. ACM (1997)
Patarin, J.: Luby-Rackoff: 7 Rounds Are Enough for formula_image Security. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 513–529. Springer, Heidelberg (2003)
Patarin, J.: Security of Random Feistel Schemes with 5 or More Rounds. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 106–122. Springer, Heidelberg (2004)
Pointcheval, D., Johansson, T. (eds.): EUROCRYPT 2012. LNCS, vol. 7237. Springer, Heidelberg (2012)
Soleimany, H., Blondeau, C., Yu, X., Wu, W., Nyberg, K., Zhang, H., Zhang, L., Wang, Y.: Reflection Cryptanalysis of PRINCE-Like Ciphers. Journal of Cryptology, 1–27 (2013)
van Oorschot, P.C., Wiener, M.: A Known-Plaintext Attack on Two-Key Triple Encryption. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 318–325. Springer, Heidelberg (1991)
Wang, X., Sako, K. (eds.): ASIACRYPT 2012. LNCS, vol. 7658, pp. 2012–2018. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 International Association for Cryptologic Research
About this paper
Cite this paper
Dinur, I., Dunkelman, O., Keller, N., Shamir, A. (2014). Cryptanalysis of Iterated Even-Mansour Schemes with Two Keys. In: Sarkar, P., Iwata, T. (eds) Advances in Cryptology – ASIACRYPT 2014. ASIACRYPT 2014. Lecture Notes in Computer Science, vol 8873. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45611-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-662-45611-8_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45610-1
Online ISBN: 978-3-662-45611-8
eBook Packages: Computer ScienceComputer Science (R0)