en>Yobot: /* Localization of categories */WP:CHECKWIKI error fixes using AWB (10093)

2014-05-05T12:09:04Z

Localization of categories: WP:CHECKWIKI error fixes using AWB (10093)

en>D.Lazard: /* Introduction and motivation */ Formatting: Adding \quad twice + more common notation for the category of modules

2013-12-15T18:58:06Z

Introduction and motivation: Formatting: Adding \quad twice + more common notation for the category of modules

New page

{{Infobox block cipher
| name = KASUMI
| image =
| caption =
| designers = [[Mitsubishi Electric]]
| publish date =
| derived from = [[MISTY1]]
| derived to =
| related to =
| certification =
| key size = 128 bits
| block size = 64 bits
| structure = [[Feistel network]]
| rounds = 8
| cryptanalysis =
}}

'''KASUMI''' is a [[block cipher]] used in [[UMTS]], [[GSM]], and [[GPRS]] [[mobile phone|mobile communications]] systems.
In UMTS, KASUMI is used in the [[confidentiality]] (''f8'') and [[Data integrity|integrity]] algorithms (''f9'') with names UEA1 and UIA1, respectively.<ref>{{cite web
| publisher=3GPP
| title=Draft Report of SA3 #38
| url=http://www.3gpp.org/ftp/tsg_sa/TSG_SA/TSGS_28/Docs/pdf/SP-050236.pdf
| year=2005
}}</ref>
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]].<ref name="sage_report">
{{cite web
| publisher=3GPP
| title=General Report on the Design, Speification and Evaluation of 3GPP Standard Confidentiality and Integrity Algorithms
| url=http://www.3gpp.org/ftp/tsg_sa/WG3_Security/_Specs/33908-300.pdf
| year=2009
}}</ref>
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.<ref name="sage_report"/>
They chose the cipher algorithm [[MISTY1]] developed<ref>
{{Cite journal
| last = Matsui
| first = Mitsuru
| last2 = Tokita
| first2 = Toshio
| title = MISTY, KASUMI and Camellia Cipher Algorithm Development
| journal = Mitsibishi Electric Advance
| volume = 100
| pages = 2–8
| publisher = Mitsibishi Electric corp.
| date = Dec 2000
| url = http://global.mitsubishielectric.com/company/rd/advance/pdf/vol100/vol100.pdf
| issn = 1345-3041
| accessdate = 2010-01-06}}
</ref>
and patented<ref>
{{Citation
| inventor-last = Matsui
| inventor-first = Mitsuru
| inventor2-last = Tokita
| inventor2-first = Toshio
| publication-date = Sep. 19, 2002
| issue-date = Aug. 22, 2006
| title = Data Transformation Apparatus and Data Transformation Method
| country-code = US
| patent-number = 7096369
}}
</ref>
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]] — [[wikt:en:霞み#Japanese|霞み]] (hiragana [[wikt:en:かすみ#Japanese|かすみ]], romaji ''[[wikt:en:kasumi#Japanese|kasumi]]'') is the [[Japanese language|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. Interestingly, the attack is ineffective against MISTY.<ref name=a5-3-broken>{{cite journal | author=Orr Dunkelman, Nathan Keller, Adi Shamir | date=2010-01-10 | title=A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony | url=http://eprint.iacr.org/2010/013}}</ref>

==Description==

KASUMI algorithm is specified in a 3GPP technical specification.<ref>{{cite web
| publisher=3GPP
| title=3GPP TS 35.202: Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification
| url=http://www.3gpp.org/ftp/Specs/html-info/35202.htm
| year=2009
}}</ref>
KASUMI is a block cipher with 128-bit key and 64-bit input and output.
The core of KASUMI is an eight-round [[Feistel network]]. The round functions
in the main Feistel network are irreversible Feistel-like network
transformations. In each round the round function uses a round key
which consists of eight 16-bit sub keys
derived from the original 128-bit key using a fixed key schedule.

===Key schedule===

The 128-bit key ''K'' is divided into eight 16-bit sub keys ''Ki'':

<math>K=K_1 \| K_2 \| K_3 \| K_4 \| K_5 \| K_6 \| K_7 \| K_8\,</math>

Additionally a modified key ''K''', similarly divided into 16-bit
sub keys ''K'i'', is used. The modified key is derived from
the original key by XORing with 0x123456789ABCDEFFEDCBA9876543210 (chosen as a [[Nothing up my sleeve number|"nothing up my sleeve" number]]).

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:

<math>
\begin{array}{lcl}
KL_{i,1} & = & {\rm ROL}(K_i,1) \\
KL_{i,2} & = & K'_{i+2} \\
KO_{i,1} & = & {\rm ROL}(K_{i+1},5) \\
KO_{i,2} & = & {\rm ROL}(K_{i+5},8) \\
KO_{i,3} & = & {\rm ROL}(K_{i+6},13) \\
KI_{i,1} & = & K'_{i+4} \\
KI_{i,2} & = & K'_{i+3} \\
KI_{i,3} & = & K'_{i+7}
\end{array}
</math>

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 algorithm===
KASUMI algorithm processes the 64-bit word in two 32-bit halves, left (<math>L_i</math>)
and right (<math>R_i</math>).
The input word is concatenation of the left and right halves of the first round:

<math>{\rm input} = R_0\|L_0\,</math>.

In each round the right half is XOR'ed with the output of the round function
after which the halves are swapped:

<math>\begin{array}{rcl}L_i & = & F_i(KL_i,KO_i,KI_i,L_{i-1})\oplus R_{i-1} \\ R_i & = & L_{i-1}\end{array}</math>

where ''KLi'', ''KOi'', ''KIi'' 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 ''FLi'' and ''FOi''.
For an odd round

<math>F_i(K_i,L_{i-1})=FO(KO_i, KI_i, FL(KL_i, L_{i-1}))\,</math>

and for an even round

<math>F_i(K_i,L_{i-1})=FL(KL_i, FO(KO_i, KI_i, L_{i-1}))\,</math>.

The output is the concatenation of the outputs of the last round.

<math>{\rm output} = R_8\|L_8\,</math>.

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.

====Function FL====

The 32-bit input ''x'' of <math>FL(KL_i,x)</math> is divided to two 16-bit halves <math>x=l\|r</math>.
First the left half of the input <math>l</math> is ANDed bitwise with round key <math>KL_{i,1}</math> and rotated
left by one bit. The result of that is XOR'ed to the right half of the input <math>r</math> to get the right
half of the output <math>r'</math>.

<math>r'= {\rm ROL}(l \wedge KL_{i,1},1) \oplus r</math>

Then the right half of the output <math>r'</math> is ORed bitwise with the round key <math>KL_{i,2}</math> and rotated
left by one bit. The result of that is XOR'ed to the left half of the input <math>l</math> to get the left
half of the output <math>l'</math>.

<math>l'= {\rm ROL}(r' \vee KL_{i,2},1) \oplus l</math>

Output of the function is concatenation of the left and right halves <math>x'=l'\|r'</math>.

====Function FO====

The 32-bit input ''x'' of <math>FO(KO_i, KI_i, x)</math> is divided into two 16-bit halves <math>x=l_0\|r_0</math>, and passed through three rounds of a Feistel network.

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.

<math>
\begin{array}{lcl}
r_j & = & FI(KI_{i,j}, l_{j-1} \oplus KO_{i,j}) \oplus r_{j-1} \\
l_j & = & r_{j-1}
\end{array}
</math>

The output of the function is <math>x' = l_3\|r_3</math>.

====Function FI====
The function ''FI'' is an irregular Feistel-like network.

The 16-bit input <math>x</math> of the function <math>FI(KI,x)</math> is divided to two halves <math>x=l_0\|r_0</math>
of which <math>l_0</math> is 9 bits wide and <math>r_0</math> is 7 bits wide.

Bits in the left half <math>l_0</math> are first shuffled by 9-bit [[substitution box]] (S-box) ''S9'' and the result is XOR'ed with
the zero-extended right half <math>r_0</math> to get the new 9-bit right half <math>r_1</math>.

<math>r_1=S9(l_0)\oplus (00\|r_0)\,</math>

Bits of the right half <math>r_0</math> 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 <math>r_1</math> to get the new 7-bit left half <math>l_1</math>.

<math>l_1=S7(r_0)\oplus LS7(r_1)\,</math>

The intermediate word <math>x_1=l_1\|r_1</math> is XORed with the round key KI to get <math>x_2=l_2\|r_2</math>
of which <math>l_2</math> is 7 bits wide and <math>r_2</math> is 9 bits wide.

<math>x_2=KI\oplus x_1</math>

Bits in the right half <math>r_2</math> are then shuffled by 9-bit S-box ''S9'' and the result is XOR'ed with
the zero-extended left half <math>l_2</math> to get the new 9-bit right half of the output <math>r_3</math>.

<math>r_3=S9(r_2)\oplus (00\|l_2)\,</math>

Finally the bits of the left half <math>l_2</math> 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 <math>r_3</math> to get the 7-bit left
half <math>l_3</math> of the output.

<math>l_3=S7(l_2)\oplus LS7(r_3)\,</math>

The output is the concatenation of the final left and right halves <math>x'=l_3\|r_3</math>.

====Substitution boxes====

The [[substitution box]]es (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.

S7 is defined by the following array:

<source lang="C">
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
};
</source>

S9 is defined by the following array:

<source lang="C">
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
};
</source>

==Cryptanalysis==

In 2001, an [[impossible differential cryptanalysis|impossible differential attack]] on six rounds of KASUMI was presented by Kühn (2001).<ref>{{cite conference
| last=Kühn
| first=Ulrich
| title=Cryptanalysis of Reduced Round MISTY
| conference=EUROCRYPT 2001
| url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.7609
}}</ref>

In 2003 Elad Barkan, [[Eli Biham]] and Nathan Keller demonstrated [[man-in-the-middle attack]]s against the [[GSM]] protocol which avoided the A5/3 cipher and thus breaking the protocol. This approach does not attack the A5/3 cipher, however.<ref>{{cite conference
| author=Elad Barkan, [[Eli Biham]], Nathan Keller
| title=Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication
| pages=600–616
| conference=CRYPTO 2003
| url=http://cryptome.org/gsm-crack-bbk.pdf
}}</ref> The full version of their paper was published later in 2006.<ref>{{cite web
| url = http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf
| title = Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)
| author = Elad Barkan, [[Eli Biham]], Nathan Keller
}}</ref>

In 2005, Israeli researchers [[Eli Biham]], Orr Dunkelman and Nathan Keller published a [[related-key attack|related-key]] [[boomerang attack|rectangle (boomerang) attack]] on KASUMI that can break all 8 rounds faster than exhaustive search.<ref>{{cite conference
| author=[[Eli Biham]], Orr Dunkelman, Nathan Keller
| title=A Related-Key Rectangle Attack on the Full KASUMI
| pages=443–461
| conference=ASIACRYPT 2005
| url=http://www.ma.huji.ac.il/~nkeller/kasumi.ps
| format=ps
}}</ref>
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 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]].<ref name=a5-3-broken /> 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.

==See also==
* [[A5/1]] and [[A5/2]]
* [[MISTY1]]
* [[SNOW]]

==References==
{{Reflist|30em}}

==External links==
* [http://www.ma.huji.ac.il/~nkeller Nathan Keller's homepage]

{{Cryptography navbox | block}}
{{Mitsubishi Electric}}

{{DEFAULTSORT:Kasumi (Block Cipher)}}
[[Category:Feistel ciphers]]
[[Category:Broken block ciphers]]
[[Category:3GPP standards]]
[[Category:Mitsubishi Electric products, services and standards]]

Localization of a category - Revision history

en>Yobot: /* Localization of categories */WP:CHECKWIKI error fixes using AWB (10093)

en>D.Lazard: /* Introduction and motivation */ Formatting: Adding \quad twice + more common notation for the category of modules