Конкурс на новый криптостандарт AES

Б. Киви

DES и AES
Принятые на конкурс алгоритмы

В сентябре 1999 года начинается второй раунд конкурса на "передовой стандарт шифрования" AES или Advanced Encryption Standard. Теперь среди финалистов первого круга предстоит избрать лучший алгоритм, который станет новым американским криптостандартом на XXI век.

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

В 1972 и 1974 годах Национальным бюро стандартов США (сегодня это ведомство именуется НИСТ, или Национальный институт стандартов и технологий) был объявлен первый открытый конкурс на федеральный стандарт шифрования данных. Результатом этого начинания стал DES (Data Encryption Standard) - возможно, самый широко используемый и самый успешный криптоалгоритм в мире. (Достаточно отметить, что за четверть века самого скрупулезного криптоанализа так и не было найдено эффективных методов вскрытия этого шифра. Под "эффективным" понимается метод, существенно сокращающий трудозатраты по сравнению с лобовым вскрытием шифра путем тотального перебора ключей.)

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

К середине 1990-х годов было уже совершенно очевидно, что DES стал архаикой: 56 бит ключа - это слишком мало, шифр весьма медленно работает в программных реализациях, да и аппаратная реализация изначально была сориентирована на 4-битные процессоры 1970-х. С учетом всех этих обстоятельств, в январе 1997 г. НИСТ объявил о запуске программы по принятию нового криптостандарта AES. Согласно целям новой программы "AES будет определять незасекреченный алгоритм шифрования, способный защищать важную информацию правительственного уровня в следующем столетии". Исходные минимальные требования к новому криптоалгоритму были следующими:

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

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

В апреле 1997 года, после обсуждения проблемы со всеми заинтересованными сторонами, НИСТ сформулировал более конкретные требования к новому криптостандарту и их разъяснения. По убеждению НИСТ, AES должен быть симметричным блочным, а не поточным шифром. (Напомним, что в симметричном шифре один и тот же ключ применяется как для зашифрования, так и для расшифрования сообщения. Поточный шифр применяет изменяющееся от такта к такту криптопреобразование к отдельным цифрам потока данных, а блочный шифр применяет постоянное криптопреобразование к целым блокам данных.) При разъяснении позиции НИСТ было сказано, что, во-первых, блочный шифр AES станет прямым преемником концептуально такого же шифра DES, и, во-вторых, уже имеющиеся утвержденные стандарты режимов функционирования криптоалгоритма ориентированы на блочное шифрование.

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

В окончательной формулировке требования к AES стали выглядеть так. Шифр должен иметь размер блока 128 бит (существенно, что это требование сразу же вывело из игры почти все применяющиеся ныне алгоритмы, традиционно ориентированные на 64-битный блок), и допускать размеры ключей в 128, 192 и 256 бит. На сегодняшний день вполне достаточной длиной ключа считают 80 бит, однако, учитывая, что AES принимается на 20-30 лет, длина ключа выбрана с солидным запасом. Для наглядного представления о том, что дает 128-битный размер ключа, указывают, что количество всех возможных ключей такого размера равно примерно 340,000,000,000,000,000,000,000,000,000,000,000,000 (или 340 с 36 нулями).

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

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

Открывая первый раунд конкурса на новый криптостандарт, представитель НИСТ Майлз Смид удачно пошутил, представив аудитории "Общий алгоритм перехода от DES к AES":

1. Убедить руководство НИСТ в том, что DES уже недостаточно безопасен;
2. Убедить руководство НИСТ в том, что "тройной DES" недостаточно хорош, чтобы стать AES;
3. Призвать лучших криптографов мира предложить свои алгоритмы;
4. Призвать лучших криптографов мира проанализировать эти алгоритмы (что делается ныне);
5. Избежать ареста за нарушение экспортных законов;
6. Молиться о консенсусе;
7. Если же все это не пройдет, то приравнять AES = DES.

Как показали шаги 3 и 4 "Общего алгоритма", процесс перехода стартовал весьма успешно и на смену DES идут весьма достойные преемники.

В данном разделе дадим краткий обзор шифров-кандидатов, участвующих в первом круге конкурса.

CAST-256 (Канада)

Криптоалгоритм от канадской фирмы Entrust Technologies. Карлайл Эдамс, разработавший концепцию семейства шифров CAST вместе со Стэффордом Таваресом в начале 1990-х годов, говорит о новом шифре следующее: "Алгоритм CAST-256 в своей конструкции всецело опирается на идеи, которые уже очень хорошо проанализированы и проверены. Многие другие предложенные шифры являются довольно новыми, в том смысле, что новыми являются конструктивные аспекты этих шифров, в нашем же случае мы попытались опереться на вещи, уже доказанные".

Предыдущий шифр этого семейства - CAST-128 - является неофициальным канадским стандартом шифрования, и респектабельная теоретическая база данной архитектуры в сочетании с успешным противостоянием криптоанализу могли бы дать алгоритму CAST-256 весьма реальные шансы на победу в конкурсе. Однако, среди явных минусов шифра называют такие немаловажные факторы, как более медленную по сравнению с другими кандидатами производительность (следствие "консервативного дизайна"), а также необходимость хранения достаточно больших табличных массивов (4 килобайта), что затрудняет реализацию алгоритма в некоторых приложениях.

CRYPTON (Южная Корея)

Шифр Crypton представлен южнокорейской компанией Future Systems, с конца 1980-х годов работающей на рынке сетевого обеспечения и защиты информации. Автор алгоритма Че Хун Лим признает, что конструкция его шифра во многом опирается на идеи шифра SQUARE бельгийских криптографов Дамена и Рэмена (также участвующих в конкурсе). Другими словами, здесь нет традиционной для многих блочных шифров так называемой "структуры Фейстела", оперирующей в каждом цикле шифрования половиной блока данных (как в DES или CAST, к примеру). Основу данного шифра составляет другая стандартная конструкция - так называемая SP-сеть, т.е. повторяющаяся цикловая функция из замен-перестановок, ориентированная на распараллеленную нелинейную обработку всего блока данных. Помимо высокой скорости, к преимуществам такой конструкции относят и то, что она облегчает исследование стойкости шифра к методам дифференциального и линейного криптоанализа, являющимся на сегодня основными инструментами вскрытия блочных шифров.

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

DEAL (Норвегия, Канада)

Самый первый из предложенных кандидатов на AES, появившийся летом 1997 года, шифр разработан датчанином Ларсом Кнудсеном, одним из наиболее блестящих криптоаналитиков в области блочного шифрования, и его канадским коллегой Ричардом Аутебриджем. Собственно говоря, DEAL нельзя называть самостоятельной разработкой, поскольку, по сути дела, это остроумная схема использования старого знакомого DES в новой, более стойкой конфигурации. Проще говоря, это DES с увеличенными длинами блока данных и ключа, соответствующими требованиям AES. Главный недостаток такого подхода - сохраняются неудобства реализации, присущие DES, а это серьезно сказывается на производительности шифра. Учитывая, что у пользователей уже имеется и достаточно широко применяется надежный (и медленный) тройной-DES, можно уверенно констатировать минимальные шансы DEAL на победу.

Казус с тем обстоятельством, что Кнудсен везде фигурирует как представитель Норвегии, объясняется чрезвычайной мобильностью датского ученого, за несколько последних лет уже успевшего поработать во Франции, Швейцарии и Бельгии, а в настоящее время преподающего криптологию в университете Бергена, Норвегия.

DFC или Decorrelated Fast Cipher (Франция)

Французский алгоритм DFC или "декоррелированный быстрый шифр" - совместная разработка криптографов парижской Высшей нормальной школы и Национального центра научных исследований (CNRS). Шифр создан большим коллективом из 8 человек и базируется на фундаменте недавно созданной технологии конструирования блочных шифров c доказуемой стойкостью к известным криптоаналитическим атакам. Эта методика разработана, главным образом, одним из соавторов DFC Сержем Водене. Водене имеет репутацию превосходного криптографа, его теоретические идеи встречены с большим интересом, но нельзя не отметить, что уже появились аналитические результаты, несколько скомпрометировавшие достаточно красивую теорию.

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

E2 (Япония)

Шифр представлен на конкурс японской национальной телекоммуникационной компанией NTT. Название "E2" обозначает "Efficient Encryption" или "эффективное шифрование", а в остальном - это как бы японский близнец французского шифра DFC. Имеется в виду, что для описания конструкции E2 применимы практически те же самые слова (даже разработчиков - тоже 8 человек!), но с одним национальным нюансом - методика конструирования доказуемо стойких шифров здесь своя, японская.

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

FROG (Коста-Рика)

Шифр FROG выставила на конкурс международная компания TecApro Internacional, зарегистрированная в Коста-Рике. Авторы криптоалгоритма - Д. Георгудис, Д. Леру и Б. Шаве - люди, мягко говоря, малоизвестные в криптографическом мире. Согласно характеристике разработчиков, FROG - это "новый шифр с неортодоксальной структурой".

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

HPC или Hasty Pudding Cipher (США)

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

Дабы простимулировать интерес к криптоанализу своего изобретения, автор обязался награждать каждого аналитика бутылкой знаменитого шампанского "Дом Периньон". Награждение будет происходить до тех пор, пока шифр HPC не будет вскрыт, либо пока не опустеет ящик (10 бутылок).

LOKI97 (Австралия)

Новый представитель достаточно широко известного ряда шифров LOKI, разрабатываемых в стенах Академии министерства обороны Австралии с 1989 года. Авторы криптоалгоритма: Лори Браун (по сути дела, шифр LOKI - это основа его докторской диссертации), Йозеф Пьепшик (польский криптограф, перебравшийся в Австралию в конце 80-х годов) и Дженифер Себери - одна из немногих женщин-криптографов "с именем".

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

MAGENTA (Германия)

Шифр, представленный немецкой телекоммуникационной компанией Deutsche Telekom AG. Авторы алгоритма - Клаус Хубер и Михаэль Якобсон. MAGENTA - это аббревиатура от развернутого названия шифра, звучащего как "Многофункциональный алгоритм для шифрования общего назначения и сетевых телекоммуникаций". В настоящее время этот шифр используется внутри Deutsche Telekom для защиты важных данных компании. Криптоалгоритм изначально разрабатывался для работы на высоких скоростях (порядка гигабит в секунду). В основе его конструкции лежит традиционная сеть Фейстела, а в качестве цикловой нелинейной функции выбрано быстрое адамарово преобразование.

Немцы предпочли не публиковать заранее свой алгоритм в Интернете. Тем большее разочарование, надо полагать, постигло их непосредственно на самой конференции AES1, когда в ходе сессии вопросов-ответов криптосхема MAGENTA была "на лету", по сути дела, завалена искушенными в криптоанализе слушателями.

MARS (США)

Шифр MARS выставлен на конкурс корпорацией IBM. Эта компания с 60-х годов занимается самостоятельными криптографическими исследованиями, и нелишне напомнить, что алгоритм DES родился именно в стенах IBM, а Хорст Фейстел - автор той самой "сети Фейстела" - был первым руководителем криптографического подразделения корпорации.

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

RC6 (США)

Как говорится в рекламных анонсах к RC6 - новейшему алгоритму Рональда Райвиста - это "быстрый, гибкий и необычно компактный алгоритм - сочетание мощи и элегантности простоты". Райвист - это "R" в знаменитом алгоритме RSA, он один из сооснователей криптофирмы RSA Data Security и изобретатель широко используемых шифров RC2 и RC4, а также хеш-функций MD2, MD4 и MD5. Своими соавторами при создании нового криптоалгоритма Райвист называет Мэтта Робшоу, Рэя Сидни и Лайсу Йин - криптографов исследовательского центра RSA Laboratories.

RC6, возможно, самый быстрый шифр из всех кандидатов на AES в условиях платформ Pentium Pro/II, но он не очень хорошо ложится на 8-битные процессоры смарт-карт. По всеобщему признанию, шифр RC6 - это прямое эволюционное развитие предыдущего криптоалгоритм Райвиста под названием RC5, появившегося в 1995 году. Как сообщил автор, внесенные в конструкцию новшества прежде всего обусловлены результатами криптоанализа RC5 в кругах криптографической общественности. По признанию специалистов, RC6 - превосходный кандидат.

RIJNDAEL (Бельгия)

Шифр разработали известные бельгийские криптографы Йон Дамен и Винсент Рэмен из Лувенского католического университета, являющегося одним из признанных центров академической криптографии не только Бельгии, но и всей Европы. Конструкция нового шифра в значительной степени опирается на сильные идеи, воплощенные и проверенные в архитектуре шифра SQUARE, предыдущего детища этих же авторов, представленного в начале 1997 года. Как показали предварительные исследования, Rijndael может быть очень эффективно реализован на самых разных процессорах и чрезвычайно успешно противостоит известным криптоаналитическим атакам.

По замечанию авторов, главная проблема с данным шифром - это как читать его название, составленное из фамилий криптографов. В соответствии с фламандскими традициями, "ij" читается как "э", а "ae" - как открытое "а". Так что "Rijndael" - это просто "Рэндал"...

SAFER+ (США)

Новая реинкарнация достаточно широко известного сильного шифра SAFER, впервые представленного в 1993 году патриархом академической криптографии Джеймсом Мэсси из швейцарского политехникума ETH (Цюрих). Шифр SAFER был разработан им по заказу американской криптофирмы Cylink, одним из основателей которой в начале 80-х годов был и сам Дж. Мэсси. Поэтому неудивительно, что новый шифр SAFER+ выдвинут на конкурс AES корпорацией Cylink, а главный криптограф Cylink Лили Чен названа корпорацией как соавтор криптоалгоритма. (Правда, сам Джеймс Мэсси почему-то считает, что его соавторами являются Гурген Хачатрян и Мелсик Курегян из Академии наук Армении, известной своими многолетними связями с Cylink.)

Чтобы дать представление об авторитете Мэсси как криптографа, достаточно упомянуть, что он является одним из двух авторов очень сильного блочного шифра IDEA - криптографической основы знаменитой программы PGP (Pretty Good Privacy). Говоря же о минусах новой схемы, следует отметить, что шифр SAFER+ разрабатывался под 8-битные микропроцессоры и довольно медленно работает на 32-битных машинах.

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

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

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

TWOFISH (США)

Еще один потенциальный финалист. Шифр основан на хорошо известном, популярном и широко используемом в Интернете криптоалгоритме Blowfish, разработанном в 1993 году Брюсом Шнайером, автором книги-бестселлера "Прикладная криптография". За прошедшие годы в открытой литературе не появилось ни одной работы о сколь-нибудь успешном вскрытии Blowfish. В команду создателей нового шифра Twofish почти в полном составе входит консалтинговая криптофирма Шнайера Counterpane Systems (сам Шнайер, Джон Келси, Крис Холл и Нильс Фергюсон), а также шеф по технологиям фирмы Hi/fn Дуг Уайтинг и Дэвид Вагнер, исследователь из калифорнийского университета Беркли, известный по ряду заметных криптоаналитических работ.

По оценкам специалистов, новый алгоритм Twofish эффективно реализуется на 32-битных микропроцессорах, 8-битных смарт-картах и ожидаемых в будущем 64-битных архитектурах, предложенных фирмами Intel и Motorola. Дабы подчеркнуть криптостойкость своего творения, создатели Twofish объявили об учреждении приза в 10 тысяч долларов за лучшую криптоаналитическую атаку против Twofish.

Бесспорно, на конкурс AES представлено самое лучшее из того, чего достигли открытая академическая и промышленная криптография за четверть века своего развития. Теперь предстоит период тщательного изучения выставленных на конкурс кандидатов. Как мрачно пошутил один из участников конкурса Брюс Шнайер, вся эта история напоминает ему некое гигантское "дерби на выживание": на трассу выходит полтора десятка претендентов, которые крушат друг друга до тех пор, пока не останется сильнейший.

Практически сразу же вслед за публикацией в Интернете описания шифра LOKI97, появились и результаты его криптоанализа, выполненного Ларсом Кнудсеном и Винсентом Рэменом (из команд "Serpent" и "Rijndael", соответственно). Из этих результатов следовало, что цикловая функция шифра не обладает достаточной криптографической стойкостью, и с довольно высокой вероятностью можно подбирать криптоаналитические методы вскрытия шифра.

Команда "Twofish" (Вагнер, Фергюсон и Шнайер) нанесла мощный удар по команде "Frog". Было показано, что ключ шифра Frog можно вскрывать при трудозатратах около 2⁵⁷. Для DES, к примеру, с его 56-битным ключом это было бы прекрасным показателем стойкости (поскольку на лобовое вскрытие ключа тотальным перебором требуется 2⁵⁶ опробований), однако, для шифра с длиной ключа по меньшей мере 128 бит этого уже слишком мало. О том, как в ходе конференции AES1 совместными усилиями участников команд "Twofish" и "Serpent" был завален германский проект "Magenta", уже упоминалось.

Период первичной оценки шифров продолжался вплоть до конца апреля 1999 года, вехой завершения этого этапа стала конференция AES2 в Риме. Выбрав для проведения форума итальянскую столицу, организаторы конкурса явно хотели подчеркнуть международный характер мероприятия (действительно, в конференции приняли участие свыше 180 человек из 23 стран). Как надеялись в НИСТ, период времени между AES1 и AES2 достаточен для того, чтобы исследователи криптографического сообщества проверили стойкость и быстродействие всех алгоритмов, в результате чего количество претендентов естественным образом сократилось бы до пяти или менее того. Однако, нельзя сказать, чтобы все прошло гладко и в соответствии с первоначальным планом.

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

Предварительные испытания эффективности алгоритмов-кандидатов провел сам НИСТ. Под эффективностью шифра понимаются два основных показателя: скорость шифрования/расшифрования и скорость формирования криптографических ключей.

В качестве первой тестовой платформы был выбран IBM-совместимый ПК с процессором Intel-Pentium Pro 200 МГц, с 64 Мб RAM и ОС Windows 95. Тестирование проводилось с оптимизированными кодами на языке ANSI C, представленными самими разработчиками алгоритмов. (Сразу же было подчеркнуто, что предусмотрены и другие тесты на различных платформах и с различными компиляторами.)

Испытания на скорость шифрования/расшифрования (компилятор Borland) выявили 6 более-менее очевидных лидеров, продемонстрировавших скорость свыше 25 Мбит/сек: Crypton (40 Мбит/сек); Rijndael; RC6; E2; Twofish и Mars (26 Мбит/сек). На последних местах оказались Magenta и HPC со скоростью около 2 Мбит/сек, остальные алгоритмы показали результаты от 6 до 10 Мбит/сек. Сразу же было отмечено, что при других компиляторах показатели могут сильно отличаться. Например, при компиляторе DJGPP алгоритм MARS демонстрирует скорость свыше 60 Мбит/сек, а лидер Crypton - менее 30 Мбит/сек. Что же касается скорости формирования ключей, то здесь разброс оказался значительно шире: от 500 000 кл/мсек (Crypton) до 100 кл/мсек (HPC и FROG). Среди лидеров в этом разряде можно отметить алгоритмы Magenta, E2, Safer+, RC6, Rijndael, Mars, Serpent, Twofish.

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

Что же касается стойкости шифров, то этот показатель проверить значительно сложнее. В ходе этапа предварительной оценки первого круга на web-сайте НИСТ и непосредственно на конференции AES2 было представлено значительное количество криптоаналитических результатов, так или иначе "подмочивших" репутацию практически всех шифров-кандидатов. Однако, если не говорить о явных аутсайдерах LOKI, Frog, Magenta и HPC, то никаких очевидных слабостей в алгоритмах не обнаружено.

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

До середины лета с.г. запланирован период завершения первого раунда, в течение которого авторам предоставлена возможность внести "поправки и дополнительные разъяснения" к своим алгоритмам. Затем будут объявлены финалисты и с сентября 1999 г. начинается второй раунд конкурса.

В ходе второго круга Агентством национальной безопасности США будет осуществлена аппаратная реализация и тестирование шифров-финалистов на эффективность и стойкость. Дальнейшим изучением алгоритмов будет заниматься и открытое криптографическое сообщество. Результаты тестирований второго раунда будут оглашены на конференции AES3, которая пройдет в середине апреля 2000 г. в Нью-Йорке. На август же 2000 года намечено объявление победителя (победителей).

Явно неслучайное множественное число в отношении шифра-победителя - это, конечно же, отражение появившихся в НИСТ сомнений относительно однозначного исхода конкурса на AES. Что ж, время покажет...

апрель 1999