Алгоритм Lucifer

Принятый в США стандарт шифрования DES был основан на алгоритме Lucifer, разработанном в начале 1970-х гг. и его история являются достаточно интересными и заслуживают отдельного рассмотрения.

Lucifer часто называют «первым алгоритмом шифрования для гражданских применений» [338, 395]. На самом деле Lucifer представляет собой не один алгоритм, а целое семейство связанных между собой (разработанных в рамках одноименной исследовательской программы по компьютерной криптографии фирмы IBM [28]), но созданных в разное время, алгоритмов блочного симметричного шифрования данных.

По словам Брюса Шнайера [28], «существует, по меньшей мере, два различных алгоритма с таким именем, что … привело к заметной путанице». А посвященная алгоритму Lucifer статья в интернет-энциклопедии «Wikipedia» [395] упоминает о четырех вариантах этого алгоритма.

Рассмотрим поочередно различные варианты алгоритма Lucifer.

Вариант № 1

Исходный вариант алгоритма Lucifer был разработан коллективом специалистов из компании IBM под руководством Хорста Фейстеля (Horst Feistel). Этот вариант алгоритма был запатентован компанией IBM в 1971 г. (патент выдан в 1974 г.), его подробное описание можно найти в патенте США №3798359 [144].

Этот вариант алгоритма шифрует данные блоками по 48 битов, используя при этом 48-битный ключ шифрования.

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

1. Обеспечение обратной связи. Выполняется логическая операция «исключающее или» (XOR) между каждым битом обрабатываемого блока и предыдущим значением того же бита в случае, если аналогичный бит ключа раунда имеет единичное значение; в противном случае операция не выполняется. Предыдущие значения каждого обрабатываемого бита сохраняются в регистре блока обратной связи. В первом раунде алгоритма блок обратной связи операцию XOR не выполняет, а только запоминает биты обрабатываемого блока для следующего раунда.

Рис. 3.115. Обобщенная схема варианта № 1

2.     Перемешивающее преобразование. Выполняется нелинейное преобразование данных, полученных в результате предыдущей операции, путем табличной замены, зависящей от значения конкретного бита ключа раунда. Причем такая зависимость является достаточно простой: если значение управляющего бита равно 1, выполняется табличная замена S0, в противном случае используется таблица Si.

Каждый нибл данных заменяется независимо от других данных; таким образом, таблицы заменяют 4-битное входное значение также на 4-битное выходное.

Стоит сказать, что в патенте [144] не приведены конкретные значения таблиц замен; в качестве примера приведена следующая таблица:

2,5,4,0,7,6,10,1,9,14,3,12,8,15,13,11.

Это означает, что входное значение 0 заменяется значением 2, значение 1 заменяется на 5 и т. д. до значения 15, которое заменяется на 11.

3.     Рассеивающее преобразование, состоящее в простом перенаправлении входных битов таким образом, что значения всех входных битов меняются местами по определенному закону. Как и значения таблиц замен, сам закон, по которому выполняется рассеивание данных, не описан в патенте [144].

Эта операция выполняется абсолютно независимо от значения ключа шифрования.

4.     Наложение ключа. Выполняется путем побитового применения операции XOR к результату предыдущей операции и соответствующим битам ключа раунда.

Как видно из приведенного описания, в каждом раунде шифрования требуется 108 битов ключевой информации:

?        48 битов для блока обратной связи;

?         12 битов для блока перемешивания;

?        48 битов для блока наложения ключа.

Для получения 16 108-битных раундовых ключей из исходного 48-битного

ключа шифрования выполняется процедура расширения ключа (рис. 3.116):

1.    48-битный ключ загружается в 8-битные регистры KRI…KR6.

2.    Из этих регистров «набирается» необходимое количество битов ключевой информации с помощью расширяющей перестановки КЕР. Операция КЕР не выполняет каких-либо вычислений, получение 108 битов ключевой информации из 48 происходит путем неоднократного использования определенных битов ключевых регистров Л7?1…Л7?6. Ключевая перестановка КЕР не описана подробно в спецификации алгоритма.

3.    Для получения ключевой информации для следующего раунда выполняется побитовый циклический сдвиг на 1 бит содержимого каждого из ключевых регистров KRI…KR6. Затем снова производится перестановка КЕР. Этот шаг повторяется в цикле необходимое число раз до завершения работы алгоритма.

Рис. 3.116. Процедура расширения ключа в варианте № 1

Стоит сказать о том, что данный алгоритм строго нацелен на аппаратное шифрование— в патенте [144] приведено несколько подробных схем, описывающих возможные аппаратные реализации алгоритма. Программному же шифрованию, практически, не уделено внимание в данном патенте.

Очевиден и тот факт, что в описании алгоритма [144] существует множество «белых пятен». Например, не приведены таблицы замен, нет подробного описания используемого линейного преобразования, отсутствует описание перестановки КЕР и т. д. Фактически патент устанавливает некий шаблон для разработки на его основе конкретных алгоритмов шифрования с «уточненными» процедурами.

Одновременно с патентом [144] 30 июня 1971 г. Хорстом Фейстелем были поданы еще две заявки на патенты; обе предлагали специфические применения описанного выше алгоритма:

?      защиту данных, передаваемых и обрабатываемых в многотерминальных системах, с использованием алгоритма Lucifer; запатентованная схема подразумевает также обеспечение целостности данных, а также наличие двух режимов аутентификации пользователей: парольного и «запрос- ответ» [145];

?      многоступенчатое шифрование данных, обеспечивающее различные уровни защиты информации при ее передаче в многотерминальных системах; эта схема также основана на применении алгоритма Lucifer [146].

Указанные патенты также были получены фирмой ЮМ в 1974 г.

Вариант № 2

По современным меркам 48-битный размер ключа шифрования является абсолютно недостаточным; видимо, подобные мысли были и у разработчиков алгоритма Lucifer, поэтому уже в том же 1971 г. появился второй вариант алгоритма, шифрующий данные 64-битным ключом. Однако второй вариант шифровал блоками всего по 32 бита, что также явно недостаточно (поскольку при ^-битном блоке после зашифровывания порядка 2^2 блоков открытого текста на одном и том же ключе начинает происходить утечка информации о шифруемых данных — см., например, [120]).

Этот вариант алгоритма, как и предыдущий, запатентован фирмой IBM и описан в патенте [360].

Между вариантами № 2 и № 1 существенно больше различий, чем сходств. Второй вариант алгоритма разбивает шифруемый 32-битный блок данных на два субблока по 16 битов и выполняет 16 раундов преобразований, в каждом из которых выполняется следующая последовательность операций (общая структура алгоритма приведена на рис. 3.117):

1.     Шифруемый блок данных разбивается на два субблока: А и В.

2.     Субблок А разбивается на 4 фрагмента по 4 бита, каждый из которых обрабатывается раздельно (см. рис. 3.118), т. е. остальные операции повторяются для каждого фрагмента.

Рис. 3.119. Структура варианта № 3

Многократное повторение этих операций и представляет собой алгоритм шифрования.

В статье [25] не указывается подавляющее большинство параметров алгоритма: нет ни точного количества раундов, ни значений таблиц замен и перестановок, не указаны размер блока и ключа (128-битные блоки и ключи указываются лишь в качестве возможных значений). Таким образом, данный вариант алгоритма Lucifer является еще более «шаблонным», чем вариант № 1.

Стоит отметить тот факт, что даже всемирно известные эксперты в области криптографии делают различные предположения о том, какой из вариантов алгоритма Lucifer был предшественником алгоритма DES. Например, в [263] «прямым предшественником» DES назван алгоритм, описанный в патенте [360] (т. е. вариант № 2), тогда как в [28] сказано, что DES разработан на базе 128-битного алгоритма Lucifer, т. е. варианта № 3 (вариант № 4 появился существенно позже, чем DES, поэтому предшественником быть не мог). Видимо, решающим фактором в пользу алгоритма № 3 стоит считать тот факт, что описывающий DES патент [143] ссылается именно на статью [25] в качестве первоисточника.

Вариант № 4

Можно утверждать, что вариант № 4 похож одновременно на три предыдущих. Как и в варианте № 2, здесь выполняется разбиение 128-битного шифруемого блока на два субблока, один из которых обрабатывается следующим образом (рис. 3.120) [338]:

1. Выполняется наложение ключа раунда путем применения операции XOR к битам обрабатываемого субблока и 64-битного фрагмента ключа раунда KXt (/ — номер текущего раунда).

Рис. 3.120. Структура варианта № 4

2. Управляемая ключом табличная замена выполняется весьма похоже на варианты № 1 и № 3:

•                если значение j-rо бита (у = 0…7) 8-битного управляющего фрагмента ключа раунда KS( равно 1, ниблы j-r о байта обрабатываемого субблока меняются местами;

•                старший нибл каждого байта «прогоняется» через таблицу замен 50, младший— через Sj. Таблицы определены следующим образом (табл. 3.74).

Таблица 3.74

 

Входное значение

0

1

2

3

4

5

6

7

8

9

10

и

12

13

14

15

So

12

15

7

10

14

13

11

0

2

6

3

1

9

4

5

8

S.

7

2

14

9

3

11

0

4

12

13

1

10

6

15

8

5

3. Выполняется фиксированная перестановка (Р) битов субблока согласно табл. 3.75.

Таблица 3.75

10

21

52

56

27

1

47

38

18

29

60

0

35

9

55

46

26

37

4

8

43

17

63

54

34

45

12

16

51

25

7

62

42

53

20

24

59

33

15

6

50

61

28

32

3

41

23

14

58

5

36

40

11

49

31

22

2

13

44

48

19

57

39

30

Значение входного бита 10 (здесь биты нумеруются слева направо, начиная с 0-го) помещается в выходной бит 0, значение 21-го бита — в бит 1 и т. д.

4.     Результат предыдущей операции накладывается на необработанный субблок операцией XOR.

5.     Субблоки меняются местами (во всех раундах, кроме последнего).

Всего выполняется 16 раундов описанных выше преобразований.

Процедура расширения ключа решает задачу получения 16 ключей раундов по 72 бита каждый (64 бита KXt и 8 битов KS{) из исходного 128-битного ключа шифрования. Расширение выполняется весьма простым способом:

1.     В качестве фрагмента KSt используется первый байт ключа шифрования (считая байты ключа слева направо, начиная с 1).

2.     В качестве фрагмента KXt используются первые 8 байтов ключа шифрования (т. е. первый байт ключа используется в обоих фрагментах).

3.     Ключ шифрования циклически сдвигается влево на 7 байтов, после чего аналогично «набираются» фрагменты ключа для следующего раунда.

В отличие от вариантов № 1 и № 3, вариант № 4 описан достаточно подробно для его реализации, как программной, так и аппаратной.

Криптоанализ вариантов алгоритма

Какие-либо криптоаналитические работы, посвященные вариантам № 1 и № 2 алгоритма Lucifer, не получили широкую известность. Двум последним вариантам «повезло» больше; известны следующие результаты их криптоанализа.

? В 1991 г. Эли Бихам и Эди Шамир исследовали вариант № 3 [77]. Для определенности они использовали перестановку Р из алгоритма DES, а в качестве таблиц S0 и Si были взяты строки 3 и 4 таблицы замен S{ алгоритма DES (табл. 3.76).

Таблица 3.76

 

Входное значение

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

So

4

1

14

8

13

6

2

11

15

12

9

7

3

10

5

0

5,

15

12

8

2

4

9

1

7

5

11

3

14

10

0

6

13

Согласно [77], 8-раундовый вариант № 3 с 32-битным блоком вскрывается при наличии всего 24 выбранных открытых текстов и соответствующих им шифртекстов путем выполнения порядка 221 тестовых операций шифрования.

В той же работе Бихам и Шамир описали возможную атаку на аналогичный алгоритм со 128-битным блоком, для успешного осуществления которой требуется 60-70 выбранных открытых текстов и порядка 253 операций шифрования.

Кроме того, Бихам и Шамир утверждали, что вариант № 4 является еще более слабым.

? Последнее утверждение было доказано в работе [48], которую опубликовали Ишаи Бен-Аройя и Эли Бихам в 1993 г. В ней описана атака на вариант № 4 алгоритма Lucifer, в котором обнаружилось подмножество ключей (весьма большое — около 55 % всех возможных значений ключа), слабых к дифференциальному криптоанализу. При использовании ключа шифрования из данного подмножества алгоритм вскрывается при наличии

236 выбранных открытых текстов.

Данные криптоаналитические исследования развеяли широко распространенный миф о том, что «превращение» алгоритма Lucifer в DES ослабило алгоритм. Статьи [48] и [77] доказывают обратное— Lucifer существенно менее стоек, чем DES.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

1 комментарий »

 
  • Плотников says:

    Интересно было прочитать об истории алгоритма, к тому же я дома по работе использую его периодически. Шифрую программой cybersafe, она поддерживает и его и алгоритм efs, которым я регулярно пользуюсь для прозрачного шифрования.
    Вообще, история шифрования очень занимательная штука – я как-то пол дня просидел, переходя из ссылки к ссылке , зачитывался )
    Автору спасибо.

 

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100