Конкурс на Advanced Encryption Standard

Целью проведения конкурса AES был поиск нового стандарта шифрования на замену таких алгоритмов как DES и IDEA, криптостойкость которых была подвергнута сомнению, а впоследствии и вовсем признали эти алгоритмы ненадежными. В результате проведения конкурса был выбран новый стандарт шифрования Advanced Encryption Standard (AES). Новый стандарт дал новое направление в криптологии — реализация шифров шифрования информации на многоядерных процессорах, которые использовали несколько потоков для обработки информации. Это позволило увеличить длину ключа для зашифровки и дешифровки информации.

С 2011 года новые процессоры Intel получать новые инструкции для AES[3]. AES является ведущим стандартом симметричного шифрования, который используется в широком диапазоне приложений, и постоянно растущий спрос на безопасность и приватность данных обеспечил его повсеместное применение.

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

поиск источников информации, связанных с основными этапы конкурса на AES;

произвести анализ источников информации;

провести сравнение основных шифров и сделать выводы.

1. DES и AES

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

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

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

AES должен быть открыто опубликован;

AES должен быть симметричным блочным шифром;

AES должен быть разработан так, чтобы длину ключа можно было при необходимости увеличить;

AES должен допускать как аппаратную, так и программную реализацию;

AES должен быть бесплатным, то есть либо незапатентованным, либо с аннулированными патентными правами;

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

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

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

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

В окончательной формулировке требования к AES стали выглядеть так. Шифр должен иметь размер блока 128 бит (существенно, что это требование сразу же вывело из игры почти все применяющиеся ныне алгоритмы, традиционно ориентированные на 64-битный блок), и допускать размеры ключей в 128, 192 и 256 бит[4]. На сегодняшний день вполне достаточной длиной ключа считают 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» [7]:

Убедить руководство НИСТ в том, что DES уже недостаточно безопасен;

Убедить руководство НИСТ в том, что «тройной DES» недостаточно хорош, чтобы стать AES;

Призвать лучших криптографов мира предложить свои алгоритмы;

Призвать лучших криптографов мира проанализировать эти алгоритмы (что делается ныне);

Избежать ареста за нарушение экспортных законов;

Молиться о консенсусе;

Если же все это не пройдет, то приравнять AES = DES.

NIST установил всего два обязательных требования к алгоритмам-участникам конкурса:

128-битный размер блока шифруемых данных, не менее трех поддерживаемых алгоритмом размеров ключей шифрования: 128, 192 и 256 бит.

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

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

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

2.1 CAST-256 (Канада)

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

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

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

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

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

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

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

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

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

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

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

2.5 E2 (Япония)

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

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

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

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

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

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

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

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

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

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

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

2.9 MAGENTA (Германия)

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

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

2.10 MARS (США)

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

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

2.11 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 — превосходный кандидат.

2.12 RIJNDAEL (Бельгия)

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

2.13 SAFER+ (США)

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

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

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

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

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

2.15 TWOFISH (США)

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

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

2. Основные этапы конкурса на AES

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

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

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

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

3. Предварительные итоги первого раунда

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

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

В качестве первой тестовой платформы был выбран IBM-совместимый ПК с процессором Intel-Pentium Pro 200 МГц, с 64 Мб RAM и ОС Windows 95[5]. Тестирование проводилось с оптимизированными кодами на языке 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 было представлено значительное количество криптоаналитических результатов, так или иначе «подмочивших» репутацию практически всех шифров-кандидатов.

3.1 Финалист AES — шифр MARS

Алгоритм MARS был разработан коллективом криптологов из корпорации IBM. Именно IBM в свое время разработала семейство алгоритмов Lucifer, которое легло в основу прошлого стандарта шифрования США — DES. Из авторов Lucifer в разработке алгоритма MARS принял участие Дон Копперсмит (Don Coppersmith), известный также и другими работами в области криптологии.

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

Структура алгоритма Разработчики алгоритма MARS придали ему сильно гетерогенную структуру — раунды алгоритма весьма различаются между собой. Алгоритм MARS можно описать следующим образом:

Рис. 1 — Структура алгоритма MARS

Предварительное наложение ключа: на 32-битные субблоки A, B, C, D накладываются 4 фрагмента расширенного ключа k0… k3 операцией сложения по модулю 232.

Выполняются 8 раундов прямого перемешивания (без участия ключа шифрования).

Выполняются 8 раундов прямого криптопреобразования.

Выполняются 8 раундов обратного криптопреобразования. Этапы 3 и 4 называются «криптографическим ядром» алгоритма MARS.

Выполняются 8 раундов обратного перемешивания, также без участия ключа шифрования.

Финальное наложение фрагментов расширенного ключа k36… k39 операцией вычитания по модулю 232.

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

Рис. 2 — Раунд прямого перемешивания алгоритма MARS

Раунд прямого перемешивания показан на рис. 2. Как видно из рисунка, в раунде выполняются следующие действия:

Значение субблока A прогоняется через таблицу замен S0 и накладывается на субблок Bоперацией XOR.

Исходное значение субблока A вращается на 8 бит вправо.

Результат предыдущего шага обрабатывается таблицей замен S1 и снова накладывается на субблок B операцией сложения по модулю 232.

Результат шага 2 вращается на 8 бит вправо.

Результат предыдущего шага обрабатывается таблицей замен S0 и накладывается на субблок С операцией сложения по модулю 232.

Результат шага 4 вращается на 8 бит вправо.

Результат предыдущего шага обрабатывается таблицей замен S1 и накладывается на субблок D операцией XOR.

Субблоки меняются местами, как показано на рис. 2.

Кроме того, в некоторых раундах прямого перемешивания выполняются следующие дополнительные операции (не приведены на рис. 2):

В раундах 0 и 4 после шага 7 выполняется наложение значения субблока D на субблок Aоперацией сложения по модулю 232.

В раундах 1 и 5 субблок B аналогичным образом накладывается на субблок A.

По словам авторов алгоритма, эти операции существенно усиливают алгоритм MARS против дифференциального криптоанализа.

Структура раунда прямого криптопреобразования приведена на рис. 3.

конкурс advanced encryption standard

Рис. 3 — Раунд прямого криптопреобразования алгоритма MARS

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

Преобразование E.

Рис. 4 — Операция E алгоритма MARS

Из входного значения формируются три потока O1… O3, над которыми производятся следующие действия:

O2 = I, O3 = O2 <<< 13, O2 = O2 + k2r+4 mod 232, O3 = O3 * k2r+5 mod 232, O3 = O3 <<< 5, O1 = S (O2), O1 = O1 O3, O2 = O2 <<< O3', O3 = O3 <<< 5, O1 = O1 O3, O1 = O1 <<< O3',

где I — входное значение, r — номер текущего раунда, считая с 0-го (при нумерации раундов в данном случае учитываются только раунды криптоядра алгоритма), S — табличная замена для операции E, представляет собой объединение описанных выше таблиц S0 и S1; объединенная таблица содержит 512 значений, выходное значение выбирается по значению 9 младших бит входного слова.

Стоит обратить внимание на то, что в преобразовании E используются операции вращения на переменное число бит; в этом случае запись O3' обозначает, что число бит вращения определяется значением младших пяти бит текущего значения O3.

Структура обратного криптораунда показана на рис. 5.

Рис. 5 — Раунд обратного криптопреобразования алгоритма MARS

От прямого криптораунда его отличает лишь измененный порядок наложения выходных значений преобразования E O1… O3 на слова B, C и D.

Рис. 6 — Раунд обратного перемешивания алгоритма MARS

Раунд обратного перемешивания более существенно отличается от прямого. Фактически, обратное перемешивание выполняет обратные операции в обратной последовательности:

Значение субблока A прогоняется через таблицу замен S1 и накладывается на субблок Bоперацией XOR.

Исходное значение субблока A вращается на 8 бит влево.

Результат предыдущего шага обрабатывается таблицей замен S0 и накладывается на субблок C операцией вычитания по модулю 232.

Результат шага 2 вращается на 8 бит влево.

Результат предыдущего шага обрабатывается таблицей замен S1 и накладывается на субблок D операцией вычитания по модулю 232.

Результат шага 4 вращается на 8 бит влево.

Результат предыдущего шага обрабатывается таблицей замен S0 и накладывается на субблок D операцией XOR.

Субблоки меняются местами, как показано на рис. 6.

Аналогично прямому перемешиванию, в некоторых раундах выполняются следующие дополнительные операции, не показанные на рис. 6:

В раундах 1 и 5 после шага 7 выполняется наложение значения субблока A на субблок Bоперацией вычитания по модулю 232.

В раундах 2 и 6 субблок C аналогичным образом накладывается на субблок B.

Расшифрование выполняется применением обратных операций в обратной последовательности; подробно расшифрование описано в спецификации алгоритма.

Процедура расширения ключа Ключ шифрования алгоритма MARS может иметь любой размер в диапазоне от 128 до 448 бит включительно, кратный 32 битам. Расширение ключа представляет собой формирование на основе ключа шифрования 40 подключей по 32 бита каждый (причем, подключи должны обладать определенными характеристиками, о которых будет сказано ниже), для чего выполняются следующие операции:

Формируется временный массив T0… T14:

T0 = KI0, T1 = KI1, … Tn-1 = KIn-1, Tn = n, Tn+1 = Tn+2 = … = T14 = 0,

где KI0… KIn-1 — исходный ключ шифрования, n — его размер в 32-битных словах — от 4 до 14 включительно.

Данный шаг повторяется 4 раза (каждая итерация дает 10 вычисленных фрагментов расширенного ключа) и содержит следующие операции:

линейное преобразование:

Ti = Ti * ((Ti-7 mod 15 * Ti-2 mod 15) <<< 3) / (4i + j),

где j — номер итерации, начиная с 0, i = 0…14;

перемешивание массива T:

Ti = (Ti * S (Ti-1 mod 15)) <<< 9,

где S — табличная замена, выполняемая по тем же правилам, что и в операции E;

заключительная перестановка:

k10j+n = T4n mod15,

где n = 0…9.

Наложение на вычисленные подключи дополнительных требований, состоящих в следующем:

Каждый подключ, используемый для умножения в операции E (то есть подключи с нечетными индексами от k5 до k35 включительно), должен иметь нечетное значение. Мало того, единичными должны быть два младших бита подключа, а не один.

Те же подключи не должны содержать 10 нулевых или 10 единичных бит подряд.

Модификация подключей в соответствии с данными требованиями выполняется следующим образом:

2 младших бита обрабатываемого подключа устанавливаются в единичные значения; старое значение запоминается в переменной j (оно будет использовано впоследствии). Результирующее значение подключа обозначается как W.

Вычисляется 32-битная маска M, которая будет использована для модификации подключа — для обеспечения отсутствия в нем 10 подряд нулевых или единичных бит. Маска вычисляется следующим образом: A) Устанавливаются в 1 биты M, соответствующие тем битам обрабатываемого подключа, которые входят в последовательности из 10 нулевых или 10 единичных бит. Остальные биты устанавливаются в 0. B) Обнуляются те единичные биты маски M, которые соответствуют любому из условий:

i < 2, i = 31, Wi ≠ Wi-1, Wi ≠ Wi+1,

где i — номер бита, начиная с 0, а Wi — значение i-го бита.

Используется таблица корректирующих значений B, определенная следующим образом: B0 = A4A8D57B, B1 = 5B5D193B, B2 = C8A8309B, B3 = 73F9A978.

Элементы таблицы B эквивалентны элементам с 265-го по 268-й включительно объединенной таблицы S; именно эти элементы используются для коррекции подключей благодаря их специфическим свойствам. С помощью данной таблицы следующим образом вычисляется финальное значение подключа Ki:

Ki = W * ((Bj <<< Ki-1) & M),

где & - логическая побитовая операция «и», а вращение Bj определяется пятью младшими битами предыдущего подключа Ki-1.

Описанная процедура гарантирует требуемые свойства у подключей.

3.3 Финалист AES — шифр RC6

Алгоритм RC6 был разработан в 1998 г. рядом специалистов научного подразделения известнейшей фирмы RSA Data Security — RSA Laboratories: Рональдом Ривестом (Ronald Rivest, основатель RSA Data Security), Мэттом Робшоу (Matt Robshaw), Рэем Сидни (Ray Sidney) и Икван Лайзой Ин (Yiqun Lisa Yin) специально для участия в конкурсе AES. Алгоритм во многом унаследовал черты предыдущего алгоритма Рональда Ривеста — 64-битного блочного шифра RC5, разработанного в 1997 г. (подробное описание RC5 на русском языке можно найти в [9]). Фактически, алгоритм претерпел два принципиальных изменения:

в отличие от RC5, в алгоритме используется умножение по модулю 232;

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

Структура алгоритма Как и алгоритм RC5, RC6 имеет гибкую структуру: помимо секретного ключа, параметрами алгоритма являются следующие:

размер слова w; RC6 шифрует блоками по 4 слова;

количество раундов алгоритма R;

размер секретного ключа в байтах b.

Аналогично RC5, для уточнения параметров алгоритма, используемых в его конкретной реализации, применяется обозначение RC6-w/R/b. Поскольку в конкурсе AES 128-битный блок является обязательным, значение w фиксировано и равно 32. В спецификации алгоритма фиксируется также количество раундов: R = 20. Поскольку конкурс AES предусматривает использование трех фиксированных размеров ключей, рассмотрим три следующих варианта алгоритма: RC6−32/20/16, RC6−32/20/24 и RC6−32/20/32, совокупность которых и будет подразумеваться далее под названием «RC6».

Структура алгоритма представлена на рис. 7.

Рис. 7 — Структура алгоритма RC6

Как было сказано выше, в алгоритме используется 20 раундов преобразований, перед которыми выполняется частичное входное отбеливание:

B = B + K0 mod 232, D = D + K1 mod 232,

где A, B, C, D — текущие значения обрабатываемых 32-битных субблоков, K0… K43 — фрагменты расширенного ключа.

Аналогичным образом выполняется частичное выходное отбеливание:

A = A + K42 mod 232, C = C + K43 mod 232.

В каждом раунде алгоритма выполняются следующие действия:

t1 = f (B) <<< 5, t2 = f (D) <<< 5, A = ((A? t1) <<< t2) + K2i mod 232, C = ((C t2) <<< t1) + K2i+1 mod 232,

где t1 и t2 — временные переменные, количество бит вращения на переменное число бит определяется значением 5 младших бит параметра (t1 или t2), функция f () выполняет следующее квадратичное преобразование:

f (x) = x * (2x + 1) mod 232.

В конце каждого раунда выполняется сдвиг субблоков.

При расшифровании подключи используются в обратном порядке, наложение подключей вместо сложения по модулю 232 выполняется вычитанием, а также сдвиг субблоков выполняется в начале раунда и в обратную сторону. Преобразование f () не претерпело изменений.

Рис. 8 — Расшифрование алгоритмом RC6

Процедура расширения ключа Процедура расширения ключа RC6 аналогична RC5, за исключением того, что RC6 требуется существенно больше сгенерированных подключей, а именно 2R+4, то есть K0… K43 для 20 раундов. Рассмотрим данную процедуру для алгоритма RC6 в варианте для конкурса AES, то есть с указанными выше фиксированными параметрами.

Расширение ключа выполняется в два этапа:

Инициализация массива расширенных ключей K0… K43, которая производится следующим образом:

K0 = P32, Ki+1 = Ki + Q32 mod 232,

где P32 и Q32 — псевдослучайные константы, образованные путем умножения на 232дробной части и последующего округления до ближайшего нечетного целого двух математических констант:

P32 = B7E15163, Q32 = 9E3779B9

Авторы алгоритма в его спецификации утверждают, что выбор данных значений не является важным. Соответственно, аналогично описанному выше алгоритму Twofish-FK, при необходимости создания реализации алгоритма RC6, не совместимой со стандартной, следует изменить значения P32 и Q32.

Циклически выполняются следующие действия:

A = Ki = (Ki + A + B mod 232) <<< 3, B = KIj = (KIj + A + B mod 232) <<< (A + B), i = i + 1 mod 44, j = j + 1 mod c,

где i, j, A и B — временные переменные, их начальные значения равны нулю, KI — исходный ключ шифрования, представленный в виде c 32-битных слов. Выполняется 3c итераций цикла.

3.4 Финалист AES — шифр Serpent

Алгоритм разработан группой ученых из нескольких исследовательских центров мира. Алгоритм представляет собой сетей Фейштеля для четырех ветвей смешанного типа: 2 четные ветви изменяют совместо значения нечетных, затем меняются местами. В качестве криптопреобразований используются только исключающее «ИЛИ», табличные подстановки и битовые сдвиги. Алгоритм состоит из 32 раундов. Сами раунды составлены таким образом, что добавление к ветвями материала ключа на первом и последнем раундах образует входное и выходное забеливание.

Рис. 9 — Структура алгоритма Serpent

3.5 Финалист AES — шифр TwoFish

Алгоритм разработан команией Counterpain Security Systems, возглавляемой Брюсом Шнайером (англ. Bruce Schneier). Предыдущая программная разработка этой фирмы, называвшаяся BlowFish, являлась и до сих пор является признанным криптостойким алгоритмом.

В алгоритме TwoFish разработчики оставили некоторые удачные решения из проекта-предшественника, кроме этого произвели тщательные исследования по перемешиванию данных в сети Фейштеля. Алгоритм представляет собой сеть Фейштеля смешанного типа: первая и вторая ветвь на нечетных раундах производят модификацию третьей и четвертой, на четных раундах ситуация меняется на противоположную. В алгоритме используется криптопреобразование Адамара (англ. Pseudo-Hadamar Transform) — обратимое арифметическое сложение первого потока со вторым, а затем второго с первым.

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

Рис. 10 -Структура алгоритма TwoFish

3.6 Победитель AES — шифр Rijndael

Данный алгоритм разработан двумя специалистами по криптографии из Бельгии. Он является нетрадиционным блочным шифром, поскольку не использует сеть Фейштеля для криптопреобразований. Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байт размером 4×4, 4×6 или 4×8 в зависимости от установленной длины блока. Далее на соответствующих этапах преобразования производятся либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами в таблице.

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

Алгоритм состоит из некоторого количества раундов (от 10 до 14 — это зависит от размера блока и длины ключа), в которых последовательно выполняются следующие операции:

ByteSub — табличная подстановка 8×8 бит,

Рис. 11 — Подстановка ByteSub

ShiftRow — сдвиг строк в двумерном массиве на различные смещения,

Рис. 12 — Сдвиг строк ShiftRow

MixColumn — математическое преобразование, перемешивающее данные внутри столбца,

Рис. 13 — Математическое преобразование MixColumm

AddRoundKey — добавление материала ключа операцией XOR.

Рис. 14 — Добавление ключа операцией XOR

В последнем раунде операция перемешивания столбцов отсутствует, что делает всю последовательность операций симметричной.

4. Сравнение шифров

В результате первого этапа конкурса были выбраны 5 алгоритмов без явно выраженных недостатков: MARS, RC6, Rijndael, Serpent и Twofish. Началось детальное изучение именно этих алгоритмов продолжавшееся еще год с небольшим. В результате победителем конкурса стал алгоритм Rijndael; ему было присвоено название AES, под именем которого он уже достаточно широко реализован и, видимо, по широте распространения обойдет своего предшественника — алгоритм DES.

Сформулируем основные достоинства и недостатки каждого алгоритма, который прошел во второй тур.

Таблица 1 — Сравнение шифров