"Компьютерра", декабрь 1999, n 49

О процессе принятия AES

Берд Киви

kiwibyrd@mail.ru


Скоро исполняется три года "процессу AES" - инициативе создания всеобщими усилиями "шифра 21 века". Инициативе, родившейся в Лаборатории информационных технологий Национального института стандартов (НИСТ) США.

Все это время совместными усилиями НИСТа, промышленности и мирового криптографического сообществы ведется работа над созданием "передового стандарта шифрования" или AES (Advanced Encryption Standard). Официальная цель работы - разработать Федеральный стандарт на обработку информации (FIPS), определяющий алгоритм шифрования, который будет способен защищать важную, но несекретную правительственную информацию на значительном протяжении следующего столетия. Как показывает опыт с DES, предыдущим стандартом такого рода, данный алгоритм будет использоваться не только правительством США, но также и американским частным сектором вкупе с финансовыми, промышленными и частными пользователями всего мира.

Начало

Формальное начало процессу разработки нового криптостандарта было положено 2 января 1997 года, когда НИСТ объявил о своем решении разрабатывать AES по причине моральной устаревшести DES и недостаточной эффективности заменившего его алгоритма "Triple DES" (по сути дела, тот же самый шифр, применяемый три раза). Затем, 12 сентября того же года был опубликован официальный призыв ко всем заинтересованным кругам о выдвижении своих алгоритмов в качестве возможных кандидатов. Тогда же были оговорены следующие первичные требования, которым должен удовлетворять AES: это должен быть незасекреченный, открыто опубликованный алгоритм шифрования, бесплатно доступный по всему миру. Спустя некоторое время было уточнено, что AES будет блочным шифром, реализующим криптографию с симметричным ключом, причем алгоритм (как минимум) должен поддерживать 128-битную длину шифруемого блока текста и длины ключей размером 128, 192 и 256 бит. Если же формулировать цель процесса AES совсем кратко, то ее можно свести к таким словам: "новый блочный шифр должен быть более стойким и более эффективным, чем Triple DES".

Критерии оценки алгоритмов-кандидатов были разработаны на основе первичных требований НИСТ и последовавшего затем публичного обсуждения на проведенном в Институте стандартов открытом семинаре 15 апреля 1997 года. Все оценочные критерии были разбиты на три основные категории: стойкость, стоимость, характеристики алгоритма.

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

Стоимость - это вторая важная область оценки, куда включаются и вопросы (аннулирования необходимости) лицензирования, и вычислительная эффективность (скорость) на разнообразных платформах, и требования к памяти.

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

Первый раунд - 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)

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

Архитектура шифров. Все блочные шифры имеют в своей основе следующую идею. Подлежащий зашифрованию текст нарезается на блоки равной длины, и каждый блок шифруется с помощью одного и того же криптопреобразования, зависящего от секретного ключа. Для повышения стойкости шифра это преобразование циклически повторяется несколько раз (итерируется). Основные различия алгоритмов, как правило, сводятся к различиям в цикловом преобразовании. Если кратко описывать архитектурные решения, представленные в алгоритмах-кандидатах, то можно выделить три основные группы: сети Файстеля, SP-сети, "неортодоксальные конструкции".

Сети Файстеля, классическая архитектура, названа в честь Хорста Файстеля - первого руководителя криптографического подразделения IBM и изобретателя шифра, из которого впоследствии получился DES. Здесь блок разбивается на две равные половины, одна из которых комбинируется с ключом, а затем складывается с другой половиной блока, после чего результат и исходная половина блока меняются местами. Среди кандидатов к "классической сети Файстеля" можно отнести алгоритмы DEAL, DFC, E2, LOKI97, MAGENTA, TWOFISH. К "модифицированной сети Файстеля" обычно относят конструктивно аналогичные шифры, манипулирующие субблоками разной длины. К таким алгоритмам относятся CAST-256, MARS, RC6.

SP-сети или "сети замен-перестановок". Другая общераспространенная архитектура, цикловое преобразование которой заключается в прогоне всего блока текста через слои замен и перестановок, зависящие от ключа. К этой группе принадлежат такие алгоритмы-кандидаты, как CRYPTON, Rijndael, SAFER+ и SERPENT.

"Неортодоксальные конструкции". Среди AES-кандидатов таких шифров оказалось два: FROG и HPC. Сразу можно сказать, что в науке криптографии "неортодоксальность" пока не приводила к гениальным прорывам. Не произошло этого и в процессе AES, поскольку алгоритмы из этой группы не продемонстрировали в процессе их изучения ни очевидной для всех стойкости, ни выдающейся производительности, ни особой гибкости.

Представив все 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 (США). В основе архитектуры кандидата от IBM лежит прочное "криптографическое ядро", новаторски упакованное в "защитную скорлупу" специальной структуры, призванной защитить стойкость алгоритма от всех нынешних и будущих атак. Весьма сложная схема шифра существенно затрудняет криптоанализ, что в условиях конкурса очевидно является минусом, нежели плюсом. Еще одна особенность - комбинирование в шифре множества различных операций, включая и сравнительно новую и поэтому относительно мало изученную технику циклического "прокручивания" бит слова на количество позиций, изменяющееся в зависимости от шифруемых данных и секретного ключа. Как следствие, обладая и в целом хорошей производительностью, особенно хорошо MARS работает на тех компьютерных платформах, которые эффективно поддерживают его прокручивания и перемножения. Ко второму раунду MARS пришел в модифицированном разработчиками виде, и теперь должен повысить свою гибкость и способность функционировать в ограниченных по памяти условиях, свойственных смарт-картам младших моделей.

RC6, алгоритм от RSA Laboratories (США). Как и все остальные разработки его главного конструктора, патриарха открытой криптографии Рональда Райвеста, этот шифр чрезвычайно прост по своей архитектуре (его можно даже воспроизвести по памяти) и весьма компактно укладывается как в программную, так и в аппаратную реализацию. Простота алгоритма должна существенно облегчить дальнейший анализ его стойкости во втором раунде, к тому же серьезную помощь должны оказать и уже имеющиеся результаты криптоанализа его предшественника, алгоритма RC5 схожей конструкции. В RC6 не используются традиционные в блочных шифрах таблицы замены (S-боксы), вместо этого опору стойкости алгоритма составляет техника прокручивания бит на разное количество позиций в зависимости от шифруемых данных. Собственно говоря, именно с подачи Райвеста эта техника и получила в свое время толчок к распространению в новых криптосхемах. По своей производительности RC6 весьма быстрый алгоритм, который особенно хорош на платформах, эффективно поддерживающих операции прокручивания и перемножения. Быстро здесь реализуется и еще одна существенная для шифра фаза - разворачивание ключа.

Rijndael (Бельгия, в соответствии с фламандскими правилами название читается как "Рэндал"). Самостоятельная и оригинальная разработка молодых, но достаточно широко известных в криптографическом сообществе ученых из Бельгии Йона Дамена и Винсента Рэмена. Алгоритм демонстрирует превосходную производительность на всех рассматриваемых в состязании платформах. Для шифра характерны быстрое разворачивание ключа и низкие требования к памяти, так что он также хорошо работает и в аппаратной реализации, и в ограниченных по памяти условиях. Простая конструкция схемы и консервативный выбор операций должны облегчить дальнейший криптоанализ шифра. Кроме того, специалистами отдельно отмечается, что избранные конструкторами операции относительно просто защитить от известных опасных атак на физическую реализацию криптоалгоритма. Еще одна важная положительная характеристика (хотя и не рассматривавшаяся при выборе финалистов) - в шифре Rijndael имеется существенный потенциал к распараллеливанию, то есть к получению выгод в производительности благодаря применению компьютерных процессоров, позволяющих одновременно выполнять множество инструкций.

Serpent (Великобританя, Израиль, Норвегия). Шифр "Змей" - пока последний из совместных проектов англичанина Росса Андерсона и израильтянина Эли Бихама, имеющих в своем активе уже целый зверинец криптоалгоритмов: Bear, Lion, Tiger (медведь, лев, тигр). При разработке Serpent авторы специально пригласили датчанина Ларса Кнудсена (работающего в университете Бергена, Норвегия), знаменитого своими крайне успешными криптоаналитическими работами по вскрытию блочных шифров, чтобы он выявил все возможные слабые места в стойкости нового алгоритма. Поскольку и сам Бихам - соавтор метода дифференциального анализа, лежащего в основе современных методов вскрытия блочных шифров, то в результате такого сотрудничества появился чрезвычайно стойкий алгоритм. "Ультраконсервативный по запасу прочности", как охарактеризовали его в НИСТ, поскольку создав шифр, противостоящий всем известным на сегодня атакам, разработчики затем удвоили количество его итераций. Как следствие этого, по своей скорости Serpent оказывается медленнее, чем четыре остальных финалиста. Тем не менее, для повышения производительности разработчиками предложен специальный метод оптимизации ("bitslice"), изобретенный в свое время Бихамом при оптимизации программных версий шифра DES. Алгоритм Serpent хорошо ложится в аппаратное исполнение и в ограниченные по памяти устройства. Реализующая SP-сеть простая конструкция и консервативный выбор операций существенно упрощают анализ стойкости, а также выбранные операции облегчают защиту от атак на физические реализации шифра.

Twofish (США). Данный алгоритм - прямой потомок качественного и широко распространенного шифра Брюса Шнайера Blowfish. Новая криптосхема демонстрирует быструю и разностороннюю производительность на множестве платформ, хорошо укладывается как в аппаратные, так и в ограниченные по памяти смарт-картные реализации. Одна из главных особенностей шифра - изменяющиеся в зависимости от секретного ключа таблицы замены (S-боксы). Как полагают разработчики, в общем случае такие таблицы обеспечивают более высокую стойкость, нежели S-боксы с фиксированными значениями (успешное противостояние Blowfish всем попыткам вскрытия в течение последних пяти лет косвенно подтверждает это утверждение). Возможность проведения предварителных вычислений данных таблиц позволяет шифру Twofish при необходимости гибко наращивать свою производительность. Схема имеет множество настраиваемых элементов, и в зависимости от этих установок, Twofish может быть оптимизирован по скорости, разворачиванию ключа, памяти, размеру кода в программной реализации или по занимаемому пространству в реализации аппаратной. Ощутимый минус конструкции - ее сложность, затрудняющая криптоанализ стойкости шифра. Помимо самого Шнайера в команду разработчиков входит почти весь коллектив его фирмы Conterpane Systems (Джон Келси, Крис Холл и Нильс Фергюсон; сейчас, правда, фирма сильно расширяется), а также Дуг Уайтинг - шеф по науке фирмы Hifn, и Дэвид Вагнер - аспирант Калифорнийского университета в Беркли.

Вопросы, вопросы...

Объявив финалистов, НИСТ формально открыл следующий, второй раунд процесса оценки оставшихся кандидатов, который продлится до 15 мая 2000 года. Однако, помимо сугубо технических вопросов криптоанализа и тестирования эффективности схем на разных платформах, четко обрисовался и обширный круг сопутствующих процессу непростых проблем иного качества.

В начале ноября этого года НИСТ опубликовал довольно внушительный список "Дискуссионных вопросов относительно AES". Будучи всецело преданными избранному принципу открытого коллегиального обсуждения, эксперты НИСТ вынесли эти проблемы на суд общественности. Перечислим основные темы развернувшейся дискуссии.

Сколько должно быть алгоритмов AES - один или несколько? За то, чтобы в итоге их было несколько, выдвигаются следующие аргументы: (1) гибкость, поскольку в случае вскрытия одного из AES-шифров сразу будет иметься под рукой уже реализованная альтернатива; (2) максимально широкое покрытие всех областей применения, поскольку в рамках одного алгоритма практически невозможно одновременно обеспечить такие взаимо-исключающие качества, как максимальная стойкость и максимальная производительность. Главные аргументы за то, чтобы AES был единственным: (1) стоимость, поскольку несколько алгоритмов влекут за собой проблемы совместимости и повышают стоимость продуктов при реализации в них нескольких шифров; (2) риск, поскольку увеличение числа алгоритмов повышает вероятность того, что один из стандартов будет взломан. Если же какой-то из алгоритмов будет вскрыт, то это подорвет доверие публики и к оставшимся.

В кулуарах нередко всплывает и еще одна связанная со всем этим проблема: сможет ли Институт стандартов самой передовой в технологических аспектах страны избрать в качестве национального эталона шифрования иностранную разработку, коль скоро зарубежные схемы ничем не уступают американским? Для самолюбия США это, мягко говоря, было бы несколько уязвительно. Видимо, подстилая соломку под вполне вероятный компромиссный вариант "один отечественный-один импортный", НИСТ включает в список сопутствующих вопросов и почти риторические, типа "Если избрать единственный AES-шифр, то что делать в случае его вскрытия? Когда следует решать, что доверие к шифру подорвано? Если выбирать несколько, то сколько именно?"...

Как строить соотношение между скоростью и запасом стойкости? В блочных шифрах, как правило, увеличение количества итераций циклового криптопреобразования повышает стойкость, но соответственно снижает и скорость зашифрования/расшифрования. Под запасом стойкости принято понимать количество циклов, выполняемых алгоритмом после того, как достигнут "порог стойкости" (т.е. когда обеспечено противостояние всем известным атакам). Разработчики разных алгоритмов так или иначе отдавали предпочтение либо повышению стойкости, либо повышению производительности. Вопрос же в том, какими критериями в соотношении "скорость / запас стойкости" руководствоваться НИСТу при выборе победителя?

Насколько при выборе AES важны смарт-карты младшего класса и подобное им оборудование? В связи со смарт-картами вообще возникает множество вопросов, поскольку не все алгоритмы одинаково хорошо вписываются в аскетичные требования по памяти RAM и ROM . Смарт-карты весьма уязвимы к разработанным в последние годы атакам типа таймерной, дифференциального анализа питания и подобным им методам вскрытия. В функционально ограниченных смарт-картах младшего класса особенно сложно противостоять такого рода атакам. Высказывалось мнение, что подобные устройства по самой своей сути небезопасны и вопрос о безопасной реализации AES в таких условиях просто неуместен. Имеется, естественно, и противоположное мнение.

Насколько важным является соотношение между производительностью в программной и аппаратной версиях AES-шифра? В первом раунде тестировались исключительно программные реализации алгоритмов. Во втором раунде алгоритмы будут описаны также на языке аппаратной разработки VHDL, что позволит оценить их производительность при реализации на чипах FPGA и, возможно, ASIC. Но сразу же возникает вопрос, какие из метрик реализации и производительности считать наиболее важными для AES?

Какие режимы функционирования должны быть доступны для AES? Как известно, для предыдущего стандарта, шифра DES, было регламентрировано 4 режима использования: ECB - электронная кодововая книга, CBC - зацепление шифрблоков, CFB - обратная связь от шифртекста, и OFB - обратная связь от выхода (стандарт FIPS 81, DES Modes of Operation ). В качестве предмета дискуссии вынесен вопрос о том, пригодны ли для AES данные режимы работы? Поскольку каждый из этих режимов имеет свои преимущества и недостатки, есть еще один вопрос: имеются ли другие режимы, которые были бы желательны для AES?

Что дальше

Ближе к концу второго раунда НИСТ проведет AES3 - Третью конференцию AES- кандидатов для открытого обсуждения результатов анализа алгоритмов- финалистов. Эта конференция пройдет 13-14 апреля 2000 года в Нью-Йорке. Затем НИСТ намерен изучить и обобщить всю доступную информацию, после чего последует его объявление предлагаемого стандарта AES, который будет содержать один или несколько алгоритмов, отобранных среди финалистов. AES будет предложен в качестве Федерального стандарта (FIPS) и опубликован для изучения и комментариев общественности. В случае необходимости, в проект стандарта будут внесены поправки. Как планируется, процесс широкого изучения и обсуждения продлится около года, так что окончательное принятие стандарта ожидается к лету 2001 года.

*******

При подготовке статьи использованы, главным образом, материалы с официальной страницы НИСТ США "The AES home page". Дискуссионный форум для обсуждения алгоритмов-кандидатов и всего AES- процесса находится по адресу http://aes.nist.gov .

декабрь 1999


Hosted by uCoz