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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Combined AttacksAESSHACALMD4MD5HMAC
Contact author(s)
Kim Jongsung @ esat kuleuven be
History
2006-12-04: received
Short URL
https://ia.cr/2006/451
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/451,
      author = {Jongsung Kim},
      title = {Combined Differential, Linear and Related-Key Attacks on Block Ciphers and MAC Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2006/451},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/451}},
      url = {https://eprint.iacr.org/2006/451}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.