NESSIE – конкурс криптоалгоритмов

© Панасенко Сергей, 2004.

В январе 2000 года в Бельгии начался трехлетний европейский криптопроект NESSIE (New European Schemes for Signatures, Integrity, and Encryption), целью которого являлся отбор криптографических алгоритмов, на базе которых, теоретически, должны формироваться будущие криптостандарты Европы.

Конкурс AES

За три года до старта NESSIE в США состоялся весьма похожий конкурс AES (Advanced Encryption Standard). «Конкурсантами» являлись алгоритмы блочного шифрования, присланные различными организациями и частными лицами, из которых специалисты Института стандартов и технологий США (NIST – National Institute of Standards and Technologies) должны были выбрать новый стандарт блочного шифрования США.
Из 15 алгоритмов, присланных на конкурс, NIST выбрал на первом этапе те 5 из них, в которых не обнаружилось уязвимостей и различных недостатков (недостатками считались, например, низкая скорость шифрования или высокие требования к оперативной и/или энергонезависимой памяти). На втором этапе эксперты отдали предпочтение алгоритму Rijndael (его авторы – криптографы из Бельгии Joan Daemen и Vincent Rijmen), который и стал новейшим стандартом блочного шифрования США.

Организаторы и участники NESSIE

Конкурс NESSIE был организован рядом научных организаций из Бельгии, Германии, Великобритании, Франции, Норвегии и Израиля. Как и в конкурсе AES, участниками могли стать любые организации и частные лица со всего мира; для участия следовало прислать алгоритм собственной разработки, предназначенный для выполнения одной из следующих криптографических операций:

Кроме того, на конкурс были присланы алгоритм асимметричной идентификации и криптоаналитический алгоритм.
Как видно, NESSIE был задуман как существенно более широкий, чем AES, проект – шутка ли, его устроители замахнулись, фактически, на выбор криптостандартов для большинства криптографических применений! Впрочем, к этой теме мы еще вернемся несколько позже.
Еще одно техническое отличие NESSIE от AES – более подробные технические требования к алгоритмам: если описание блочного шифра – потенциального криптостандарта США – можно было уложить в несколько строк, то организаторы NESSIE установили строгий интерфейс к реализациям алгоритмов в виде описания экспортируемых функций на «portable C».
Выбор оптимальных алгоритмов проходил в 3 этапа:

  1. Первичное изучение алгоритма.
  2. Криптоаналитические исследования, на основании которых делался вывод о возможных уязвимостях конкретного алгоритма.
  3. Сравнение алгоритмов, прошедших предыдущий этап, по ряду критериев: быстродействие, минимальные требования к вычислительным ресурсам и т. д.

Как и на конкурс AES, алгоритмы были присланы буквально со всего мира. Стоит отметить, что в конкурсе принимал участие и алгоритм из России – алгоритм блочного шифрования NUSH, который, к сожалению, был отвергнут на достаточно раннем этапе по причине отсутствия в нем табличных замен или других нелинейных операций, что доказанно делало этот алгоритм уязвимым к линейному криптоанализу (линейный криптоанализ основан на поиске зависимостей между символами открытого и зашифрованного текста).
Среди остальных претендентов стоит отметить алгоритмы, участвовавшие в конкурсе AES: RC6 (представлен компанией RSA Laboratories) и SAFER++ (разработчики – фирма ETH Zurich, Швейцария в сотрудничестве с Академией Наук Армении), последний из них – незначительно измененный SAFER+, который был отклонен на первом этапе конкурса AES. Кроме того, претендентами в конкурсе NESSIE были широко используемый алгоритм блочного шифрования IDEA и известная схема электронной подписи на эллиптических кривых ECDSA. Часть участвовавших алгоритмов была разработана специально в надежде победить в конкурсе NESSIE.

Победители конкурса

На первом этапе исследований алгоритмов эксперты выбрали 24, из которых впоследствии было выбрано 12 алгоритмов, не содержащих уязвимостей. Здесь организаторы конкурса дополнили список несколькими известными или стандартизованными алгоритмами (например, алгоритмом блочного шифрования Rijndael, алгоритмом хэширования SHA, являющимся стандартом хэширования США, и т.д.), не представленными на конкурс. Выбор победителей конкурса проводился из этого расширенного списка претендентов, состоящего из 17 криптографических алгоритмов. Причем, что интересно, в данном списке «финалистов» конкурса оказалось (с учетом добавлений) целых шесть хэш-функций, но ни одного потокового шифра, поскольку ни один из них не удовлетворил экспертов конкурса по криптостойкости.
Рассмотрим подробно алгоритмы, которые победили в наиболее интересной, на мой взгляд, категории блочных шифров, а именно следующие:

  1. MISTY1 для шифрования 64-битных блоков,
  2. AES (т.е. Rijndael) и Camellia (128 бит),
  3. SHACAL-2 (256 бит).

MISTY1

Алгоритм MISTY1 был разработан в 1996 году японской корпорацией Mitsubishi Electric.
Структурная схема алгоритма представлена на рис. 1. Как видно из схемы, данный алгоритм является сетью Фейстеля (т.е. разбивает входной поток на два субблока, результат обработки одного из которых накладывается на другой субблок, затем субблоки меняются местами, см. рис. 2), причем, обработка субблоков в алгоритме различается для четных и нечетных раундов. Количество раундов алгоритма не ограничено, однако, рекомендовано выполнять 8 раундов преобразований.
Помимо значения обрабатываемого субблока, операции FL и FO (см. рис. 1) используют в качестве параметра и значение определенного подключа, вычисляемое на этапе расширения 128-битного ключа шифрования данного алгоритма. Операция FL выполняет несложные преобразования входных данных с участием ключа, тогда как операция FO является, фактически, еще одной 4-раундовой сетью Фейстеля: в ней обрабатываемый 32-битный субблок разбивается еще на две части по 16 бит, одна из которых складывается с фрагментом ключа, после чего к ней применяется операция FI, результат накладывается на другую часть, после чего 16-битные части меняются местами. В свою очередь, операция FI является еще более интересной (см. рис. 3): 16-битное входное значение после разбиения на 7- и 9-битные блоки «прогоняется» через таблицы замен S7 (для 7 бит) и S9 (для 9 бит), которые обеспечивают, таким образом, перемешивающую часть криптопреобразований.
MISTY1 был признан весьма стойким алгоритмом шифрования, в основном, из-за уникальной структуры «вложенных» сетей Фейстеля. Кроме того, MISTY1 является весьма нетребовательным к ресурсам, а также данный алгоритм оптимизирован под аппаратную реализацию, поэтому без проблем может быть использован в устройствах с ограниченными возможностями, например, в смарт-картах.

Camellia

Шифр Camellia был также разработан компанией Mitsubishi Electric в сотрудничестве с еще одной известной японской корпорацией – Nippon Telegraph and Telephone (NTT). Для последней это был не первый опыт участия в международных криптоконкурсах – на конкурс AES корпорация NTT выдвигала алгоритм E2, который не прошел в финал конкурса.
Именно от E2 алгоритм Camellia унаследовал большую часть выполняемых операций. Camellia представляет собой сеть Фейстеля, в каждом раунде которой выполняется основное преобразование, показанное на рис. 4. В зависимости от длины ключа (алгоритм допускает использование 128-, 192- и 256-битных ключей) выполняется 18 или 24 раундов, причем после каждого шестого раунда, исключая последний, выполняется преобразование FL, практически не измененное по сравнению с аналогичной операцией алгоритма MISTY1.
Как видно на рис. 4, содержимое 64-битного субблока обрабатывается побайтно применением следующих операций:

  1. сложение по модулю 2 с соответствующим байтом ключа раунда;
  2. табличная замена (с помощью четырех таблиц s1 … s4);
  3. сложение по модулю два с конкретными байтами субблока;
  4. байтовая перестановка.

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

SHACAL-2

Алгоритм SHACAL-2 был представлен на конкурс французской компанией Gemplus, которая является широко известным производителем смарт-карт и оборудования для работы с ними.
SHACAL-2 шифрует блоками по 256 бит, используя 512-битный ключ шифрования. Данный алгоритм можно описать следующим образом:

    1. 256-битный блок открытого текста разбивается на 8 частей и записывается в 8 32-битных регистров, обозначаемых латинскими буквами A … H.
    2. Выполняется 64 раунда преобразований над регистрами A … H согласно рис. 5, где:

    Wi – ключ раунда, вычисляемый из 512-битного ключа шифрования на этапе расширения ключа,
    Ki – константы, различные для каждого раунда,
    T1, T2 – промежуточные величины,
    Ch(E, F, G) = (E AND F) ⊕ ( NOT E AND G),
    Maj(A, B, C) = (A AND B) ⊕ (A AND C) ⊕ (B AND C),
    Sum0(A) = (A >> 2) ⊕ (A >> 13) ⊕ (A >> 22),
    Sum1(E) = (E >> 6) ⊕ (E >> 11) ⊕ (E >> 25)
    .

    1. Шифртекстом является конкатенация восьми 32-битных фрагментов, находящихся в регистрах A … H.

Эксперты не нашли уязвимостей и у данного алгоритма.

Политика

Изначально многие специалисты считали, что конкурс NESSIE – это противопоставление конкурсу AES – «не могут же американцы выбрать алгоритм из Европы, поэтому будем выбирать сами». После того, как в конкурсе AES победил алгоритм из Бельгии, европейские страсти несколько поутихли. А выбор алгоритмов блочного шифрования и вовсе нельзя считать политизированным – видно «победное шествие» японских криптографов на конкурсе NESSIE.
Еще более интересна судьба на этом конкурсе алгоритма Rijndael - победителя AES. Vincent Rijmen, один из его разработчиков, по окончании конкурса AES считал, что в Европе совершенно логично выбрать тот же Rijndael в качестве стандарта. Однако, несмотря на то, что данный алгоритм был назван одним из победителей, он был одновременно «не рекомендован к стандартизации».
Если же сравнивать сами конкурсы криптоалгоритмов: AES и NESSIE, - то по многим параметрам NESSIE явно уступает американскому конкурсу. Во-первых, AES был весьма конкретен – только выбор алгоритма блочного шифрования, тогда как NESSIE явно не хватило фокусировки на более узких задачах. Во-вторых, конкурс AES организовывал и проводил государственный институт США, именно уполномоченный на выбор нового стандарта, а консорциум, проводящий NESSIE, состоял из научных организаций, что навевало мысли на «инициативу снизу» и вызывало сомнения в будущем победителей конкурса как «криптостандартов единой Европы». Ну и, наконец, США уже имеют опыт стандартизации криптоалгоритмов – вспомним DES, который был стандартом блочного шифрования почти во всем мире в течение 20 лет, причем, в нем не было найдено уязвимостей (не считая конструктивных – короткого ключа) за все это время. А вот в Евросоюзе подобного стандарта до сих пор не было. Последим ближайшие пару лет за новыми европейскими криптостандартами?

 

Рисунки:

  1. Схема алгоритма MISTY1.
  2. Сеть Фейстеля.
  3. Схема операции FI в алгоритме MISTY1.
  4. Основное преобразование алгоритма Camellia.
  5. Раунд алгоритма SHACAL-2.
Алгоритмы шифрования...

Rambler's Top100

Перейти на главную страницу

Карта сайта

Список статей