KASUMI

Short description: Block cipher

KASUMIGeneral

Designers| Mitsubishi Electric
Derived from| MISTY1
Cipher detail
Key sizes| 128 bits
Block sizes| 64 bits
Structure| Feistel network
Rounds| 8

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 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.[5]

## Contents

* 1 Description
* 1.1 Key schedule
* 1.2 The algorithm
* 1.2.1 Function FL
* 1.2.2 Function FO
* 1.2.3 Function FI
* 1.2.4 Substitution boxes
* 2 Cryptanalysis
* 3 See also
* 4 References
* 5 External links

## Description

KASUMI algorithm is specified in a 3GPP technical specification.[6] 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:

K=K1‖K2‖K3‖K4‖K5‖K6‖K7‖K8

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).

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:

KLi,1=ROL(Ki,1)KLi,2=K'i+2KOi,1=ROL(Ki+1,5)KOi,2=ROL(Ki+5,8)KOi,3=ROL(Ki+6,13)KIi,1=K'i+4KIi,2=K'i+3KIi,3=K'i+7

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 (Li) and right (Ri). The input word is concatenation of the left and right halves of the first round:

input=R0‖L0.

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

Li=Fi(KLi,KOi,KIi,Li−1)⊕Ri−1Ri=Li−1

where KLi, KOi, KIi are round keys for the ith 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

Fi(Ki,Li−1)=FO(KOi,KIi,FL(KLi,Li−1))

and for an even round

Fi(Ki,Li−1)=FL(KLi,FO(KOi,KIi,Li−1)).

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

output=R8‖L8.

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 FL(KLi,x) is divided to two 16-bit halves x=l‖r. First the left half of the input l is ANDed bitwise with round key KLi,1 and rotated left by one bit. The result of that is XOR'ed to the right half of the input r to get the right half of the output r′.

r′=ROL(l∧KLi,1,1)⊕r

Then the right half of the output r′ is ORed bitwise with the round key KLi,2 and rotated left by one bit. The result of that is XOR'ed to the left half of the input l to get the left half of the output l′.

l′=ROL(r′∨KLi,2,1)⊕l

Output of the function is concatenation of the left and right halves x′=l′‖r′.

#### Function FO

The 32-bit input x of FO(KOi,KIi,x) is divided into two 16-bit halves x=l0‖r0, 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.

rj=FI(KIi,j,lj−1⊕KOi,j)⊕rj−1lj=rj−1

The output of the function is x′=l3‖r3.

#### Function FI

The function FI is an irregular Feistel-like network.

The 16-bit input x of the function FI(Ki,x) is divided to two halves x=l0‖r0 of which l0 is 9 bits wide and r0 is 7 bits wide.

Bits in the left half l0 are first shuffled by 9-bit substitution box (S-box) S9 and the result is XOR'ed with the zero-extended right half r0 to get the new 9-bit right half r1.

r1=S9(l0)⊕(00‖r0)

Bits of the right half r0 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 r1 to get the new 7-bit left half l1.

l1=S7(r0)⊕LS7(r1)

The intermediate word x1=l1‖r1 is XORed with the round key KI to get x2=l2‖r2 of which l2 is 7 bits wide and r2 is 9 bits wide.

x2=KI⊕x1

Bits in the right half r2 are then shuffled by 9-bit S-box S9 and the result is XOR'ed with the zero-extended left half l2 to get the new 9-bit right half of the output r3.

r3=S9(r2)⊕(00‖l2)

Finally the bits of the left half l2 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 r3 to get the 7-bit left half l3 of the output.

l3=S7(l2)⊕LS7(r3)

The output is the concatenation of the final left and right halves x′=l3‖r3.

#### Substitution boxes

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.

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

## Cryptanalysis

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 man-in-the-middle attacks 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.[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 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.

## See also

* A5/1 and A5/2
* SNOW

## References

1. ↑ "Draft Report of SA3 #38". 3GPP. 2005. http://www.3gpp.org/ftp/tsg_sa/TSG_SA/TSGS_28/Docs/pdf/SP-050236.pdf.
2. ↑ 2.0 2.1 "General Report on the Design, Speification and Evaluation of 3GPP Standard Confidentiality and Integrity Algorithms". 3GPP. 2009. http://www.3gpp.org/ftp/tsg_sa/WG3_Security/_Specs/33908-300.pdf.
3. ↑ Matsui, Mitsuru; Tokita, Toshio (Dec 2000). "MISTY, KASUMI and Camellia Cipher Algorithm Development". Mitsubishi Electric Advance (Mitsubishi Electric corp.) 100: 2-8. ISSN 1345-3041. http://global.mitsubishielectric.com/company/rd/advance/pdf/vol100/vol100.pdf. Retrieved 2010-01-06.
4. ↑ Matsui, Mitsuru & Toshio Tokita, "Data Transformation Apparatus and Data Transformation Method", US patent 7096369, published Sep. 19, 2002, issued Aug. 22, 2006
5. ↑ 5.0 5.1 Orr Dunkelman; Nathan Keller; Adi Shamir (2010-01-10). A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony. http://eprint.iacr.org/2010/013.
6. ↑ "3GPP TS 35.202: Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification". 3GPP. 2009. http://www.3gpp.org/ftp/Specs/html-info/35202.htm.
7. ↑ Kühn, Ulrich. "Cryptanalysis of Reduced Round MISTY". EUROCRYPT 2001.
8. ↑ Elad Barkan, Eli Biham, Nathan Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication". CRYPTO 2003. pp. 600–616. https://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf. Retrieved 2019-09-15.
9. ↑ Elad Barkan, Eli Biham, Nathan Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)". https://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf.
10. ↑ Eli Biham, Orr Dunkelman, Nathan Keller. "A Related-Key Rectangle Attack on the Full KASUMI" (ps). ASIACRYPT 2005. pp. 443–461. http://www.ma.huji.ac.il/~nkeller/kasumi.ps.

## External links

* Nathan Keller's homepage

* v
* t
* e

Block ciphers (security summary)

Common
algorithms|

* AES
* Blowfish
* DES (internal mechanics, Triple DES)
* Serpent
* Twofish

Less common
algorithms|

* Camellia
* CAST-128
* GOST
* IDEA
* RC2
* RC5
* RC6
* SEED
* ARIA
* Skipjack
* TEA
* XTEA

Other
algorithms|

* 3-Way
* Akelarre
* Anubis
* BaseKing
* BassOmatic
* BATON
* BEAR and LION
* CAST-256
* Chiasmus
* CIKS-1
* CIPHERUNICORN-A
* CIPHERUNICORN-E
* CLEFIA
* CMEA
* Cobra
* COCONUT98
* Crab
* Cryptomeria/C2
* CRYPTON
* CS-Cipher
* DEAL
* DES-X
* DFC
* E2
* FEAL
* FEA-M
* FROG
* G-DES
* Grand Cru
* Hasty Pudding cipher
* Hierocrypt
* ICE
* IDEA NXT
* Intel Cascade Cipher
* Iraqi
* Kalyna
* KASUMI
* KeeLoq
* KHAZAD
* Khufu and Khafre
* KN-Cipher
* Kuznyechik
* Ladder-DES
* Libelle
* LOKI (97, 89/91)
* Lucifer
* M6
* M8
* MacGuffin
* Madryga
* MAGENTA
* MARS
* Mercy
* MESH
* MISTY1
* MMB
* MULTI2
* MultiSwap
* New Data Seal
* NewDES
* Nimbus
* NOEKEON
* NUSH
* PRESENT
* Prince
* Q
* RC6
* REDOC
* Red Pike
* S-1
* SAFER
* SAVILLE
* SC2000
* SHACAL
* SHARK
* Simon
* SM4
* Speck
* Spectr-H64
* Square
* SXAL/MBAL
* Threefish
* Treyfer
* UES
* xmx
* XXTEA
* Zodiac

Design|

* Feistel network
* Key schedule
* Lai–Massey scheme
* Product cipher
* S-box
* P-box
* SPN
* Confusion and diffusion
* Avalanche effect
* Block size
* Key size
* Key whitening (Whitening transformation)

Attack
(cryptanalysis)|

* Brute-force (EFF DES cracker)
* MITM
* Biclique attack
* 3-subset MITM attack
* Linear (Piling-up lemma)
* Differential
* Impossible
* Truncated
* Higher-order
* Differential-linear
* Distinguishing (Known-key)
* Integral/Square
* Boomerang
* Mod n
* Related-key
* Slide
* Rotational
* Side-channel
* Timing
* Power-monitoring
* Electromagnetic
* Acoustic
* Differential-fault
* XSL
* Interpolation
* Partitioning
* Rubber-hose
* Black-bag
* Davies
* Rebound
* Weak key
* Tau
* Chi-square
* Time/memory/data tradeoff

Standardization|

* AES process
* CRYPTREC
* NESSIE

Utilization|

* Initialization vector
* Mode of operation
* Padding

* v
* t
* e

Cryptography

* History of cryptography
* Cryptanalysis
* Outline of cryptography

* Symmetric-key algorithm
* Block cipher
* Stream cipher
* Public-key cryptography
* Cryptographic hash function
* Message authentication code
* Random numbers
* Steganography

* Category

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/KASUMI. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=KASUMI&oldid=279640"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template