A Practical-Time Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony
Orr Dunkelman (Weizmann Institute of Science)
Thursday 16 September 2010, 16.00, b-it 1.25 (cosec meeting room)
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.