Алгоритм Skipjack

интересен по многим причинам.

?     Данный алгоритм разработан Агентством Национальной Безопасности США для шифрования в специальных случаях [28].

?     Фактически алгоритм Skipjack представлял собой еще один стандарт шифрования США— разработанный в 1987 г. и существующий одновременно со стандартом DES. Принципиальное различие этих алгоритмов состоит в том, что DES являлся открытым стандартом, алгоритм был опубликован и полностью открыт, что позволило всем заинтересованным специалистам оценить стойкость алгоритма. В отличие от DES, алгоритм Skipjack был долгое время засекречен, его описание стало доступно на сайте института NIST только в 1998 г. [358].

?     Брюс Шнайер в [28] утверждает, что алгоритм является секретным не для повышения его надежности, а для того, чтобы его нельзя было использовать в сторонних реализациях— подразумевалось использование Skipjack только в аппаратных реализациях Clipper и Fortezza. Микросхема Clipper получила скандальную известность благодаря тому, что в ней реализован механизм депонирования ключей. Это означает, что любой ключ шифрования какого-либо пользователя (использующего реализацию Skipjack в микросхеме Clipper) может быть легко вскрыт правительственными чиновниками США, получившими соответствующий ордер. Аналогичный механизм существует и в криптоплате Fortezza. Настойчивое навязывание Clipper пользователям со стороны АНБ стало причиной многочисленных протестов против использования данной системы со стороны различных американских правозащитных организаций. Следствием этого стал факт ограниченного распространения алгоритма Skipjack и его аппаратных реализаций.

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

шифрует данные блоками по 64 бита и использует 80- битный ключ шифрования. В процессе шифрования обработка данных производится по 16-битным словам, т. е. входной блок данных разбивается на 4 слова, обозначаемые wx, vv2 , vv3 и w4 . Выполняются 32 раунда преобразований, причем алгоритм предполагает два варианта функций раундов (функция А и функция В), в каждом раунде задействована только одна из них [358].

Рис. 3.196. Функция А

I

Функция А представлена на рис. 3.196:

1.     Над словом W] выполняется операция G, которая представляет собой зависящее от ключа преобразование (подробно описана далее).

2.     Результат предыдущего шага складывается операцией XOR со значением слова vv4.

3.     Результат предыдущего шага складывается операцией XOR с текущим значением счетчика (см. далее), результат этой операции становится новым значением слова wx.

4.      Текущее значение vv3 замещает старое значение vv4 .

5.     Текущее значение w2 замещает старое значение vv3.

6.     Результат шага 1 становится новым значением w2 .

7.     Значение счетчика увеличивается на 1.

Рис. 3.197. Функция В

Функция В представлена на рис. 3.197:

1.     Над словом Wj выполняется операция G.

2.     Значение слова wx складывается операцией XOR с текущим значением счетчика.

3.     Результат предыдущего шага складывает^ операцией XOR со значением слова w2.

4.      Результат шага 1 становится новым значением слова w2 .

5.     Текущее значение w4 замещает старое значение wx.

6.     Текущее значение vv3 замещает старое значение w4 .

7.     Результат шага 3 становится новым значением слова w3.

8.     Значение счетчика увеличивается на 1.

В процессе зашифровывания 8 раз выполняется функция А, затем 8 раз выполняется функция В, затем эти 16 раундов повторяются, т. е.:

где Р и С — соответственно, открытый текст и результат его зашифровывания.

Перед выполнением этих 32 операций значение счетчика устанавливается в 1.

Расшифровывание производится путем выполнения обратных операций в обратной последовательности. Перед расшифровыванием счетчик устанавливается в 32.

Рис. 3.198. Операция G

Операция G представляет собой 4-раундовую сеть Фейстеля, в которой в каждом раунде выполняются следующие действия (рис. 3.198):

1. Обрабатываемый в текущем раунде байт входного слова (правый в нечетных раундах или левый — в четных) складывается операцией XOR с байтом ключа шифрования Ki, индекс которого определяется по формуле:

где:

•                   к — номер текущего раунда алгоритма;

•                   г — номер текущего раунда операции G.

2. Результат предыдущего шага замещается согласно таблице замен F (табл. 3.132); старший нибл входного значения определяет номер строки

(начиная с нуля), а младший нибл — номер столбца, на пересечении которых находится выходное значение.

Таблица 3.132

A3

D7

09

83

F8

48

F6

F4

ВЗ

21

15

78

99

В1

AF

F9

Е7

2D

4D

СЕ

СА

52

95

D9

38

44

28

OA

DF

02

АО

17

F1

60

68

12

В7

СЗ

Е9

FA

3D

53

96

84

ВА

F2

63

19

АЕ

Е5

F5

F7

16

А2

39

В6

0F

С1

93

81

ЕЕ

В4

ЕА

D0

91

2F

В8

55

В9

DA

85

3F

41

BF

Е0

58

80

5F

66

ОВ

D8

90

35

D5

СО’

А7

33

06

65

69

45

00

94

56

6D

98

76

97

FC

В2

С2

во

FE

DB

20

Е1

ЕВ

D6

Е4

DD

47

1D

42

ED

49

ЗС

CD

43

27

D2

07

D4

DE

С7

67

18

89

СВ

30

IF

8D

С6

8F

АА

С8

74

DC

С9

5D

31

А4

70

88

61

9F

0D

87

50

82

54

64

26

7D

03

40

34

73

D1

С4

ГО

ЗВ

СС

FB

7F

АВ

Е6

ЗЕ

А5

AD

04

23

14

51

22

F0

29

79

71

FF

Е2

ОС

EF

ВС

72

75

6F

37

А1

ЕС

D3

62

86

10

Е8

08

77

11

BE

92

4F

24

С5

32

36

9D

CF

F3

А6

ВВ

АС

А9

13

57

25

В5

ЕЗ

BD

А8

ЗА

01

05

59

46

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

Процедура расширения ключа у данного алгоритма отсутствует— операция G использует байты исходного ключа шифрования по мере необходимости без их предварительной обработки. Однако в спецификации алгоритма Skipjack [358] определен также протокол KEA (Key Exchange Algorithm) — протокол выработки общего симметричного ключа на основе секретного ключа отправителя информации и открытого ключа получателя. Данный протокол базируется на известном алгоритме вычисления общего ключа Диффи—Хеллмана. Очевидно, что 80-битный ключ шифрования может быть как вычислен с помощью алгоритма КЕА, так и задан напрямую, что традиционно для алгоритмов симметричного шифрования.

Криптостойкость алгоритма

В то время, пока алгоритм Skipjack был засекречен, у пользователей и специалистов возникало множество вопросов по поводу его криптостойкости: пусть в реализациях алгоритма присутствует механизм депонирования ключей, позволяющий уполномоченным лицам вычислить сессионный ключ; но достаточно ли надежен сам секретный алгоритм? Нет ли в нем каких-либо случайных или преднамеренно внедренных разработчиками уязвимостей?

Скорее всего, стремясь пресечь слухи о возможных слабостях алгоритма, в 1993 г. АНБ передало спецификацию алгоритма и сопроводительную документацию к нему пяти известным экспертам в области криптологии для изучения алгоритма и опубликования отчета, который не должен был содержать описания внутренней реализации алгоритма, однако должен был дать понять (не в последнюю очередь благодаря авторитету изучавших алгоритм экспертов) заинтересованным лицам, что алгоритм Skipjack является криптографически стойким.

Отчет экспертов [105] появился в июле 1993 г. и содержал, в частности, следующие выводы:

?      благодаря 80-битному ключу алгоритма Skipjack (сравнивая с 56-битным ключом DES), учитывая предполагаемую скорость развития вычислительной техники, крайне незначителен риск взлома алгоритма перебором всех возможных вариантов ключа (атака методом «грубой силы» ) в ближайшие 30-40 лет;

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

. тоанализа;

?      криптостойкость алгоритма Skipjack не зависит от секретности самого алгоритма.

Причем по поводу второго из приведенных выводов эксперты сделали оговорку, что за предоставленное им время серьезный анализ алгоритма провести невозможно, поэтому вывод базируется только на изучении ими критериев и процесса разработки и тестирования алгоритма, проведенных в АНБ.

Полномасштабный криптоанализ алгоритма Skipjack начался уже после опубликования его спецификации в 1998 г. В том же году вышла работа ряда специалистов из Израиля [61], в которой, в частности, было отмечено свойство несимметричности ключа шифрования Skipjack, незначительно снижающее трудоемкость полного перебора ключей. В этой же работе было представлено несколько атак на усеченные версии алгоритма с неполным количеством раундов и другими изменениями. Стоит отметить одну из опубликованных атак, действовавшую против варианта Skipjack, в котором не было всего трех операций XOR по сравнению со стандартной версией — в раундах № 4, 16 и 17. Такая версия алгоритма получила название Skipjack- 3XOR. Интересно, что удаление всего трех операций XOR из 320 подобных операций приводит к полной слабости алгоритма— в этом случае ключ

вскрывается при наличии 29 пар блоков открытого текста и шифртекста выполнением всего около миллиона операций шифрования.

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

Были предприняты и более поздние попытки криптоанализа алгоритма Skipjack (например, [166, 225]), однако все они оказались неспособными взломать полноценную и полнораундовую версию алгоритма. При этом многие криптоаналитики высказывали мнение, что успешность атак на усеченные версии алгоритма говорит о его потенциальной слабости, что, впрочем, не доказано.

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

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

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