06 июля 2007

C. Панасенко. Эволюция алгоритмов шифрования.

C. Панасенко

CIO, июнь 2007

Эволюция алгоритмов шифрования происходит постоянно. Это обусловлено не только постоянно повышающимися требованиями к ним (например, быстродействие и гибкость в реализации на различных платформах), но, прежде всего, постоянным усилением криптоаналитических методов (см. статьи «Современные методы вскрытия алгоритмов шифрования», «Атаки на шифраторы с использованием утечек данных по побочным каналам» «Криптоаналитические атаки на связанных ключах» и «Алгоритм шифрования AES и его криптоанализ»). В целях поддержания должного уровня криптостойкости алгоритмы шифрования подвергаются различным модификациям, усиливающим их против новейших видов криптоаналитических атак. Как и в большинстве других направлений защиты компьютерной информации, здесь наблюдается противостояние «брони и снаряда». Противодействие разработчиков алгоритмов шифрования и криптоаналитиков рассмотрим на примере семейства алгоритмов SAFER, пережившего за десяток лет множество модификаций.

Алгоритм SAFER K-64

Алгоритм блочного симметричного шифрования SAFER K-64 был разработан в 1993 г. известным криптологом Джеймсом Мэсси (James L. Massey) из Технологического Института г. Цюрих, Швейцария, для американской корпорации Cylink. Название алгоритма – аббревиатура от Secure and Fast Encryption Routine, т.е. «сильный и быстрый алгоритм шифрования»; «K-64» в названии алгоритма обозначает использование 64-битного ключа шифрования [6].

Структура алгоритма

SAFER K-64 шифрует данные 64-битными блоками. Блок данных представляется в виде 8-байтового массива (байты нумеруются слева направо от 1 до 8). Алгоритм представляет собой подстановочно-перестановочную сеть (Substitution-Permutation Network, SPN, см., например, [15]), в каждом раунде которой выполняются следующие преобразования (см. рис. 1) [6]:

Рис. 1. Раунд алгоритма SAFER K-64.

Первое наложение ключа: на данные накладывается 8-байтный фрагмент расширенного ключа K_2i-1, где i – номер текущего раунда (раунды нумеруются, начиная с 1; процедура расширения ключа будет описана ниже). Байты ключа №№ 1, 4, 5 и 8 накладываются на аналогичные байты данных с помощью побитовой логической операции «исключающее или» (XOR); для наложения остальных байт ключа используется операция сложения по модулю 256.
Нелинейное преобразование, заключающееся в следующем:
- Байты данных №№ 1, 4, 5 и 8 обрабатываются следующей операцией (на рис. 1 обозначена как E): y = 45x mod 257, где x и y – соответственно, входное и выходное значения данной операции, причем, если y = 256 (что происходит при x = 128), y обнуляется.
Остальные байты обрабатываются обратной операцией L: y = log₄₅ x mod 257, причем для x = 0 значение y устанавливается в 128.
Второе наложение ключа; выполняется аналогично первому (однако, с использованием другого фрагмента расширенного ключа – K_2i), но с инверсным применением операций: байты, которые в первом наложении ключа обрабатывались операцией XOR, здесь обрабатываются сложением по модулю 256, и наоборот.
Затем выполняются 3 уровня преобразований PHT (Pseudo Hadamard Transform – псевдоадамарово преобразование); операция PHT выполняет несложное преобразование двух входных байт данных (x₁ и x₂), давая в результате два выходных байта y₁ и y₂, и определяется следующим образом:
y₁ = 2x₁ + x₂ mod 256,
y₂ = x₁ + x₂ mod 256,
что схематически представлено на рис. 2.

Рис. 2. Преобразование PHT.

Между уровнями преобразований PHT выполняется перестановка байт данных по следующему закону:

Это означает, что байт № 1 остается на своем месте, входное значение байта № 3 становится выходным значением байта № 2 и т. д.

Автор рекомендует выполнять 6 раундов описанных выше преобразований (количество раундов алгоритма обозначим как R), но допускает увеличение числа раундов до десяти.

После выполнения R раундов алгоритма применяется выходное преобразование, полностью аналогичное описанной выше операции первого наложения ключа; в данном случае применяется последний из фрагментов расширенного ключа K_2R+1.

Следует учесть, что в зависимости от требований к реализации алгоритма описанные выше операции E и L могут быть реализованы напрямую или в виде таблиц замен. Таблица замен для E выглядит так [13]:

1	45	226	147	190	69	21	174	120	3	135	164	184	56	207	63
8	103	9	148	235	38	168	107	189	24	52	27	187	191	114	247
64	53	72	156	81	47	59	85	227	192	159	216	211	243	141	177
255	167	62	220	134	119	215	166	17	251	244	186	146	145	100	131
241	51	239	218	44	181	178	43	136	209	153	203	140	132	29	20
129	151	113	202	95	163	139	87	60	130	196	82	92	28	232	160
4	180	133	74	246	19	84	182	223	12	26	142	222	224	57	252
32	155	36	78	169	152	158	171	242	96	208	108	234	250	199	217
0	212	31	110	67	188	236	83	137	254	122	93	73	201	50	194
249	154	248	109	22	219	89	150	68	233	205	230	70	66	143	10
193	204	185	101	176	210	198	172	30	65	98	41	46	14	116	80
2	90	195	37	123	138	42	91	240	6	13	71	111	112	157	126
16	206	18	39	213	76	79	214	121	48	104	54	117	125	228	237
128	106	144	55	162	94	118	170	197	127	61	175	165	229	25	97
253	77	124	183	11	238	173	75	34	245	231	115	35	33	200	5
225	102	221	179	88	105	99	86	15	161	49	149	23	7	58	40

Данная таблица обозначает, что значение 0 заменяется значением 1, значение 1 – значением 45 и т. д.

Таблица замен для L [13]:

128	0	176	9	96	239	185	253	16	18	159	228	105	186	173	248
192	56	194	101	79	6	148	252	25	222	106	27	93	78	168	130
112	237	232	236	114	179	21	195	255	171	182	71	68	1	172	37
201	250	142	65	26	33	203	211	13	110	254	38	88	218	50	15
32	169	157	132	152	5	156	187	34	140	99	231	197	225	115	198
175	36	91	135	102	39	247	87	244	150	177	183	92	139	213	84
121	223	170	246	62	163	241	17	202	245	209	23	123	147	131	188
189	82	30	235	174	204	214	53	8	200	138	180	226	205	191	217
208	80	89	63	77	98	52	10	7	136	181	86	76	46	107	158
210	61	60	3	19	251	15	81	117	74	145	113	35	190	118	42
95	249	212	85	11	220	55	49	22	116	215	119	167	230	7	219
164	47	70	243	97	69	103	227	12	162	59	28	133	24	4	29
41	160	143	178	90	216	166	126	238	141	83	75	161	154	193	14
122	73	165	44	129	196	199	54	43	127	67	149	51	242	108	104
109	240	2	40	206	221	155	234	94	153	124	20	134	207	229	66
184	64	120	45	58	233	100	31	146	144	125	57	111	224	137	48

Преобразования PHT в совокупности также могут быть заменены умножением байтового массива данных на матрицу M (в конечном поле GF(256)) [8, 10]:

8	4	4	2	4	2	2	1
4	2	4	2	2	1	2	1
4	2	2	1	4	2	2	1
2	1	2	1	2	1	2	1
4	4	2	2	2	2	1	1
2	2	2	2	1	1	1	1
2	2	1	1	2	2	1	1
1	1	1	1	1	1	1	1

Расшифрование

При расшифровании шифртекст, прежде всего, подвергается входному преобразованию с участием фрагмента расширенного ключа K_2R-1, которое инверсно выходному преобразованию при зашифровании:

Байты №№ 1, 4, 5 и 8 обрабатываются операцией XOR.
Остальные байты обрабатываются операцией вычитания:

y = x – k mod 256,

где k – соответствующий байт накладываемого фрагмента ключа.

После этого выполняется R раундов расшифрования, в каждом из которых выполняются следующие операции (см. рис. 3):

Рис. 3. Раунд расшифрования алгоритма SAFER K-64

Выполняется 3 уровня обратного псевдоадамарового преобразования (IPHT – Inverse PHT), которое определяется следующим образом:
y₁ = x₁ - x₂ mod 256,
y₂ = -x₁ + 2x₂ mod 256,
Между уровнями преобразований IPHT выполняется перестановка байт, обратная перестановке, которая использовалась при зашифровании, т.е.:

1 5 2 6 3 7 4 8
Обратное второе наложение ключа: на данные накладывается 8-байтный фрагмент расширенного ключа K_2R+2-2i. Байты ключа №№ 2, 3, 6 и 7 накладываются на аналогичные байты данных с помощью операции XOR; для наложения остальных байт ключа используется описанная выше операция вычитания.
Обратное нелинейное преобразование:
- Байты данных №№ 1, 4, 5 и 8 обрабатываются операцией L.
- Остальные байты обрабатываются операцией E.
- Обратное первое наложение ключа, полностью аналогичное описанному выше входному преобразованию; здесь используется фрагмент расширенного ключа K_2R+1-2i.

Как видно, при расшифровании происходит выполнение обратных операций в обратном порядке.

Преобразование IPHT также может быть заменено умножением на матрицу M^-1 (аналогично описанному выше для PHT) [10]:

1	-1	-1	1	-1	1	1	-1
-1	1	1	-1	2	-2	-2	2
-1	2	1	-2	1	-2	-1	2
1	-2	-1	2	-2	4	2	-4
-1	1	2	-2	1	-1	-2	2
1	-1	-2	2	-2	2	4	-4
1	-2	-2	4	-1	2	2	-4
-1	2	2	-4	2	-4	-4	8

Расширение ключа

Процедура расширения ключа алгоритма SAFER K-64 достаточно проста. Она состоит из 2R + 1 раундов, в каждом из которых вычисляется один из 8-байтных фрагментов расширенного ключа. Раунд процедуры расширения ключа состоит из следующих операций (см. рис. 4):

Рис. 4. Процедура расширения ключа алгоритма SAFER K-64.

Шаг 1. Каждый байт результата шага 1 предыдущего раунда вращается влево на 3 бита (на рис. 4 данная операция обозначена как <<<_B). В первом раунде процедуры расширения ключа вместо результата шага 1 предыдущего раунда используется исходный 8-байтный ключ шифрования.

Шаг 2. Результат предыдущего шага складывается побайтно по модулю 256 с константой B_i (где i – номер раунда процедуры расширения ключа, i = 2…2R+1). Константы B_i определяются с помощью описанной выше операции E:

B_i [j] = E(E(9i + j)),

где B_i [j] – j-й байт константы B_i. Стоит отметить, что константы B_i могут как вычисляться в процессе расширения ключа, так и быть заданы в виде набора констант (для 10 раундов шифрования, начиная с B₂) [13]:
16733B1E8E70BD86
477E2456F1778846
B1BAA3B7100AC537
C95A28AC64A5ECAB
C66795580DF89AF6
66DC053DD38AC3D8
6AE9364943BFEBD4
9B68A0655D57921F
715CBB22C1BE7BBC
63945F2A61B83432
FDFB1740E6511D41
8F29DD0480DEE731
7F01A2F739DA6F23
FE3AD01CD1303E12
CD0FE0A8AF82592C
7DADB2EFC287CE75
1302904F2E723385
8DCFA981E2C4272F
7A9F52E115382BFC
42C708E409555E8C

Фрагмент расширенного ключа K₁ эквивалентен исходному ключу шифрования без каких-либо изменений.

Несомненное достоинство процедуры расширения ключа состоит в том, что фрагменты расширенного ключа могут вычисляться «на лету», т.е. в процессе зашифрования по мере необходимости.

Криптоанализ алгоритма SAFER K-64

Криптоанализ алгоритма SAFER K-64 был начат Ларсом Кнудсеном (Lars R. Knudsen) в 1995 г. Он предложил атаку на связанных ключах [2]: для почти каждого ключа K существует ключ K’ (отличающийся от K значением одного байта), такой, что для достаточно большого множества открытых текстов (до 2²⁸ из возможных 2⁶⁴) после 6 раундов шифрования результаты шифрования каждого из текстов на ключах K и K’ абсолютно эквивалентны. Финальное преобразование делает результаты шифрования различными, но только в одном байте шифртекста. Данная особенность позволяет вычислить 8 бит 64-битного ключа шифрования алгоритма SAFER K-64 на основе от 2⁴⁴ до 2⁴⁷ выбранных открытых текстов. Найденная Кнудсеном атака не снижает практической криптостойкости алгоритма. Однако, согласно [2], в случае, если SAFER K-64 используется в режиме хэширования, то для нахождения коллизии (двух текстов с одинаковым хэш-значением) требуется 2²³ операций шифрования вместо 2³² (последнее следует из парадокса дней рождения), что делает весьма сомнительной возможность использования данного алгоритма в качестве основы хэш-функций. Вывод автора [2] состоит в том, что для достижения достаточной криптостойкости алгоритму SAFER K-64 недостаточно раундов: необходимо, как минимум, 10 вместо шести.

Данная атака была усилена Джоном Келси (John Kelsey), Брюсом Шнайером (Bruce Schneier) и Дэвидом Вагнером (David Wagner) [1]: их вариант атаки для нахождения с высокой вероятностью 28 бит ключа требует от 2²⁴ до 2²⁹ выбранных открытых текстов (и их зашифрование на 256 связанных ключах). Как пишут авторы [1], алгоритм SAFER K-64 подвержен атакам на связанных ключах из-за его достаточно простой и «однообразной» (генерация подключей происходит с минимальными отличиями) процедуры расширения ключа.

Еще одна слабость процедуры расширения ключа была описана в работе [8].

Описанный ниже алгоритм SAFER SK-64 противостоит приведенным выше атакам.

В работах [3] и [4] описана атака на 5-раундовый (из 6 раундов) SAFER K-64, для которой требуется 2⁴⁵ выбранных открытых текстов и 2⁴⁶ операций шифрования или 2⁴⁶ выбранных открытых текстов и 2³⁵ операций.

Алгоритм SAFER K-128

В 1995 г. автор алгоритма SAFER K-64 в [7] писал (устный доклад на эту тему был сделан автором на конференции в декабре 1994 г.), что данный алгоритм был весьма положительно принят в мире и реализован в множестве различных средств. Поэтому почти сразу после презентации алгоритма SAFER K-64 Джеймс Мэсси начал разработку алгоритма SAFER K-128, который шифрует с использованием уже 128-битного ключа шифрования.

SAFER K-128 отличается от SAFER K-64 только процедурой расширения ключа, которая была предложена автору алгоритма специалистами МВД Сингапура [7].

Рис. 5. Процедура расширения ключа алгоритма SAFER K-128.

Процедура расширения ключа алгоритма SAFER K-128 приведена на рис. 5 [14]. Ее отличие от исходной легко видно в том, что фрагменты расширенного ключа формируются параллельно из двух 64-битных половин 128-битного исходного ключа шифрования:

правая половина ключа (K_b) является первым фрагментом расширенного ключа (K₁) и формирует все остальные фрагменты с нечетными индексами;
левая половина ключа (K_a) формирует все фрагменты расширенного ключа с четными индексами.

Как видно из рис. 5, в случае, если K_a = K_b, то алгоритм SAFER K-128 становится полностью совместимым (при одинаковом количестве раундов R) с алгоритмом SAFER K-64, в котором используется ключ K = K_a = K_b. Кстати, количество раундов в алгоритме SAFER K-128 рекомендуется большее, чем в SAFER K-64: 10 раундов рекомендует автор алгоритма в [7], максимальное количество раундов – 12.

Там же, в [7], Джеймс Мэсси отмечает ряд соображений касательно описанной выше атаки Ларса Кнудсена [2]:

в части нахождения коллизий за 2²³ вместо 2³² операций атака применима и к алгоритму SAFER K-128;
автор алгоритма считает, что применение алгоритма блочного шифрования в качестве основы хэш-функции происходит достаточно редко, но в этом случае достаточно увеличить количество раундов алгоритма SAFER K-64 с 6 до, как минимум, 10, каких-либо более серьезных модификаций алгоритма не требуется.

Алгоритмы SAFER SK-64, SAFER SK-128 и SAFER SK-40

Усиление процедуры расширения ключа алгоритма SAFER K-64 против изобретенной им же атаки предложил в [2] Ларс Кнудсен. В сообщении на конференции sci.crypt в 1995 г. [5] Мэсси предложил два усовершенствованных варианта алгоритма SAFER: SAFER SK-64 и SAFER SK-128.

По сравнению с алгоритмом SAFER K-64 в них изменилась только процедура расширения ключа, которая была усилена именно в соответствии с предложениями Ларса Кнудсена.

Рис. 6 Процедура расширения ключа алгоритма SAFER SK-64.

Процедура расширения ключа алгоритма SAFER SK-64 приведена на рис. 6. Ее отличия от исходной состоят в следующем:

Исходный 64-битный ключ шифрования разбивается на 8 байт, к которым добавляется еще один, полученный в результате применения побитовой операции XOR к соответствующим битам 8-ми байт ключа.
В каждом раунде процедуры расширения ключа выполняется сдвиг этих 9 байт на 1 байт влево.
В результате, в формировании фрагментов расширенного ключа в каждом раунде процедуры участвуют различные байты ключа (включая дополнительный 9-й байт): K₁ формируется полностью аналогично алгоритму SAFER K-64 из байтов исходного ключа, K₂ – из байтов с 2-го по 9-й, K₃ – из байтов с 3-го по 9-й и 1-го и т. д.

В свою очередь, процедура расширения ключа алгоритма SAFER SK-128 является некоторой комбинацией процедур расширения ключа алгоритмов SAFER K-128 и SAFER SK-64, а именно:

Исходный 128-битный ключ шифрования разбивается на 2 64-битных фрагмента K_a и K_b.
Правая половина ключа (K_b) дополняется 9-м байтом (аналогично процедуре SAFER SK-64) и участвует в формировании фрагментов расширенного ключа с нечетными индексами (см. рис. 7).
Левая половина ключа (K_a) также дополняется 9-м байтом и участвует в формировании фрагментов с четными индексами (см. рис. 8).

Рис. 7. Процедура расширения ключа алгоритма SAFER SK-128 (нечетные фрагменты).

Рис. 8. Процедура расширения ключа алгоритма SAFER SK-128 (четные фрагменты).

У алгоритмов SAFER SK-64 и SAFER SK-128 сохраняется то свойство, что если K_a = K_b, то алгоритм SAFER SK-128 является полностью совместимым (при одинаковом количестве раундов R) с алгоритмом SAFER SK-64, в котором используется ключ K = K_a = K_b. Минимальное и рекомендованное количество раундов алгоритма SAFER SK-64 увеличено по сравнению с SAFER K-64 и составляет 8 вместо 6. У SAFER SK-128 количество раундов осталось прежним (как у SAFER K-128).

«SK» в названии алгоритма обозначает Strengthened Key Schedule, т.е. «усиленное расширение ключа». Однако, известна шутка [11], что SK так же хорошо может обозначать и «Stop Knudsen», поскольку новая процедура расширения ключа делает атаку Кнудсена невозможной.

В ряде источников, например, [12] и [13] упоминается алгоритм SAFER SK-40, использующий 40-битный ключ шифрования. Такой короткий ключ шифрования позволял алгоритму SAFER SK-40 обойти существовавшие на тот момент в США экспортные ограничения. Алгоритм (включая процедуру расширения ключа) мало чем отличался от SAFER SK-64. Как было сказано выше, в процедуре расширения ключа алгоритма SAFER SK-64 к 8 байтам исходного ключа определенным образом добавляется 9-й байт (см. рис. 6). У SAFER SK-40 эти 9 байт (обозначим их KI₁…KI₉) формируются иначе (см. рис. 9) [13]:

Байты с 1-го по 5-й формируются непосредственно из 40-битного ключа;
Остальные байты (с 6-го по 9-й) формируются, соответственно, так:

KI₆ = KI₁ ⊕ KI₃ ⊕ 129,
KI₇ = KI₁ ⊕ KI₄ ⊕ KI₅ ⊕ 66,
KI₈ = KI₂ ⊕ KI₃ ⊕ KI₅ ⊕ 36,
KI₉ = KI₂ ⊕ KI₄ ⊕ 24.

Далее идет обычная для SAFER SK-64 процедура расширения ключа.

Рис. 9. Начальный этап процедуры расширения ключа алгоритма SAFER SK-40.

Криптоанализ алгоритмов SAFER SK-64 и SAFER SK-128

Какие-либо работы, вскрывающие полнораундовые версии алгоритмов SAFER SK-64 и SAFER SK-128, не получили широкой известности. Было предложено несколько атак на версии алгоритмов с уменьшенным числом раундов, среди которых можно отметить следующие:

В работе [10] описана атака на 3,75-раундовый SAFER SK-64 (по мнению ее авторов, «0,75 раунда» – это раунд алгоритма без преобразований PHT) методом невозможных дифференциалов, для которой требуется 2³² выбранных открытых текстов и 2⁶² тестовых операций шифрования.
Там же описана Square-атака на 3,25-раундовые SAFER SK-64 и SAFER SK-128 (0,25 раунда включает только первое наложение ключа), использующая 2^10,3 выбранных открытых текстов и 2³⁸ тестовых операций.
В [9] описана атака методом линейного криптоанализа на 4,75-раундовый SAFER SK-128, для которой требуется 2⁶⁴ известных открытых текстов (т.е. все возможные открытые тексты и соответствующие им шифртексты) и 2⁹⁰ операций шифрования.

Как видно, даже атаки на усеченные версии данных алгоритмов не являются достаточно практичными.

Список литературы:

Kelsey J., Schneier B., Wagner D. Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. // http://www.schneier.com – 1996.
Knudsen L.R. A Key-schedule Weakness in SAFER K-64. // http://citeseer.ist.psu.edu – 1995 – Ecole Normale Superieure, Paris, France.
Knudsen L.R. Why SAFER K Changed Its Name. // http://citeseer.ist.psu.edu – April 1996 – Ecole Normale Superieure, Paris.
Knudsen L.R., Berson T.A. Truncated Differentials of SAFER. // http://citeseer.ist.psu.edu.
Massey J.L. Announcement of a Strengthened Key Schedule for the cipher SAFER (Secure And Fast Encryption Routine) for both 64 and 128 bit key lengths. // http://groups.google.com – Sep 12 1995.
Massey J.L. SAFER K-64: A Byte-Oriented Block-Ciphering Algorithm. // http://citeseer.ist.psu.edu – 1994 – Swiss Federal Institute of Technology, Zurich.
Massey J.L. SAFER K-64: One Year Later. // http://citeseer.ist.psu.edu – 1995 – Swiss Federal Institute of Technology, Zurich, Switzerland.
Murphy S. An Analysis of SAFER. //http://www.isg.rhul.ac.uk/>http://www.isg.rhul.ac.uk – 22 July 1997 – University of London, Egham, U.K.
Nakahara J.Jr. Cryptanalysis and Design of Block Ciphers. // http://citeseer.ist.psu.edu – June 2003 – Katholieke Universiteit Leuven.
Nakahara J.Jr., Preneel B., Vandewalle J. Impossible Differential Attacks on Reduced-Round SAFER Ciphers. // http://citeseer.ist.psu.edu – March 12, 2003 – Katholieke Universiteit Leuven, Belgium.
SAFER. From Wikipedia, the free encyclopedia. //http://en.wikipedia.org/> http://en.wikipedia.org.
SAFER+. Cylink Corporation’s Submission for the Advanced Encryption Standard. // First Advanced Encryption Standard Candidate Conference, Ventura, CA, August 20-22, 1998. Cylink Corporation.
Savard J. SAFER (Secure And Fast Encryption Routine). //http://www.quadibloc.com/> http://www.quadibloc.com.
Schubert A., Meyer V., Anheier W. Reusable Cryptographic VLSI Core Based on the SAFER K-128 Algorithm with 251.8 Mbit/s Throughput. //http://www.item.uni-bremen.de/> http://www.item.uni-bremen.de – University of Bremen, Germany, 1998.
Панасенко С. Назначение и структура алгоритмов шифрования. // iXBT. – http://www.ixbt.com/>http://www.ixbt.com – 2006.

Об авторе: С. Панасенко, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук. Тел. (495)532-1313, (495)531-0000, е-mail develop@ancud.ru, сайт www.panasenko.ru

Источник: CIO

Показать все статьи автора >>

Просмотров: 1681

06 июля 2007

C. Панасенко. Эволюция алгоритмов шифрования.

Ссылки по теме

Ваши комментарии:

Публикации организации

Все публикации организации

В этой же рубрике

Информация

Отраслевые СМИ