KASUMI broken

KASUMI, also termed A5/3, is a block cipher used to secure 3GPP mobile phone communications. Israeli researchers Eli Biham, Orr Dunkelman and Nathan Keller have discovered a related-key rectangle attack on KASUMI that can break all 8 rounds faster than exhaustive search. The paper is to be presented at ASIACRYPT 2005 in December, but there is a technical report available online.

The attack requires 2^54.6 chosen plaintexts and ciphertexts, each of which has been encrypted under one of four different keys, and has a time complexity equivalent to 2^76.1 KASUMI encryptions. Clearly, this is not a practical attack by any stretch of the imagination (the alarmist title of this post notwithstanding), but it's an interesting result, and it invalidates some proofs about the security of the 3GPP protocols that had relied on the presumed strength of KASUMI.

Biham, Dunkelman and Keller have previously found serious flaws in the GSM stream ciphers A5/1 and A5/2.

Tags: Cryptography , Cryptanalysis , KASUMI