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

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

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

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

  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-31284IDEA64Xuejia Lai, James L. Massey (Ascom Systec Ltd., Швейцария).5Khazad64Paulo Sergio L.M. Barreto (Бразилия) и Vincent Rijmen (Бельгия)6Anubis1287MISTY164Mitsuru 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 представляет собой SP-сеть (см. статью «Назначение и структура алгоритмов шифрования», содержащую классификацию криптографических алгоритмов и описание наиболее часто встречающихся структур алгоритмов шифрования), состоящую из 8 раундов преобразований. Между раундами, а также перед первым раундом и после последнего выполняется наложение на обрабатываемый блок данных одного из фрагментов расширенного ключа k0. k8 (процедура расширения ключа будет подробно описана ниже) побитовой логической операцией «исключающее или» (XOR) – см. рис. 1 [12].

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

  1. Входное значение x разбивается на два 8-битных фрагмента xl и xr.
  2. Вычисляются байты выходного значения:

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

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

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

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

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

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

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

  1. Входное значение y разбивается на два 8-битных фрагмента yl и yr.
  2. Вычисляются байты выходного значения:

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

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

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

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

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

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

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

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

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

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

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

Первичный криптоанализ алгоритма 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.

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

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

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

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

07FC5570988E844EBC75CE1802E95D801C6078429D2EF5E8C67A2FA4B25F19870B9B9CD3C3773D6FB92D4DF78CA7AC173C5A41C929EDDE27693072A8953EF9D8218B44D7110D48FD6A0157E5BD85EC1E379FB59A7C09F1B194818208FBC0510F617F1A569613C16799035EB6CAFA9EDFD683CCA21223B765D0397D3BD5B0AF1F06C834C51B794B66BF884AC4EF583F0A2C73D1F86BE620B82243B333E7F0717E528947630E6DE3BE5964EEF6385CF45B49D4E0F3BB54262B008690FFFEA67B05AD68A110EBC7E2F2468A6C146ECF354550D2927493E1DAAEA953E440CDBA97A3913125763632283A244CDBD98DDC622AEA15DDC2A50C041D8FCBB44F16ABAAA0

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

C465C88B8BC465C8C88BC46565C88BC4

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

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

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

82C434F6F682C43434F682C4C434F682

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

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

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

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

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

1010110111100101

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

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

0101101011011011

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм Nimbus

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

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

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

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

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

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

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

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

  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-битный вариант алгоритма.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Затем фрагменты ключа используются в итерациях, а также в начальном и финальном преобразованиях согласно следующей таблице: ПрименениеИспользуемый фрагмент ключа (в зависимости от его размера)128 бит192 бита256 битKS0K4K4K12KS1K5K5K13KS2K6K6K14KS3K7K7K15KF0K3K11K13KF1K2K10K12KF2K1K9K15KF3K0K8K14KRiKi mod n

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

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

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

📎📎📎📎📎📎📎📎📎📎