Paper 2006/451

Combined Differential, Linear and Related-Key Attacks on Block Ciphers and MAC Algorithms

Jongsung Kim

Abstract

Differential and linear attacks are the most widely used cryptanalytic tools to evaluate the security of symmetric-key cryptography. Since the introduction of differential and linear attacks in the early 1990's, various variants of these attacks have been proposed such as the truncated differential attack, the impossible differential attack, the square attack, the boomerang attack, the rectangle attack, the differential-linear attack, the multiple linear attack, the nonlinear attack and the bilinear attack. One of the other widely used cryptanalytic tools is the related-key attack. Unlike the differential and linear attacks, this attack is based on the assumption that the cryptanalyst can obtain plaintext and ciphertext pairs by using different, but related keys. This thesis provides several new combined differential, linear and related-key attacks, and shows their applications to block ciphers, hash functions in encryption mode and message authentication code (MAC) algorithms. The first part of this thesis introduces how to combine the differential-style, linear-style and related-key attacks: we combine them to devise the differential-nonlinear attack, the square-(non)linear attack, the related-key differential-(non)linear attack, the related-key boomerang attack and the related-key rectangle attack. The second part of this thesis presents some applications of the combined attacks to exiting symmetric-key cryptography. Firstly, we present their applications to the block ciphers SHACAL-1, SHACAL-2 and AES. In particular, we show that the differential-nonlinear attack is applicable to 32-round SHACAL-2, which leads to the best known attack on SHACAL-2 that uses a single key. We also show that the related-key rectangle attack is applicable to the full SHACAL-1, 42-round SHACAL-2 and 10-round AES-192, which lead to the first known attack on the full SHACAL-1 and the best known attacks on SHACAL-2 and AES-192 that use related keys. Secondly, we exploit the related-key boomerang attack to present practical distinguishing attacks on the cryptographic hash functions MD4, MD5 and HAVAL in encryption mode. Thirdly, we show that the related-key rectangle attack can be used to distinguish instantiated HMAC and NMAC from HMAC and NMAC with a random function.

Note: The submission is Jongsung Kim's Ph.D. thesis approved by ESAT/COSIC in K.U.Leuven.