Abstract
In this paper, we provide a theoretical infrastructure of the reflection attack. In addition, we mount the reflection attack on some ciphers such as GOST, DEAL and a variant of DES. The attack method exploits certain similarities among round functions which have not been utilized in the previous self-similarity attacks. As an illustration, we introduce a chosen plaintext attack on full-round GOST under the assumption that its S-boxes are bijective. The attack works on approximately 2224 keys and its complexity is 2192 steps with 232 chosen plaintexts. Also, we introduce a known plaintext attack on 30-round GOST, which works for any key. The key is recovered with 2224 steps by using only 232 known plaintexts. As another example, we deduce that the reflection attack works on DEAL for certain keys. For instance, a 192-bit DEAL-key can be identified as a weak key by using approximately 266 known plaintexts. Then, the key can be recovered with 2136 steps. The number of weak keys of 192-bit DEAL is roughly 280.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Babbage, S.: Improved Exhaustive Search Attacks on Stream Ciphers. In: IEE Conference publication European Convention on Security and Detection, vol. 408, pp. 161–166. IEE (1995)
Bellare, M., Rogaway, P.: The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006)
Biham, E.: New Types of Cryptanalytic Attacks Using Related Keys. J. of Cryptology 7, 229–246 (1994)
Biham, E., Dunkelman, O., Keller, N.: Improved Slide Attacks. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 153–166. Springer, Heidelberg (2007)
Biham, E., Dunkelman, O., Keller, N.: Related-Key Boomerang and Rectangle Attacks. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 507–525. Springer, Heidelberg (2005)
Biham, E., Dunkelman, O., Keller, N.: New Cryptanalytic Results on IDEA. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 412–427. Springer, Heidelberg (2006)
Biham, E., Dunkelman, O., Keller, N.: A Simple Related-Key Attack on the Full SHACAL-1. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 20–30. Springer, Heidelberg (2006)
Biham, E., Dunkelman, O., Keller, N.: A Unified Approach to Related-Key Attacks. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 73–96. Springer, Heidelberg (2008)
Biham, E., Shamir, A.: Differential Cryptanalysis of Data Encryption Standard. Springer, Heidelberg (1993)
Biryukov, A., Wagner, D.: Slide Attacks. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer, Heidelberg (1999)
Biryukov, A., Wagner, D.: Advanced Slide Attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 589–606. Springer, Heidelberg (2000)
Carter, G., Dawson, E., Nielsen, L.: Key Schedules of Iterated Block Ciphers. In: Boyd, C., Dawson, E. (eds.) ACISP 1998. LNCS, vol. 1438, pp. 80–89. Springer, Heidelberg (1998)
Coppersmith, D.: The Real Reason for Rivest’s Phenomenon. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 535–536. Springer, Heidelberg (1985)
Courtois, N., Bard, G.V., Wagner, D.: Algebraic and Slide Attacks on KeeLoq. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 89–104. Springer, Heidelberg (2008)
Dunkelman, O., Keller, N., Kim, J.: Related-Key Rectangle Attack on the Full SHACAL-1. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 28–44. Springer, Heidelberg (2007)
Golić, J.: Cryptanalysis of Alleged A5 Stream Cipher. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 239–255. Springer, Heidelberg (1997)
Furuya, S.: Slide Attacks with a Known-Plaintext Cryptanalysis. In: Kim, K.-c. (ed.) ICISC 2001. LNCS, vol. 2288, pp. 214–225. Springer, Heidelberg (2002)
Henricksen, M.: Design, Implementation and Cryptanalysis of Modern Symmetric Ciphers. PhD Thesis, ISRC, Faculty of Information Technology, Queensland University of Technology (2005)
Hong, J., Sarkar, P.: Rediscovery of the Time Memory Tradeoff. In: Cryptology ePrint Archive, Report 2005/090 (2005)
Hong, S., Kim, J., Kim, G., Lee, S., Preneel, B.: Related-Key Rectangle Attacks on Reduced Versions of SHACAL-1 and AES-192. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 368–383. Springer, Heidelberg (2005)
Kaliski, B.S., Rivest, R.L., Sherman, T.: Is DES a Pure Cipher? (Results of More Cycling Experiments on DES). In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 212–222. Springer, Heidelberg (1986)
Kara, O., Manap, C.: A new class of Weak Keys for Blowfish. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 167–180. Springer, Heidelberg (2007)
Kelsey, J., Schneier, B.: Key-Schedule Cryptanalysis of DEAL. In: Heys, H.M., Adams, C.M. (eds.) SAC 1999. LNCS, vol. 1758, pp. 118–134. Springer, Heidelberg (2000)
Kelsey, J., Schneier, B., Wagner, D.: Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 237–251. Springer, Heidelberg (1996)
Ko, Y., Hong, S., Lee, W., Lee, S., Kang, J.: Related Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 299–316. Springer, Heidelberg (2004)
Kim, J., Hong, S., Preneel, B.: Related-Key Rectangle Attacks on Reduced AES-192 and AES-256. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 225–241. Springer, Heidelberg (2007)
Knudsen, L.: DEAL - a 128-Bit Block Cipher, http://www.ii.uib.no/~larsr/aes.html
Knudsen, L.: Cryptanalysis of LOKI91. In: Zheng, Y., Seberry, J. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 196–208. Springer, Heidelberg (1993)
Lucks, S.: On the Security of 128-Bit Block Cipher DEAL. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 60–70. Springer, Heidelberg (1999)
Matsui, M.: Linear Cryptanalysis Method of DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Moore, J.H., Simmons, G.J.: Cycle Structure of the DES with Weak and Semi-Weak Keys. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 9–32. Springer, Heidelberg (1987)
Moore, J.H., Simmons, G.J.: Cycle Structure of the DES for Keys Having Palindromic (or Antipalindromic) Sequences of Round Keys. IEEE Transactions on Software Engineering 13, 262–273 (1987)
Schneier, B.: Description of a New Variable - Length Key, 64 Bit Block Cipher (Blowfish). In: Anderson, R. (ed.) FSE 1993. LNCS, vol. 809, pp. 191–204. Springer, Heidelberg (1994)
Seki, H., Kaneko, T.: Differential Cryptanalysis of Reduced Rounds of GOST. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 315–323. Springer, Heidelberg (2001)
Vaudenay, S.: Decorrelation: A Theory for Block Cipher Security. J. of Cryptology 16(4), 249–286 (1985)
Zabotin, I.A., Glazkov, G.P., Isaeva, V.B.: Cryptographic Protection for Information Processing Systems. Cryptographic Transformation Algorithm. In: Government Standard of the USSR, GOST 28147-89 (1989)
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
Kara, O. (2008). Reflection Cryptanalysis of Some Ciphers. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds) Progress in Cryptology - INDOCRYPT 2008. INDOCRYPT 2008. Lecture Notes in Computer Science, vol 5365. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89754-5_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-89754-5_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89753-8
Online ISBN: 978-3-540-89754-5
eBook Packages: Computer ScienceComputer Science (R0)