KASUMI

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

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

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

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

ОписаниеПравить

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

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

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

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

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

\text{[math]}

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

Затем для каждого $\text{[math]}$ $\text{[math]}$ $1\leq i\leq 8$ :

\text{[math]}

R_{i}=L_{i-1}

\text{[math]}

L_{i}=R_{i-1}\oplus f_{i}(L_{i-1},RK_{i})

где $\text{[math]}$ $\text{[math]}$ $f_{i}$ — раундовая функция. $\text{[math]}$ $\text{[math]}$ $RK_{i}$ — раундовый 128-битный ключ

\text{[math]}

RK_{i}=KL_{i}||KO_{i}||KI_{i}

На выходе $\text{[math]}$ $\text{[math]}$ $(L_{8}||R_{8})$

Функция раундаПравить

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

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

\text{[math]}

f_{i}(I,RK_{i})=FO(FL(I,KL_{i}),KO_{i},KI_{i})

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

\text{[math]}

f_{i}(I,RK_{i})=FL(FO(I,KO_{i},KI_{i}),KL_{i})

Функция FLПравить

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

\text{[math]}

KL_{i}=KL_{i,1}||KL_{i,2}

.

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

\text{[math]}

I=L||R

.

Определим:

\text{[math]}

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

\text{[math]}

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

Где $\text{[math]}$ $\text{[math]}$ $ROL(x)$ — циклический сдвиг влево на 1 бит.

На выходе $\text{[math]}$ $\text{[math]}$ $(L'||R')$ .

Функция FOПравить

На вход функции подается 32-битный блок данных и два ключа по 48 бит: $\text{[math]}$ $\text{[math]}$ $KO_{i},KI_{i}$ .

Входная строка I разделяется на две части по 16 бит: $\text{[math]}$ $\text{[math]}$ $I=L_{0}||R_{0}$ .

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

\text{[math]}

KO_{i}=KO_{i,1}||KO_{i,2}||KO_{i,3}

и

\text{[math]}

KI_{i}=KI_{i,1}||KI_{i,2}||KI_{i,3}

.

Затем для $\text{[math]}$ $\text{[math]}$ $1\leq j\leq 3$ определим:

\text{[math]}

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

\text{[math]}

L_{j}=R_{j-1}

На выходе $\text{[math]}$ $\text{[math]}$ $(L_{3}||R_{3})$ .

Функция FIПравить

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

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

\text{[math]}

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

.

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

\text{[math]}

KI_{i,j}=KI_{i,j,1}||KI_{i,j,2}

.

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

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

\text{[math]}

ZE(x)

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

\text{[math]}

TR(x)

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

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

\text{[math]}

L_{1}=R_{0}~~~~~~~~~~~~~~~~~~~~~~~~~R_{1}=S9[L_{0}]\oplus ZE(R_{0})

\text{[math]}

L_{2}=R_{1}\oplus KI_{i,j,2}~~~~~~~~~~~~~R_{2}=S7[L_{1}]\oplus TR(R_{1})\oplus KI_{i,j,1}

\text{[math]}

L_{3}=R_{2}~~~~~~~~~~~~~~~~~~~~~~~~~R_{3}=S9[L_{2}]\oplus ZE(R_{2})

\text{[math]}

L_{4}=S7[L_{3}]\oplus TR(R_{3})~~~~~~R_{4}=R_{3}

Функция возвращает значение $\text{[math]}$ $\text{[math]}$ $(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:

\text{[math]}

K=K_{1}||K_{2}||K_{3}||\dots ||K_{8}

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

\text{[math]}

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
$\text{[math]}$ $\text{[math]}$ $KL_{i,1}$	K1<<<1	K2<<<1	K3<<<1	K4<<<1	K5<<<1	K6<<<1	K7<<<1	K8<<<1
$\text{[math]}$ $\text{[math]}$ $KL_{i,2}$	K3'	K4'	K5'	K6'	K7'	K8'	K1'	K2'
$\text{[math]}$ $\text{[math]}$ $KO_{i,1}$	K2<<<5	K3<<<5	K4<<<5	K5<<<5	K6<<<5	K7<<<5	K8<<<5	K1<<<5
$\text{[math]}$ $\text{[math]}$ $KO_{i,2}$	K6<<<8	K7<<<8	K8<<<8	K1<<<8	K2<<<8	K3<<<8	K4<<<8	K5<<<8
$\text{[math]}$ $\text{[math]}$ $KO_{i,3}$	K7<<<13	K8<<<13	K1<<<13	K2<<<13	K3<<<13	K4<<<13	K5<<<13	K6<<<13
$\text{[math]}$ $\text{[math]}$ $KI_{i,1}$	K5'	K6'	K7'	K8'	K1'	K2'	K3'	K4'
$\text{[math]}$ $\text{[math]}$ $KI_{i,2}$	K4'	K5'	K6'	K7'	K8'	K1'	K2'	K3'
$\text{[math]}$ $\text{[math]}$ $KI_{i,3}$	K8'	K1'	K2'	K3'	K4'	K5'	K6'	K7'

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

КриптоанализПравить

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

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

В 2005 году Эли Бихам, Орр Дункельман и Натан Келлер опубликовали атаку на KASUMI методом бумеранга, которая взламывает шифр быстрее, чем полный перебор.^[3] Для атаки требуется $\text{[math]}$ $\text{[math]}$ $2^{54.6}$ выбранных открытых текстов, каждый из которых был зашифрован одним из 4 связанных ключей, и имеет сложность по времени, эквивалентную $\text{[math]}$ $\text{[math]}$ $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 не была снижена защищенность алгоритма.^[2]

ПримечанияПравить

↑ (англ) Universal Mobile Telecommunications System (UMTS); Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification (неопр.). ETSI (2007). Архивировано 11 апреля 2012 года.
↑ ¹ ² * Orr Dunkelman, Nathan Keller, Adi Shamir. A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony (англ.) // International Association for Cryptologic Research Eprint archive : journal. — 2010. — 10 January. Архивировано 3 февраля 2013 года.
- A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony // CRYPTO 2010, Lecture Notes in Computer Science Volume 6223, 2010, pp 393-410 doi:10.1007/978-3-642-14623-7 21
↑ ¹ ² (англ.) Eli Biham, Orr Dunkelman, Nathan Keller. A Related-Key Rectangle Attack on the Full KASUMI. ASIACRYPT 2005. pp. 443–461. Архивировано из оригинала (ps) 2013-10-11. Дата обращения 2009-11-27. Архивная копия от 11 октября 2013 на Wayback Machine
↑ (англ) Elad Barkan, Eli Biham, Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (PDF). CRYPTO 2003. pp. 600–616. Архивировано из оригинала (PDF) 2005-12-16. Используется устаревший параметр |deadlink= (справка); Параметры |deadurl= и |deadlink= дублируют друг друга (справка); Некорректное значение |dead-url=404 (справка) Архивная копия от 16 декабря 2005 на Wayback Machine
↑ (англ) Elad Barkan, Eli Biham, Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version) (неопр.). Архивировано 11 апреля 2012 года.

[1] (англ) Universal Mobile Telecommunications System (UMTS); Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification (неопр.). ETSI (2007). Архивировано 11 апреля 2012 года.

[a5-3-broken-2] ¹ ² * Orr Dunkelman, Nathan Keller, Adi Shamir. A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony (англ.) // International Association for Cryptologic Research Eprint archive : journal. — 2010. — 10 January. Архивировано 3 февраля 2013 года.
A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony // CRYPTO 2010, Lecture Notes in Computer Science Volume 6223, 2010, pp 393-410 doi:10.1007/978-3-642-14623-7 21

[3] A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony // CRYPTO 2010, Lecture Notes in Computer Science Volume 6223, 2010, pp 393-410 doi:10.1007/978-3-642-14623-7 21

[huji-3] ¹ ² (англ.) Eli Biham, Orr Dunkelman, Nathan Keller. A Related-Key Rectangle Attack on the Full KASUMI. ASIACRYPT 2005. pp. 443–461. Архивировано из оригинала (ps) 2013-10-11. Дата обращения 2009-11-27. Архивная копия от 11 октября 2013 на Wayback Machine

[4] (англ) Elad Barkan, Eli Biham, Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (PDF). CRYPTO 2003. pp. 600–616. Архивировано из оригинала (PDF) 2005-12-16. Используется устаревший параметр |deadlink= (справка); Параметры |deadurl= и |deadlink= дублируют друг друга (справка); Некорректное значение |dead-url=404 (справка) Архивная копия от 16 декабря 2005 на Wayback Machine

[5] (англ) Elad Barkan, Eli Biham, Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version) (неопр.). Архивировано 11 апреля 2012 года.

[1]

[2]

[3]

[4]

[5]