Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Summer 2010 

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.

Imprint, webmaster & more