nach oben

Journal of Cryptology

Erschienen in:

01.10.2014

A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony

verfasst von: Orr Dunkelman, Nathan Keller, Adi Shamir

Erschienen in: Journal of Cryptology | Ausgabe 4/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Over the last 20 years, the privacy of most GSM phone conversations was protected by the A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They are being replaced now by the new A5/3 and A5/4 algorithms, which are based on the block cipher KASUMI. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple related-key distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2⁻¹⁴. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128-bit key of the full KASUMI with a related-key attack which uses only 4 related keys, 2²⁶ data, 2³⁰ bytes of memory, and 2³² time. These completely practical complexities were experimentally verified by performing the attack in less than two hours on a single-core of a PC. Interestingly, neither our technique nor any other published attack can break the original MISTY block cipher (on which KASUMI is based) significantly faster than exhaustive search. Our results thus indicate that the modifications made by ETSI’s SAGE group in moving from MISTY to KASUMI made it extremely weak when related-key attacks are allowed, but do not imply anything about its resistance to single-key attacks. Consequently, there is no indication that the way KASUMI is implemented in GSM and 3G networks is practically vulnerable in any realistic attack model.

Vorheriger Artikel A Characterization of Chameleon Hash Functions and New, Efficient Designs

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

Our implementation of the attack used the official reference implementation of KASUMI [25], which is not optimized for exhaustive search.

In [21] it was shown that the independence assumptions underlying the attack may fail in various cases, and hence it is desirable to check the validity of the assumptions experimentally in each specific case. In the case of KASUMI considered in this paper, we have verified both the distinguisher and the attack experimentally, and the probabilities match the theoretical prediction with high precision (as described in Sect. 4.2).

This estimate is based on a randomness assumption that could be inaccurate in our case due to dependence between the differential characteristics. However, our experiments verify that this probability is indeed as expected.

An almost perfect nonlinear permutation, introduced in [22], is a permutation f:GF(2ⁿ)→GF(2ⁿ) such that for any a≠0, the function g(x,a)=f(x)⊕f(x⊕a) assumes exactly 2ⁿ⁻¹ different values. In an almost perfect nonlinear permutation, for any two pairs of distinct input values with the same difference, the corresponding output pairs cannot have the same difference. The S-boxes S7 and S9 used in KASUMI were designed as almost perfect nonlinear permutations, in order to obtain maximal security with respect to differential and linear cryptanalysis (see [23]).

We used 100 keys, and for each of them we generated 2²⁴ quartets. We first verified using the official key schedule that many right quartets are encountered, and then we modified the key schedule in the way described above. None of the experiments yielded a right quartet.

We alert the reader that KASUMI employs a swap operation after the last round.

In our case, the guess of KO _8,1 and KI _8,1 is sufficient for computing the difference in the left half of the output of FO8, since the right half of the input difference to FO8 is zero. By the structure of FL, this difference and the output difference of FL8 yield the input and output differences of the OR operation.

The simple proof of this claim is given in [7, Sect. 4.3].

The need to perform the final step several times arises since due to the differential nature of the attack, a few key candidates cannot be distinguished from the right key until the exhaustive search step. As can be seen in Table 5, the number of these keys decreases when more right quartets are analyzed.

[1]

A5/1 Security Project, Creating A5/1 rainbow tables (2009). Available online at http://reflextor.com/trac/a51

[2]

E. Barkan, E. Biham, Conditional estimators: an effective attack on A5/1, in Proceedings of Selected Areas in Cryptology 2005. Lecture Notes in Computer Science, vol. 3897 (Springer, Berlin, 2006), pp. 1–19

[3]

E. Barkan, E. Biham, N. Keller, Instant ciphertext-only cryptanalysis of GSM encrypted communication, in Advances in Cryptology, Proceedings of CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729 (Springer, Berlin, 2003), pp. 600–616 CrossRef

[4]

E. Biham, New types of cryptanalytic attacks using related keys. J. Cryptol. 7(4), 229–246 (1994) MATH

[5]

E. Biham, O. Dunkelman, N. Keller, New results on boomerang and rectangle attacks, in Proceedings of Fast Software Encryption 2002. Lecture Notes in Computer Science, vol. 2365 (Springer, Berlin, 2002), pp. 1–16 CrossRef

[6]

E. Biham, O. Dunkelman, N. Keller, Related-key boomerang and rectangle attacks, in Advances in Cryptology, Proceedings of EUROCRYPT 2005. Lecture Notes in Computer Science, vol. 3494 (Springer, Berlin, 2005), pp. 507–525 CrossRef

[7]

E. Biham, O. Dunkelman, N. Keller, A related-key rectangle attack on the full KASUMI, in Advances in Cryptology, Proceedings of ASIACRYPT 2005. Lecture Notes in Computer Science, vol. 3788 (Springer, Berlin, 2005), pp. 443–461 CrossRef

[8]

A. Biryukov, C. De Cannière, G. Dellkrantz, Cryptanalysis of SAFER++, in Advances in Cryptology, Proceedings of CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729 (Springer, Berlin, 2003), pp. 195–211 CrossRef

[9]

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

[10]

A. Biryukov, A. Shamir, D. Wagner, Real time cryptanalysis of A5/1 on a PC, in Proceedings of Fast Software Encryption 2000. Lecture Notes in Computer Science, vol. 1978 (Springer, Berlin, 2001), pp. 1–18 CrossRef

[11]

M. Blunden, A. Escott, Related key attacks on reduced round KASUMI, in Proceedings of Fast Software Encryption 2001. Lecture Notes in Computer Science, vol. 2355 (Springer, Berlin, 2002), pp. 277–285 CrossRef

[12]

M. Briceno, I. Goldverg, D. Wagner, A pedagogical implementation of the GSM A5/1 and A5/2 “voice privacy” encryption algorithms (1999). Available online at http://cryptome.org/gsm-a512.htm

[13]

P. Ekdahl, T. Johansson, Another attack on A5/1. IEEE Trans. Inf. Theory 49(1), 284–289 (2003) CrossRefMATHMathSciNet

[14]

S. Hong, J. Kim, G. Kim, S. Lee, B. Preneel, Related-key rectangle attacks on reduced versions of SHACAL-1 and AES-192, in Proceedings of Fast Software Encryption 1999. Lecture Notes in Computer Science, vol. 3557 (Springer, Berlin, 2005), pp. 368–383 CrossRef

[15]

K. Jia, J. Chen, M. Wang, X. Wang, Practical attack on the full MMB block cipher, in Proceedings of Selected Areas in Cryptology 2011. Lecture Notes in Computer Science, vol. 7118 (Springer, Berlin, 2011), pp. 185–199

[16]

K. Jia, H. Yu, X. Wang, A meet-in-the-middle attack on the full KASUMI. IACR ePrint report 2011/466

[17]

J. Kelsey, B. Schneier, D. Wagner, Key schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES, in Advances in Cryptology, Proceedings of CRYPTO 1996. Lecture Notes in Computer Science, vol. 1109 (Springer, Berlin, 1996), pp. 237–251

[18]

J. Kim, G. Kim, S. Hong, D. Hong, The related-key rectangle attack—application to SHACAL-1, in Proceedings of Australasian Conference on Information Security and Privacy 2004. Lecture Notes in Computer Science, vol. 3108 (Springer, Berlin, 2004), pp. 123–136

[19]

J. Kim, S. Hong, B. Preneel, E. Biham, O. Dunkelman, N. Keller, Related-key boomerang and rectangle attacks: theory and experimental analysis. IEEE Trans. Inf. Theory 58(7), 4948–4966 (2012) CrossRefMathSciNet

[20]

M. Matsui, Block encryption algorithm MISTY, in Proceedings of Fast Software Encryption 1997. Lecture Notes in Computer Science, vol. 1267 (Springer, Berlin, 1997), pp. 64–74

[21]

S. Murphy, The return of the cryptographic boomerang. IEEE Trans. Inf. Theory 57(4), 2517–2521 (2011) CrossRef

[22]

K. Nyberg, Perfect nonlinear S-boxes, in Advances in Cryptology, Proceedings of EUROCRYPT 1991. Lecture Notes in Computer Science, vol. 547 (Springer, Berlin, 1991), pp. 378–386

[23]

K. Nyberg, L.R. Knudsen, Provable security against differential cryptanalysis, in Advances in Cryptology, Proceedings of CRYPTO 1992. Lecture Notes in Computer Science, vol. 740 (Springer, Berlin, 1993), pp. 566–578

[24]

3rd Generation Partnership Project, Technical specification group services and system aspects, 3G security. Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 2: KASUMI Specification, V3.1.1 (2001)

[25]

3rd Generation Partnership Project, Technical specification group services and system aspects, 3G security. Specification of the A5/3 Encryption Algorithms for GSM and ECSD, and the GEA3 Encryption Algorithm for GPRS; Document 4: Design and Evaluation Report, V6.1.0 (2002)

[26]

D. Wagner, The boomerang attack, in Proceedings of Fast Software Encryption 1999. Lecture Notes in Computer Science, vol. 1636 (Springer, Berlin, 1999), pp. 156–170 CrossRef

Titel: A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony
verfasst von: Orr Dunkelman
Nathan Keller
Adi Shamir
Publikationsdatum: 01.10.2014
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 4/2014
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-013-9154-9

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 4/2014

Using Symmetries in the Index Calculus for Elliptic Curves Discrete Logarithm

Authenticated Adversarial Routing

A Characterization of Chameleon Hash Functions and New, Efficient Designs

Improved Cryptanalysis of AES-like Permutations