Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others

Biryukov, Alex; Nikolic, Ivica

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

Biryukov, Alex; Nikolic, Ivica

2010 • In EUROCRYPT

Peer reviewed

Permalink
https://hdl.handle.net/10993/17075

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

RK-Cryptanalysis-tool.pdf

Publisher postprint (335.07 kB)

Download

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Cryptanalysis tool; related-key attack

Abstract :

[en] While di fferential behavior of modern ciphers in a single secret key scenario is relatively well understood, and simple techniques for computation of security lower bounds are readily available, the security of modern block ciphers against related-key attacks is still very ad hoc. In this paper we make a first step towards provable security of block ciphers against related-key attacks by presenting an efficient search tool for finding diff erential characteristics both in the state and in the key (note that due to similarities between block ciphers and hash functions such tool will be useful in analysis of hash functions as well). We use this tool to search for the best possible (in terms of the number of rounds) related-key diff erential characteristics in AES, byte-Camellia, Khazad, FOX, and Anubis. We show the best related-key diff erential characteristics for 5, 11, and 14 rounds of AES-128, AES-192, and AES-256 respectively. We use the optimal diff erential characteristics to design the best related-key and chosen key attacks on AES-128 (7 out of 10 rounds), AES-192 (full 12 rounds), byte-Camellia (full 18 rounds) and Khazad (7 and 8 out of 8 rounds). We also show that ciphers FOX and Anubis have no related-key attacks on more than 4-5 rounds.

Disciplines :

Computer science

Identifiers :

UNILU:UL-CONFERENCE-2011-102

Author, co-author :

Biryukov, Alex ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)

Nikolic, Ivica

Language :

English

Title :

Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others

Publication date :

2010

Event name :

EUROCRYPT

Event place :

French Riviera, France

Event date :

2010

Audience :

International

Main work title :

EUROCRYPT

ISBN/EAN :

978-3-642-13189-9

Pages :

322-344

Peer reviewed :

Peer reviewed

Additional URL :

http://www.cryptolux.org/index.php/Block_ciphers

Commentary :

EUROCRYPT

Available on ORBilu :

since 25 June 2014

Statistics

Number of views

200 (1 by Unilu)

Number of downloads

308 (1 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

WoS citations^™

Bibliography

Aoki, K., Ichikawa, T., Kanda, M., Matsui, M., Moriai, S., Nakajima, J., Tokita, T.: Camellia: A 128-bit block cipher suitable for multiple platforms - design and analysis. In: Stinson, D.R., Tavares, S.E. (eds.) SAC 2000. LNCS, vol. 2012, pp. 39-56. Springer, Heidelberg (2000)
Barreto, P., Rijmen, V.: The Anubis Block Cipher. Submission to the NESSIE Project (2000)
Barreto, P., Rijmen, V.: The Khazad Legacy-Level Block Cipher. Submission to the NESSIE Project (2000)
Biham, E.: New types of cryptanalytic attacks using related keys. J. Cryptology 7(4), 229-246 (1994)
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., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptology 4(1), 3-72 (1991)
Biryukov, A.: Analysis of involutional ciphers: Khazad and Anubis. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 45-53. Springer, Heidelberg (2003)
Biryukov, A., Dunkelman, O., Keller, N., Khovratovich, D., Shamir, A.: Key recovery attacks of practical complexity on AES variants with up to 10 rounds. In: EUROCRYPT 2010 (to appear, 2010)
Biryukov, A., Khovratovich, D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 1-18. Springer, Heidelberg (2009)
Biryukov, A., Khovratovich, D., Nikolić, I.: Distinguisher and related-key attack on the full AES-256. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 231-249. Springer, Heidelberg (2009)
Cannière, C.D., Rechberger, C.: Finding SHA-1 characteristics: General results and applications. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 1-20. Springer, Heidelberg (2006)
Chowdhury, D.R., Rijmen, V., Das, A. (eds.): INDOCRYPT 2008. LNCS, vol. 5365. Springer, Heidelberg (2008)
Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, Heidelberg (2002)
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 (2000)
Fouque, P.-A., Leurent, G., Nguyen, P.: Automatic search of differential path in MD4. Cryptology ePrint Archive, Report 2007/206 (2007)
Gilbert, H., Minier, M.: A collision attack on 7 rounds of Rijndael. In: AES Candidate Conference, pp. 230-241 (2000)
Gilbert, H., Peyrin, T.: Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations. In: FSE 2010 (to appear, 2010)
Gorski, M., Lucks, S.: New related-key boomerang attacks on AES. In: Chowdhury, et al. (eds.) [12], pp. 266-278
Hirose, S.: Some plausible constructions of double-block-length hash functions. In: Robshaw [33], pp. 210-225
Junod, P., Vaudenay, S.: FOX: A new family of block ciphers. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 114-129. Springer, Heidelberg (2004)
Khovratovich, D., Biryukov, A., Nikolić, I.: Speeding up collision search for byte-oriented hash functions. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 164-181. Springer, Heidelberg (2009)
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) (Pubitemid 41425176)
Knudsen, L.R., Rijmen, V.: Known-key distinguishers for some block ciphers. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 315-324. Springer, Heidelberg (2007)
Lai, X., Massey, J.L.: Hash function based on block ciphers. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 55-70. Springer, Heidelberg (1993)
Lee, S., Hong, S., Lee, S., Lim, J., Yoon, S.: Truncated differential cryptanalysis of Camellia. In: Kim, K.-c. (ed.) ICISC 2001. LNCS, vol. 2288, pp. 32-38. Springer, Heidelberg (2002)
Lu, J., Dunkelman, O., Keller, N., Kim, J.: New impossible differential attacks on AES. In: Chowdhury, et al (eds.) [12], pp. 279-293
Lu, J., Kim, J., Keller, N., Dunkelman, O.: Improving the efficiency of impossible differential cryptanalysis of reduced Camellia and MISTY1. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 370-386. Springer, Heidelberg (2008)
Matsui, M.: Linear cryptoanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386-397. Springer, Heidelberg (1994)
Matsui, M.: On correlation between the order of S-boxes and the strength of DES. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 366-375. Springer, Heidelberg (1994)
Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.S.: The rebound attack: Cryptanalysis of reduced Whirlpool and Grøstl. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 260-276. Springer, Heidelberg (2009)
Muller, F.: A new attack against Khazad. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 347-358. Springer, Heidelberg (2003)
National Institute of Standards and Technology. Advanced encryption standard (AES). FIPS 197 (November 2001)
Robshaw, M.J.B. (ed.): FSE 2006. LNCS, vol. 4047. Springer, Heidelberg (2006)
Schläffer, M., Oswald, E.: Searching for differential paths in MD4. In: Robshaw (ed.) [33], pp. 242-261
Stevens, M.: Fast collision attack on MD5. Cryptology ePrint Archive, Report 2006/104 (2006)