KASUMI

У этого термина существуют и другие значения, см. KASUMI (значения).

KASUMI
Создатель:	ETSI
Создан:	1999 год
Опубликован:	1999 год
Размер ключа:	128 бит
Размер блока:	64 бит
Число раундов:	8
Тип:	модификация сети Фейстеля

KASUMI (от японск.霞 (hiragana かすみ, romaji kasumi) — туман, mist) — блочный шифр, использующийся в сетях сотовой связи 3GPP. Также обозначается A5/3 при использовании в GSM и GEA3 в GPRS.

KASUMI разработан группой SAGE (Security Algorithms Group of Experts), которая является частью Европейского Института по Стандартизации в области Телекоммуникаций (ETSI)^[1]. За основу был взят существующий алгоритм MISTY1 и оптимизирован для использования в сотовой связи.

Описание

KASUMI использует 64-битный размер блока и 128-битный ключ в 8-раундовой схеме Фейстеля. В каждом раунде используется 128-битный раундовый ключ, состоящий из восьми 16-битных подключей, полученных из исходного ключа по фиксированной процедуре генерации подключей.

Схема шифрования

Основной алгоритм

KASUMI разлагается в набор функций (FL, FO, FI), которые используются вместе со связанными с ними ключами (KL, KO, KI)

Входной блок данных I разделяется на две равные части:

$~I = L_0 || R_0$

Затем для каждого $~1 \le i \le 8$:

$~R_{i} = L_{i-1}$

$~L_i = R_{i-1} \oplus f_i(L_{i-1}, RK_i)$

где $~f_i$ — раундовая функция. $~RK_i$ — раундовый 128-битный ключ

$~RK_i = KL_i || KO_i || KI_i$

На выходе $~(L_8 || R_8)$

Функция раунда

Вычисляется следующим образом:

Для раундов 1,3,5,7:

$~f_i(I, RK_i) = FO( FL( I, KL_i), KO_i, KI_i )$

Для раундов 2,4,6,8:

$~f_i(I, RK_i) = FL( FO( I, KO_i, KI_i ), KL_i )$

Функция FL

На вход функции подается 32-битный блок данных I и 32-битный ключ KL_i, который разделяется на два 16-битных подключа:

$~KL_i = KL_{i,1} || KL_{i,2}$.

Входная строка I разделяется на две части по 16 бит:

$~I = L || R$.

Определим:

$~R' = R \oplus ROL ( L \cap KL_{i,1})$

$~L' = L \oplus ROL ( R' \vee KL_{i,2})$

Где $~ROL(x)$ — циклический сдвиг влево на 1 бит.

На выходе $~(L' || R')$.

Функция FO

На вход функции подается 32-битный блок данных и два ключа по 48 бит: $~KO_i, KI_i$.

Входная строка I разделяется на две части по 16 бит: $~I = L_0 || R_0$.

48-битные ключи разделяются на три части каждый:

$~KO_i = KO_{i,1} || KO_{i,2} || KO_{i,3}$ и $~KI_i = KI_{i,1} || KI_{i,2} || KI_{i,3}$.

Затем для $~1 < j \le 3$ определим:

$~R_j = FI(L_{j-1} \oplus KO_{i,j} , KI_{i,j} ) \oplus R_{j-1}$

$~L_j = R_{j-1}$

На выходе $~(L_3 || R_3)$.

Функция FI

На вход функции подается 16-битный блок данных I и 16-битный ключ KI_{i, j}.

Вход I разделяется на две неравные составляющие: 9-битную левую часть L₀ и 7-битную правую R₀:

$~I = L_0 || R_0$.

Точно так же ключ KI_{i, j,} разделяется на 7-битную компоненту KI_{i, j,1} и 9-битную компоненту KI_{i, j,2}:

$~KI_{i,j} = KI_{i,j,1} || KI_{i,j,2}$.

Функция использует два S-блока: S7 который отображает 7-битный вход в 7-битный выход, и S9 который отображает 9-битный вход в 9-битный выход.

Также используются еще две функции:

$~ZE(x)$ Преобразует 7-битное значение x в 9-битное значение добавлением двух нулей в старшие биты.

$~TR(x)$ Преобразует 9-битное значение x в 7-битное вычеркиванием из него двух старших битов.

Функция реализуется следующим набором операций:

$~L_1 = R_0~~~~~~~~~~~~~~~~~~~~~~~~~ R_1 = S9[L_0] \oplus ZE(R_0)$

$~L_2 = R_1 \oplus KI_{i,j,2} ~~~~~~~~~~~~~R_2 = S7[L_1] \oplus TR(R_1) \oplus KI_{i,j,1}$

$~L_3 = R_2~~~~~~~~~~~~~~~~~~~~~~~~~ R_3 = S9[L_2] \oplus ZE(R_2)$

$~L_4 = S7[L_3] \oplus TR(R_3) ~~~~~~ R_4 = R_3$

Функция возвращает значение $~(L_4 || R_4)$.

S-блоки

S-блоки преобразуют 7 или 9 битный входной блок в соответственно 7 или 9 битный выходной блок, используя таблицы подстановок

Например: S7[30] = 124

Десятичная таблица замены для блока S7:

S7[0-15]	54	50	62	56	22	34	94	96	38	6	63	93	2	18	123	33
S7[16-31]	55	113	39	114	21	67	65	12	47	73	46	27	25	111	124	81
S7[32-47]	53	9	121	79	52	60	58	48	101	127	40	120	104	70	71	43
S7[48-63]	20	122	72	61	23	109	13	100	77	1	16	7	82	10	105	98
S7[64-79]	117	116	76	11	89	106	0	125	118	99	86	69	30	57	126	87
S7[80-95]	112	51	17	5	95	14	90	84	91	8	35	103	32	97	28	66
S7[96-111]	102	31	26	45	75	4	85	92	37	74	80	49	68	29	115	44
S7[112-127]	64	107	108	24	110	83	36	78	42	19	15	41	88	119	59	3

Десятичная таблица замены для блока S9:

S9[0-15]	167	239	161	379	391	334	9	338	38	226	48	358	452	385	90	397
S9[16-31]	183	253	147	331	415	340	51	362	306	500	262	82	216	159	356	177
S9[32-47]	175	241	489	37	206	17	0	333	44	254	378	58	143	220	81	400
S9[48-63]	95	3	315	245	54	235	218	405	472	264	172	494	371	290	399	76
S9[64-79]	165	197	395	121	257	480	423	212	240	28	462	176	406	507	288	223
S9[80-95]	501	407	249	265	89	186	221	428	164	74	440	196	458	421	350	163
S9[96-111]	232	158	134	354	13	250	491	142	191	69	193	425	152	227	366	135
S9[112-127]	344	300	276	242	437	320	113	278	11	243	87	317	36	93	496	27
S9[128-143]	487	446	482	41	68	156	457	131	326	403	339	20	39	115	442	124
S9[144-159]	475	384	508	53	112	170	479	151	126	169	73	268	279	321	168	364
S9[160-175]	363	292	46	499	393	327	324	24	456	267	157	460	488	426	309	229
S9[176-191]	439	506	208	271	349	401	434	236	16	209	359	52	56	120	199	277
S9[192-207]	465	416	252	287	246	6	83	305	420	345	153	502	65	61	244	282
S9[208-223]	173	222	418	67	386	368	261	101	476	291	195	430	49	79	166	330
S9[224-239]	280	383	373	128	382	408	155	495	367	388	274	107	459	417	62	454
S9[240-255]	132	225	203	316	234	14	301	91	503	286	424	211	347	307	140	374
S9[256-271]	35	103	125	427	19	214	453	146	498	314	444	230	256	329	198	285
S9[272-287]	50	116	78	410	10	205	510	171	231	45	139	467	29	86	505	32
S9[288-303]	72	26	342	150	313	490	431	238	411	325	149	473	40	119	174	355
S9[304-319]	185	233	389	71	448	273	372	55	110	178	322	12	469	392	369	190
S9[320-335]	1	109	375	137	181	88	75	308	260	484	98	272	370	275	412	111
S9[336-351]	336	318	4	504	492	259	304	77	337	435	21	357	303	332	483	18
S9[352-367]	47	85	25	497	474	289	100	269	296	478	270	106	31	104	433	84
S9[368-383]	414	486	394	96	99	154	511	148	413	361	409	255	162	215	302	201
S9[384-399]	266	351	343	144	441	365	108	298	251	34	182	509	138	210	335	133
S9[400-415]	311	352	328	141	396	346	123	319	450	281	429	228	443	481	92	404
S9[416-431]	485	422	248	297	23	213	130	466	22	217	283	70	294	360	419	127
S9[432-447]	312	377	7	468	194	2	117	295	463	258	224	447	247	187	80	398
S9[448-463]	284	353	105	390	299	471	470	184	57	200	348	63	204	188	33	451
S9[464-479]	97	30	310	219	94	160	129	493	64	179	263	102	189	207	114	402
S9[480-495]	438	477	387	122	192	42	381	5	145	118	180	449	293	323	136	380
S9[496-511]	43	66	60	455	341	445	202	432	8	237	15	376	436	464	59	461

Получение раундовых ключей

Каждый раунд KASUMI получает ключи из общего ключа K следующим образом:

• 128-битный ключ K разделяется на 8:

$~K = K_1 || K_2 || K_3 || \dots || K_8$

• Вычисляется второй массив K_j:

$~K_{j'} = K_j \oplus C_j$

где C_j определяются по таблице:

C1	0x0123
С2	0x4567
С3	0x89AB
С4	0xCDEF
С5	0xFEDC
С6	0xBA98
С7	0x7654
С8	0x3210

• Ключи для каждого раунда вычисляются по следующей таблице:

Ключ	1	2	3	4	5	6	7	8
$~KL_{i,1}$	K1<<<1	K2<<<1	K3<<<1	K4<<<1	K5<<<1	K6<<<1	K7<<<1	K8<<<1
$~KL_{i,2}$	K3'	K4'	K5'	K6'	K7'	K8'	K1'	K2'
$~KO_{i,1}$	K2<<<5	K3<<<5	K4<<<5	K5<<<5	K6<<<5	K7<<<5	K8<<<5	K1<<<5
$~KO_{i,2}$	K6<<<8	K7<<<8	K8<<<8	K1<<<8	K2<<<8	K3<<<8	K4<<<8	K5<<<8
$~KO_{i,3}$	K7<<<13	K8<<<13	K1<<<13	K2<<<13	K3<<<13	K4<<<13	K5<<<13	K6<<<13
$~KI_{i,1}$	K5'	K6'	K7'	K8'	K1'	K2'	K3'	K4'
$~KI_{i,2}$	K4'	K5'	K6'	K7'	K8'	K1'	K2'	K3'
$~KI_{i,3}$	K8'	K1'	K2'	K3'	K4'	K5'	K6'	K7'

где X<<<n — циклический сдвиг на n бит влево.

Криптоанализ

В 2001 году была представлена атака методом невозможных дифференциалов. Автор - Ульрих Кён (2001).^[2]

В 2003 году Элад Баркан, Эли Бихам и Натан Келлер продемонстрировали атаку с посредником на протокол GSM, что позволяет обойти шифр A5/3 и таким образом сломать протокол. Однако, этот подход не взламывает шифр A5/3 напрямую.^[3] Полная версия была опубликована позже, в 2006.^[4]

В 2005 году Эли Бихам, Орр Дункельман и Натан Келлер опубликовали атаку на KASUMI методом бумеранга, которая взламывает шифр быстрее, чем полный перебор.^[2] Для атаки требуется $2^{54.6}$ выбранных открытых текстов, каждый из которых был зашифрован одним из 4 связанных ключей, и имеет сложность по времени, эквивалентную $2^{76.1}$ шифрованиям KASUMI. Эта атака показывает небезопасность шифрования KASUMI в 3G сетях.

Примечания

1. ↑ (англ) Universal Mobile Telecommunications System (UMTS); Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification. ETSI (2007). Архивировано из первоисточника 11 апреля 2012.
2. ↑ ^{1 2}  (англ.) Eli Biham, Orr Dunkelman, Nathan Keller. "A Related-Key Rectangle Attack on the Full KASUMI" (ps) in ASIACRYPT 2005.: 443-461. 
3. ↑ (англ) Elad Barkan, Eli Biham, Nathan Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication" in CRYPTO 2003.: 600-616. 
4. ↑ (англ) Elad Barkan, Eli Biham, Nathan Keller Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version). Архивировано из первоисточника 11 апреля 2012.