Advanced Encryption Standard (AES) – Часть1.Процесс разработки AES

Введение

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

Формальное начало процессу разработки нового криптостандарта было положено 2 января 1997 года, когда НИСТ объявил о своем решении разрабатывать. Затем, 12 сентября того же года был опубликован официальный призыв ко всем заинтересованным кругам о выдвижении своих алгоритмов в качестве возможных кандидатов.

Требования к новому стандарту были следующими:

• блочный шифр.
• длина блока, равная 128 битам.
• ключи длиной 128, 192 и 256 бит.

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

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

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

Принятие нового стандарта

Первый раунд - 15 кандидатов

20 августа 1998 года прошла "Первая конференция кандидатов на AES" или AES1, где НИСТ объявил о приеме на конкурс 15 алгоритмов-кандидатов, в разработке которых принимали участие криптографы из 12 стран мира. (Еще 6 алгоритмов- кандидатов, в том числе и российский, не были допущены к конкурсу на основании, как пояснил НИСТ, "неполноты" представленной документации.) Вот список алгоритмов, вышедших в первый круг отбора:

страна

алгоритм

кто представил

Австралия

LOKI97

Lawrie Brown, Josef Pieprzyk, Jennifer Seberry

Бельгия

RIJNDAEL

Joan Daemen, Vincent Rijmen

Великобритания, Израиль, Норвегия

SERPENT

Ross Anderson, Eli Biham, Lars Knudsen

Германия

MAGENTA

Deutsche Telekom AG

Канада

CAST-256

Entrust Technologies, Inc.

DEAL

Outerbridge, Knudsen

Корея

CRYPTON

Future Systems, Inc.

Коста-Рика

FROG

TecApro Internacional S.A.

США

HPC

Rich Schroeppel

MARS

IBM

RC6

RSA Laboratories

SAFER+

Cylink Corporation

TWOFISH

Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson

Франция

DFC

Centre National pour la Recherche Scientifique

Япония

E2

Nippon Telegraph and Telephone Corporation (NTT)

Представив все 15 алгоритмов на конференции AES1, а затем и в соответствующем официальном документе, НИСТ призвал общественность принять активное участие в исследовании и обсуждении кандидатов.

Понемногу выявились явные аутсайдеры конкурса - те алгоритмы, для которых были продемонстрированы методы криптоанализа, так или иначе понижающие возможную (при имеющихся длинах блока и ключа) стойкость. Среди наименее удачливых в этом отношении претендентов оказались шифры LOKI97, FROG, MAGENTA, DEAL и SAFER +. Для алгоритмов CRYPTON и DFC было продемонстрировано наличие "слабых ключей", облегчающих вскрытие.

Для остальных криптоалгоритмов в ходе первого раунда не было получено сколь- нибудь существенных криптоаналитических результатов. (Хотя, к примеру, шифр HPC или "заварной пудинг" особо и не анализировали вследствие чрезвычайной экзотичности конструкции.) В этом же раунде были проведены и тестирования программных реализаций алгоритмов на производительность. Непосредственно в НИСТ шифры исследовались на эффективность в оптимизированных реализациях на языках Си и Java.

После этого в марте 1999 года была проведена AES2 - Вторая конференция кандидатов на AES, где были обсуждены результаты криптографического анализа, проведенного мировым криптографическим сообществом в отношении алгоритмов-кандидатов, а также выявленная в процессе тестирования эффективность программных версий шифров.

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

Второй раунд - пятерка лучших

9 августа 1999 г. НИСТ объявил победителей первого раунда. На основании проделанного анализа и с учетом принятых в процессе обсуждения поправок к алгоритмам, были отобраны пять алгоримтов-финалистов: MARS, RC6, Rijndael, Serpent и Twofish (не попавшие в финал алгоритмы E2 и CAST-256 можно считать "замыкающими список лучших".) В пятерке шифров-победителей за время исследований в первом раунде не было найдено никаких сколь-нибудь существенных уязвимостей и по своим характеристикам каждый из кандидатов потенциально был оценен как "превосходная технология".

Далее рассмотрим каждый из алгоритмов в алфавитном порядке:

MARS выполняет последовательность преобразований в следующем порядке: сложение с ключом в качестве pre-whitening, 8 раундов прямого перемешивания без использования ключа, 8 раундов прямого преобразования с использованием ключа, 8 раундов обратного преобразования с использованием ключа, 8 раундов обратного перемешивания без использования ключа и вычитание ключа в качестве post-whitening. 16 раундов с использованием ключа называются криптографическим ядром. Раунды без ключа используют два 8х16- битных S-boxes и операции сложения и XOR. В дополнение к этим элементам раунды с ключом используют 32-битное умножение ключа, зависимые от данных циклические сдвиги и добавление ключа. Как раунды перемешивания, так и раунды ядра являются раундами модифицированной сети Фейштеля, в которых четверть блока данных используется для изменения остальных трех четвертей блока данных. MARS предложен корпорацией IBM.

RC6 является параметризуемым семейством алгоритмов шифрования, основанных на сети Фейштеля; для AES было предложено использовать 20 раундов. Функция раунда в RC6 задействует переменные циклические сдвиги, которые определяются квадратичной функцией от данных. Каждый раунд также включает умножение по модулю 32, сложение, XOR и сложение с ключом. Сложение с ключом также используется для pre- и pos-whitening. RC6 был предложен лабораторией RSA.

Rijndael представляет собой алгоритм, использующий линейно-подстановочные преобразования и состоящий из 10, 12 или 14 раундов в зависимости от длины ключа. Блок данных, обрабатываемый с использованием Rijndael, делится на массивы байтов, и каждая операция шифрования является байт-ориентированной. Функция раунда Rijndael состоит из четырех слоев. В первом слое для каждого байта применяется S-box размерностью 8х8 бит. Второй и третий слои являются линейными перемешиваниями, в которых строки рассматриваются в качестве сдвигаемых массивов и столбцы перемешиваются. В четвертом слое выполняется операция XOR байтов подключа и каждого байта массива. В последнем раунде перемешивание столбцов опущено. Rijndael предложен Joan Daemen (Proton World International) и Vincent Rijmen (Katholieke Universiteit Leuven).

Serpent является алгоритмом, использующим линейно-подстановочные преобразования и состоящим из 32 раундов. Serpent также определяет некриптографические начальную и заключительную перестановки, которые облегчают альтернативный режим реализации, называемый bitslice. Функция раунда состоит из трех слоев: операция XOR с ключом, 32-х параллельное применение одного из восьми фиксированных S-boxes и линейное преобразование. В последнем раунде слой XOR с ключом заменен на линейное преобразование. Serpent предложен Ross Anderson (University of Cambridge), Eli Biham (Technion) и LarsKnudsen (University of California San Diego).

Twofish является сетью Фейштеля с 16 раундами. Сеть Фейштеля незначительно модифицирована с использованием однобитных ротаций. Функция раунда влияет на 32-битные слова, используя четыре зависящих от ключа S-boxes, за которыми следуют фиксированные максимально удаленные отдельные матрицы в GF(2⁸), преобразование псевдо-Адамара и добавление ключа. Twofish был предложен Bruce Schneier, John Kelsey и Niels Ferguson (Counterpane Internet Security, Inc.), Doug Whiting (Hi/fn, Inc.), David Wagner (University of California Berkley) и Chris Hall (Princeton University).

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

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

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

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