nach oben

Journal of Cryptology

Erschienen in:

01.07.2015

Improved Single-Key Attacks on 8-Round AES-192 and AES-256

verfasst von: Orr Dunkelman, Nathan Keller, Adi Shamir

Erschienen in: Journal of Cryptology | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

AES is the most widely used block cipher today, and its security is one of the most important issues in cryptanalysis. After 13 years of analysis, related-key attacks were recently found against two of its flavors (AES-192 and AES-256). However, such a strong type of attack is not universally accepted as a valid attack model, and in the more standard single-key attack model at most 8 rounds of these two versions can be currently attacked. In the case of 8-round AES-192, the only known attack (found 10 years ago) is extremely marginal, requiring the evaluation of essentially all the 2¹²⁸ possible plaintext/ciphertext pairs in order to speed up exhaustive key search by a factor of 16. In this paper we introduce three new cryptanalytic techniques, and use them to get the first non-marginal attack on 8-round AES-192 (making its time complexity about a million times faster than exhaustive search, and reducing its data complexity to about 1/32,000 of the full codebook). In addition, our new techniques can reduce the best known time complexities for all the other combinations of 7-round and 8-round AES-192 and AES-256.

Nächster Artikel GNUC: A New Universal Composability Framework

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

In [6] the authors note that the function \(f_{c_{1},\ldots,c_{25}}(x)\) can be written as \(f_{c_{1},\ldots,c_{25}}(x) = g_{c_{1},\ldots,c_{24}}(x) \oplus c_{25}\), and thus one can reduce the number of possible sequences by picking some x ₀, and considering the augmented function \(f'_{c_{1},\ldots,c_{24}} (x) = f_{c_{1},\ldots,c_{25}}(x) - f_{c_{1},\ldots,c_{25}}(x_{0}) = g_{c_{1},\ldots,c_{24}} (x) - g_{c_{1},\ldots,c_{24}}(x_{0})\). In this case, the number of parameters is reduced to 24, the number of “interesting” entries in each sequence is reduced to 255 (as f′(x ₀)=0, independently of the choice of x ₀ and c ₁,…,c ₂₄), and the number of possible sequences is reduced to 2¹⁹².

Unlike sets, elements can occur multiple times, and the multiset retains this multiplicity along with the values.

The calculation of the number of possible values is explained at the end of this section.

Picking a different starting point X ^0,⋆, results in changing all the 255 entries of the multiset by XORing them with X ^0,⋆⊕X ⁰. As there are at most 255 other values for X ^0,⋆, each multiset belongs to the same equivalence class with as at most 255 other multisets.

The probability of 2⁻¹²⁰ is based on the assumption that 4-round AES behaves like a random permutation with respect to this differential, and thus forcing 120 bits to be equal has this probability. Theoretically, it may be the case that due to the algebraic structure of AES, this differential is impossible, which would lead to very strong impossible differential attacks on reduced-round variants of AES. However, we could not find any specific reason why this should be the case, and unfortunately, we cannot check this differential experimentally due to its extremely low probability.

Actually, given the input/output differences, with probability of about 1/2 there are no such pairs, with probability of about 1/2 there are two pairs, and with probability of about 1/256 there are four pairs.

We note that while the table of possible multisets is constructed according to one member of the right pair, it may occur that in the actual attack, the other member is chosen as P ⁰, and thus the multiset does not match the table (even for the right key guess). A simple solution is to repeat the attack for both members of the right pair. A more advanced solution, which allows to save the extra factor two in the time complexity of the attack, is to store the multisets only up to XOR with a constant value. This can be achieved by a small modification to the preprocessing phase, consisting of XORing each multiset with the 256 possible byte values and storing in the table the resulting multiset which is the least in the lexicographic order amongst the 256 possibilities.

The four bytes of k ₇ are 0 and 4 (for obtaining byte 0 of W[27]) and bytes 7 and 15 (for obtaining byte 3 of W[23]).

In the description of our attack we assume that the last round does not contain the MixColumns operation. If it does contain it, one can swap the order of the last round’s MixColumns and AddRoundKey and apply the attack with the respective changes.

In order to do it, the adversary considers structures of size 2⁹⁶ each, in which bytes 1,6,11,12 are constant and the other bytes take all the 2⁹⁶ possible values. This allows to use bytes 5 and 10 as the additional active byte in the input of the differential. All three additional bytes cannot be used in parallel, since this would require structures of size 2¹²⁸.

[1]

A. Biryukov, D. Khovratovich, Related-key cryptanalysis of the full AES-192 and AES-256, in Advances in Cryptography, Proceedings of ASIACRYPT 2009. Lecture Notes in Computer Science, vol. 5912 (Springer, Berlin, 2009), pp. 1–18 CrossRef

[2]

A. Biryukov, D. Khovratovich, I. Nikolic, Distinguisher and related-key attack on the full AES-256, in Advances in Cryptography, Proceedings of CRYPTO 2009. Lecture Notes in Computer Science, vol. 5677 (Springer, Berlin, 2009), pp. 231–249 CrossRef

[3]

A. Biryukov, O. Dunkelman, N. Keller, D. Khovratovich, A. Shamir, Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds, in Advances in Cryptography, Proceedings of EUROCRYPT 2010. Lecture Notes in Computer, vol. 6110 (Springer, Berlin, 2010), pp. 299–319 CrossRef

[4]

J. Daemen, V. Rijmen, AES proposal: Rijndael, in NIST AES Proposal (1998)

[5]

J. Daemen, V. Rijmen, The Design of Rijndael: AES—the Advanced Encryption Standard (Springer, Berlin, 2002) CrossRef

[6]

H. Demirci, A. Aydin Selçuk, A meet-in-the-middle attack on 8-round AES, in Proceedings of Fast Software Encryption 2008. Lecture Notes in Computer Science, vol. 5086 (Springer, Berlin, 2008), pp. 116–126 CrossRef

[7]

H. Demirci, I. Taskin, M. Çoban, A. Baysal, Improved meet-in-the-middle attacks on AES, in Proceedings of INDOCRYPT 2009. Lecture Notes in Computer Science, vol. 5922 (Springer, Berlin, 2009), pp. 144–156 CrossRef

[8]

P. Derbez, P.-A. Fouque, Exhausting Demirci–Selcuk Meet-in-the-Middle Attacks against Reduced-Round AES, pre-proceedings of Fast Software Encryption 2013. Lecture Notes in Computer Science (2013, to appear)

[9]

P. Derbez, P.-A. Fouque, J. Jean, Improved key recovery attacks on reduced-round AES in the single-key setting, in Advances in Cryptology, Eurocrypt 2013 (2013). doi:10.1007/978-3-642-38348-9_23

[10]

O. Dunkelman, N. Keller, A new attack on the LEX stream cipher, in Advances in Cryptography, Proceedings of ASIACRYPT 2008. Lecture Notes in Computer Science, vol. 5350 (Springer, Berlin, 2008), pp. 539–556. doi:10.1007/978-3-540-89255-7_33 CrossRef

[11]

N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, D. Whiting, Improved cryptanalysis of Rijndael, in Proceedings of Fast Software Encryption 2000. Lecture Notes in Computer Science 1978 (Springer, Berlin, 2001), pp. 213–230. doi:10.1007/3-540-44706-7_15 CrossRef

[12]

H. Gilbert, M. Minier, A collision attack on 7 rounds of Rijndael, in Proceedings of the Third AES Candidate Conference (AES3), New York, USA (2000), pp. 230–241

[13]

J. Lu, O. Dunkelman, N. Keller, J. Kim, New impossible differential attacks on AES, in Proceedings of INDOCRYPT 2008. Lecture Notes in Computer Science, vol. 5365 (Springer, Berlin, 2008), pp. 279–293 CrossRef

[14]

H. Mala, M. Dakhilalian, V. Rijmen, M. Modarres-Hashemi, Improved impossible differential cryptanalysis of 7-round AES-128, in Proceedings of INDOCRYPT 2010. Lecture Notes in Computer Science, vol. 6498 (Springer, Berlin, 2010), pp. 282–291 CrossRef

[15]

US National Institute of Standards and Technology, Advanced Encryption Standard, Federal Information Processing Standards Publications, vol. 197 (2001)

[16]

W. Zhang, W. Wu, L. Zhang, D. Feng, Improved related-key impossible differential attacks on reduced-round AES-192, in Proceedings of Selected Areas in Cryptography 2006. Lecture Notes in Computer Science, vol. 4356 (Springer, Berlin, 2007), pp. 15–27 CrossRef

Titel: Improved Single-Key Attacks on 8-Round AES-192 and AES-256
verfasst von: Orr Dunkelman
Nathan Keller
Adi Shamir
Publikationsdatum: 01.07.2015
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 3/2015
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-013-9159-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2015

Polynomial-Time Solutions of Computational Problems in Noncommutative-Algebraic Cryptography

Provable Unlinkability Against Traffic Analysis with Low Message Overhead

Protocols for Multiparty Coin Toss with a Dishonest Majority

GNUC: A New Universal Composability Framework

Reflection Cryptanalysis of PRINCE-Like Ciphers

A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy

Premium Partner