Принятые на конкурс алгоритмы: CAST-256 (Канада), CRYPTON (Южная Корея), DEAL (Норвегия, Канада), DFC или Decorrelated Fast Cipher (Франция). Основные этапы конкурса на Advanced Encryption Standard. Финалист и победитель конкурса, сравнение шифров.
Целью проведения конкурса AES был поиск нового стандарта шифрования на замену таких алгоритмов как DES и IDEA, криптостойкость которых была подвергнута сомнению, а впоследствии и вовсем признали эти алгоритмы ненадежными. Поточный шифр применяет изменяющееся от такта к такту криптопреобразование к отдельным цифрам потока данных, а блочный шифр применяет постоянное криптопреобразование к целым блокам данных.) При разъяснении позиции НИСТ было сказано, что, во-первых, блочный шифр AES станет прямым преемником концептуально такого же шифра DES, и, во-вторых, уже имеющиеся утвержденные стандарты режимов функционирования криптоалгоритма ориентированы на блочное шифрование. Шифр должен иметь размер блока 128 бит (существенно, что это требование сразу же вывело из игры почти все применяющиеся ныне алгоритмы, традиционно ориентированные на 64-битный блок), и допускать размеры ключей в 128, 192 и 256 бит[4]. Карлайл Эдамс, разработавший концепцию семейства шифров CAST вместе со Стэффордом Таваресом в начале 1990-х годов, говорит о новом шифре следующее: "Алгоритм CAST-256 в своей конструкции всецело опирается на идеи, которые уже очень хорошо проанализированы и проверены. Предыдущий шифр этого семейства - CAST-128 - является неофициальным канадским стандартом шифрования, и респектабельная теоретическая база данной архитектуры в сочетании с успешным противостоянием криптоанализу могли бы дать алгоритму CAST-256 весьма реальные шансы на победу в конкурсе.Как известно, проанализировав результаты всех исследований, эксперты выбрали в качестве стандарта AES алгоритм Rijndael[6]. Это преимущество связано с развитием многоядерных процессоров, способных обрабатывать информацию в несколько потоков. Что касается алгоритмов Serpent, Twofish, MARS и RC6, то видно, что они практически равнозначны по совокупности характеристик, за исключением алгоритма MARS, имеющего существенно больше недостатков, в том числе, алгоритм практически нереализуем в условиях ограниченных ресурсов. В курсовой работе были рассмотрены основные претенденты на новый стандарт AES. Было очень трудно найти описание самих алгоритмов, принцип их действия и свойства.
Введение
Целью проведения конкурса 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.
3. Основные этапы конкурса на AES
Бесспорно, на конкурс AES представлено самое лучшее из того, чего достигли открытая академическая и промышленная криптография за четверть века своего развития. Теперь предстоит период тщательного изучения выставленных на конкурс кандидатов. Как мрачно пошутил один из участников конкурса Брюс Шнайер, вся эта история напоминает ему некое гигантское "дерби на выживание": на трассу выходит полтора десятка претендентов, которые крушат друг друга до тех пор, пока не останется сильнейший.
Практически сразу же вслед за публикацией в Интернете описания шифра LOKI97, появились и результаты его криптоанализа, выполненного Ларсом Кнудсеном и Винсентом Рэменом (из команд "Serpent" и "Rijndael", соответственно). Из этих результатов следовало, что цикловая функция шифра не обладает достаточной криптографической стойкостью, и с довольно высокой вероятностью можно подбирать криптоаналитические методы вскрытия шифра.
Команда "Twofish" (Вагнер, Фергюсон и Шнайер) нанесла мощный удар по команде "Frog". Было показано, что ключ шифра Frog можно вскрывать при трудозатратах около 257. Для DES, к примеру, с его 56-битным ключом это было бы прекрасным показателем стойкости (поскольку на лобовое вскрытие ключа тотальным перебором требуется 256 опробований), однако, для шифра с длиной ключа по меньшей мере 128 бит этого уже слишком мало. О том, как в ходе конференции AES1 совместными усилиями участников команд "Twofish" и "Serpent" был завален германский проект "Magenta", уже упоминалось.
Период первичной оценки шифров продолжался вплоть до конца апреля 1999 года, вехой завершения этого этапа стала конференция AES2 в Риме. Выбрав для проведения форума итальянскую столицу, организаторы конкурса явно хотели подчеркнуть международный характер мероприятия (действительно, в конференции приняли участие свыше 180 человек из 23 стран). Как надеялись в НИСТ, период времени между AES1 и AES2 достаточен для того, чтобы исследователи криптографического сообщества проверили стойкость и быстродействие всех алгоритмов, в результате чего количество претендентов естественным образом сократилось бы до пяти или менее того. Однако, нельзя сказать, чтобы все прошло гладко и в соответствии с первоначальным планом.
3.1 Предварительные итоги первого раунда
Одна из самых больших проблем при сравнении разнообразных алгоритмов - это два конфликтующих между собой требования к конструкции шифра: стойкость и скорость. Упор на усиление одного из этих параметров неминуемо ослабляет другой. Поскольку разработчики разных шифров вольно или невольно отдавали предпочтение одному из этих показателей, задача сравнения получившиеся в итоге конструкций оказывается достаточно нетривиальной.
Предварительные испытания эффективности алгоритмов-кандидатов провел сам НИСТ. Под эффективностью шифра понимаются два основных показателя: скорость шифрования/расшифрования и скорость формирования криптографических ключей.
В качестве первой тестовой платформы был выбран 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.2 Финалист 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 раундов прямого перемешивания (без участия ключа шифрования).
Алгоритм представляет собой расширенную сеть Фейстеля. В каждом раунде выполняется обработка одного из субблоков и наложение результатов обработки на остальные субблоки, после чего субблоки меняются местами. Конкретные преобразования зависят от типа раунда и будут рассмотрены ниже. Кроме того, между раундами могут выполняться различные дополнительные действия, которые также будут описаны далее.
Рис. 2 - Раунд прямого перемешивания алгоритма MARS
Раунд прямого перемешивания показан на рис. 2. Как видно из рисунка, в раунде выполняются следующие действия: Значение субблока A прогоняется через таблицу замен S0 и накладывается на субблок Воперацией XOR.
Исходное значение субблока A вращается на 8 бит вправо.
Результат предыдущего шага обрабатывается таблицей замен S1 и снова накладывается на субблок B операцией сложения по модулю 232.
Результат шага 2 вращается на 8 бит вправо.
Результат предыдущего шага обрабатывается таблицей замен S0 и накладывается на субблок С операцией сложения по модулю 232.
Результат шага 4 вращается на 8 бит вправо.
Результат предыдущего шага обрабатывается таблицей замен S1 и накладывается на субблок D операцией XOR.
Субблоки меняются местами, как показано на рис. 2.
Кроме того, в некоторых раундах прямого перемешивания выполняются следующие дополнительные операции (не приведены на рис. 2): В раундах 0 и 4 после шага 7 выполняется наложение значения субблока D на субблок Аоперацией сложения по модулю 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 и накладывается на субблок Воперацией XOR.
Исходное значение субблока A вращается на 8 бит влево.
Результат предыдущего шага обрабатывается таблицей замен S0 и накладывается на субблок C операцией вычитания по модулю 232.
Результат шага 2 вращается на 8 бит влево.
Результат предыдущего шага обрабатывается таблицей замен S1 и накладывается на субблок D операцией вычитания по модулю 232.
Результат шага 4 вращается на 8 бит влево.
Результат предыдущего шага обрабатывается таблицей замен S0 и накладывается на субблок D операцией XOR.
Субблоки меняются местами, как показано на рис. 6.
Аналогично прямому перемешиванию, в некоторых раундах выполняются следующие дополнительные операции, не показанные на рис. 6: В раундах 1 и 5 после шага 7 выполняется наложение значения субблока A на субблок Воперацией вычитания по модулю 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, соотв
Вывод
Как известно, проанализировав результаты всех исследований, эксперты выбрали в качестве стандарта AES алгоритм Rijndael[6]. Практически по всем характеристикам Rindael, как минимум, не уступает остальным алгоритмам-финалистам. Но его основной плюс в возможности параллельных вычислений. Это преимущество связано с развитием многоядерных процессоров, способных обрабатывать информацию в несколько потоков. Также основным преимуществом является его легкая программная и техническая реализация.
Что касается алгоритмов Serpent, Twofish, MARS и RC6, то видно, что они практически равнозначны по совокупности характеристик, за исключением алгоритма MARS, имеющего существенно больше недостатков, в том числе, алгоритм практически нереализуем в условиях ограниченных ресурсов. Также основным их недостатком является, то что у этих алгоритмов нет возможности параллельных вычислений. TWOFISH и MARS очень трудно реализуются программно.
В курсовой работе были рассмотрены основные претенденты на новый стандарт AES. Было очень трудно найти описание самих алгоритмов, принцип их действия и свойства. Так же очень интересный фактор при реализации алгоритма - это его программная реализация. Именно этот фактор очень влиял на выбор основного финалиста. Сделаны основные выводы. Рассмотрены многие источники литературы. Все поставленные цели и задачи выполнены.
В работе рассмотрены 5 алгоритмов, прошедших во второй этап конкурса. Всего таких алгоритмов было 15. Еще можно подробнее рассмотреть и проанализировать все 15 алгоритмов. Это даст более подробный анализ всех претендентов.
Сейчас актуальна информация о возможности взлома AES: «Данное исследование пошатнуло многие основы, так как мы получили первый метод взлома, AES-шифра с одним ключом, (немного) более быстрый, чем брут форс атака, - заявил Нейт Лаусон, криптограф и начальник отдела консультаций по безопасности компании Root Labs. - Однако с практической точки зрения, AES-шифр взломать пока невозможно»[10]. Можно сделать вывод, что скорее всего скоро придет замена AES, но пока AES взломан теоретически.
Список литературы
1. Панасенко С. Алгоритм шифрования DES и его варианты. // Connect! Мир связи. - 2006 - № 3-6.
2. Панасенко С. Интересные алгоритмы шифрования, часть 2. // BYTE/Россия. - 2006 - № 5 - с. 74-79.
3. Панасенко С.П., Батура В.П. Основы криптографии: учебное пособие. Под ред. Л.Г. Гагариной. - М.: Финансы и статистика, 2005 - 176 с.
4. Соколов А.В., Шаньгин В.Ф. Защита информации в распределенных корпоративных сетях и системах. - М.: ДМК Пресс, 2002 - 656 с.
5. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. - Пер. с англ.: М.: Издательство ТРИУМФ, 2002 - 816 с.
6. AES Round 1 Information. // - January 26, 2001.
7. Anderson R., Biham E. Two Practical and Provably Secure Block Ciphers: BEAR and LION. // - 1995.
8. Anderson R., Biham E., Knudsen L. Serpent: A Proposal for the Advanced Encryption Standard. // .
9. Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES). // - Department of Commerce - National Institute of Standards and Technology - Federal Register: September 12, 1997
10. AES взломан.//
Размещено на
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
