Конференция AES3 [продолжение истории]

(Май 2000)

Третья часть цикла о процессе принятия всеобщего криптостандарта AES (начало см. тут: часть 1; часть 2).

Летом нынешнего (2000) года должен завершиться второй круг конкурса шифров-кандидатов на AES — новый криптографический стандарт, призванный защищать конфиденциальную информацию по крайней мере в течение нескольких первых десятилетий XXI века.

Организатором конкурса является Национальный институт стандартов и технологий (НИСТ) США, с самого начала придавший процессу международный масштаб. Для подведения промежуточных итогов конкурса 13-14 апреля в нью-йоркском отеле «Хилтон» устраивалась «Третья конференция кандидатов на AES» или просто AES3.

Мероприятие это прошло по сути дела незамеченным средствами массовой информации. Причина тому понятна — сенсаций не было, писать неинтересно. Но это все же как посмотреть.

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

Напомним, что во втором круге участвуют 5 шифров-финалистов:
«Serpent» от Андерсона (Англия), Кнудсена (Дания) и Бихама (Израиль);
«Mars » от Копперсмита, Геннаро и др. из IBM (США);
«Rijndael » от Рэймена и Дамена (Бельгия);
«RC6» от Райвеста, Робшоу и др. из RSA Security (США);
«Twofish » от Шнайера, Келси и др. (США).

Если пытаться в двух словах охарактеризовать каждый из этих очень сильных шифров, то можно, с известной долей субъективности, сказать так: самую сложную конструкцию (что затрудняет анализ стойкости, т.е. является недостатком) имеют Mars и Twofish; наиболее простую конструкцию имеют Rijndael и RC6 (последний называют «самым элегантным»), но в основе этих алгоритмов лежат недостаточно глубоко изученные (т.е. пока «мутноватые») криптопреобразования; Serpent обладает наиболее прозрачной «консервативной» конструкцией, но на многих производит несколько тяжеловесное впечатление из-за выбранного разработчиками очень большого запаса прочности.

Криптоанализ

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

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

Типичный пример выглядит следующим образом: для вскрытия нескольких циклов одного из шифров требуется 2^229 частичных зашифрований, 2^69 байт памяти и 2^69 подобранных открытых текстов… Показательно, что и сами авторы такой «атаки» признают фактическую бесполезность подобного результата, но делают предположение, что в будущем, быть может, эти результаты смогут привести к чему-то реальному.

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

Производительность

В отличие от криптоаналитических работ, представленные на конференции результаты по производительности шифров были более содержательными.

За прошедший с предыдущей конференции год криптоалгоритмы-кандидаты были реализованы и протестированы в самых разнообразных воплощениях: как программно — на языках ANSI C, ассемблер, Java и проч. в условиях разнообразных архитектур; так и аппаратно — в смарт-картах и FPGA-чипах.

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

Самое забавное, что те версии кодов, что были представлены в начале состязаний в НИСТ США непосредственно авторами криптоалгоритмов, оказались самыми неторопливыми в работе. Причина тому, скорее всего, весьма простая — криптографы не особо искушены в написании оптимизированных программ.

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

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

Количество победителей

По инициативе НИСТ процесс выбора AES сопровождается дискуссией относительно количества шифров-победителей. На конференции AES3 вполне четко сформировалось мнение, что победитель определенно должен быть один.

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

В качестве компромисса был предложен вариант с одним победителем и одним «шифром для резерва». Эта идея, похоже, получила более широкую поддержку. Причем сразу же было отмечено, что в отличие от модели с «парным вариантом» AES1/AES2 , в модели «основной/резервный» AES должны быть совсем иные критерии отбора.

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

Финал

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

Ну, а если подводить итоги без шуток, то очень большие шансы на победу демонстрирует бельгийский шифр Rijndael (читается «рэйндал»).

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

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

(Окончание следует)