Rambler's Top100
Английский язык
Алгоритмы шифрования
Опубликовано 22 декабря 2007 года

       Как было обещано в предыдущей части статьи,  рассмотрим алгоритмы семейства SHACAL, один из которых стал победителем конкурса NESSIE в части алгоритмов с большим размером шифруемого блока данных.

Кроме того, в данной статье будет рассмотрен алгоритм Khazad – один из алгоритмов-финалистов, но не победителей конкурса NESSIE.

 

Алгоритмы семейства SHACAL

 

Алгоритмы семейства SHACAL имеют весьма интересную структуру – они основаны на преобразованиях, используемых функциями хэширования семейства SHA (Secure Hash Algorithm). Алгоритмы SHA являются основой стандарта хэширования США SHS (Secure Hash Standard) [8], в связи с чем данные алгоритмы получили широчайшее распространение.

Подобное «родство» алгоритма симметричного шифрования и алгоритма хэширования в данном случае интересно, в частности, по следующим соображениям:

1.     Алгоритмы SHACAL основаны на очень тщательно исследованных криптоаналитиками алгоритмах SHA. Действительно, за годы, в течение которых SHA являются стандартом хэширования (с 1993 г.), данные алгоритмы были весьма тщательно исследованы. И можно утверждать, что семейство SHACAL «унаследовало» результаты криптоанализа алгоритмов SHA.

2.     Достаточно часто алгоритмы хэширования используются вместе с алгоритмами шифрования. Алгоритм семейства SHACAL и соответствующий ему алгоритм SHA могут быть весьма просто реализованы «в паре», поскольку они разделяют один и тот же набор функций.

Семейство SHACAL разработано двумя специалистами французской корпорации Gemplus, которая известна как один из крупнейших в мире производителей смарт-карт и оборудования для работы с ними. Авторы алгоритма: Хелена Хандшух (Helena Handschuh) и Давид Насаш (David Naccache).

 

SHACAL-1

 

Алгоритм SHACAL-1 (или просто SHACAL) был изначально предложен на конкурс NESSIE [10]. Он основан на преобразованиях алгоритма SHA-1. Данная статья не содержит описания функций SHA (подробное описание можно найти в [8]) – здесь описаны только те преобразования, которые используются непосредственно в алгоритме шифрования.

Итак, SHACAL-1 шифрует 160-битный блок данных с использованием 512-битного ключа шифрования. Допускается использование более коротких ключей шифрования (не короче 128 бит), которые перед выполнением расширения ключа (процедура расширения ключа также унаследована от SHA-1 и будет описана ниже) должны быть дополнены нулевыми битами для достижения 512-битного размера.

В алгоритме SHACAL-1 предусмотрено 80 раундов шифрования. Шифруемое сообщение представляется в виде пяти 32-битных субблоков A, B, C, D и E, над которыми в каждом раунде выполняются следующие действия (см. рис. 1 Раунд алгоритма SHACAL-1.):

Ai+1 = Ki + (Ai <<< 5) + fi(Bi, Ci, Di) + Ei + Mi,

Bi+1 = Ai,

Ci+1 = Bi <<< 30,

Di+1 = Ci,

Ei+1 = Di,

где i – номер раунда (i = 0…79),

Ki – фрагмент расширенного ключа для i-го раунда,

fi – функция для i-го раунда (см. ниже),

<<< – операция побитового циклического сдвига влево,

Mi – модифицирующие константы, определенные следующим образом (указаны шестнадцатеричные значения):

Раунды

Значение константы

0…19

5A827999

20…39

6ED9EBA1

40…59

8F1BBCDC

60…79

CA62C1D6

Используемые в раундах функции fi определены так:

Раунды

Функция

0…19

f(x, y, z) = (x & y) | (x’ & z)

20…39, 60…79

f(x, y, z) = x Å y Å z

40…59

f(x, y, z) = (x Å y) | (x Å z) | (y Å z)

В таблице символами &, | и Å обозначены, соответственно, побитовые логические операции «и», «или» и «исключающее или» (XOR); x обозначает побитовый комплемент к x.

Шифртекстом является конкатенация содержимого переменных A80, B80, C80, D80 и E80.

Процедура расширения ключа в алгоритме SHACAL-1 также весьма проста, она выполняется в два этапа:

Этап 1.     512-битный исходный ключ шифрования делится на 16 фрагментов по 32 бита K0K15.

Этап 2.     Остальные фрагменты расширенного ключа K16K79 вычисляются из первых 16 фрагментов следующим образом:

Ki = (Ki-3 Å Ki-8 Å Ki-14 Å Ki-16) <<< 1.

Ни в [10], ни в [11] авторы алгоритма не описали процесс расшифрования алгоритмом SHACAL. Такое описание можно найти, например, в работе [13]. Согласно этому описанию, раунды расшифрования выполняются в обратной последовательности; каждый из них подразумевает выполнение следующих операций (см. рис. 2 Раунд расшифрования алгоритма SHACAL-1):

Ai = Bi+1,

Bi = Ci+1 <<< 2,

Ci = Di+1,

Di = Ei+1,

Ei = K’i + (Bi+1 <<< 5)’ + fi’(Ci+1 <<< 2, Di+1, Ei+1) + Ai+1 + M’i + 4,

Здесь и далее запись f’(x) обозначает побитовый комплемент результата выполнения операции f(x).

Поражает простота алгоритма SHACAL – достаточно сравнить его с описанными в предыдущей части статьи алгоритмами MISTY1 и Camellia, чтобы убедиться, что структура алгоритма крайне проста. Из этого следуют следующие достоинства данного алгоритма:

·       простота реализации;

·       легкая доказуемость отсутствия каких-либо внедренных авторами недокументированных возможностей;

Кроме того, стоит отметить, что SHACAL предъявляет весьма низкие требования к ресурсам и обладает высоким быстродействием. Высокая скорость шифрования данным алгоритмом на всех тестируемых платформах была отмечена, например, в [24]. А авторы [17] описали архитектуру шифратора, выполняющего шифрование по алгоритму SHACAL-1 со скоростью 17 гигабит в секунду, что вряд ли достижимо (в разумных ценовых пределах) для подавляющего большинства других алгоритмов шифрования.

 

SHACAL-0

 

Стоит отметить, что в некоторых работах (например, в [26]) наряду с алгоритмом SHACAL-1 упоминается некий алгоритм SHACAL-0. Видимо, имеется в виду возможный (не предложенный авторами семейства SHACAL) вариант, основанный на функции SHA-0. Такой вариант отличался бы от SHACAL-1 только процедурой расширения ключа, в которой в описанной выше формуле вычисления Ki отсутствовал бы циклический сдвиг влево на 1 бит [10].

 

SHACAL-2

 

В 2001 г. авторы алгоритма SHACAL-1 воспользовались тем, что в течение конкурса NESSIE можно было вносить некоторые незначительные изменения в алгоритм, и представили новый вариант алгоритма SHACALSHACAL-2 [11].

Стоит сказать, что в данном случае различия между алгоритмами SHACAL-1 и SHACAL-2 сложно считать несущественными. SHACAL-2 основан на преобразованиях более нового алгоритма хэширования – SHA-256 [8], который принципиально отличается от SHA-1.

SHACAL-2 шифрует данные 256-битными блоками с использованием 512-битного ключа. Аналогично алгоритму SHACAL-1, допускается использование ключей меньших размеров (не менее 128 бит), которые дополняются битовыми нулями до 512 бит.

Шифруемый блок данных делится на 8 фрагментов по 32 бита (которые обозначены буквами AH). Алгоритм выполняет 64 раунда преобразований, в каждом из которых данные фрагменты обрабатываются следующим образом (см. рис. 3 Раунд алгоритма SHACAL-2):

T = Hi + S1(Ei) + Ch(Ei, Fi, Gi) + Mi + Ki,

Hi+1 = Gi,

Gi+1 = Fi,

Fi+1 = Ei,

Ei+1 = Di + T,

Di+1 = Ci,

Ci+1 = Bi,

Bi+1 = Ai,

Ai+1 = T + S0(Ai) + Maj(Ai, Bi, Ci).

где T – временная переменная.

Используемые функции определены следующим образом:

S0(x) = (x >>> 2) Å (x >>> 13) Å (x >>> 22),

S1(x) = (x >>> 6) Å (x >>> 11) Å (x >>> 25),

Ch(x, y, z) = (x & y) Å (x’ & z),

Maj(x, y, z) = (x & y) Å (x & z) Å (y & z),

где >>> – операция побитового циклического сдвига вправо.

Модифицирующие константы Mi (i = 0…63) приведены в таблице (по порядку от M0 до M63):

428a2f98

71374491

b5c0fbcf

e9b5dba5

3956c25b

59f111f1

923f82a4

ab1c5ed5

d807aa98

12835b01

243185be

550c7dc3

72be5d74

80deb1fe

9bdc06a7

c19bf174

e49b69c1

efbe4786

0fc19dc6

240ca1cc

2de92c6f

4a7484aa

5cb0a9dc

76f988da

983e5152

a831c66d

b00327c8

bf597fc7

c6e00bf3

d5a79147

06ca6351

14292967

27b70a85

2e1b2138

4d2c6dfc

53380d13

650a7354

766a0abb

81c2c92e

92722c85

a2bfe8a1

a81a664b

c24b8b70

c76c51a3

d192e819

d6990624

f40e3585

106aa070

19a4c116

1e376c08

2748774c

34b0bcb5

391c0cb3

4ed8aa4a

5b9cca4f

682e6ff3

748f82ee

78a5636f

84c87814

8cc70208

90befffa

a4506ceb

bef9a3f7

c67178f2

Фрагменты расширенного ключа K0K63 вычисляются в процессе процедуры расширения ключа, которая выполняется следующим образом:

Этап 1.     Аналогично алгоритму SHACAL-1, 512-битный исходный ключ шифрования делится на 16 фрагментов по 32 бита K0K15.

Этап 2.     Остальные фрагменты расширенного ключа K16K63 вычисляются из первых 16 фрагментов следующим образом:

Ki = O1(Ki-2) + Ki-7 + O0(Ki-15) + Ki-16,

где функции O0 и O1 определены так:

O0(x) = (x >>> 7) Å (x >>> 18) Å (x >> 3),

O1(x) = (x >>> 17) Å (x >>> 19) Å (x >> 10),

где >> – операция побитового сдвига (не циклического) вправо.

Аналогично алгоритму SHACAL-1 авторы SHACAL-2 в [11] не описали процесс расшифрования. Такое описание можно найти в работе [13]. Раунды расшифрования алгоритма выполняются в обратной последовательности; в каждом из них производятся следующие действия (см. рис. 4 Раунд расшифрования алгоритма SHACAL-2):

T = Ai+1 + S0’(Bi+1) + Maj’(Bi+1, Ci+1, Di+1) + 2,

Hi = T + S1’(Fi+1) + Ch’(Fi+1, Gi+1, Hi+1) + Mi’ + Ki’ + 4,

Gi = Hi+1,

Fi = Gi+1,

Ei = Fi+1,

Di = Ei+1 + T’ + 1,

Ci = Di+1,

Bi = Ci+1,

Ai = Bi+1.

 

Криптоанализ алгоритма SHACAL-1

 

Первичный криптоанализ алгоритма SHACAL-1 был выполнен авторами алгоритма в [9] и [10], где была отмечена стойкость алгоритма к линейному и дифференциальному криптоанализу.

В дальнейшем, как отмечено авторами [3], SHACAL подвергся массированному криптоанализу со стороны ряда экспертов. Из криптоаналитических исследований данного алгоритма стоит отметить следующие:

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

·       Ряд экспертов из университета г. Сеул, Корея, предложили атаку усовершенствованным методом бумеранга (см. цикл статей «Современные методы вскрытия алгоритмов шифрования») на SHACAL-1 с различным размером ключа шифрования. Основные результаты таковы [14]:

Размер ключа, бит

Количество раундов

Требуемое количество выбранных открытых текстов

Количество тестовых операций шифрования

160

37

2158,8

287,8

256

39

2158,5

2250,8

512

47

2158,5

2508,4

·       В работе [4] были скорректированы результаты предыдущей работы: предложенная атака на вариант с 512-битным ключом распространена на 49 раундов, для ее осуществления требуется 2151,9 выбранных открытых текстов или выбранных шифртекстов и 2508,5 операций.

·       Уже после конкурса NESSIE, в 2006 г. вышла работа [15], в которой предложена лучшая на текущий момент атака на алгоритм SHACAL-1 из атак, не использующих связанные ключи. Атака на 55 раундов SHACAL-1 c 512-битным ключом использует дифференциальный криптоанализ, она успешна при наличии 2154 выбранных шифртекстов и при выполнении 2507,26 операций шифрования. В данной работе предложены и некоторые другие варианты атак на SHACAL-1.

·       В том же году авторы работы [7] сделали вывод, что, в связи с «наследственностью» SHACAL-1 от SHA-1, новые результаты в поиске коллизий в SHA-1 будут выливаться в новые атаки на SHACAL-1 на связанных ключах, которые действуют, как минимум, на класс слабых ключей. В данной работе была предложена первая атака на полнораундовый SHACAL-1 с 512-битным ключом с использованием 4-х связанных ключей. Для этой атаки требуется 2159,8 выбранных открытых текстов и 2423 операций шифрования или 2153,8 выбранных открытых текстов и 2504,2 операций. Авторы отмечают, что атака является абсолютно теоретической, поскольку требуемые для атаки ресурсы абсолютно превышают существующие вычислительные возможности.

·       А в совсем недавней работе [3] предыдущая атака была усилена: авторами работы предложено несколько вариантов атак, одна из которых требует наличия 2101,3 выбранных открытых текстов, зашифрованных на 8 связанных ключах, и выполнения 2101,3 операций. По сравнению с предыдущей атакой, предложенная в [3] атака выглядит существенно более практичной, что позволило ее авторам сделать вывод о структуре алгоритма SHACAL-1: «Использование линейной процедуры расширения ключа совместно с раундами схожей структуры – не лучший способ создания стойких блочных шифров».

Кроме того, в работе [19] утверждается, что SHACAL относительно сложно защищаем от атак по потребляемой мощности.

По результатам первого этапа конкурса NESSIE алгоритм SHACAL-1 был выбран в финал конкурса. Эксперты отметили, что в алгоритме не найдено уязвимостей, а также высокое быстродействие алгоритма. Кроме того, интересной показалась возможность интеграции алгоритмов SHACAL-1 и SHA-1, о которой было сказано выше [23].

Однако, в финале конкурса SHACAL-1 не оказался в числе алгоритмов-победителей из-за сомнений экспертов в стойкости его процедуры расширения ключа [21].

 

Криптоанализ алгоритма SHACAL-2

 

В рамках конкурса NESSIE не было найдено каких-либо уязвимостей в алгоритме SHACAL-2. Мало того, во время конкурса не были известны какие-либо атаки даже на усеченные версии алгоритма [22]. SHACAL-2 стал одним из победителей конкурса NESSIE [21], причем, помимо криптостойкости, эксперты отметили и высочайшую скорость шифрования данным алгоритмом [23].

Уже после окончания конкурса начали появляться различные работы, посвященные атакам на варианты алгоритма SHACAL-2 с уменьшенным числом раундов. Например, в работе [16] предложена атака на 42-раундовый вариант SHACAL-2 с 512-битным ключом, для которой требуется наличие 2243,38 выбранных открытых текстов на двух связанных ключах и 2488,37 операций.

В работе [13] описаны другие варианты атак на SHACAL-2, однако, они менее эффективны, чем упомянутая выше атака на 42 раунда алгоритма.

Алгоритмы симметричного шифрования, основанные на хэш-функциях, были предложены различными криптологами задолго до алгоритма SHACAL (например, алгоритмы Bear, Lion и Lioness, подробно описанные в [29]). Однако, все они имели те или иные проблемы с криптостойкостью и/или быстродействием. Таким образом, на сегодняшний день алгоритм SHACAL-2 является единственным широко известным алгоритмом (из основанных на хэш-функциях), не имеющим проблем с криптостойкостью и обладающим высокой скоростью шифрования.

 

Алгоритм Khazad

 

Алгоритм Khazad разработан специально для участия в конкурсе NESSIE интернациональным дуэтом специалистов: Пауло Баррето (Paulo Sergio L.M. Barreto) из Бразилии и Винсентом Риджменом (Vincent Rijmen) из Бельгии. Последний широко известен в мире как один из разработчиков стандарта шифрования США AES (см. статью «Алгоритм шифрования AES и его криптоанализ»). Название алгоритма произошло от названия Казад-Дум (Khazad-dum) – Подгорного Царства гномов из трилогии Дж. Р.Р. Толкиена «Властелин Колец» [12].

 

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

 

Предшественником алгоритма Khazad считается разработанный в 1995 г. Винсентом Риджменом и Джоан Деймен (Joan Daemen) алгоритм SHARK (SHARK подробно описан в [28]). Авторы Khazad утверждают, что в основе алгоритма лежит стратегия разработки криптографически стойких алгоритмов шифрования (Wide-Trail Strategy), предложенная Джоан Деймен в работе [6].

Khazad шифрует 64-битные блоки данных с использованием 128-битного ключа шифрования. Алгоритм Khazad представляет блок данных в виде строки из 8 байт, которая обрабатывается в каждом раунде алгоритма следующей последовательностью операций [1]:

1.     Табличная замена g: значение каждого байта строки заменяется с помощью следующей таблицы S(x):

A7[1]

D3

E6

71

D0

AC

4D

79

3A

C9

91

FC

1E

47

54

BD

8C

A5

7A

FB

63

B8

DD

D4

E5

B3

C5

BE

A9

88

0C

A2

39

DF

29

DA

2B

A8

CB

4C

4B

22

AA

24

41

70

A6

F9

5A

E2

B0

36

7D

E4

33

FF

60

20

08

8B

5E

AB

7F

78

7C

2C

57

D2

DC

6D

7E

0D

53

94

C3

28

27

06

5F

AD

67

5C

55

48

0E

52

EA

42

5B

5D

30

58

51

59

3C

4E

38

8A

72

14

E7

C6

DE

50

8E

92

D1

77

93

45

9A

CE

2D

03

62

B6

B9

BF

96

6B

3F

07

12

AE

40

34

46

3E

DB

CF

EC

CC

C1

A1

C0

D6

1D

F4

61

3B

10

D8

68

A0

B1

0A

69

6C

49

FA

76

C4

9E

9B

6E

99

C2

B7

98

BC

8F

85

1F

B4

F8

11

2E

00

25

1C

2A

3D

05

4F

7B

B2

32

90

AF

19

A3

F7

73

9D

15

74

EE

CA

9F

0F

1B

75

86

84

9C

4A

97

1A

65

F6

ED

09

BB

26

83

EB

6F

81

04

6A

43

01

17

E1

87

F5

8D

E3

23

80

44

16

66

21

FE

D5

31

D9

35

18

02

64

F2

F1

56

CD

82

C8

BA

F0

EF

E9

E8

FD

89

D7

C7

B5

A4

2F

95

13

0B

F3

E0

37

Данная таблица заменяет значение 0 на A7, 1 – на D3 и т.д.

Стоит сказать, что таблица полностью эквивалентна используемой в алгоритме Anubis (это еще один алгоритм шифрования, представленный на конкурс теми же авторами, его подробное описание можно найти в [27]). Значения таблицы соответствуют следующему соотношению:

S(S(x)) = x.

2.     Преобразование q, которое заключается в умножении байтовой строки данных на фиксированную матрицу H:

1

3

4

5

6

8

B

7

3

1

5

4

8

6

7

B

4

5

1

3

B

7

6

8

5

4

3

1

7

B

8

6

6

8

B

7

1

3

4

5

8

6

7

B

3

1

5

4

B

7

6

8

4

5

1

3

7

B

8

6

5

4

3

1

3.     Наложение материала ключа s(Ki): на блок данных операцией XOR накладывается 8-байтный фрагмент расширенного ключа Ki для текущего раунда i. Процедура расширения ключа подробно описана ниже.

В алгоритме предусмотрено выполнение восьми раундов, перед первым из которых выполняется входное отбеливание – операция s с фрагментом ключа K0 (раунды нумеруются, начиная с 1). В последнем раунде алгоритма не выполняется операция q. Т.е. последовательность операций при зашифровании выглядит следующим образом:

s(K0) ® (g ® q ® s(K1)) ®® (g ® q ® s(K7)) ® g ® s(K8).

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

s(K8) ® (g ® q ® s(q(K1))) ®® (g ® q ® s(q(K7))) ® g ® s(K0).

Тот факт, что данная последовательность действий приведет к корректному расшифрованию, доказан в спецификации алгоритма [1].

Процедура расширения ключа также весьма проста. Она выполняется в два этапа, на первом из которых инициализируются 64-битные переменные K-1 и K-2: в качестве K-2 берутся первые 8 байт исходного ключа шифрования, в качестве K-1 – оставшиеся 8 байт.

Затем вычисляется последовательность подключей K0K8 следующим образом:

Ki = f(Ci, Ki-1) Å Ki-2,

где f(x, y) – функция раунда алгоритма, т.е. последовательная обработка 64-битной переменной x операциями g, q и s(y),

Ci – набор 64-битных констант; каждый j-й байт константы Ci вычисляется так:

Ci,j = S(8i + j).

 

Модификация алгоритма

 

Пользуясь возможностью незначительного изменения алгоритма в течение первого раунда конкурса, авторы Khazad также внесли изменения в свой алгоритм. В новом варианте спецификации алгоритма [1] исходный алгоритм Khazad назван Khazad-0, а название Khazad присвоено модифицированному алгоритму.

Изменения коснулись только таблицы замен: теперь для упрощения аппаратной реализации алгоритма таблица замен является суперпозицией двух других таблиц замен (замещающих 4-битные значения) P и Q (структура таблицы замен приведена на рис. 5 Структура таблицы замен модифицированного алгоритма Khazad).

P:

3

F

E

0

5

4

B

C

D

A

9

6

7

8

2

1

Q:

9

E

5

6

A

2

3

C

F

0

4

D

7

B

1

8

В зависимости от ресурсов шифратора таблица S может быть реализована как с помощью приведенных таблиц P и Q, так и напрямую. Сама модифицированная таблица S выглядит следующим образом:

BA

54

2F

74

53

D3

D2

4D

50

AC

8D

BF

70

52

9A

4C

EA

D5

97

D1

33

51

5B

A6

DE

48

A8

99

DB

32

B7

FC

E3

9E

91

9B

E2

BB

41

6E

A5

CB

6B

95

A1

F3

B1

02

CC

C4

1D

14

C3

63

DA

5D

5F

DC

7D

CD

7F

5A

6C

5C

F7

26

FF

ED

E8

9D

6F

8E

19

A0

F0

89

0F

07

AF

FB

08

15

0D

04

01

64

DF

76

79

DD

3D

16

3F

37

6D

38

B9

73

E9

35

55

71

7B

8C

72

88

F6

2A

3E

5E

27

46

0C

65

68

61

03

C1

57

D6

D9

58

D8

66

D7

3A

C8

3C

FA

96

A7

98

EC

B8

C7

AE

69

4B

AB

A9

67

0A

47

F2

B5

22

E5

EE

BE

2B

81

12

83

1B

0E

23

F5

45

21

CE

49

2C

F9

E6

B6

28

17

82

1A

8B

FE

8A

09

C9

87

4E

E1

2E

E4

E0

EB

90

A4

1E

85

60

00

25

F4

F1

94

0B

E7

75

EF

34

31

D4

D0

86

7E

AD

FD

29

30

3B

9F

F8

C6

13

06

05

C5

11

77

7C

7A

78

36

1C

39

59

18

56

B3

B0

24

20

B2

92

A3

C0

44

62

10

B4

84

43

93

C2

4A

BD

8F

2D

BC

9C

6A

40

CF

A2

80

4F

1F

CA

AA

42

 

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

 

Первичный криптоанализ алгоритма был выполнен его авторами: в [1] утверждается, что Khazad обладает высокой криптостойкостью против линейного и дифференциального криптоанализа, использования усеченных дифференциалов, атак на связанных ключах и ряда других.

Khazad не привлек такого пристального внимания криптоаналитиков, как рассмотренные ранее алгоритмы MISTY1, Camellia и SHACAL – известно существенно меньше работ, посвященных его криптоанализу, среди которых можно отметить следующие:

·       Некоторые недочеты первичного криптоанализа Khazad (незначительно снижающие заявленную авторами алгоритма стойкость к линейному криптоанализу) были указаны авторами работы [2].

·       В работе [18] предлагается атака на 5-раундовый Khazad методом интегрального криптоанализа, для которой требуется 264 выбранных открытых текстов (т.е., фактически, результаты зашифрования всех возможных значений блока открытого текста).

·       В работе [19] показано, что реализации Khazad легко защищаемы от атак по потребляемой мощности.

·       Авторы [20] применили против алгоритма Khazad дифференциальный анализ на основе сбоев (см. статью «Атаки на шифраторы с использованием утечек данных по побочным каналам»). Полнораундовый Khazad может быть вскрыт всего при наличии трех шифртекстов с внесенной ошибкой, однако, модель атаки не является реалистичной.

·       В работе [5] найден класс из 264 слабых ключей, при использовании которых 5-раундовый Khazad вскрывается при наличии 234 выбранных открытых текстов или шифртекстов.

Как видно, никаких сколько-нибудь серьезных проблем с криптостойкостью алгоритма Khazad обнаружено не было, что отмечено и экспертами конкурса NESSIE [21]. Кроме того, экспертами отмечена весьма высокая скорость шифрования данного алгоритма [24]. Khazad был признан перспективным алгоритмом, весьма интересным для дальнейшего изучения, но не стал одним из победителей конкурса из-за подозрений экспертов, что структура алгоритма может содержать скрытые уязвимости, которые могут быть обнаружены в будущем [21].

 

 

1.          Barreto P.S.L.M., Rijmen V. The Khazad Legacy-Level Block Cipher. // http://www.cosic.esat.kuleuven.be[2].

2.          Biham E., Dunkelman O., Furman V., Mor T. Preliminary Report on the NESSIE Submissions: Anubis, Camellia, Khazad, IDEA, Misty1, NIMBUS, and Q. // http://www.cosic.esat.kuleuven.be – Technion, Haifa, Israel.

3.          Biham E., Dunkelman O., Keller N. A Simple Related-Key Attack on the Full SHACAL-1. // http://www.cosic.esat.kuleuven.be.

4.          Biham E., Dunkelman O., Keller N. Rectangle Attacks on 49-Round SHACAL-1. // http://vipe.technion.ac.il – Technion, Haifa, Israel.

5.          Biryukov A. Analysis of Involutional Ciphers: Khazad and Anubis. // http://citeseer.ist.psu.edu – Katholieke Universiteit Leuven, Belgium.

6.          Daemen J. Cipher and Hash Function Design Strategies Based on Linear and Differential Cryptanalysis. // http://homes.esat.kuleuven.be – 1995.

7.          Dunkelman O., Keller N., Kim J. Related-Key Rectangle Attack on the Full SHACAL-1. // http://www.cosic.esat.kuleuven.be.

8.          FIPS Publication 180-2. Specifications for the Secure Hash Standard. // http://csrc.nist.gov – 2002 August 1.

9.          Handschuh H., Knudsen L.R., Robshaw M.J. Analysis of SHA-1 in Encryption Mode. // http://citeseer.ist.psu.edu – 2001.

10.       Handschuh H., Naccache D. SHACAL. // http://www.cosic.esat.kuleuven.be – 2000 – Gemplus, Issy-les-Moulineaux.

11.       Handschuh H., Naccache D. SHACAL. // http://www.cosic.esat.kuleuven.be – 2001 – Gemplus, Issy-les-Moulineaux.

12.       Khazad – from Wikipedia, the free encyclopedia. // http://eng.wikipedia.org.

13.       Kim J. Combined Differential, Linear and Related-Key Attacks on Block Ciphers and MAC Algorithms. // http://www.cosic.esat.kuleuven.be – November 2006 – Katholieke Universiteit Leuven, Belgium.

14.       Kim J., Moon D., Lee W., Hong S., Lee S., Jung S. Amplified Boomerang Attack Against Reduced-Round SHACAL. // http://www.iacr.orgKorea University, Seoul, Korea.

15.       Lu J., Kim J., Keller N., Dunkelman O. Differential and Rectangle Attacks on Reduced-Round SHACAL-1. // http://www.cosic.esat.kuleuven.be – 2006.

16.       Lu J., Kim J., Keller N., Dunkelman O. Related-Key Rectangle Attack on 42-Round SHACAL-2. // http://www.cosic.esat.kuleuven.be.

17.       McLoone M., McCanny J.V. Very High Speed 17 Gbps SHACAL Encryption Architecture (Abstract). // http://www.springerlink.com – 2003 – Queen’s University of Belfast, Northern Ireland.

18.       Muller F., A New Attack Against Khazad. // http://www.iacr.org – DCSSI Crypto Lab, Issy-les-Moulineaux, France.

19.       Oswald E., Preneel B. A Theoretical Evaluation of some NESSIE Candidates regarding their Susceptibility towards Power Analysis Attacks. // http://www.iaik.tugraz.at – Katholieke Universiteit Leuven, Belgium – October 4, 2002.

20.       Piret G., Quisquater J.-J. A Differential Fault Attack Technique against SPN Strustures, with Application to the AES and Khazad. // http://www.dice.ucl.ac.be – 2003 – Universite Catolique de Louvain, Belgium.

21.       Portfolio of recommended cryptographic primitives. // http://www.cryptonessie.org – NESSIE consortium, February 27, 2003.

22.       Preneel B., Biryukov A., Oswald E., Van Rompay B., Granboulan L., Dottax E., Murphy S., Dent A., White J., Dichtl M., Pyka S., Schafheutle M., Serf P., Biham E., Barkan E., Dunkelman O., Quisquater J.-J., Ciet M., Sica F., Knudsen L., Parker M., Raddum H. Public Report D20: NESSIE security report. // http://www.cosic.esat.kuleuven.be. – February 19, 2003 – Version 2.0.

23.       Preneel B., Bosselaers A., Ors S.B., Biryukov A., Granboulan L., Dottax E., Murphy S., Dent A., White J., Dichtl M., Pyka S., Serf P., Biham E., Barkan E., Dunkelman O., Ciet M., Sica F., Knudsen L., Raddum H. NESSIE Public Report D18: Update on the selection of algorithms for further investigation during the second round. // http://www.cosic.esat.kuleuven.be. – Version 1.0 – March 11, 2002.

24.       Preneel B., Van Rompay B., Granboulan L., Martinet G., Dichtl M., Schafheutle M., Serf P., Bibliovitz A., Biham E., Dunkelman O., Ciet M., Quisquater J-J., Sica F. NESSIE Public Report D14: Report on the Performance Evaluation of NESSIE Candidates I. // http://www.cosic.esat.kuleuven.be. – Version 3.3 – November 20, 2001.

25.       Saarinen M.-J.O. Cryptanalysis of Block Ciphers Based on SHA-1 and MD5. // http://www.m-js.com – Helsinki University of Technology, Finland.

26.       Xiao L., Heys H.M. An Improved Power Analysis Attack Against Camellia’s Key Schedule. // http://eprint.iacr.org – September 22, 2005.

27.       Панасенко С. Алгоритмы шифрования – участники конкурса NESSIE. Часть 2. // iXBT. – http://www.ixbt.com/soft/nessie-part2.shtml – 10.04.2007 г.

28.       Панасенко С. Интересные алгоритмы шифрования, часть 2. // BYTE/Россия. – 2006 - № 5 – с. 74-79.

29.       Панасенко С. Интересные алгоритмы шифрования, часть 3. // BYTE/Россия. – 2006 – № 10 – с. 74-80.

 

 

Об авторе:

Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.

С автором можно связаться:      по телефонам (495)532-1313, (495)531-0000

или по E-mail develop@ancud.ru

http://www.panasenko.ru

 



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

[2] Существуют два варианта данного документа, не отличающиеся какими-либо атрибутами. Один из вариантов описывает исходную версию алгоритма Khazad, второй – модифицированную.

/  бумажный номер
Тема номера: Bombardier
Читайте на сайте тему номера "Bombardier" и другие статьи из журнала "CIO" от 15 мая 2010 года
  Архив номеров журнала

14:52 / Безопасность Windows 7. DirectAccess
Новости Украины:
Microsoft лучше всех и аналогов пока ему нет
10:20 / Безопасность Windows 7. DirectAccess
Гость:
fghg [url=http://www.gjhjk.org/] gjhk[/url]
17:29 / Безопасность Windows 7. DirectAccess
Гость:
а вот в линуксе...

/  предыдущий номер
Тема номера: Mattel
Читайте на сайте тему номера "Mattel" и другие статьи из журнала "CIO" от 15 декабря 2009 года
  Архив номеров журнала