Некоторые варианты алгоритма шифрования DES
© Сергей Панасенко, 2009.
Алгоритм шифрования DES (Data Encryption Standard – стандарт шифрования данных) был принят в качестве стандарта шифрования США более 30 лет назад. DES – алгоритм шифрования с наиболее богатой и интересной историей. История алгоритма DES включает в себя и множество вариантов алгоритма, разработанных с целью его усиления против различных видов атак и предложенных как известными экспертами, так и начинающими криптологами.
Данная статья посвящена некоторым из известных вариантов алгоритма DES. Поскольку варианты DES неотделимы от оригинального алгоритма DES, начнем со структуры данного алгоритма.
Структура алгоритма DES
DES шифрует информацию блоками по 64 бита с помощью 64-битного ключа шифрования, в котором используется только 56 битов (процедура расширения ключа подробно описана далее).
Шифрование информации выполняется следующим образом (см. рис. 1). Сначала над 64-битным блоком данных выполняется начальная перестановка согласно таблице:
58 |
50 |
42 |
34 |
26 |
18 |
10 |
2 |
60 |
52 |
44 |
36 |
28 |
20 |
12 |
4 |
62 |
54 |
46 |
38 |
30 |
22 |
14 |
6 |
64 |
56 |
48 |
40 |
32 |
24 |
16 |
8 |
57 |
49 |
41 |
33 |
25 |
17 |
9 |
1 |
59 |
51 |
43 |
35 |
27 |
19 |
11 |
3 |
61 |
53 |
45 |
37 |
29 |
21 |
13 |
5 |
63 |
55 |
47 |
39 |
31 |
23 |
15 |
7 |
Данная таблица означает, что значение входного бита 58 (здесь и далее все биты нумеруются слева направо, начиная с 1-го) помещается в выходной бит 1, значение 50-го бита – в бит 2 и т. д.
Результат начальной перестановки делится на 2 субблока по 32 бита (на рис. 1 обозначены A0 и B0), над которыми производятся 16 раундов следующих преобразований:
Ai = Bi-1,
Bi = Ai-1 f(Bi-1, Ki),
где:
Структура функции раунда f() приведена на рис. 2. Данная функция выполняется в несколько шагов:
16 |
7 |
20 |
21 |
29 |
12 |
28 |
17 |
1 |
15 |
23 |
26 |
5 |
18 |
31 |
10 |
2 |
8 |
24 |
14 |
32 |
27 |
3 |
9 |
19 |
13 |
30 |
6 |
22 |
11 |
4 |
25 |
Во всех раундах, кроме последнего, субблоки меняются местами.
После выполнения 16 раундов преобразований субблоки A16 и B16 объединяются в 64-битный блок, над которым выполняется финальная перестановка данных согласно следующей таблице:
40 |
8 |
48 |
16 |
56 |
24 |
64 |
32 |
39 |
7 |
47 |
15 |
55 |
23 |
63 |
31 |
38 |
6 |
46 |
14 |
54 |
22 |
62 |
30 |
37 |
5 |
45 |
13 |
53 |
21 |
61 |
29 |
36 |
4 |
44 |
12 |
52 |
20 |
60 |
28 |
35 |
3 |
43 |
11 |
51 |
19 |
59 |
27 |
34 |
2 |
42 |
10 |
50 |
18 |
58 |
26 |
33 |
1 |
41 |
9 |
49 |
17 |
57 |
25 |
Финальная перестановка является инверсной по отношению к описанной выше начальной перестановке. Результат финальной перестановки и является блоком зашифрованных данных.
Расшифрование данных алгоритмом DES выполняется абсолютно так же, как и зашифрование, однако с обратным порядком использования ключей раунда: в i-м раунде расшифрования используется ключ K(17-i).
Таблицы замен алгоритма DES
Упомянутые выше таблицы замен S1…S8 выглядят следующим образом.
S1:
14 |
4 |
13 |
1 |
2 |
15 |
11 |
8 |
3 |
10 |
6 |
12 |
5 |
9 |
0 |
7 |
0 |
15 |
7 |
4 |
14 |
2 |
13 |
1 |
10 |
6 |
12 |
11 |
9 |
5 |
3 |
8 |
4 |
1 |
14 |
8 |
13 |
6 |
2 |
11 |
15 |
12 |
9 |
7 |
3 |
10 |
5 |
0 |
15 |
12 |
8 |
2 |
4 |
9 |
1 |
7 |
5 |
11 |
3 |
14 |
10 |
0 |
6 |
13 |
S2:
15 |
1 |
8 |
14 |
6 |
11 |
3 |
4 |
9 |
7 |
2 |
13 |
12 |
0 |
5 |
10 |
3 |
13 |
4 |
7 |
15 |
2 |
8 |
14 |
12 |
0 |
1 |
10 |
6 |
9 |
11 |
5 |
0 |
14 |
7 |
11 |
10 |
4 |
13 |
1 |
5 |
8 |
12 |
6 |
9 |
3 |
2 |
15 |
13 |
8 |
10 |
1 |
3 |
15 |
4 |
2 |
11 |
6 |
7 |
12 |
0 |
5 |
14 |
9 |
S3:
10 |
0 |
9 |
14 |
6 |
3 |
15 |
5 |
1 |
13 |
12 |
7 |
11 |
4 |
2 |
8 |
13 |
7 |
0 |
9 |
3 |
4 |
6 |
10 |
2 |
8 |
5 |
14 |
12 |
11 |
15 |
1 |
13 |
6 |
4 |
9 |
8 |
15 |
3 |
0 |
11 |
1 |
2 |
12 |
5 |
10 |
14 |
7 |
1 |
10 |
13 |
0 |
6 |
9 |
8 |
7 |
4 |
15 |
14 |
3 |
11 |
5 |
2 |
12 |
S4:
7 |
13 |
14 |
3 |
0 |
6 |
9 |
10 |
1 |
2 |
8 |
5 |
11 |
12 |
4 |
15 |
13 |
8 |
11 |
5 |
6 |
15 |
0 |
3 |
4 |
7 |
2 |
12 |
1 |
10 |
14 |
9 |
10 |
6 |
9 |
0 |
12 |
11 |
7 |
13 |
15 |
1 |
3 |
14 |
5 |
2 |
8 |
4 |
3 |
15 |
0 |
6 |
10 |
1 |
13 |
8 |
9 |
4 |
5 |
11 |
12 |
7 |
2 |
14 |
S5:
2 |
12 |
4 |
1 |
7 |
10 |
11 |
6 |
8 |
5 |
3 |
15 |
13 |
0 |
14 |
9 |
14 |
11 |
2 |
12 |
4 |
7 |
13 |
1 |
5 |
0 |
15 |
10 |
3 |
9 |
8 |
6 |
4 |
2 |
1 |
11 |
10 |
13 |
7 |
8 |
15 |
9 |
12 |
5 |
6 |
3 |
0 |
14 |
11 |
8 |
12 |
7 |
1 |
14 |
2 |
13 |
6 |
15 |
0 |
9 |
10 |
4 |
5 |
3 |
S6:
12 |
1 |
10 |
15 |
9 |
2 |
6 |
8 |
0 |
13 |
3 |
4 |
14 |
7 |
5 |
11 |
10 |
15 |
4 |
2 |
7 |
12 |
9 |
5 |
6 |
1 |
13 |
14 |
0 |
11 |
3 |
8 |
9 |
14 |
15 |
5 |
2 |
8 |
12 |
3 |
7 |
0 |
4 |
10 |
1 |
13 |
11 |
6 |
4 |
3 |
2 |
12 |
9 |
5 |
15 |
10 |
11 |
14 |
1 |
7 |
6 |
0 |
8 |
13 |
S7:
4 |
11 |
2 |
14 |
15 |
0 |
8 |
13 |
3 |
12 |
9 |
7 |
5 |
10 |
6 |
1 |
13 |
0 |
11 |
7 |
4 |
9 |
1 |
10 |
14 |
3 |
5 |
12 |
2 |
15 |
8 |
6 |
1 |
4 |
11 |
13 |
12 |
3 |
7 |
14 |
10 |
15 |
6 |
8 |
0 |
5 |
9 |
2 |
6 |
11 |
13 |
8 |
1 |
4 |
10 |
7 |
9 |
5 |
0 |
15 |
14 |
2 |
3 |
12 |
S8:
13 |
2 |
8 |
4 |
6 |
15 |
11 |
1 |
10 |
9 |
3 |
14 |
5 |
0 |
12 |
7 |
1 |
15 |
13 |
8 |
10 |
3 |
7 |
4 |
12 |
5 |
6 |
11 |
0 |
14 |
9 |
2 |
7 |
11 |
4 |
1 |
9 |
12 |
14 |
2 |
0 |
6 |
10 |
13 |
15 |
3 |
5 |
8 |
2 |
1 |
14 |
7 |
4 |
10 |
8 |
13 |
15 |
12 |
9 |
0 |
3 |
5 |
6 |
11 |
Расширение ключа в алгоритме DES
Схема процедуры расширения ключа показана на рис. 4. Ее задача – формирование 16 ключей раунда, которое выполняется следующим образом.
Как было сказано выше, из 64-битного ключа шифрования алгоритм DES использует только 56 битов. Каждый 8-й бит отбрасывается и никак не применяется в алгоритме, причем использование оставшихся битов ключа шифрования в реализациях алгоритма DES никак не лимитировано стандартом. Процедура извлечения 56 значащих битов из 64-битного ключа на рис. 4 обозначена как E. Помимо извлечения, данная процедура выполняет еще и перестановку битов ключа согласно следующим таблицам:
57 |
49 |
41 |
33 |
25 |
17 |
9 |
1 |
58 |
50 |
42 |
34 |
26 |
18 |
10 |
2 |
59 |
51 |
43 |
35 |
27 |
19 |
11 |
3 |
60 |
52 |
44 |
36 |
63 |
55 |
47 |
39 |
31 |
23 |
15 |
7 |
62 |
54 |
46 |
38 |
30 |
22 |
14 |
6 |
61 |
53 |
45 |
37 |
29 |
21 |
13 |
5 |
28 |
20 |
12 |
4 |
В результате перестановки формируются два 28-битных значения C и D. Верхняя таблица определяет выборку битов ключа для C, нижняя – для D.
Затем выполняется 16 раундов преобразований, каждый из которых дает один из ключей раунда Ki. В каждом раунде производятся следующие действия:
14 |
17 |
11 |
24 |
1 |
5 |
3 |
28 |
15 |
6 |
21 |
10 |
23 |
19 |
12 |
4 |
26 |
8 |
16 |
7 |
27 |
20 |
13 |
2 |
41 |
52 |
31 |
37 |
47 |
55 |
30 |
40 |
51 |
45 |
33 |
48 |
44 |
49 |
39 |
56 |
34 |
53 |
46 |
42 |
50 |
36 |
29 |
32 |
Сочетание циклического сдвига и сжимающей перестановки приводит к тому, что в каждом из ключей раундов используется уникальный набор битов ключа шифрования.
При расшифровании данных можно использовать ту же процедуру расширения ключа, но применять ключи раундов в обратном порядке. Есть и другой вариант: в каждом раунде процедуры расширения ключа вместо циклического сдвига влево выполнять циклический сдвиг вправо на n’ бит, где n’ = 0 для первого раунда, n’ = 1 для раундов 2, 9, 16 и n’ = 2 для остальных раундов. Такая процедура расширения ключа сразу даст нужные для расшифрования ключи раунда K(17-i).
Направления усиления алгоритма
Многими экспертами DES был признан весьма сильным на то время алгоритмом шифрования. Тем не менее, несколько уязвимостей алгоритма стали известны в первые же несколько лет его использования:
Следовательно, различные последующие варианты алгоритма DES предлагались с целью его усиления против данных уязвимостей. Криптологи предлагали следующие варианты усиливающих модификаций алгоритма:
Кроме того, появлялись и различные обобщающие варианты алгоритма DES (на различные размеры ключа, шифруемого блока и переменное число раундов – например, алгоритмы GDES и xDESi), а также несколько «облегченных» и учебных вариантов алгоритма (например, Lightweight DES и SDES).
Рассмотрим несколько примеров вариантов алгоритма DES, предложенных во время его использования в качестве стандарта шифрования США (описание многих других вариантов алгоритма DES, а также упоминаемых в данной статье атак и различных режимов шифрования можно найти в книге С. Панасенко «Алгоритмы шифрования. Специальный справочник», вышедшей в издательстве «БХВ-Петербург» в 2009 г.).
Brown-Seberry-DES
Данный вариант алгоритма DES предложен на конференции AUSCRYPT в 1990 г. двумя австралийскими криптологами: Лоуренсом Брауном (Lawrence Brown) и Дженнифер Себерри (Jennifer Seberry).
По сравнению со стандартным DES в Brown-Seberry-DES изменена только процедура расширения ключа, да и та весьма незначительно. Изменения затрагивают лишь значение n – число битов циклического сдвига, которое Браун и Себерри предлагают сделать константным и равным семи в каждом раунде процедуры расширения ключа (чему авторами данного варианта дается математическое обоснование).
В результате Brown-Seberry-DES оказался нестоек к расширенной сдвиговой атаке, изобретатели которой Алекс Бирюков (Alex Biryukov) и Дэвид Вагнер (David Wagner) предложили метод вскрытия данного алгоритма при наличии всего 128 выбранных открытых текстов (и соответствующих им шифртекстов) выполнением незначительного количества тестовых операций шифрования (однако, данная атака выполнима не для всех возможных ключей, а только для 240 уязвимых).
Кроме того, стоит отметить, что в одной из основополагающих работ по атакам на связанных ключах известного криптолога Эли Бихама (Eli Biham) утверждается, что DES не подвержен атакам на связанных ключах именно из-за циклического сдвига на переменное число битов в процедуре расширения ключа. Следовательно, вариант Brown-Seberry-DES потенциально уязвим к атакам на связанных ключах.
Extended DES
Extended DES предложил тот же Лоуренс Браун с участием Дженнифер Себерри. Авторы Extended DES попытались с его помощью решить проблему короткого ключа алгоритма DES. Основная идея Extended DES состоит в том, что все участвующие в DES фрагменты данных и ключа увеличиваются в размерах в 2 раза, в результате чего алгоритм шифрует 128-битные блоки с использованием достаточно длинного 112-битного ключа.
Ясно, что основные операции DES при таком «удвоении» алгоритма претерпели бы различные изменения, но, тем не менее, Браун и Себерри полагали, что Extended DES унаследует все положительные стороны стандартного DES, в том числе, высокую криптостойкость.
Авторами Extended DES были предложены следующие изменения в криптопреобразования:
Алгоритм Extended DES остался шаблонным, поскольку его авторы только обозначили направления доработки DES, но сами не выработали конкретные параметры алгоритма. В результате реализации Extended DES или результаты криптоанализа данного алгоритма с какими-либо конкретными параметрами не получили широкой известности.
DES*
DES* – это еще один из вариантов алгоритма DES. Специфика данного варианта заключается в его применении – он используется в качестве одного из вариантов однонаправленных функций для зашифрования паролей пользователей (и их последующего хранения в файле паролей). Рассмотрим порядок зашифрования паролей (см. рис. 5):
В данном случае модификатор пароля обеспечивает не только саму модификацию пароля (т. е. «неодинаковость» двух эквивалентных паролей в зашифрованном виде), но и дополнительные преимущества:
Некоторые эксперты отмечают, что алгоритм DES* сам существует во множестве различных вариантов, характеризующихся следующими параметрами:
Кроме того, может варьироваться количество итераций шифрования.
DESL и DESXL
Авторы алгоритма DESL (DES Lightweight – «облегченный» DES) при разработке данного алгоритма преследовали цель создания крайне нетребовательного к ресурсам (но, тем не менее, достаточно криптостойкого) алгоритма шифрования. Данный алгоритм предполагалось использовать в устройствах с крайне низкими ресурсами, а именно, в пассивных радиочастотных метках (RFID – Radio Frequency Identification Device).
DESL был разработан совсем недавно, в 2006 г., рядом немецких криптологов. Его отличие от исходного алгоритма DES состоит лишь в том, что вместо восьми таблиц замен здесь используется лишь одна, но более стойкая к различным видам криптоанализа, чем любая из таблиц стандартного DES (что доказано авторами DESL). Таким образом, экономится достаточно много (для пассивных RFID) энергонезависимой памяти для хранения таблиц.
Таблица алгоритма DESL выглядит так:
14 |
5 |
7 |
2 |
11 |
8 |
1 |
15 |
0 |
10 |
9 |
4 |
6 |
13 |
12 |
3 |
5 |
0 |
8 |
15 |
14 |
3 |
2 |
12 |
11 |
7 |
6 |
9 |
13 |
4 |
1 |
10 |
4 |
9 |
2 |
14 |
8 |
7 |
13 |
0 |
10 |
12 |
15 |
1 |
5 |
11 |
3 |
6 |
9 |
6 |
15 |
5 |
3 |
8 |
4 |
11 |
7 |
1 |
12 |
2 |
0 |
14 |
10 |
13 |
DESXL – это аналогичная DESL облегченная версия известного варианта DES – алгоритма DESX. Отличие DESX от DES (и, следовательно, DESXL от DESL) состоит в том, что в DESX выполняется входное и выходное отбеливание данных (наложение дополнительного ключа):
C = k3 DESk1(k2 M),
где M и C – это, соответственно, открытый текст и шифртекст, а k1…k3 – фрагменты ключа шифрования, первый из которых является 56-битным, а остальные – 64-битными.
DESXL предполагается использовать в тех RFID, где стойкости DESL по каким-либо причинам может быть недостаточно. В настоящее время оба алгоритма активно продвигаются авторами на различных конференциях, посвященных криптографии для RFID, например, на конференциях RFID Security: Theory and Practice и Workshop Wireless Technologies, прошедших в 2008 г.
DES-80
В конце 1996 г. правительство Канады заказало в фирме Entrust Technologies разработку варианта алгоритма DES, который удовлетворял бы следующим критериям:
Сотрудники Entrust Technologies провели всесторонний анализ свойств процедуры расширения ключа алгоритма DES и ряда его вариантов, в результате которого был разработан алгоритм DES-80.
Его процедура расширения ключа выполняется в 2 этапа. Первый этап состоит из 24 раундов преобразований, в каждом из которых выполняются следующие действия (см. рис. 6):
fi = F(KH, KL),
K = K <<< (i + 8),
KH = KH + fi mod 232,
где:
Второй этап вычисляет ключи раундов DES K1…K16 на основе переменных fi следующим образом: выполняются 3 раунда, в каждом из которых вычисляются ключи 4-х раундов DES (см. рис. 7):
K4i+j = f6i+1[j] || f6i+2[j] || f6i+3[j] || f6i+4[j] || f6i+5[j] || f6i+6[j],
где:
Права на алгоритм DES-80 принадлежат правительству Канады. Автору статьи не удалось найти какие-либо сведения о том, используется ли данный алгоритм, а также какие-либо результаты его криптоанализа.
S-DES
Алгоритм S-DES – это специфический вариант алгоритма DES, разработанный с учебными целями. Алгоритм шифрует данные 8-битными блоками с использованием 10-битного ключа. S-DES является как бы «уменьшенной» вариацией DES, в которой используются преобразования, аналогичные преобразованиям DES.
Как и в DES, в алгоритме S-DES выполняются начальная и финальная перестановки с аналогичным принципом действия. Начальная перестановка выглядит следующим образом:
2 |
6 |
3 |
1 |
4 |
8 |
5 |
7 |
Финальная перестановка:
4 |
1 |
3 |
5 |
7 |
2 |
8 |
6 |
Между начальной и финальной перестановкой выполняются два раунда преобразований, каждый из которых обрабатывает правый 4-битный субблок данных и накладывает результат обработки на левый субблок операцией XOR. Между раундами субблоки меняются местами.
Структура раунда приведена на рис. 8. Как и в алгоритме DES, раунд начинается с выполнения расширяющей перестановки EP, которая расширяет 4-битный субблок с получением 8-битного результата (см. рис. 9).
Затем на данные операцией XOR накладывается 8-битный ключ раунда Ki (где i – номер раунда). Результат этой операции делится на 2 фрагмента по 4 бита, которые прогоняются через таблицы замен S1 и S2. Таблицы заменяют 4-битные фрагменты 2-битными, принцип их работы похож на принцип работы таблиц S1…S8 алгоритма DES:
Таблица S1 выглядит так:
1 |
0 |
3 |
2 |
3 |
2 |
1 |
0 |
0 |
2 |
1 |
3 |
3 |
1 |
3 |
2 |
Таблица S2:
0 |
1 |
2 |
3 |
2 |
0 |
1 |
3 |
3 |
0 |
1 |
0 |
2 |
1 |
0 |
3 |
Выходные значения таблиц S1 и S2 объединяются в 4-битный субблок, над которым выполняется перестановка P:
2 |
4 |
3 |
1 |
Процедура расширения ключа алгоритма S-DES также похожа на таковую у DES с учетом уменьшенных размеров блока и ключа, а также количества раундов (см. рис. 10). Прежде всего, над ключом выполняется операция E, выполняющая выборку битов ключа для формирования 5-битных значений C и D. Биты ключа для C и D определяются следующими таблицами:
3 |
5 |
2 |
7 |
4 |
10 |
1 |
9 |
8 |
6 |
Затем C и D циклически сдвигаются влево на i позиций. Ключ раунда получается путем извлечения из 10-битного значения C || D 8 битов согласно сжимающей перестановке CP:
6 |
3 |
7 |
4 |
8 |
5 |
10 |
9 |
Использование S-DES в качестве реального алгоритма шифрования невозможно ввиду малых размеров ключа и шифруемого блока.
2K-DES и 4K-DES
Данные варианты алгоритма DES весьма просты. 2K-DES выполняет 64 раунда шифрования 96-битным ключом, который представляется в виде двух 48-битных половинок, поочередно используемых в раундах алгоритма.
Не более сложен и 4K-DES: то же количество раундов он выполняет уже 192-битным ключом, который представляется в виде 4-х поочередно используемых 48-битных частей.
2K-DES и 4K-DES, фактически, не предназначались для какого-либо использования по прямому назначению – их авторы (упоминавшиеся выше Алекс Бирюков и Дэвид Вагнер) проиллюстрировали на данных алгоритмах силу расширенной сдвиговой атаки. Для вскрытия 2K-DES с ее помощью требуется всего 232 известных открытых текстов и 233 тестовых операций шифрования независимо от количества раундов алгоритма. Выбранных открытых текстов для вскрытия алгоритма требуется намного меньше: 217 (и столько же операций шифрования). Этот вариант атаки применим и к алгоритму 4K-DES с теми же требуемыми ресурсами.
DES-SK/N
Семейство алгоритмов DES-SK/N предложено в 1996 г. Ури Блюменталем (Uri Blumenthal) и Стивеном Белловином (Steven M. Bellowin). Основная идея DES-SK/N состоит в увеличении размера ключа алгоритма DES и усилении его процедуры расширения ключа против различных атак, направленных на слабости данной процедуры. Кроме того, авторы предлагают увеличить и сделать переменным (т. е. привести в зависимость от требований к конкретным реализациям алгоритма) количество раундов алгоритма, которое обозначается как N в названии алгоритма. Рекомендуемый авторами алгоритм семейства – 32-раундовый DES-SK/32.
Процедура расширения ключа алгоритмов DES-SK/N достаточно сложна. В качестве входного значения данная процедура принимает исходный ключ шифрования K переменного размера (от 40 до 256 битов включительно); размер ключа в битах обозначается как n. В процедуре расширения ключа активно используется функция преобразования n-битного K в некую m-битную последовательность, которую обозначим как Km. Данное преобразование выполняется так:
Сама процедура расширения ключа выглядит следующим образом (см. рис. 11):
Как видно, процедура расширения ключа алгоритмов DES-SK/N весьма сложна. Данные алгоритмы не вызвали какого-либо интереса со стороны криптологов, их реализации не получили широкой известности, поэтому сложно сказать, достигли ли авторы семейства алгоритмов DES-SK/N поставленных целей.
Заключение
В течение всего того времени, когда алгоритм DES являлся стандартом шифрования США (и наиболее часто используемым во всем мире алгоритмом шифрования), криптологи изобретали различные варианты данного алгоритма. Этот процесс продолжается и сейчас. И хотя многие из этих вариантов имеют чисто историческое значение, есть такие, которые способны продлить жизнь алгоритму DES – прежде всего, совсем новые варианты DESL и DESXL, которых, судя по всему, ожидает достаточно активное использование в их специфичной нише. Стоит предположить, что это не последние варианты алгоритма DES.
Рисунки: