KASUMI is a block cipher used in UMTS, GSM, and GPRS mobile communications systems.
KASUMI was designed for 3GPP to be used in UMTS security system by the Security Algorithms Group of Experts (SAGE), a part of the European standards body ETSI.
[2] Because of schedule pressures in 3GPP standardization, instead of developing a new cipher, SAGE agreed with 3GPP technical specification group (TSG) for system aspects of 3G security (SA3) to base the development on an existing algorithm that had already undergone some evaluation.
[2] They chose the cipher algorithm MISTY1 developed[3] and patented[4] by Mitsubishi Electric Corporation.
The original algorithm was slightly modified for easier hardware implementation and to meet other requirements set for 3G mobile communications security.
KASUMI is named after the original algorithm MISTY1 — 霞み (hiragana かすみ, romaji kasumi) is the Japanese word for "mist".
In January 2010, Orr Dunkelman, Nathan Keller and Adi Shamir released a paper showing that they could break Kasumi with a related-key attack and very modest computational resources; this attack is ineffective against MISTY1.
The core of KASUMI is an eight-round Feistel network.
KASUMI algorithm processes the 64-bit word in two 32-bit halves, left (
The input word is concatenation of the left and right halves of the first round:
Both FL and FO functions divide the 32-bit input data to two 16-bit halves.
The FL function is an irreversible bit manipulation while the FO function is an irreversible three round Feistel-like network.
The result of that is XOR'ed to the left half of the input
Output of the function is concatenation of the left and right halves
, and passed through three rounds of a Feistel network.
The function FI is an irregular Feistel-like network.
are first shuffled by 9-bit substitution box (S-box) S9 and the result is XOR'ed with the zero-extended right half
are shuffled by 7-bit S-box S7 and the result is XOR'ed with the seven least significant bits (LS7) of the new right half
are then shuffled by 9-bit S-box S9 and the result is XOR'ed with the zero-extended left half
are shuffled by 7-bit S-box S7 and the result is XOR'ed with the seven least significant bits (LS7) of the right half of the output
The output is the concatenation of the final left and right halves
The substitution boxes (S-boxes) S7 and S9 are defined by both bit-wise AND-XOR expressions and look-up tables in the specification.
The bit-wise expressions are intended to hardware implementation but nowadays it is customary to use the look-up tables even in the HW design.
[7] In 2003 Elad Barkan, Eli Biham and Nathan Keller demonstrated man-in-the-middle attacks against the GSM protocol which avoided the A5/3 cipher and thus breaking the protocol.
[9] 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.
[10] The attack requires 254.6 chosen plaintexts, each of which has been encrypted under one of four related keys, and has a time complexity equivalent to 276.1 KASUMI encryptions.
While this is obviously 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 2010, Dunkelman, Keller and Shamir published a new attack that allows an adversary to recover a full A5/3 key by related-key attack.
[5] The time and space complexities of the attack are low enough that the authors carried out the attack in two hours on an Intel Core 2 Duo desktop computer even using the unoptimized reference KASUMI implementation.
The authors note that this attack may not be applicable to the way A5/3 is used in 3G systems; their main purpose was to discredit 3GPP's assurances that their changes to MISTY wouldn't significantly impact the security of the algorithm.