Paper 2010/013

A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony

Orr Dunkelman, Nathan Keller, and Adi Shamir

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 in third generation networks by a new A5/3 block cipher called KASUMI, which is a modified version of the MISTY cryptosystem. 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, $2^{26}$ data, $2^{30}$ bytes of memory, and $2^{32}$ 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 $2^{128}$ complexity of exhaustive search, which indicates that the changes made by the GSM Association in moving from MISTY to KASUMI resulted in a much weaker cryptosystem.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
A53GSM telephonyKASUMIMISTYsandwich attackpractical attack
Contact author(s)
adi shamir @ weizmann ac il
History
2010-01-12: received
Short URL
https://ia.cr/2010/013
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/013,
      author = {Orr Dunkelman and Nathan Keller and Adi Shamir},
      title = {A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony},
      howpublished = {Cryptology ePrint Archive, Paper 2010/013},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/013}},
      url = {https://eprint.iacr.org/2010/013}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.