KASUMI

KASUMI (от японск.霞 (hiragana かすみ, romaji kasumi) — туман, mist) — блочный шифр, использующийся в сетях сотовой связи. В UMTS используется в криптографических функциях f8 и f9, в GSM используется в алгоритме A5/3, а в GPRS — в алгоритме GEA/3, причем два последних используют шифр KASUMI с ключом длины 64 бита.

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

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

Как показали в 2010 году криптоаналитики, в процессе изменений надежность алгоритма MISTY1 была снижена: KASUMI имеет уязвимости для некоторых типов атак, тогда как MISTY1 является стойким по отношению к ним.

Описание

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

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

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

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

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

$I=L_{0}||R_{0}$

Затем для каждого $1\leq i\leq 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\leq j\leq 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).

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

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

В январе 2010 Orr Dunkelman, Nathan Keller и Ади Шамир опубликовали работу, в которой показали уязвимость Kasumi для атаки на основе связанных ключей (Related-key attack). Злоумышленник может восстановить полный ключ A5/3 с использованием незначительного количества вычислительных ресурсов (авторы оценивают их в 2²⁶ по данным, 2³⁰ по памяти и 2³² по времени и смогли реализовать её за 2 часа работы современного персонального компьютера). Авторы также отметили, что атака может быть не применима к тому способу, каким KASUMI используется в сетях 3G. Разработанная ими атака также не применима к оригинальному MISTY, и они ставят под сомнение заявления 3GPP о том, что при создании KASUMI не была снижена защищенность алгоритма.