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

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, 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 ETSI’s SAGE group in moving from MISTY to KASUMI resulted in a much weaker cipher.