KASUMI (block cipher)

Infobox block cipher
name = KASUMI


caption =
designers = Security Algorithms Group of Experts
publish date =
derived from = MISTY1
derived to =
key size = 128 bits
block size = 64 bits
structure = Feistel network
rounds = 8
cryptanalysis = Related-key rectangle attack using 2^54.6 chosen plaintexts with a complexity of 2^76.1

In cryptography, KASUMI, also termed A5/3, is a block cipher used in the confidentiality ("f8") and integrity algorithms ("f9") for 3GPP mobile communications. A number of serious weaknesses in the cipher have been identified.

KASUMI was designed by the Security Algorithms Group of Experts (SAGE), part of the European standards body ETSI. Rather than invent a cipher from scratch, SAGE selected an existing algorithm, MISTY1, and optimised it slightly for implementation in hardware. Hence, MISTY1 and KASUMI are very similar — "kasumi" (霞) is the Japanese word for "mist" — and the cryptanalysis of one is likely to be readily adaptable to the other. KASUMI maintains an efficient implementation in software.

KASUMI has a block size of 64 bits and a key size of 128 bits. It is a Feistel cipher with eight rounds, and like MISTY1 and MISTY2, it has a recursive structure, with subcomponents also having a Feistel-like form.

In 2001, an impossible differential attack on six rounds of KASUMI was presented by Kühn (2001).

In 2005, Israeli researchers Eli Biham, Orr Dunkelman and Nathan Keller published a related-key rectangle (boomerang) attack on KASUMI that can break all 8 rounds faster than exhaustive search. The attack requires 2^54.6 chosen plaintexts, each of which has been encrypted under one of four related keys, and has a time complexity equivalent to 2^76.1 KASUMI encryptions. While this is not a practical attack, it invalidates some proofs about the security of the 3GPP protocols that had relied on the presumed strength of KASUMI.

In 2006 Elad Barkan, Eli Biham and Nathan Keller demonstrated attacks against A5/1 and A5/2, that allow attackers to tap GSM mobile phone conversations and decrypt them either in real-time, or at any later time. Protocol weaknesses allow recovery of the key, but the KASUMI algorithm is unaffected in itself.

ee also

* A5/1 and A5/2

References

* ETSI, [http://www.etsi.org/website/document/algorithms/ts_135202v070000p.pdf "Universal Mobile Telecommunications System (UMTS); Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification"] , 2007.
* Kühn, U. "Cryptanalysis of Reduced Round MISTY", EUROCRYPT 2001.
* Eli Biham, Orr Dunkelman and Nathan Keller, A Related-Key Rectangle Attack on the Full KASUMI, ASIACRYPT 2005, 443–461
* Elad Barkan, Eli Biham and Nathan Keller, Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication, CRYPTO 2003, pp600–616 [http://cryptome.org/gsm-crack-bbk.pdf (PDF)] .

External links

* [http://global.mitsubishielectric.com/pdf/advance/vol100/03Vol100_TR2.pdf Article on KASUMI (and MISTY) in Mitsubishi Advance (PDF)]
* [http://www.ma.huji.ac.il/~nkeller Nathan Keller's homepage]