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). За основу был взят существующий алгоритм MISTY1 и оптимизирован для использования в сотовой связи.

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

Описание

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

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

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

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

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

<math>I = L_0 || R_0</math>

Затем для каждого <math>1 \le i \le 8</math>:

<math>R_{i} = L_{i-1}</math>

<math>L_i = R_{i-1} \oplus f_i(L_{i-1}, RK_i)</math>

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

<math>RK_i = KL_i || KO_i || KI_i</math>

На выходе <math>(L_8 || R_8)</math>

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

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

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

<math>f_i(I, RK_i) = FO( FL( I, KL_i), KO_i, KI_i )</math>

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

<math>f_i(I, RK_i) = FL( FO( I, KO_i, KI_i ), KL_i )</math>

Функция FL

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

<math>KL_i = KL_{i,1} || KL_{i,2}</math>.

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

<math>I = L || R</math>.

Определим:

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

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

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

На выходе <math>(L' || R')</math>.

Функция FO

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

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

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

<math>KO_i = KO_{i,1} || KO_{i,2} || KO_{i,3}</math> и <math>KI_i = KI_{i,1} || KI_{i,2} || KI_{i,3}</math>.

Затем для <math>1 \le j \le 3</math> определим:

<math>R_j = FI(L_{j-1} \oplus KO_{i,j} , KI_{i,j} ) \oplus R_{j-1}</math>

<math>L_j = R_{j-1}</math>

На выходе <math>(L_3 || R_3)</math>.

Функция FI

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

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

<math>I = L_0 || R_0</math>.

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

<math>KI_{i,j} = KI_{i,j,1} || KI_{i,j,2}</math>.

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

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

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

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

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

<math>L_1 = R_0~~~~~~~~~~~~~~~~~~~~~~~~~ R_1 = S9[L_0] \oplus ZE(R_0)</math>

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

<math>L_3 = R_2~~~~~~~~~~~~~~~~~~~~~~~~~ R_3 = S9[L_2] \oplus ZE(R_2)</math>

<math>L_4 = S7[L_3] \oplus TR(R_3) ~~~~~~ R_4 = R_3</math>

Функция возвращает значение <math>(L_4 || R_4)</math>.

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:

<math>K = K_1 || K_2 || K_3 || \dots || K_8</math>

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

<math>K_{j'} = K_j \oplus C_j</math>

где 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
<math>KL_{i,1}</math>	K1<<<1	K2<<<1	K3<<<1	K4<<<1	K5<<<1	K6<<<1	K7<<<1	K8<<<1
<math>KL_{i,2}</math>	K3'	K4'	K5'	K6'	K7'	K8'	K1'	K2'
<math>KO_{i,1}</math>	K2<<<5	K3<<<5	K4<<<5	K5<<<5	K6<<<5	K7<<<5	K8<<<5	K1<<<5
<math>KO_{i,2}</math>	K6<<<8	K7<<<8	K8<<<8	K1<<<8	K2<<<8	K3<<<8	K4<<<8	K5<<<8
<math>KO_{i,3}</math>	K7<<<13	K8<<<13	K1<<<13	K2<<<13	K3<<<13	K4<<<13	K5<<<13	K6<<<13
<math>KI_{i,1}</math>	K5'	K6'	K7'	K8'	K1'	K2'	K3'	K4'
<math>KI_{i,2}</math>	K4'	K5'	K6'	K7'	K8'	K1'	K2'	K3'
<math>KI_{i,3}</math>	K8'	K1'	K2'	K3'	K4'	K5'	K6'	K7'

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

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

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

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

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

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

Отрывок, характеризующий KASUMI

Участие Ростова в дуэли Долохова с Безуховым было замято стараниями старого графа, и Ростов вместо того, чтобы быть разжалованным, как он ожидал, был определен адъютантом к московскому генерал губернатору. Вследствие этого он не мог ехать в деревню со всем семейством, а оставался при своей новой должности всё лето в Москве. Долохов выздоровел, и Ростов особенно сдружился с ним в это время его выздоровления. Долохов больной лежал у матери, страстно и нежно любившей его. Старушка Марья Ивановна, полюбившая Ростова за его дружбу к Феде, часто говорила ему про своего сына.
– Да, граф, он слишком благороден и чист душою, – говаривала она, – для нашего нынешнего, развращенного света. Добродетели никто не любит, она всем глаза колет. Ну скажите, граф, справедливо это, честно это со стороны Безухова? А Федя по своему благородству любил его, и теперь никогда ничего дурного про него не говорит. В Петербурге эти шалости с квартальным там что то шутили, ведь они вместе делали? Что ж, Безухову ничего, а Федя все на своих плечах перенес! Ведь что он перенес! Положим, возвратили, да ведь как же и не возвратить? Я думаю таких, как он, храбрецов и сынов отечества не много там было. Что ж теперь – эта дуэль! Есть ли чувство, честь у этих людей! Зная, что он единственный сын, вызвать на дуэль и стрелять так прямо! Хорошо, что Бог помиловал нас. И за что же? Ну кто же в наше время не имеет интриги? Что ж, коли он так ревнив? Я понимаю, ведь он прежде мог дать почувствовать, а то год ведь продолжалось. И что же, вызвал на дуэль, полагая, что Федя не будет драться, потому что он ему должен. Какая низость! Какая гадость! Я знаю, вы Федю поняли, мой милый граф, оттого то я вас душой люблю, верьте мне. Его редкие понимают. Это такая высокая, небесная душа!
Сам Долохов часто во время своего выздоровления говорил Ростову такие слова, которых никак нельзя было ожидать от него. – Меня считают злым человеком, я знаю, – говаривал он, – и пускай. Я никого знать не хочу кроме тех, кого люблю; но кого я люблю, того люблю так, что жизнь отдам, а остальных передавлю всех, коли станут на дороге. У меня есть обожаемая, неоцененная мать, два три друга, ты в том числе, а на остальных я обращаю внимание только на столько, на сколько они полезны или вредны. И все почти вредны, в особенности женщины. Да, душа моя, – продолжал он, – мужчин я встречал любящих, благородных, возвышенных; но женщин, кроме продажных тварей – графинь или кухарок, всё равно – я не встречал еще. Я не встречал еще той небесной чистоты, преданности, которых я ищу в женщине. Ежели бы я нашел такую женщину, я бы жизнь отдал за нее. А эти!… – Он сделал презрительный жест. – И веришь ли мне, ежели я еще дорожу жизнью, то дорожу только потому, что надеюсь еще встретить такое небесное существо, которое бы возродило, очистило и возвысило меня. Но ты не понимаешь этого.
– Нет, я очень понимаю, – отвечал Ростов, находившийся под влиянием своего нового друга.

Осенью семейство Ростовых вернулось в Москву. В начале зимы вернулся и Денисов и остановился у Ростовых. Это первое время зимы 1806 года, проведенное Николаем Ростовым в Москве, было одно из самых счастливых и веселых для него и для всего его семейства. Николай привлек с собой в дом родителей много молодых людей. Вера была двадцати летняя, красивая девица; Соня шестнадцати летняя девушка во всей прелести только что распустившегося цветка; Наташа полу барышня, полу девочка, то детски смешная, то девически обворожительная.
В доме Ростовых завелась в это время какая то особенная атмосфера любовности, как это бывает в доме, где очень милые и очень молодые девушки. Всякий молодой человек, приезжавший в дом Ростовых, глядя на эти молодые, восприимчивые, чему то (вероятно своему счастию) улыбающиеся, девические лица, на эту оживленную беготню, слушая этот непоследовательный, но ласковый ко всем, на всё готовый, исполненный надежды лепет женской молодежи, слушая эти непоследовательные звуки, то пенья, то музыки, испытывал одно и то же чувство готовности к любви и ожидания счастья, которое испытывала и сама молодежь дома Ростовых.
В числе молодых людей, введенных Ростовым, был одним из первых – Долохов, который понравился всем в доме, исключая Наташи. За Долохова она чуть не поссорилась с братом. Она настаивала на том, что он злой человек, что в дуэли с Безуховым Пьер был прав, а Долохов виноват, что он неприятен и неестествен.
– Нечего мне понимать, – с упорным своевольством кричала Наташа, – он злой и без чувств. Вот ведь я же люблю твоего Денисова, он и кутила, и всё, а я всё таки его люблю, стало быть я понимаю. Не умею, как тебе сказать; у него всё назначено, а я этого не люблю. Денисова…
– Ну Денисов другое дело, – отвечал Николай, давая чувствовать, что в сравнении с Долоховым даже и Денисов был ничто, – надо понимать, какая душа у этого Долохова, надо видеть его с матерью, это такое сердце!
– Уж этого я не знаю, но с ним мне неловко. И ты знаешь ли, что он влюбился в Соню?
– Какие глупости…
– Я уверена, вот увидишь. – Предсказание Наташи сбывалось. Долохов, не любивший дамского общества, стал часто бывать в доме, и вопрос о том, для кого он ездит, скоро (хотя и никто не говорил про это) был решен так, что он ездит для Сони. И Соня, хотя никогда не посмела бы сказать этого, знала это и всякий раз, как кумач, краснела при появлении Долохова.
Долохов часто обедал у Ростовых, никогда не пропускал спектакля, где они были, и бывал на балах adolescentes [подростков] у Иогеля, где всегда бывали Ростовы. Он оказывал преимущественное внимание Соне и смотрел на нее такими глазами, что не только она без краски не могла выдержать этого взгляда, но и старая графиня и Наташа краснели, заметив этот взгляд.
Видно было, что этот сильный, странный мужчина находился под неотразимым влиянием, производимым на него этой черненькой, грациозной, любящей другого девочкой.
Ростов замечал что то новое между Долоховым и Соней; но он не определял себе, какие это были новые отношения. «Они там все влюблены в кого то», думал он про Соню и Наташу. Но ему было не так, как прежде, ловко с Соней и Долоховым, и он реже стал бывать дома.
С осени 1806 года опять всё заговорило о войне с Наполеоном еще с большим жаром, чем в прошлом году. Назначен был не только набор рекрут, но и еще 9 ти ратников с тысячи. Повсюду проклинали анафемой Бонапартия, и в Москве только и толков было, что о предстоящей войне. Для семейства Ростовых весь интерес этих приготовлений к войне заключался только в том, что Николушка ни за что не соглашался оставаться в Москве и выжидал только конца отпуска Денисова с тем, чтобы с ним вместе ехать в полк после праздников. Предстоящий отъезд не только не мешал ему веселиться, но еще поощрял его к этому. Большую часть времени он проводил вне дома, на обедах, вечерах и балах.

ХI
На третий день Рождества, Николай обедал дома, что в последнее время редко случалось с ним. Это был официально прощальный обед, так как он с Денисовым уезжал в полк после Крещенья. Обедало человек двадцать, в том числе Долохов и Денисов.
Никогда в доме Ростовых любовный воздух, атмосфера влюбленности не давали себя чувствовать с такой силой, как в эти дни праздников. «Лови минуты счастия, заставляй себя любить, влюбляйся сам! Только это одно есть настоящее на свете – остальное всё вздор. И этим одним мы здесь только и заняты», – говорила эта атмосфера. Николай, как и всегда, замучив две пары лошадей и то не успев побывать во всех местах, где ему надо было быть и куда его звали, приехал домой перед самым обедом. Как только он вошел, он заметил и почувствовал напряженность любовной атмосферы в доме, но кроме того он заметил странное замешательство, царствующее между некоторыми из членов общества. Особенно взволнованы были Соня, Долохов, старая графиня и немного Наташа. Николай понял, что что то должно было случиться до обеда между Соней и Долоховым и с свойственною ему чуткостью сердца был очень нежен и осторожен, во время обеда, в обращении с ними обоими. В этот же вечер третьего дня праздников должен был быть один из тех балов у Иогеля (танцовального учителя), которые он давал по праздникам для всех своих учеников и учениц.
– Николенька, ты поедешь к Иогелю? Пожалуйста, поезжай, – сказала ему Наташа, – он тебя особенно просил, и Василий Дмитрич (это был Денисов) едет.
– Куда я не поеду по приказанию г'афини! – сказал Денисов, шутливо поставивший себя в доме Ростовых на ногу рыцаря Наташи, – pas de chale [танец с шалью] готов танцовать.
– Коли успею! Я обещал Архаровым, у них вечер, – сказал Николай.
– А ты?… – обратился он к Долохову. И только что спросил это, заметил, что этого не надо было спрашивать.
– Да, может быть… – холодно и сердито отвечал Долохов, взглянув на Соню и, нахмурившись, точно таким взглядом, каким он на клубном обеде смотрел на Пьера, опять взглянул на Николая.
«Что нибудь есть», подумал Николай и еще более утвердился в этом предположении тем, что Долохов тотчас же после обеда уехал. Он вызвал Наташу и спросил, что такое?
– А я тебя искала, – сказала Наташа, выбежав к нему. – Я говорила, ты всё не хотел верить, – торжествующе сказала она, – он сделал предложение Соне.
Как ни мало занимался Николай Соней за это время, но что то как бы оторвалось в нем, когда он услыхал это. Долохов был приличная и в некоторых отношениях блестящая партия для бесприданной сироты Сони. С точки зрения старой графини и света нельзя было отказать ему. И потому первое чувство Николая, когда он услыхал это, было озлобление против Сони. Он приготавливался к тому, чтобы сказать: «И прекрасно, разумеется, надо забыть детские обещания и принять предложение»; но не успел он еще сказать этого…