Paper 2017/832

Mixture Differential Cryptanalysis and Structural Truncated Differential Attacks on round-reduced AES

Lorenzo Grassi

Abstract

At Eurocrypt 2017 the first secret-key distinguisher for 5-round AES -- based on the “multiple-of-8” property -- has been presented. Although it allows to distinguish a random permutation from an AES-like one, it seems rather hard to implement a key-recovery attack different than brute-force like using such a distinguisher. In this paper we introduce “Mixture Differential Cryptanalysis” on round-reduced AES-like ciphers, a way to translate the (complex) “multiple-of-8” 5-round distinguisher into a simpler and more convenient one (though, on a smaller number of rounds). Given a pair of chosen plaintexts, the idea is to construct new pairs of plaintexts by mixing the generating variables of the original pair of plaintexts. Here we theoretically prove that for 4-round AES the corresponding ciphertexts of the original pair of plaintexts lie in a particular subspace if and only if the corresponding pairs of ciphertexts of the new pairs of plaintexts have the same property. Such secret-key distinguisher -- which is independent of the secret-key, of the details of the S-Box and of the MixColumns matrix (except for the branch number equal to 5) -- can be used as starting point to set up new key-recovery attacks on round-reduced AES. Besides a theoretical explanation, we also provide a practical verification both of the distinguisher and of the attack. As a second contribution, we show how to combine this new 4-round distinguisher with a modified version of a truncated differential distinguisher in order to set up new 5-round distinguishers, that exploit properties which are independent of the secret key, of the details of the S-Box and of the MixColumns matrix. As a result, while a “classical” truncated differential distinguisher exploits the probability that a couple of texts satisfies or not a given differential trail independently of the others couples, our distinguishers work with sets of N >> 1 (related) couples of texts. In particular, our new 5-round AES distinguishers exploit the fact that such sets of texts satisfy some properties with a different probability than a random permutation. Even if such 5-round distinguishers have higher complexity than e.g. the “multiple-of-8” one present in the literature, one of them can be used as starting point to set up the first key-recovery attack on 6-round AES that exploits directly a 5-round secret-key distinguisher. The goal of this paper is indeed to present and explore new approaches, showing that even a distinguisher like the one presented at Eurocrypt -- believed to be hard to exploit - can be used to set up a key-recovery attack.

Note: New name for the proposed distinguishers and attacks

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
lorenzo grassi @ iaik tugraz at
History
2019-07-01: last of 6 revisions
2017-08-31: received
See all versions
Short URL
https://ia.cr/2017/832
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/832,
      author = {Lorenzo Grassi},
      title = {Mixture Differential Cryptanalysis and Structural Truncated Differential Attacks on round-reduced AES},
      howpublished = {Cryptology ePrint Archive, Paper 2017/832},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/832}},
      url = {https://eprint.iacr.org/2017/832}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.