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 recently announced A5/4) algorithm based
on the block cipher KASUMI, which is a modified version of MISTY. In
this work 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.

This is a joint work with Nathan Keller and Adi Shamir.