Алгоритмы шифрования – участники конкурса NESSIE. Часть 1


Конкурс NESSIE

Европейский конкурс криптоалгоритмов NESSIE стартовал несколько позже конкурса AES (см. статью «Алгоритмы шифрования – финалисты конкурса AES», часть 1 и часть 2) – в феврале 2000 г. NESSIE – аббревиатура от New European Schemes for Signature, Integrity, and Encryption – новые европейские алгоритмы подписи, обеспечения целостности и шифрования. Как видно из названия алгоритма, цели конкурса NESSIE были заметно шире, чем у конкурса AES. В рамках конкурса NESSIE рассматривались алгоритмы следующих категорий [13, 14]:

  1. Блочное симметричное шифрование (на конкурс принято 17 алгоритмов).
  2. Потоковое шифрование (6 алгоритмов).
  3. Вычисление кодов аутентификации сообщений (Message Authentication Code – MAC, 2 алгоритма).
  4. Хэширование (1 алгоритм).
  5. Асимметричное шифрование (5 алгоритмов).
  6. Электронная цифровая подпись (7 алгоритмов).
  7. Идентификация (1 алгоритм).

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

Как и на конкурсе AES, алгоритмы-участники конкурса были присланы, практически, со всех концов Света. Причем, абсолютным лидером по количеству рассмотренных на конкурсе алгоритмов явилась Япония – из 39 участников конкурса в Японии было разработано 8.

В отличие от конкурса AES, единственной экспертной организацией в котором был институт NIST, организаторами конкурса NESSIE был интернациональный консорциум из следующих организаций, известных своими исследованиями в области криптологии:

  1. Католический Университет г. Лювен (Leuven), Бельгия – координатор проекта.
  2. Высшее учебное заведение Ecole Normale Superieure, Париж, Франция.
  3. Университет Royal Holloway, Лондон, Великобритания.
  4. Корпорация Siemens AG, Германия.
  5. Технологический Институт Technion, Хайфа, Израиль.
  6. Университет г. Берген, Норвегия.

Еще одно принципиальное отличие NESSIE (касательно алгоритмов блочного шифрования) от конкурса AES состояло в том, что не был установлен какой-либо конкретный размер блока шифруемых данных, поэтому в конкурсе рассматривались 64-, 128-, 160- и 256-битные блочные шифры. Для начала приведем общий список алгоритмов блочного шифрования, участвовавших в конкурсе:

АлгоритмРазмеры блока, битАвторы (организация1, страна)
1CS-Cipher64Jacques Stern, Serge Vaudenay (CS Communication & Systemes, Франция)
2Hierocrypt-L164Kenji Ohkuma, Fumihiko Sano, Hirofumi Muratani, Masahiko Motoyama, Shinichi Kawamura (Toshiba Corporation, Япония)
3Hierocrypt-3128
4IDEA64Xuejia Lai, James L. Massey (Ascom Systec Ltd., Швейцария).
5Khazad64Paulo Sergio L.M. Barreto (Бразилия) и Vincent Rijmen (Бельгия)
6Anubis128
7MISTY164Mitsuru Matsui (Mitsubishi Electric Corporation, Япония)
8Nimbus64Alexis Warner Machado (Бразилия)
9NUSH64, 128, 256Лебедев Анатолий Николаевич, Волчков Алексей Анатольевич (ЛАН Крипто, Россия)
10SAFER++64, 128James L. Massey (Швейцария), Gurgen H. Khachatrian (США), Melsik K. Kuregian (Армения)
11Grand Cru128Johan Borst (Бельгия)
12Noekeon128Joan Daemen, Michael Peeters, Gilles Van Assche, Vincent Rijmen (Бельгия)
13Q128Leslie McBride (США)
14RC6128 и болееRonald R. Rivest, Matthew J.B. Robshaw, Raymond M. Sidney, Yiqun Lisa Yin (RSA Security Inc., США)
15SC2000128Takeshi Shimoyama, Hitoshi Yanami, Kazuhiro Yokoyama, Masahiko Takenaka, Kouichi Itoh, Jun Yajima, Naoya Torii, Hidema Tanaka (Fujitsu Laboratories LTD., Япония)
16Camellia128Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, Mitsuru Matsui, Shiho Moriai, Junko Nakajima, Toshio Tokita (Nippon Telegraph and Telephone Corporation и Mitsubishi Electric Corporation, Япония)
17SHACAL160Helena Handschuh, David Naccache (Gemplus, Франция)

Еще одна аналогия с конкурсом AES – два раунда конкурса. Причем, их назначение полностью аналогично конкурсу AES: в первом раунде конкурса NESSIE были рассмотрены все алгоритмы, из которых во второй раунд были выбраны те из них, у которых не было явно выраженных недостатков. Соответственно, во втором раунде из финалистов были выбраны лучшие.

Начнем описание алгоритмов с 64-битных блочных шифров, не вышедших во второй раунд конкурса.

Многие материалы, касающиеся конкурса NESSIE, доступны на его домашней страничке, которая поддерживается Католическим Университетом г. Лювен.

Алгоритм CS-Cipher

Авторы алгоритма шифрования CS-Cipher (или просто CS) – Жак Стерн (Jacques Stern) и Серж Воденэ (Serge Vaudenay) из расположенного в Париже высшего учебного заведения Ecole Normale Superieure (ENS). ENS представляет собой университет, предлагающий обучение по различным направлениям, как для студентов старших курсов, так и послевузовское. ENS ведет свою историю с 1796 года, его специалисты хорошо известны в мире своими исследовании в области криптографии.

Название алгоритма CS происходит от французского словосочетания Chiffrement Symetrique, что весьма просто переводится как «симметричный шифр». Алгоритм шифрует данные 64-битными блоками с использованием ключа переменной длины – до 128 бит.

CS был впервые представлен авторами на конференции Fast Software Encryption в 1998 г., а в сентябре 2000 г. предложен на конкурс NESSIE его авторами при участии Пьера-Алана Фуке (Pierre-Alain Fouque) из компании CS Communication & Systemes, владеющей правами на алгоритм [9].

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

Структура алгоритма CS
Рис. 1. Структура алгоритма CS

Алгоритм CS представляет собой SP-сеть (см. статью «Назначение и структура алгоритмов шифрования», содержащую классификацию криптографических алгоритмов и описание наиболее часто встречающихся структур алгоритмов шифрования), состоящую из 8 раундов преобразований. Между раундами, а также перед первым раундом и после последнего выполняется наложение на обрабатываемый блок данных одного из фрагментов расширенного ключа k0...k8 (процедура расширения ключа будет подробно описана ниже) побитовой логической операцией «исключающее или» (XOR) – см. рис. 1 [12].

Операция E() алгоритма CS
Рис. 2. Операция E() алгоритма CS

В каждом раунде (функция E() на рис. 1) выполняются следующие операции (см. рис. 2):

  1. 64-битный блок данных делится на 4 слова по 16 бит, каждое из которых обрабатывается операцией M() (подробно описана ниже).
  2. Выполняется байтовая перестановка результата предыдущего шага согласно таблице:
    0, 2, 4, 6, 1, 3, 5, 7.

    Т.е. байт 0 остается на своем месте, байт 2 становится байтом 1 и т.д. Байты отсчитываются справа налево.
  3. Результат предыдущего шага складывается операцией XOR с константой c, после чего повторяются шаги 1 и 2. 64-битные константы с и c’ (используется на следующем шаге) получены из шестнадцатеричной записи первых 128 бит дробной части константы e и выглядят так:
    c = B7E151628AED2A6A,
    c’ = BF7158809CF4F3C7.
  4. Результат предыдущего шага обрабатывается аналогично шагу 3, но вместо константы c используется c’.
Функция M() алгоритма CS
Рис. 3. Функция M() алгоритма CS

Функция M() обрабатывает 16-битные слова следующим образом (см. рис. 3):

  1. Входное значение x разбивается на два 8-битных фрагмента xl и xr.
  2. Вычисляются байты выходного значения:
    yl = P(h(xl) xr),
    yr = P((xl <<< 1) xr),
    где <<< – операция циклического сдвига на указанное число бит влево,
    преобразование P() будет подробно описано ниже,
    а функция h() определена следующим образом:
    h(n) = ((n <<< 1) & 552 ) n),
    где & – побитовая логическая операция «и».
  3. Выходное значение y – результат конкатенации:
    M(x) = y = yl || yr.
Преобразование P() алгоритма CS
Рис. 4. Преобразование P() алгоритма CS

Преобразование P() замещает 8-битное входное значение p = pl || pr (pl и pr имеют размер по 4 бита) 8-битным значением q = ql || qr путем следующих вычислений (см. рис. 4):

t = pl f(pr),
qr = pr g(t),
ql = t f(qr),

где t – временная переменная,
функция g() будет подробно описана ниже,
а функция f() определена следующим образом:
Входное значение0123456789ABCDEF
Выходное значениеFDBB7577EDABEDEF

Выходное значение функции f() также может быть вычислено из входного следующим образом:

где - побитовый комплемент к n.
Функция g() является табличной заменой:

Входное значение0123456789ABCDEF
Выходное значениеA602BE18D453FC79

Стоит сказать, что для ускорения шифрования данных преобразование P(pl, pr) может быть реализовано не описанными выше вычислениями, а в виде следующей табличной замены (строки соответствуют значению pl, столбцы – pr):

 0123456789ABCDEF
0290D61409CEB9E8F1F855F585B013986
1972ED7D635AE171621B6694EA5728708
23C18E6E7FAADB889B700F76F73841163
33F967F6EBF149DACA40E7EF6204A6230
403C54B5A46A344657D4D3D4279491B5C
5F56CB59454FF56570BF4430C4F706D0A
6E4023E2FA247E0C1D51A95A7515E332B
75DD41D2CEE75ECDD7C4CA6B478483A32
898AFC0E12D090F1EB9278AE9BDE39F07
9B1EA9293536A311080F2D89B0436068E
ABEA96445381C7A6BF3A1F0CD37251581
BFB90E8D97B5219282688FCD1E28CA034
C8267DACBC741E5C4C8EFDBC3CCABCEED
DD0BBD3D2716813129AB3C2CADE77DCDF
E6683BC8D60C62223B28B910576CF74C9
FAAF199A859503B2AFEF924B0BAFDF855

Расшифрование

Расшифрование выполняется применением обратных операций в обратной последовательности. Обратной к операции E() является операция E-1(), приведенная на рис. 5.

Операция E-1() алгоритма CS
Рис. 5. Операция E-1() алгоритма CS

Сначала в данной операции выполняется обратная (по отношению к применяемой в операции E()) байтовая перестановка, затем применяется операция M-1(), затем выполняется XOR обрабатываемых данных с константой c’ и т.д.
M-1() также выполняется в несколько шагов:

  1. Входное значение y разбивается на два 8-битных фрагмента yl и yr.
  2. Вычисляются байты выходного значения:
    xl = h’(P(yl) P(yr)),
    xr = (xl <<< 1) P(yr),
    где функция h’() определена следующим образом:
    h’(n) = ((n <<< 1) & AA) n).
  3. Выходное значение x – результат конкатенации:
    M-1(y) = x = xl || xr.

Процедура расширения ключа

Расширение ключа выполняется в несколько этапов. Сначала ключ шифрования (если его размер меньше 128 бит) дополняется справа нулями до 128 бит.

Затем дополненный 128-битный ключ k делится на две 64-битные части:

k = k-1 || k-2,

на основе которых выполняется итеративное вычисление подключей k0...k8 (см. рис. 6):

Расширение ключа в алгоритме CS
Рис. 6. Расширение ключа в алгоритме CS

ki = ki-2 F(ci, ki-1).

Функция F() определена следующим образом:

F(n1,n2) = T(P’(n1 n2)),

где P’() обозначает параллельное применение функции P() к каждому байту входного 64-битного значения.

Преобразование P() было описано выше, а T() представляет собой битовую перестановку (xii-й бит 64-битного значения x):

T(x) = x63 || x55 || ... || x7 || x62 || x54 || ... || x6 || ...... || x56 || x48 || ... || x0,

т.е. первые 8 бит выходного значения составляются из каждого первого бита 8 байт входного значения, затем используются 8 вторых бит и т.д.

Константы ci получены из первых строк описанной выше таблицы преобразования P() и выглядят следующим образом:

c0 = 290D61409CEB9E8F,
c1 = 1F855F585B013986,
c2 = 972ED7D635AE1716,
c3 = 21B6694EA5728708,
c4 = 3C18E6E7FAADB889,
c5 = B700F76F73841163,
c6 = 3F967F6EBF149DAC,
c7 = A40E7EF6204A6230,
c8 = 03C54B5A46A34465.

Как видно, при зашифровании расширение ключа может выполняться «на лету», т.е. по мере необходимости. Однако, при расшифровании подключи применяются в обратной последовательности, поэтому расширение ключа необходимо выполнить до начала расшифрования.

Достоинства и недостатки алгоритма

Первичный криптоанализ алгоритма CS был проведен одним из его авторов – Сержем Воденэ [15], который доказал, что измененный вариант алгоритма с константами и подключами, замененными на случайные величины, не подвержен дифференциальному и линейному криптоанализу. Кроме того, для достижения стойкости против данных видов атак достаточно 5? раундов алгоритма.

Эксперты конкурса NESSIE в отчете [11] также подтверждают, что у алгоритма CS не обнаружено слабостей и каких-либо атак на него. Однако, исследования производительности алгоритмов-участников конкурса показали, что алгоритм CS является наиболее медленным среди всех 64-битных участников [8, 9]. Поэтому CS не вышел во второй этап конкурса именно из-за низкой скорости шифрования [8].

Алгоритм Hierocrypt-L1

Hierocrypt-L1 предложен на конкурс NESSIE известной японской корпорацией Toshiba. Авторы алгоритма: Кенджи Окума (Kenji Ohkuma), Фумихико Сано (Fumihiko Sano), Хирофуми Муратани (Hirofumi Muratani), Масахико Мотояма (Masahiko Motoyama) и Шиничи Кавамура (Shinichi Kawamura).

Алгоритм шифрует данные 64-битными блоками с использованием 128-битных ключей шифрования.

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

Аналогично алгоритму CS, Hierocrypt-L1 представляет собой SP-сеть. Его структура представлена на рис. 7.

Структура алгоритма Hierocrypt-L1.
Рис. 7. Структура алгоритма Hierocrypt-L1.

Всего алгоритм выполняет 6 раундов преобразований (причем, последний раунд отличается от предыдущих), после которых производится заключительное наложение материала ключа [5, 6].

В каждом из первых пяти раундов над обрабатываемым 64-битным блоком данных выполняются следующие операции:

  1. Операция XS, которая будет подробно описана ниже.
  2. Операция PH, представляющая собой умножение блока на фиксированную матрицу MH:

    где x1...x8 – 8-битные фрагменты входного значения, y1...y8 – 8-битные фрагменты результата, умножение выполняется в поле GF(28), а матрица MH определена следующим образом:
    10101110
    11011111
    11100111
    01011101
    11010101
    11101010
    11111101
    10101011

Операция XS, фактически, представляет собой вложенную SP-сеть, которая выполняет следующие преобразования (см. рис. 8):

Операция XS алгоритма Hierocrypt-L1
Рис. 8. Операция XS алгоритма Hierocrypt-L1
  1. Наложение 64-битного фрагмента ключа раунда:

    Y = X Ki,1,

    где X и Y – соответственно, входное и выходное значения текущей операции, а Ki,1 – первый фрагмент ключа i-го раунда.

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

    07FC5570988E844EBC75CE1802E95D80
    1C6078429D2EF5E8C67A2FA4B25F1987
    0B9B9CD3C3773D6FB92D4DF78CA7AC17
    3C5A41C929EDDE27693072A8953EF9D8
    218B44D7110D48FD6A0157E5BD85EC1E
    379FB59A7C09F1B194818208FBC0510F
    617F1A569613C16799035EB6CAFA9EDF
    D683CCA21223B765D0397D3BD5B0AF1F
    06C834C51B794B66BF884AC4EF583F0A
    2C73D1F86BE620B82243B333E7F0717E
    528947630E6DE3BE5964EEF6385CF45B
    49D4E0F3BB54262B008690FFFEA67B05
    AD68A110EBC7E2F2468A6C146ECF3545
    50D2927493E1DAAEA953E440CDBA97A3
    913125763632283A244CDBD98DDC622A
    EA15DDC2A50C041D8FCBB44F16ABAAA0

    Таким образом, таблица заменяет значение 0 на 7, 1 – на FC, 2 – на 55 и т.д.

  3. 64-битный блок делится на два 32-битных фрагмента, которые параллельно обрабатываются процедурой PL, которая выполняет над субблоком умножение на фиксированную матрицу ML:

    где x1...x4 и y1...y4 – 8-битные фрагменты, соответственно, входного и выходного значения, а матрица ML определена так:

    C465C88B
    8BC465C8
    C88BC465
    65C88BC4

    Умножение выполняется в поле GF(28) с образующим полиномом x8 + x6 + x5 + x + 1. Причем, фрагменты входного значения (xn) и элементы матрицы (a) преобразуются в элементы поля GF(28) различным образом:

  4. Наложение второго 64-битного фрагмента ключа раунда:

    Y = X Ki,2.
  5. Повторное выполнение описанной выше табличной замены S.

Последний раунд отличается от предыдущих тем, что в нем выполняется только операция XS; операция PH в последнем раунде не выполняется.

Кроме того, как было сказано выше, после шестого раунда выполняется наложение на блок данных 64-битного фрагмента расширенного ключа K7.

Расшифрование выполняется применением обратных операций в обратной последовательности. При этом, в операциях PH-1 и PL-1 используются, соответственно, следующие матрицы:

10111101
01011110
10101111
01101010
10100101
11011010
11101101
01011011


82C434F6
F682C434
34F682C4
C434F682

Расширение ключа

Процедура расширения ключа является достаточно сложной по сравнению с многими другими алгоритмами. Она состоит из двух этапов:

  1. Генерация промежуточных ключей на основе ключа шифрования.
  2. Вычисление расширенного ключа на основе промежуточных ключей.

Рассмотрим первый из данных этапов.

Вычисление промежуточного ключа в алгоритме Hierocrypt-L1.
Рис. 9. Вычисление промежуточного ключа в алгоритме Hierocrypt-L1

Он подразумевает выполнение следующих операций (см. рис. 9):

Z3 = P5(KI3) H0,
Z4 = PB(KI4),
Z1 = KI2,
Z2 = KI1 F(KI2 Z3),

где KI1...KI4 – 32-битные фрагменты исходного ключа шифрования,
Z1...Z4 – 32-битные фрагменты промежуточного ключа,
H0 – одна из констант, используемых в процедуре расширения ключа (см. ниже),
P5 – операция умножения 32-битного значения на фиксированную матрицу M5:

где x1...x4 и y1...y4 – 8-битные фрагменты, соответственно, входного и выходного значения, а матрица M5 определена так:

1010
1101
1110
0101

Умножение выполняется в поле GF(28).

PB – аналогичная операция умножения на матрицу MB, определенную следующим образом:

0101
1010
1101
1011

Функция F() выполняется в несколько шагов:

  1. Входное значение разбивается на 4 фрагмента по 8 бит.
  2. Каждый из фрагментов прогоняется через описанную выше таблицу замен S.
  3. Выходное значение функции F() – результат умножения выходного значения предыдущего шага на матрицу M8 (аналогично описанной выше операции P5):

    1010
    0101
    0111
    1011

Этап 2 процедуры расширения ключа – вычисление необходимого количества подключей на основе промежуточного ключа.

Прямой раунд процедуры расширения ключа в алгоритме Hierocrypt-L1
Рис. 10. Прямой раунд процедуры расширения ключа в алгоритме Hierocrypt-L1

Данный процесс выполняется в 7 раундов, в первых четырех из которых выполняются следующие преобразования (см. рис. 10):

T1 || T2 = P16(X3 || X4),
Y3 = P5(T1) Hi,
Y4 = PB(T2),
Y1 = X2,
Y2 = X1 F(X2 Y3),

где X1...X4 и Y1...Y4 – соответственно, 32-битные фрагменты входного и выходного значения; в первом раунде в качестве входного значения используются Z1...Z4, в последующих – выходные значения предыдущего раунда,
T1 и T2 – временные переменные,
H1...H4 – константы, используемые в процедуре расширения ключа (совместно с упомянутой выше H0):

H0 = 5A827999,
H1 = 6ED9EBA1,
H2 = 8F1BBCDC,
H3 = CA62C1D6,
H4 = F7DEF58A.

Данные константы – шестнадцатеричная запись дробной части иррациональных чисел


n = 2, 3, 5, 10, 15 для H0, H1, H2, H3, H4 соответственно.

P16 – аналогичное используемому в функции F() умножению на матрицу M8, однако, обрабатываемое данной операцией 64-битное значение делится на 4 16-битных фрагмента (а не на 8-битные), соответственно, умножение выполняется в поле GF(216).

Фактически, каждый из первых четырех раундов идентичен первому этапу расширения ключа, за исключением присутствия операции P16 и других используемых констант Hi. Ключи шифрования для i-го раунда шифрования вычисляются в конце i-го раунда этапа 2 процедуры расширения ключа:

Ki,1,1 = Y2,
Ki,1,2 = Y2 X1 Y3,
Ki,2,1 = Y2 X1 Y4,
Ki,2,2 = Y1 Y4,

где Ki,j,1 и Ki,j,2 – 32-битные «половинки» подключей i-го раунда Ki,1 и Ki,2 (их применение было описано выше).

Впоследствии выполняются 3 раунда (с 5-го по 7-й), которые являются обратными первым четырем – таким образом, для n = 1...3 выполняется следующее соотношение фрагментов расширенного ключа:

Kn,j = K8-n,j.

В каждом обратном раунде выполняются следующие преобразования (см. рис. 11):

Обратный раунд процедуры расширения ключа в алгоритме Hierocrypt-L1
Рис. 11. Обратный раунд процедуры расширения ключа в алгоритме Hierocrypt-L1
Y1 = X2 F(X1 X3),
Y2 = X1,
T1 = PB(X3 H9-i),
T2 = P5(X4),
Y3 || Y4 = P16-1(T1 || T2).

Операция P16-1 является обратной к операции P16, т.е. по описанным выше правилам выполняет умножение 16-битных фрагментов входного значения на следующую матрицу:

1110
1101
0110
1001

Ключи раундов шифрования 5-7 вычисляются следующим образом:

Ki,1,1 = Y1 X3,
Ki,1,2 = Y1 X2 T1,
Ki,2,1 = Y1 X2 T2,
Ki,2,2 = Y2 T2.

Процедура расширения ключа позволяет генерировать подключи «на лету», однако, только при зашифровании – при расшифровании придется сначала вычислить полный набор подключей.

Достоинства и недостатки алгоритма

Эксперты конкурса NESSIE после изучения алгоритма Hierocrypt-L1, а также различных посвященных ему материалов пришли к выводу, что данный алгоритм имеет исключительно медленную процедуру расширения ключа, что существенно ограничивает возможную область применения алгоритма [8]. Кроме того, были обнаружены уязвимости в процедуре расширения ключа, а также несколько вариантов атак на версии алгоритма с усеченным числом раундов [7]. Эти недостатки алгоритма Hierocrypt-L1 не позволили ему выйти во второй раунд конкурса NESSIE.

Алгоритм Nimbus

Алгоритм шифрования Nimbus разработан Алексисом Уорнером Мачадо (Alexis Warner Machado) из компании Gauss Informatica, Бразилия. Алгоритм исключительно прост в описании, структуру его раунда можно, фактически, представить одной формулой (см. рис. 12) [4]:

Раунд алгоритма Nimbus
Рис. 12. Раунд алгоритма Nimbus
y = ki * g(k5+i x) mod 264,

где x и y – соответственно, входное и выходное значения текущего (i-го) раунда преобразований, i = 0...4;
k0...k9 – фрагменты расширенного ключа (см. ниже);
функция g() представляет собой битовую перестановку, она просто меняет местами биты №№ n и 63-n для n = 0...31.

Расшифрование выглядит не сложнее – так же, как и при зашифровании, выполняется 5 раундов преобразований:

x = g(k’4-i * y mod 264) k9-i,

где x и y – соответственно, выходное и входное значения i-го раунда расшифрования,
а k’n – мультипликативная обратная величина к kn по модулю 264.

Стоит сказать, что автор алгоритма не ограничивает размер блока 64 битами: можно шифровать блоками по 128 и 256 бит и более. При этом используются вычисления по модулю 2128, 2256 и т.д. Поскольку с увеличением размера блока сложность подобных вычислений нелинейно возрастает, дальнейшее увеличение размера блока не выглядит оправданным.

Процедура расширения ключа

Nimbus использует ключи шифрования переменного размера, от 64 до 576 бит; размер ключа шифрования должен быть кратен 64 битам. Исходный ключ представляется в виде последовательности 64-битных блоков K0...Km. Генерация на их основе последовательности подключей k0…k9 выполняется следующим образом:

  1. Инициализация подключей, состоящая в обнулении последовательности k0...k9.
  2. В цикле по i от 0 до m (m – размер ключа в 64-битных блоках) выполняются следующие действия:
    • Вычисляется промежуточное значение x:

      x = Ki E(Ki),

      где E() представляет собой зашифрование входного значения алгоритмом Nimbus на наборе фиксированных подключей, который выглядит так:

      k0243F6A8885A308D3
      k113198A2E03707345
      k2A4093822299F31D1
      k3082EFA98EC4E6C89
      k4452821E638D01377
      k5BE5466CF34E90C6C
      k6C0AC29B7C97C50DD
      k73F84D5B5B5470917
      k89216D5D98979FB1B
      k9D1310BA698DFB5AC

      Данные константы представляют собой шестнадцатеричную запись дробной части числа .

    • В цикле по j от 0 до 9 выполняются следующие операции:

      x = E(x),
      kj = x E(x kj).
  3. Обеспечивается нечетность значений подключей k0...k4, которые используются в операциях умножения при шифровании – путем установки младших бит k0...k4 в единичное значение.

Стоит обратить внимание на следующие свойства алгоритма и процедуры расширения ключа:

  1. При необходимости достаточно легко можно увеличить количество раундов алгоритма (в абсолютном большинстве алгоритмов это приводит к увеличению криптостойкости за счет снижения скорости шифрования). Для этого достаточно лишь увеличить число подключей (и соответствующие циклы в описанных выше шагах 1-3 процедуры расширения ключа) и, собственно, число раундов алгоритма.
  2. Расширение ключа никоим образом невозможно выполнять «на лету», что можно считать недостатком алгоритма.

Достоинства и недостатки алгоритма

В спецификации алгоритма [4] его автор утверждал, что Nimbus обладает стойкостью против всех известных атак, в случае, если количество раундов алгоритма превышает 4 (а в спецификации установлено 5 раундов алгоритма). Однако, алгоритм не был выбран во второй раунд конкурса NESSIE из-за найденной специалистами атаки, которую весьма реально осуществить на практике [7].

Данная атака была изобретена известными криптологами из института Technion, Израиль: Эли Бихамом (Eli Biham) и Владимиром Фурманом (Vladimir Furman) [1]. Атака позволяет вычислить ключ шифрования полнораундового алгоритма Nimbus на основе всего 256 выбранных открытых текстов и соответствующих им шифртекстов путем выполнения не более 210 тестовых операций шифрования. При наличии у злоумышленника возможности выбора шифртекстов для атаки требуется еще меньше материала – достаточно 136 выбранных шифртекстов (и соответствующих им открытых текстов) при той же вычислительной сложности. Впоследствии специалистам из Университета Беркли (США) удалось распространить принципы атаки, предложенной Бихамом и Фурманом, на ряд других алгоритмов шифрования [2].

Таким образом, алгоритм Nimbus оказался наиболее слабым из всех алгоритмов блочного шифрования, участвовавших в конкурсе NESSIE.

Алгоритм NUSH

Алгоритм NUSH предложен на конкурс NESSIE Российской компанией «ЛАН Крипто», которая представляет собой одну из наиболее известных отечественных компаний-разработчиков средств криптографической защиты информации (в том числе, и на основе криптоалгоритмов собственной разработки). Авторы алгоритма – одни из наиболее значимых в России экспертов по криптологии: Президент компании «ЛАН Крипто» Лебедев А.Н. и Президент Российской Криптологической Ассоциации «РусКрипто» Волчков А.А.

В отличие от рассмотренных выше алгоритмов CS-Cipher и Nimbus, алгоритм NUSH имеет несколько фиксированных размеров шифруемого блока данных: 64, 128 и 256 бит. Рассмотрим 64-битный вариант алгоритма.

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

Структура алгоритма NUSH
Рис. 13. Структура алгоритма NUSH

Структура алгоритма показана на рис. 13 [3]. Шифруемый блок данных разбивается на 4 субблока по 16 бит (обозначаемые как a, b, c, d).

Прежде всего, выполняется начальное преобразование, состоящее в том, что на каждый субблок операцией XOR накладывается фрагмент расширенного ключа (процедура расширения ключа будет описана ниже) для начального преобразования KS0...KS3:

A = a KS0,
B = b KS1,
C = c KS2,
D = d KS3,

где A, B, C, D – значения соответствующих субблоков после выполнения текущей операции.

Затем выполняется 9 раундов преобразований; структура раунда будет описана ниже.

По завершении 9 раундов выполняется финальное преобразование, в котором операцией XOR на субблоки накладываются подключи для финального преобразования KF0...KF3:

A = a KF0,
B = b KF1,
C = c KF2,
D = d KF3.

Основой каждого раунда алгоритма является преобразование ("итерация" согласно спецификации алгоритма) R(X1, X2, X3, X4, k, s); в одной итерации выполняются следующие действия (см. рис. 14):

Итерация алгоритма NUSH
Рис. 14. Итерация алгоритма NUSH

Y3 = (X2 + (X3 k) mod 216) >>> s,
Y1 = X1 + (Y3 # X4) mod 216,
Y2 = X2,
Y4 = X4,

где X1...X4 и Y1...Y4 - соответственно, входные и выходные значения обрабатываемых субблоков,
k – модифицированный фрагмент расширенного ключа для текущей итерации,
>>> – побитовый циклический сдвиг операнда вправо на переменное число бит,
s – число бит сдвига, различно для каждой итерации и выбирается из таблицы S:

РаундИтерацияs
004
017
0211
038
107
1114
125
134
208
212
229
234
3013
311
3214
336
407
4112
425
431
502
514
5212
533
609
612
6211
6313
7012
713
726
7311
807
8115
824
8314

Символом # обозначена побитовая логическая операция "и" (&) или побитовая логическая операция "или" (|), конкретная из которых также выбирается из следующей таблицы:

РаундИтерация#
00&
01|
02&
03|
10|
11|
12|
13|
20&
21|
22|
23&
30|
31&
32|
33|
40|
41|
42&
43&
50&
51&
52&
53|
60&
61|
62|
63|
70&
71|
72&
73&
80|
81|
82&
83|

Раунд состоит из четырех итераций (в таблицах выше пронумерованы от 0 до 3), выполняемых по следующему закону:

R(a, b, c, d, KRC4i, S[4i]),
R(b, c, d, a, KRC4i + 1, S[4i + 1]),
R(c, d, a, b, KRC4i + 2, S[4i + 2]),
R(d, a, b, c, KRC4i + 3, S[4i + 3]),

где i – номер текущего раунда, начиная с 0,
KRCn – модифицированный фрагмент расширенного ключа для текущей итерации (KRn):

KRCn = KRn + c mod 216,

где c – модифицирующая константа согласно следующей таблице:

РаундИтерацияс
00AC25
018A93
02243D
03262E
10F887
11C4F2
128E36
139FA1
207DC0
216A29
226D84
2334BD
30A267
31CC15
3204FE
33B94A
40DF24
4140EF
4296DA
43905F
50D631
51AA62
524D15
5370CB
607533
6145FC
625337
63D25E
70A926
711C7B
725F12
734ECC
803C86
8128DB
82FC01
837CB1

Расшифрование

Расшифрование выполняется применением обратных операций в обратной последовательности. Таким образом, при расшифровании сначала выполняется обратное финальное преобразование, затем 9 раундов по 4 обратных итерации, после чего – обратное начальное преобразование.

Обратные финальное и начальное преобразования полностью аналогичны прямым – на субблоки a, b, c, d операцией XOR накладываются, соответственно, фрагменты расширенного ключа KF0...KF3 и KS0...KS3.

Итерации каждого раунда также выполняются в обратной последовательности (i = 9…1):

R-1(d, a, b, c, KRC4i - 1, S[4i - 1]),
R-1(c, d, a, b, KRC4i - 2, S[4i - 2]),
R-1(b, c, d, a, KRC4i - 3, S[4i - 3]),
R-1(a, b, c, d, KRC4i - 4, S[4i - 4]).

Итерация R-1(X1, X2, X3, X4, k, s) выглядит следующим образом (см. рис. 15):

Обратная итерация алгоритма NUSH
Рис. 15. Обратная итерация алгоритма NUSH

Y4 = X4, Y2 = X2, Y1 = X1 – (X3 # X4) mod 216, Y3 = ((X3 >>> (16 – s)) k) – X2 mod 216.

Расширение ключа

Процедура расширения ключа весьма проста и напоминает таковую у отечественного стандарта шифрования ГОСТ 28147-89 [17] – исходный ключ шифрования делится на фрагменты K0...Kn-1 (n – размер ключа шифрования в 16-битных словах), т.е.:

  • K0...K7 для 128-битного ключа,
  • K0...K11 для 192-битного ключа,
  • K0...K15 для 256-битного ключа.

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

ПрименениеИспользуемый фрагмент ключа (в зависимости от его размера)
128 бит192 бита256 бит
KS0K4K4K12
KS1K5K5K13
KS2K6K6K14
KS3K7K7K15
KF0K3K11K13
KF1K2K10K12
KF2K1K9K15
KF3K0K8K14
KRiKi mod n

Символом i в таблице обозначен сквозной номер итерации (от 0 до 35), т.е. в итерациях фрагменты ключа используются поочередно в прямом порядке.

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

Алгоритм NUSH не выбран во второй раунд конкурса [10] благодаря атаке, предложенной китайскими учеными Ву Венлинг (Wu Wenling) и Фенг Денггуо (Feng Dengguo) [16]. Найденная ими атака позволяет методом линейного криптоанализа вычислить 128-битный ключ шифрования алгоритма NUSH при наличии 258 известных открытых текстов (и соответствующих им шифртекстов) выполнением 2124 тестовых операций шифрования. При этом, при наличии 262 известных открытых текстов вычислительная сложность снижается до 255 тестовых операций шифрования. Аналогичные атаки существуют для 192- и 256-битных ключей.

Следует отметить, что данные атаки весьма сложно реализуемы на практике, однако их оказалось достаточно в качестве доказательства недостаточного запаса криптостойкости (security margin) [10] алгоритма NUSH.

  1. Biham E., Furman V. Differential Cryptanalysis of Nimbus. // http://www.cosic.esat.kuleuven.be. – November 29, 2000.
  2. Borisov N., Chew M., Johnson R., Wagner D. Multiplicative Differentials. // http://citeseer.ifi.unizh.ch. – University of California at Berkeley.
  3. Lebedev A.N., Volchkov A.A. NUSH. Cryptographic Algorithms Based upon the Block Cipher Called «NUSH». // http://www.cosic.esat.kuleuven.be. – LAN Crypto, Int., Moscow, Russia.
  4. Machado A.W. The Nimbus Cipher. // http://www.cosic.esat.kuleuven.be. – Gauss Informatica, Brazil.
  5. Ohkuma K., Sano F., Muratani H., Motoyama M., Kawamura S. Specification of Hierocrypt-L1. // http://www.cosic.esat.kuleuven.be. – Toshiba Corporation – September 25, 2000.
  6. Ohkuma K., Sano F., Muratani H., Motoyama M., Kawamura S. Specification on a Block Cipher: Hierocrypt-L1 (revised). // http://www.cosic.esat.kuleuven.be. – Toshiba Corporation – September, 2001.
  7. 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. NESSIE Public Report D20: NESSIE Security Report. // http://www.cosic.esat.kuleuven.be. – Version 2.0 – 19 February 2003.
  8. 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.
  9. 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.
  10. Preneel B., Van Rompay B., Granboulan L., Martinet G., Murphy S., Shipsey R., White J., Dichtl M., Serf P., Schafheutle M., Biham E., Dunkelman O., Ciet M., Quisquater J-J., Sica F., Knudsen L., Raddum H. NESSIE Phase I: Selection of Primitives. // http://www.cryptonessie.org. – 23 September 2001.
  11. Preneel B., Van Rompay B., Granboulan L., Martinet G., Murphy S., Shipsey R., White J., Dichtl M., Serf P., Schafheutle M., Biham E., Dunkelman O., Furman V., Ciet M., Quisquater J-J., Sica F., Knudsen L., Raddum H. NESSIE Public Report D13: Security Evaluation of NESSIE First Phase. // http://www.cosic.esat.kuleuven.be. – 23 September 2001.
  12. Stern J., Vaudenay S. CS-Cipher. // http://www.cosic.esat.kuleuven.be. – Ecole Normale Superieure.
  13. Van Rompay B. NESSIE Public Report D02: Report on the NESSIE Call. // http://www.cosic.esat.kuleuven.be.
  14. Van Rompay B. NESSIE Public Report D07: Response to the NESSIE Call. // http://www.cosic.esat.kuleuven.be.
  15. Vaudenay S. On the Security of CS-Cipher. // http://www.cosic.esat.kuleuven.be. – Ecole Normale Superieure.
  16. Wenling W., Dengguo F. Linear cryptanalysis of NUSH block cipher. // http://www.scichina.com – Chinese Academy of Sciences – 2002.
  17. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. – М.: Госстандарт СССР, 1989.


Дополнительно

iXBT BRAND 2016

«iXBT Brand 2016» — Выбор читателей в номинации «Процессоры (CPU)»:
Подробнее с условиями участия в розыгрыше можно ознакомиться здесь. Текущие результаты опроса доступны тут.

Нашли ошибку на сайте? Выделите текст и нажмите Shift+Enter

Код для блога бета

Выделите HTML-код в поле, скопируйте его в буфер и вставьте в свой блог.