Криптография, защита компьютерных данных: информация, исследования, аналитика, экспертиза

Rambler's Top100

OZON.ru

Перейти на главную страницу

Карта сайта

Список статей

Некоторые варианты алгоритма шифрования 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 XOR f(Bi-1, Ki),

где:

Структура функции раунда f() приведена на рис. 2. Данная функция выполняется в несколько шагов:

  1. Над 32-битным входом выполняется расширяющая перестановка EP (см. рис. 3). Данная операция расширяет входное значение до 48 битов для последующего сложения с ключом раунда и обеспечивает влияние «размножаемых» битов на 2 таблицы замен (описаны ниже) вместо одной, что ускоряет возникновение зависимости каждого бита шифртекста от каждого входного бита, что называется лавинным эффектом.
  2. Результат предыдущего шага складывается с ключом раунда Ki операцией XOR.
  3. Результат сложения разбивается на 8 фрагментов по 6 битов, каждый из которых прогоняется через соответствующую таблицу замен (S1…S8). Таблицы замен являются фиксированными и описаны в стандарте. Каждая таблица содержит по 4 строки, содержащих по 16 значений от 0 до 15. Входное значение интерпретируется следующим образом: два крайних бита формируют номер строки (от 0 до 3), из которой выбирается число, расположенное в столбце, номер которого соответствует значению четырех остальных битов входа. Например, при двоичном входе 101100 (десятичное число 44) выбирается значение шестой ячейки второй строки.
  4. 4-битные значения, полученные после выполнения замен, объединяются, после чего над ними выполняется операция P, представляющая собой простую перестановку согласно следующей таблице:

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. В каждом раунде производятся следующие действия:

  1. Текущие значения C и D циклически сдвигаются влево на переменное число битов n. Для раундов 1, 2, 9 и 16 n = 1, в остальных раундах выполняется циклический сдвиг на 2 бита.
  2. C и D объединяются в 56-битное значение, к которому применяется сжимающая перестановка CP, результатом которой является 48-битный ключ раунда 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):

  1. Пароль пользователя урезается до 8 ASCII-символов; при необходимости, производится дополнение нулевыми битами. Совокупность значащих 7 битов каждого символа представляется как ключ шифрования DES.
  2. С помощью данного ключа выполняется 25-кратное зашифрование нулевого (т. е. состоящего из нулевых битов) блока данных. При этом и используется модифицированный DES, т. е. DES*, отличие которого от стандартного DES заключается в использовании различных вариантов расширяющей перестановки EP вместо стандартного (приведенного выше) варианта. В DES* EP зависит от 12-битного модификатора пароля следующим образом: если значение i-го бита модификатора пароля равно 1, то после выполнения EP меняются местами биты №№ i и (24 + i) текущего обрабатываемого 48-битного субблока данных (см. рис. 2). Таким образом, фактически, вместо фиксированной расширяющей перестановки при зашифровании каждого конкретного пароля динамически выбирается одна из 212 перестановок.
  3. Результат последнего из 25 зашифрований конкатенируется с модификатором пароля и преобразуется в строковый вид, после чего записывается в файл.

В данном случае модификатор пароля обеспечивает не только саму модификацию пароля (т. е. «неодинаковость» двух эквивалентных паролей в зашифрованном виде), но и дополнительные преимущества:

Некоторые эксперты отмечают, что алгоритм 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 XOR DESk1(k2 XOR M),

где M и C – это, соответственно, открытый текст и шифртекст, а k1k3 – фрагменты ключа шифрования, первый из которых является 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 K1K16 на основе переменных 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. Данное преобразование выполняется так:

  1. K копируется i раз, где i – наименьшее число, нацело делимое как на n, так и на m.
  2. Перед каждым копированием K вращается на 13 битов вправо.
  3. Выполняется сложение m-битовых фрагментов по модулю 2m, в результате которого получается Km.

Сама процедура расширения ключа выглядит следующим образом (см. рис. 11):

  1. Формируется 64-битная временная переменная t, которая представляет собой результат зашифрования обычным алгоритмом DES значения K64 на самом себе.
  2. Вычисляется (для последующего использования) 64-битный вектор инициализации IV, который равен результату зашифрования алгоритмом DES переменной t на ключе K64.
  3. Модифицируется переменная t которая теперь является результатом расшифрования алгоритмом DES значения K64 на самом себе.
  4. Вычисляется 64-битная временная переменная q как результат расшифрования переменной t на ключе K64.
  5. Вычисляется 192-битный промежуточный ключ G путем зашифрования значения K192 на ключе q алгоритмом DES в режиме шифрования CFB-64 с использованием вектора инициализации IV.
  6. Необходимое количество битов расширенного ключа (а именно, N * 48 битов) вычисляется путем зашифрования значения KN * 48 на ключе G алгоритмом Triple DES (вариант EDE) в режиме шифрования CFB-64 с использованием вектора инициализации IV.

Как видно, процедура расширения ключа алгоритмов DES-SK/N весьма сложна. Данные алгоритмы не вызвали какого-либо интереса со стороны криптологов, их реализации не получили широкой известности, поэтому сложно сказать, достигли ли авторы семейства алгоритмов DES-SK/N поставленных целей.

Заключение

В течение всего того времени, когда алгоритм DES являлся стандартом шифрования США (и наиболее часто используемым во всем мире алгоритмом шифрования), криптологи изобретали различные варианты данного алгоритма. Этот процесс продолжается и сейчас. И хотя многие из этих вариантов имеют чисто историческое значение, есть такие, которые способны продлить жизнь алгоритму DES – прежде всего, совсем новые варианты DESL и DESXL, которых, судя по всему, ожидает достаточно активное использование в их специфичной нише. Стоит предположить, что это не последние варианты алгоритма DES.

Рисунки:

  1. Структура алгоритма DES.
  2. Функция раунда алгоритма DES.
  3. Расширяющая перестановка алгоритма DES.
  4. Процедура расширения ключа алгоритма DES.
  5. Применение алгоритма DES*.
  6. Первый этап процедуры расширения ключа алгоритма DES-80.
  7. Второй этап процедуры расширения ключа алгоритма DES-80.
  8. Функция раунда алгоритма S-DES.
  9. Расширяющая перестановка алгоритма S-DES.
  10. Процедура расширения ключа алгоритма S-DES.
  11. Процедура расширения ключа алгоритма DES-SK/N.