KASUMI is a block cipher used in UMTS, GSM, and GPRS mobile communications systems. In UMTS KASUMI is used in the confidentiality (f8) and integrity algorithms (f9) with names UEA1 and UIA1, respectively. ^{[1]} In GSM KASUMI is used in the A5/3 key stream generator and in GPRS in the GEA3 key stream generator.
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 HW implementation and to meet other requirements set for 3G mobile communications security.
KASUMI is named after the original algorithm MISTY — 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 related key attack and very modest computational resources. Interestingly, the attack is ineffective against MISTY.^{[5]}
DescriptionEdit
KASUMI algorithm is specified in a 3GPP technical specification. ^{[6]} KASUMI is a block cipher with 128bit key and 64bit input and output. The core of KASUMI is an eightround Feistel network. The round functions in the main Feistel network are irreversible Feistellike network transformations. In each round the round function uses a round key which consists of eight 16bit sub keys derived from the original 128bit key using a fixed key schedule.
Key scheduleEdit
The 128bit key K is divided into eight 16bit sub keys K_{i}:
Additionally a modified key K', similarly divided into 16bit sub keys K'_{i}, is used. The modified key is derived from the original key by XORing with 0x123456789ABCDEFFEDCBA9876543210.
Round keys are either derived from the sub keys by bitwise rotation to left by a given amount and from the modified sub keys (unchanged).
The round keys are as follows:
Sub key index additions are cyclic so that if i+j is greater than 8 one has to subtract 8 from the result to get the actual sub key index.
The algorithmEdit
KASUMI algorithm processes the 64bit word in two 32bit halves, left () and right (). The input word is concatenation of the left and right halves of the first round:
.
In each round the right half is XOR'ed with the output of the round function after which the halves are swapped:
where KL_{i}, KO_{i}, KI_{i} are round keys for the i^{th} round.
The round functions for even and odd rounds are slightly different. In each case the round function is a composition of two functions FL_{i} and FO_{i}. For an odd round
and for an even round
.
The output is the concatenation of the outputs of the last round.
.
Both FL and FO functions divide the 32bit input data to two 16bit halves. The FL function is an irreversible bit manipulation while the FO function is an irreversible three round Feistellike network.
Function FLEdit
The 32bit input x of is divided to two 16bit halves . First the left half of the input is ANDed bitwise with round key and rotated left by one bit. The result of that is XOR'ed to the right half of the input to get the right half of the output .
Then the right half of the output is ORed bitwise with the round key and rotated left by one bit. The result of that is XOR'ed to the left half of the input to get the left half of the output .
Output of the function is concatenation of the left and right halves .
Function FOEdit
The 32bit input x of is divided into two 16bit halves .
In each of the three rounds (indexed by j that takes values 1, 2, and 3) the left half is modified to get the new right half and the right half is made the left half of the next round.
The function FI is an irregular Feistellike network.
Function FIEdit
The 16bit input of the function is divided to two halves of which is 9 bits wide and is 7 bits wide.
Bits in the left half are first shuffled by 9bit Sbox S9 and the result is XOR'ed with the zeroextended right half to get the new 9bit right half .
Bits of the right half are shuffled by 7bit Sbox S7 and the result is XOR'ed with the seven least significant bits (LS7) of the new right half to get the new 7bit left half .
The intermediate word is XORed with the round key KI to get of which is 7 bits wide and is 9 bits wide.
Bits in the right half are then shuffled by 9bit Sbox S9 and the result is XOR'ed with the zeroextended left half to get the new 9bit right half of the output .
Finally the bits of the left half are shuffled by 7bit Sbox S7 and the result is XOR'ed with the seven least significant bits (LS7) of the right half of the output to get the 7bit left half of the output.
The output is the concatenation of the final left and right halves .
SboxesEdit
The Sboxes S7 and S9 are defined by both bitwise ANDXOR expressions and lookup tables in the specification. The bitwise expressions are intended to hardware implementation but nowadays it is customary to use the lookup tables even in the HW design.
S7 is defined by the following array:
int S7[128] = { 54, 50, 62, 56, 22, 34, 94, 96, 38, 6, 63, 93, 2, 18,123, 33, 55,113, 39,114, 21, 67, 65, 12, 47, 73, 46, 27, 25,111,124, 81, 53, 9,121, 79, 52, 60, 58, 48,101,127, 40,120,104, 70, 71, 43, 20,122, 72, 61, 23,109, 13,100, 77, 1, 16, 7, 82, 10,105, 98, 117,116, 76, 11, 89,106, 0,125,118, 99, 86, 69, 30, 57,126, 87, 112, 51, 17, 5, 95, 14, 90, 84, 91, 8, 35,103, 32, 97, 28, 66, 102, 31, 26, 45, 75, 4, 85, 92, 37, 74, 80, 49, 68, 29,115, 44, 64,107,108, 24,110, 83, 36, 78, 42, 19, 15, 41, 88,119, 59, 3 };
S9 is defined by the following array:
int S9[512] = { 167,239,161,379,391,334, 9,338, 38,226, 48,358,452,385, 90,397, 183,253,147,331,415,340, 51,362,306,500,262, 82,216,159,356,177, 175,241,489, 37,206, 17, 0,333, 44,254,378, 58,143,220, 81,400, 95, 3,315,245, 54,235,218,405,472,264,172,494,371,290,399, 76, 165,197,395,121,257,480,423,212,240, 28,462,176,406,507,288,223, 501,407,249,265, 89,186,221,428,164, 74,440,196,458,421,350,163, 232,158,134,354, 13,250,491,142,191, 69,193,425,152,227,366,135, 344,300,276,242,437,320,113,278, 11,243, 87,317, 36, 93,496, 27, 487,446,482, 41, 68,156,457,131,326,403,339, 20, 39,115,442,124, 475,384,508, 53,112,170,479,151,126,169, 73,268,279,321,168,364, 363,292, 46,499,393,327,324, 24,456,267,157,460,488,426,309,229, 439,506,208,271,349,401,434,236, 16,209,359, 52, 56,120,199,277, 465,416,252,287,246, 6, 83,305,420,345,153,502, 65, 61,244,282, 173,222,418, 67,386,368,261,101,476,291,195,430, 49, 79,166,330, 280,383,373,128,382,408,155,495,367,388,274,107,459,417, 62,454, 132,225,203,316,234, 14,301, 91,503,286,424,211,347,307,140,374, 35,103,125,427, 19,214,453,146,498,314,444,230,256,329,198,285, 50,116, 78,410, 10,205,510,171,231, 45,139,467, 29, 86,505, 32, 72, 26,342,150,313,490,431,238,411,325,149,473, 40,119,174,355, 185,233,389, 71,448,273,372, 55,110,178,322, 12,469,392,369,190, 1,109,375,137,181, 88, 75,308,260,484, 98,272,370,275,412,111, 336,318, 4,504,492,259,304, 77,337,435, 21,357,303,332,483, 18, 47, 85, 25,497,474,289,100,269,296,478,270,106, 31,104,433, 84, 414,486,394, 96, 99,154,511,148,413,361,409,255,162,215,302,201, 266,351,343,144,441,365,108,298,251, 34,182,509,138,210,335,133, 311,352,328,141,396,346,123,319,450,281,429,228,443,481, 92,404, 485,422,248,297, 23,213,130,466, 22,217,283, 70,294,360,419,127, 312,377, 7,468,194, 2,117,295,463,258,224,447,247,187, 80,398, 284,353,105,390,299,471,470,184, 57,200,348, 63,204,188, 33,451, 97, 30,310,219, 94,160,129,493, 64,179,263,102,189,207,114,402, 438,477,387,122,192, 42,381, 5,145,118,180,449,293,323,136,380, 43, 66, 60,455,341,445,202,432, 8,237, 15,376,436,464, 59,461 };
CryptanalysisEdit
In 2001, an impossible differential attack on six rounds of KASUMI was presented by Kühn (2001).^{[7]}
In 2003 Elad Barkan, Eli Biham and Nathan Keller demonstrated maninthemiddle attacks against the GSM protocol that allow avoiding the A5/3 cipher and thus breaking the protocol. This approach does not attack the A5/3 cipher, however.^{[8]} The full version of their paper was published later in 2006.^{[9]}
In 2005, Israeli researchers Eli Biham, Orr Dunkelman and Nathan Keller published a relatedkey rectangle (boomerang) attack on KASUMI that can break all 8 rounds faster than exhaustive search.^{[10]} 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 2010, Dunkleman, Keller and Shamir published a new attack that allows to recover a full A5/3 key by relatedkey attack.^{[5]} The time and space complexities of the attack are low enough that the authors carried out the attack two hours on a modest 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.
See alsoEdit
ReferencesEdit
External linksEdit

es:KASUMI fr:KASUMI it:KASUMI (cifrario) ja:KASUMI ru:KASUMI