Paper 2011/466

Green Cryptanalysis: Meet-in-the-Middle Key-Recovery for the Full KASUMI Cipher

Keting Jia and Christian Rechberger and Xiaoyun Wang

Abstract

KASUMI is a block cipher with eight Feistel rounds and a key of up to 128 bits. Proposed more than 10 years ago, the confidentiality and integrity of 3G mobile communications systems depend on the security of KASUMI. In the practically interesting single key setting that we are aiming for in this work, no attack is known. For the full 8-round KASUMI we show for the first time a wide variety of results with data complexities between $2^{32}$ chosen plaintexts and as few as 2 texts, while the speed-ups over brute force are between a factor 4 and 6. For use-cases of KASUMI in 2G networks, relying on a 64-bit master key, we describe key recovery methods with extremely low data complexity and speed-ups between a factor 2 and 3 for essentially any desired success probability. The latter results are the first of this type of cryptanalysis that could result in practically realizable cost and energy savings for key recovery efforts. By also analyzing an earlier version of the KASUMI-64 design that had a different mapping from the 64-bit master key to the 128-bit cipher key, we shed some light on a high-level key schedule design issue that may be of independent interest.