Криптография движется в будущее

Уроки третьей конференции, посвященной проблеме выбора AES - перспективного стандарта шифрования, призванного прийти на смену алгоритму DES.

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

DES критикуют за целый ряд недостатков, в том числе за слишком маленькую длину ключа — всего 56 разрядов, а также не внушающий доверия «черный ход», добавленный Национальным бюро стандартов (National Bureau of Standards — NBS), предшественником современного Национального института по стандартам и технологии (National Institute of Standards and Technology — NIST). Несмотря на все нарекания и утверждения о его уязвимости для атак хакеров, до недавнего времени DES выдерживал все нападки. Но в январе 1999 года с помощью связанных через Internet в единую сеть 100 тыс. персональных компьютеров закодированное посредством DES сообщение было взломано. И на это потребовалось менее 24 часов.

Стало очевидно, что в ближайшие несколько лет, учитывая появление все более дешевого и высокопроизводительного оборудования, DES окажется несостоятельным. Чтобы решить эту проблему, еще в 1997 году NIST выпустил запрос на комментарий (Request For Comment — RFC), где описывался предполагаемый «Усовершенствованный стандарт шифрования» (Advanced Encryption Standard — AES), который должен прийти на смену DES. Специалистам по стандартизации предстояло, интенсивно сотрудничая с представителями отрасли и специалистами по криптографии, разработать следующее поколение алгоритмов шифрования частным ключом.

Шифрование частным ключом

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

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

Критерии AES

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

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

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

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

Требования и процедура

В 1998 году NIST объявил конкурс на создание алгоритма, удовлетворяющего выдвинутым Институтом требованиям. Чтобы быть утвержденным в качестве стандарта, алгоритм должен:

• реализовать шифрование частным ключом;
• представлять собой блочный шифр;
• работать со 128-разрядными блоками и ключами трех размеров (128, 192 и 256 разрядов).

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

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

Пять финалистов первого этапа получили право на участие во втором, где обсуждение будет продолжено. NIST планирует назвать победителя летом или осенью 2000 года.

Третья конференция AES

Процесс выбора алгоритма для AES характеризуется открытостью и прозрачностью. Раньше правительство США было склонно держать в секрете обсуждение стандартов шифрования. В результате, когда, вопреки заверениям властей, у критиков появились сомнения в надежности DES, алгоритм был взломан сообществом Internet.

По словам Эдварда Робака, главы отдела NIST по защите информации и председателя комитета AES, процесс выбора стандарта шифрования коренным образом изменился по сравнению с 1975 годом, когда правительство США объявило конкурс алгоритмов для DES.

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

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

Третья конференция AES прошла в Нью-Йорке 13 и 14 апреля, назадолго до завершения второго этапа. Я считаю, что NIST организовал отличную конференцию и, по мнению специалистов, провел прекрасную работу по подготовке выбора достойного варианта AES.

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

«На первой конференции по AES присутствовало 185 человек, на второй — 190, на третьей — от 230 до 250 участников. Немало специалистов приехали на конференцию из-за рубежа», — заметил Джим.

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

Сессия 1. FPGA

На первой сессии обсуждались вопросы, касающиеся программируемых матриц (FPGA — field programmable gate array). Во время дискуссии участники пришли к выводу, что некоторые из алгоритмов AES, программное осуществление которых не блещет совершенством, оказываются намного эффективнее в реализации FPGA. Примером тому может служить алгоритм Serpent, который превосходно воплощается на аппаратном уровне.

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

«Здесь было представлено поразительное множество реализаций AES на аппаратном уровне, на уровне операционной системы и на Java», — отметил он. В действительности все они — аппаратное обеспечение, операционные системы и Java — имеют уникальные характеристики, что усложняет процесс выбора алгоритма.

Сессия 2. Оценки алгоритмов применительно к различным платформам

Во время второй сессии проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах. Однако участники не пришли к единому заключению, и стало ясно, что ни один из алгоритмов не подходит для всех платформ сразу. В целом, по-видимому, достаточно хорошо на различных платформах работает алгоритм Rijndael.

Я имел возможность познакомиться с авторами алгоритма Serpent Россом Андерсоном и Эли Бихам; создателем Pretty Good Privacy Филиппом Циммерманом; Роном Ривестом из RSA Laboratories; Брайаном Сноу из Агентства национальной безопасности. В кулуарах политики и математики активно обсуждали вопросы, отражающие общую тональность конференции.

Сессия 3. Обзоры

Эта сессия была посвящена обзорам и сравнению производительности претендентов на стандарт, в том числе их реализаций на языках Ассемблера, Си и Java.

Последний материал, обсуждавшийся на этой сессии и представленный Андреасом Стернбенцем из австрийского Института прикладной обработки информации и коммуникаций, касался производительности Java. Стернбенц пришел к выводу, что для Java самым быстрым стал алгоритм RC6, а Rijndael показывает прекрасные результаты при работе со 128-разрядными ключами и намного хуже ведет себя при использовании ключей большей длины. По-видимому, хотя Rijndael и имеет превосходный график ключа, он использует дополнительные циклы для ключей большей длины.

В конце этого дня я поговорил со Стернбенцем о поддержке кандидатов на AES, созданных на основе архитектуры JCE (Java Cryptography Extension).

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

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

По поводу производительности AES и Java я обратился за комментарием к Джиму Дрею, ведущему специалисту по вопросам защиты института NIST.

«Все, кто пишет программы на Java, использующие функции блочного кода, должны знать об AES. Я надеюсь, что AES войдет в состав новой версии пакета провайдеров криптоуслуг, разрабатываемого Sun», — подчеркнул он.

На вопрос о возможных проблемах с производительностью Java Дрей ответил: «Многие полезные криптографические приложения можно написать полностью на Java. Различия в производительности Java и некоторых других языков станут менее значимы, учитывая, что общая производительность вычислительных платформ постоянно растет».

«Фактически, — добавил он, — я только что завершил подготовку пакета провайдеров услуг шифрования JCE 1.2, в котором в какой-то степени нашли отражение предложения всех пяти финалистов конкурса AES».

По мнению Дрея, преимущество по большинству показателей имеют алгоритмы Rijndael и RC6.

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

Сессия 4. Криптографический анализ и свойства, часть I

Следует заметить, что при прочих равных увеличение числа раундов в алгоритме может значительно увеличить его уровень защиты. К примеру, алгоритм Serpent, который, как было отмечено, имеет самый высокий уровень защиты среди финалистов, использует 32 раунда — больше, чем любой из его конкурентов.

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

Дополнительная сессия

Неформальная дополнительная сессия, которая началась вечером первого дня конференции, оказалась весьма полезной и информативной. Даже простое перечисление тем, на ней представленных, доказывает, что при выборе AES необходимо учитывать множество факторов. Вот эти темы: сравнительное исследование производительности финалистов AES, использующих FPGA; эмпирическая взаимосвязь функций различных раундов; криптоаналитика — уроки для AES; IP Security и ключи шифрования; наступление на Twofish; зависящие от данных перестановки и псевдослучайность (идеализированного) RC6; трудные для анализа шифры; реализация пяти финалистов AES на процессоре ARM; производительность финалистов на мультимедийном VLIW-процессоре TriMedia.

Сессия 5. Криптографический анализ и свойства, часть II

Эта сессия стала продолжением сессии 4. Три выступления продемонстрировали результаты тестирования алгоритма Rijndael с сокращенным числом раундов, тем самым подтвердив тот факт, что Rijndael может оказаться недостаточно защищенным, если его разработчики не увеличат число раундов.

Однако общий вывод сессии состоял в том, что не было проведено достаточного количества тестов для криптографических алгоритмов, которые, как предполагается, должны противостоять атакам в ближайшее десятилетие.

Сессия 6. Многоалгоритмический вариант AES

NIST может принять решение интегрировать в окончательный стандарт все пять алгоритмов-претендентов. Проводивший шестую сессию Майлс Смит, ранее работавший в NIST, заметил, что окончательный вариант для стандарта AES приходится выбирать из 31 возможной комбинации (выбрать все пять, четыре из пяти, три из пяти и т. д.). Основной вопрос как раз и состоит в том, какой вариант выйдет победителем.

Дон Джонсон из компании Certicom говорил о необходимости устойчивости — способности AES выдерживать мощные атаки в будущем. Джонсон уверен, что, хотя и несправедливо противопоставлять современную криптографическую технологию будущим неизвестным атакам, битву необходимо выиграть в любом случае. Он упомянул квантовые вычисления как пример тех мощных средств взлома, которые будущие хакеры могут иметь в своем арсенале.

Если же NIST выберет только один алгоритм, а тот окажется несостоятельным, то, по мнению Джонсона, для решения проблемы будет достаточно увеличить число раундов шифрования. Джонсон также усомнился, сможет ли стандарт AES, если он будет создан на основе какого-либо одного алгоритма, работать на различных платформах — RISC, смарт-карты, FPGA и т. д. И заключил, что на данном этапе намного больше вопросов, чем ответов.

Ян Харвей из компании NCipher также поделился своими мыслями об участии нескольких алгоритмов в стандарте. Он считает, что многоалгоритмический вариант AES позволит решить целый ряд проблем, возникающих в связи с вопросами защиты интеллектуальной собственности. В подобных случаях человек или организация пытаются доказать, что алгоритм AES или его часть являются интеллектуальной собственностью (обычно в виде патентов). Подобные ситуации, возникающие в связи с AES, могут привести к аннулированию алгоритма и/или продуктов, в которых он реализован.

Сессия 7. Тестирование отдельных алгоритмов

Материалы седьмой сессии говорят о том, что полученные результаты так и не смогли помочь выбрать наиболее достойного кандидата на стандарт. Более того, результаты тестирования можно было интерпретировать самым различным образом.

Сессия 8. Презентации претендентов

Эта сессия очень напоминала дебаты кандидатов в президенты. После того как участники вытянули жребий, установивший очередность выступлений, расстановка сил оказалась следующей: Rijndael, Serpent, MARS, RC6 и Twofish.

О Rijndael рассказал Винсент Риджмен, заявивший о надежности защиты, высокой общей производительности и простоте архитектуры своего кандидата.

Рос Андерсон превозносил алгоритм Serpent за большое число раундов, которое обеспечивает его надежность. Он отметил, что Serpent абсолютно точно соответствует всем критериям, предъявленным NIST. Андерсон также подчеркнул, что Serpent прекрасно реализуется на аппаратном уровне и особенно хорошо работает на смарт-картах.

Шаи Халеви представил MARS. Этот алгоритм много критиковали за сложную архитектуру, поскольку создается впечатление, что различные фрагменты MARS создавались разными группами корпорации IBM. Объявив основной недостаток алгоритма главным его достоинством, Халеви объяснил, что сложность вызвана уникальной гетерогенной структурой алгоритма.

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

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

Я разговаривал с Шнайером о значимости AES для разработчиков Java. По его словам, «разработчики Java не должны слишком беспокоиться. Java Cryptography Architecture позволяет очень легко подключить различные алгоритмы, и большинство разработок будут функционировать на этом уровне в любом случае».

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

Завершая дискуссию, Эд Робак из NIST рассказал о том, каким образом будет дальше развиваться процесс подготовки стандарта. До начала лета NIST принимает по электронной почте комментарии ко второму этапу подготовки стандарта. Победитель (или победители) будут объявлены летом или осенью. Если все пойдет хорошо, AES станет стандартом в 2001 году.

Резюме

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

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

Требования к AES

• Применение одного или более открытых алгоритмов шифрования
• Алгоритм будет общедоступным и не потребует лицензионных отчислений
• Алгоритм должен использовать симметричное шифрование
• Алгоритмы должны поддерживать минимальный размер блока в 128 разрядов и размеры ключей в 128, 192 и 256 разрядов