Конкурсы по выбору симметричных функций в криптографии. AES. NESSIE. CRYPTREC

4.      AES — конкурс

Advanced Encryption Standard, AES — конкурс, организованный NIST в 1997 году для выбора нового криптографического стандарта, который должен был стать преемником DES. В результате конкурса в 2000 году победителем был объявлен шифр Rijndael (который теперь часто называют по имени конкурса — AES).

Необходимость в принятии нового стандарта была вызвана небольшой длиной ключа DES (56 бит), что теоретически позволяло применить метод грубой силы (полный перебор ключей) против этого алгоритма. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала достаточного быстродействия. Модификация 3-DES обладала достаточной длиной ключа, но при этом была в три раза медленнее.

4.1. Начало конкурса

2 января 1997 года NIST объявляет о намерении выбрать преемника для DES, являвшегося американским стандартом с 1977 года. Однако, вместо опубликования алгоритма, NIST принял различные предложения от заинтересованных сторон о том, каким образом следует выбирать алгоритм. Бурный отклик со стороны открытого криптографического сообщества привёл к объявлению конкурса (12 сентября 1997 года). Свой алгоритм могла предложить любая организация или группа исследователей. Требования к новому стандарту были следующими:

 блочный шифр.

 длина блока, равная 128 битам.

 ключи длиной 128, 192 и 256 бит.

Подобные шифры были довольно редки во время объявления конкурса; возможно, лучшим был Square. Дополнительно кандидатам рекомендовалось:

 использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах)

 ориентироваться на 32-разрядные процессоры

 не усложнять без необходимости структуру шифра для того, чтобы все заинтересованные стороны были в состоянии самостоятельно провести независимыйкриптоанализ алгоритма и убедиться, что в нём не заложено каких-либо недокументированных возможностей.

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

4.2. Конкурс AES

20 августа 1998 года на 1-й конференции AES был объявлен список из 15 кандидатов: CAST- 256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS,RC6, Rijndael, SAFER+, Serpent, Twofish. В последующих обсуждениях эти алгоритмы подвергались всестороннему анализу, причём исследовались не только криптографические свойства, такие как стойкость к известным атакам, отсутствие слабых ключей, хорошие статистические свойства, но и практические аспекты реализации: оптимизацию скорости выполнения кода на различных архитектурах (от ПК до смарт-карт и аппаратных реализаций), возможность оптимизации размера кода, возможность распараллеливания. Проверка кандидатов на предмет формирования случайных двоичных последовательностей осуществлялась с помощью набора статистических тестов NIST.

4.3. Первый раунд AES

В течение первого раунда AES тестирование проводилось с 128-битными ключами. Лишь 9 алгоритмов из 15 алгоритмов смогли пройти статистические тесты, а именно: CAST-256, DFC, E2, LOKI-97, MAGENTA, MARS, Rijndael, SAFER+ и Serpent. Оставшиеся алгоритмы показали некоторые отклонения в тестах на случайный характер формируемых ими двоичных последовательностей.

В марте 1999 года прошла 2-я конференция AES, а в августе 1999 года были объявлены 5 финалистов: MARS, RC6, Rijndael, Serpent и Twofish. Все эти алгоритмы были разработаны авторитетными криптографами с мировым именем. На 3-й конференции AES в апреле 2000 года авторы выступили с докладами о своих алгоритмах.

4.4. Второй раунд AES

Во втором раунде AES оценка пригодности финалистов первого раунда в качестве генераторов случайных чисел проводилось на основе 192-битных и 256-битных ключей. Продолжительность статистических тестов NIST составило несколько месяцев, причем вычисления производились на многочисленных рабочих станциях Sun Ultra. Все данные формировались и обрабатывались в режиме онлайн. В результате второго раунда было показано, что каждый из пяти вышеуказанных алгоритмов формирует абсолютно случайную бинарную последовательность и поэтому может быть использован в качестве генератора псевдослучайных чисел, причем имеется возможность использования ключей размерами: 128, 192 и 256 бит.

4.5. Голосование

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

 Rijndael: 86 за, 10 против

 Serpent: 59 за, 7 против

 Twofish: 31 за, 21 против

 RC6: 23 за, 37 против

 MARS: 13 за, 83 против

4.6. Третья конференция AES

Третья конференция AES прошла в Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа. На ней присутствовало 250 участников, многие из которых приехали из-за рубежа. Двухдневная конференция была разделена на восемь сессий, по четыре в день, плюс к тому состоялась неформальная дополнительная сессия, подводившая итоги первого дня. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FPGA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось число раундов в алгоритмах-кандидатах. На сессиях второго дня был проанализирован Rijndael с сокращённым числом раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, ещё раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael рассказал Винсент Рэймен, заявивший о надёжности защиты, высокой общей производительности и простоте архитектуры своего кандидата.

4.7. Выбор победителя

2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как FIPS 197.

5.      Классификация критериев и показателей эффективности функционирования схем ПШ

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

При оценке стойкости используются следующие критерии:

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

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

3. Рассматриваемые схемы оцениваются в пределах заявленной области применения. Таким образом, рассмотрение уязвимости к побочным методам нападениям (например timing attack, силовые атаки) должно быть соответствующим.

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

− стойкость к методам анализа. Любая рассматриваемая схема должна быть стойкой к атакам заявленного уровня стойкости.  Подверженность анализу каким-либо методом со сложностью меньше заявленной дисквалифицирует рассматриваемую схему;

− общая концепция конструкции схемы.  Важным элементом оценки стойкости схемы криптопреобразований является используемая концепция построения и прозрачность конструкции анализируемой схемы. Ясность и прозрачность конструкторских решений,  основанных на хорошо понятных и изученных    математических и криптографических принципах, позволяют с бóльшим доверием относиться к результатам оценки стойкости    исследуемых схем.  Кроме того,  данные принципы особенно уместны при проведении сравнений между исследуемыми схемами;

− стойкость модифицируемых схем. Под модифицированной схемой понимают схему, в которой модифицируют или удаляют некоторые ее составные части. В этом случае выводы относительно стойкости схемы делают на основе оценки стойкости модифицированной схемы;

− показатели относительной защиты.  При оценке разработанных схем с идентичным функциональным назначением возникает задача сравнительного анализа стойкости предоставляемого ими уровня защиты. При проведении таких сравнений следует быть крайне осторожным в выборе критериев сравнения. Так, показателем, определяющим нижнюю границу стойкости блочных симметричных алгоритмов, является разница между количеством циклов алгоритма и количеством взломанных циклов. Однако при этом у аналитиков нет никакого общего согласия об определении или использовании такого показателя. Имеют место случаи, когда оцениваемые схемы имеют различные конструкции и концепции построения,  при их анализе используются отличные друг от друга показатели. Все это затрудняет осуществление оценки схем  с единых позиций. Таким образом, необходимо для всех схем определить некоторую нижнюю границу стойкости к методам анализа;

− характеристики среды эксплуатации и особенности применения схем.  В определенных криптографических средах представленные схемы могут обладать свойственными им достоинствами и недостатками. В качестве примера можно рассматривать схемы,  обладаю-щие стойкостью по отношению к силовым атакам и timing attack,  выполненным на смарткартах. Рассмотрение других типов атак на данные схемы было бы нецелесообразным;

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

− быстродействие схем.  Быстродействие представленных схем рассматривается на нескольких платформах с целью определения собственно быстродействия,  а также гибкости реализации и многоплатформенности приложений; 

− объем используемой памяти. В некоторых приложениях данный показатель является критичным. Любая конструкция должна гарантировать минимальный объем памяти без нанесения ущерба стойкости рассматриваемой схемы.

Таким образом,  на данный момент    в различных источниках рассмотрены показатели, относящиеся к оценке разных сторон схем преобразования.  Анализ документов,  представленных на конкурсы AES, NESSIE ,  показывает,  что наряду с показателями стой кости немаловажную роль имеют и аппаратно-реализационные показатели.

При определении эффективности функционирования схем ПШ целесообразно рассмотрение следующих основных групп показателей (рис. 6).

Рисонок 6.

Литература

1.       ASE (Конкурс). Материал из Википедии — свободной энциклопедии. Режим доступа: http://ru.wikipedia.org/wiki/AES_%28%D0%BA%D0%BE%D0%BD%D0%BA%D1%83%D1%80%D1%81%29

2.       NESSIE – конкурс криптоалгоритмов. Режим доступа: http://pgp.ua/articles/3-articles/70-nessie--konkurs-kriptoalgoritmov.html

3.       Потий А.В. Система показателей оценки эффективности функционирования схем поточного шифрования.

4.       СRYPTREC – проект по выбору криптостандартов Японии. Режим доступа: http://pgp.ua/articles/3-articles/64-cryptrec-proekt-po-vyboru-kriptostandartov-japonii.html