CoChat
Sign Up
Cited by 155Cryptographic Implementations and SecurityCoding theory and cryptographyCryptography and Residue Arithmetic

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

Open access
Dunkelman, Orr, Keller, Nathan, Shamir, Adi·2010·Lecture Notes in Computer Science
DOI 10.1007/978-3-642-14623-7_21
Open this paper in CoChat — free accountOpen PDF

Abstract

The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced by the new A5/3 (and the soon to be announced A5/4) algorithm based on the block cipher KASUMI, which is a modified version of MISTY. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2− 14. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, 226 data, 230 bytes of memory, and 232 time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the 2128 complexity of exhaustive search, which indicates that the changes made by ETSI’s SAGE group in moving from MISTY to KASUMI resulted in a much weaker cipher.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1007/978-3-642-14623-7_21

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The fastest single-key attacks on round-reduced AES variants so far are only slightly more powerful than those proposed 10 years ago.

    “Though many papers have been published on the cryptanalysis of AES, the fastest single-key attacks on round-reduced AES variants [20,33] so far are only slightly more powerful than those proposed 10 years ago [23,24].”

    From Biclique Cryptanalysis of the Full AES (2011) · cites this paper as [23]

    The Introduction and Summary discuss related-key attacks on KASUMI, not the relative strength of single-key attacks on round-reduced AES. A reference lists a reduced-round AES attack, but our copy does not compare AES attacks with those proposed ten years earlier (searched for single-key AES attacks and that comparison). (LLM, conf=0.76)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 20

  1. Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 1-19. Springer, Heidelberg (2006)
  2. Barkan, E., Biham, E., Keller, N.: Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 600-616. Springer, Heidelberg (2003)
  3. Biham, E.: New Types of Cryptanalytic Attacks Using Related Keys. Journal of Cryptology 7(4), 229-246 (1994)
  4. Biham, E., Dunkelman, O., Keller, N.: The Rectangle Attack -Rectangling the Serpent. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 340- 357. Springer, Heidelberg (2001)
  5. Biham, E., Dunkelman, O., Keller, N.: New Results on Boomerang and Rectangle Attacks. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 1-16. Springer, Heidelberg (2002)
  6. Biham, E., Dunkelman, O., Keller, N.: Related-Key Boomerang and Rectangle Attacks. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 507-525. Springer, Heidelberg (2005)
  7. Biham, E., Dunkelman, O., Keller, N.: A Related-Key Rectangle Attack on the Full KASUMI. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 443-461. Springer, Heidelberg (2005)
  8. Biryukov, A.: The Boomerang Attack on 5 and 6-Round Reduced AES. In: Dob- bertin, H., Rijmen, V., Sowa, A. (eds.) AES 2005. LNCS, vol. 3373, pp. 11-15. Springer, Heidelberg (2005)
  9. Biryukov, A., De Cannière, C., Dellkrantz, G.: Cryptanalysis of SAFER++. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 195-211. Springer, Heidelberg (2003)
  10. Biryukov, A., Khovratovich, D.: Related-key Cryptanalysis of the Full AES-192 and AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 1-18. Springer, Heidelberg (2009)
  11. Biryukov, A., Shamir, A., Wagner, D.: Real Time Cryptanalysis of A5/1 on a PC. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 1-18. Springer, Heidelberg (2001)
  12. Blunden, M., Escott, A.: Related Key Attacks on Reduced Round KASUMI. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 277-285. Springer, Heidelberg (2002)
  13. Dunkelman, O., Keller, N.: An Improved Impossible Differential Attack on MISTY1. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 441-454. Springer, Heidelberg (2008)
  14. Ekdahl, P., Johansson, T.: Another Attack on A5/1. IEEE Transactions on Infor- mation Theory 49(1), 284-289 (2003)
  15. Golic, J.D.: Cryptanalysis of Alleged A5 Stream Cipher. In: Fumy, W. (ed.) EU- ROCRYPT 1997. LNCS, vol. 1233, pp. 239-255. Springer, Heidelberg (1997)
  16. Hong, S., Kim, J., Kim, G., Lee, S., Preneel, B.: Related-Key Rectangle Attacks on Reduced Versions of SHACAL-1 and AES-192. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 368-383. Springer, Heidelberg (2005)
  17. Kelsey, J., Schneier, B., Wagner, D.: Key Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 237-251. Springer, Heidelberg (1996)
  18. Kim, J., Kim, G., Hong, S., Hong, D.: The Related-Key Rectangle Attack -Appli- cation to SHACAL-1. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 123-136. Springer, Heidelberg (2004)
  19. Matsui, M.: Block encryption algorithm MISTY. In: FSE 1997. LNCS, vol. 1267, pp. 64-74. Springer, Heidelberg (1997)
  20. Wagner, D.: The Boomerang Attack. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156-170. Springer, Heidelberg (1999)

Cited by

Sorted by citations

Authors
Dunkelman, O., Keller, N., & Shamir, A.
Affiliations
Weizmann Institute of Science (IL)
ORCID
Venue
Lecture Notes in Computer Science
Publisher
Springer Berlin Heidelberg
Published
2010
Pages
393-410
ISSN
  • 0302-9743 (ISSN-L)
  • 1611-3349
DOI
10.1007/978-3-642-14623-7_21
OpenAlex
W1563341929
Cited by
155
References
0
Citations by year
2026: 4 · 2025: 8 · 2024: 16 · 2023: 9 · 2022: 8 · 2021: 11 · 2020: 11 · 2019: 7 · 2018: 10 · 2017: 1 · 2016: 4 · 2015: 10 · 2014: 12 · 2013: 15 · 2012: 13
FWCI
11.38
Type
conference paper
Language
en
Open access
Licence
cc-by
Locations
Lecture notes in computer science (publishedVersion, cc-by)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Cryptographic Implementations and Security
  • Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
  • Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
Keywords
KASUMI, related-key attacks, sandwich attacks, Misty, A5/1, stream ciphers, block cipher cryptanalysis, key recovery, distinguishers, GSM

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review