eSTREAM: быстрые и стойкие поточные шифры

eSTREAM: быстрые и стойкие поточные шифры

B.C. Анашин
проф. д-р. физ.-мат. наук, Российский государственный гуманитарный университет

А.Ю. Богданов
escrypt GmbH - Embedded Security, ФРГ

И.С. КИЖВЭТОВ
Российский государственный гуманитарный университет

Зачем нужны поточные шифры

Инициатива eSTREАМ [1, 2] позволила собрать большое количество поточных шифров. При этом понятие "поточный шифр" в рамках инициативы формально не определялось. И не случайно.

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

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

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

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

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

В 2005 г. ISO (International Organisation for Standardization) опубликовала официальный стандарт ISO/IEC 18033-4:2005, содержащий спецификации поточных шифров SNOW 2.0 и MUGI. Это пока единственный официальный стандарт для "чистых" поточных шифров. Проект eSTREAM направлен на отбор новых поточных алгоритмов для широкого использования. Что же необходимо производителям и пользователям средств защиты информации от шифров, и в частности от шифров поточных? В отличие от множества проблем, доставляющих головную боль разработчикам шифров, это ряд конкретных требований к конечному продукту.

В первую очередь, как ни банально это звучит, стойкость (безопасность и надежность). Именно поэтому зарубежные производители сейчас выбирают TripleDES, AES, Blowfish и другие блочные шифры (в частности, ГОСТ 28147-89), у которых относительно длительный и интенсивный криптоанализ не обнаружил слабостей.

Здесь следует отметить, что криптоанализ поточных шифров отнюдь не сводится исключительно к анализу свойств генератора гаммы. Помимо собственно генератора анализу подлежат процедуры инициализации. Требования стойкости иногда налагают явные ограничения на архитектуру. Например, для обеспечения стойкости схемы на уровне два в степени l, где l - битовая длина ключа, необходимо, чтобы эффективная длина синхропосылки (initial vector, IV) была не меньше l бит. В противном случае для любого поточного шифра применима общая атака "балансировка время-память" (time-memory tradeoff). Для корреляционных, алгебраических и других классов атак таких простых рецептов защиты нет. При анализе программных и аппаратных реализаций поточных шифров в настоящее время все большее внимание уделяется побочным каналам: атаки по времени, простые и дифференциальные атаки по электропотреблению и электромагнитному излучению, атаки на основе аппаратных ошибок и т.д.

Следующим требованием является производительность, складывающаяся из двух основных показателей. Первый из них - непосредственно скорость шифрования, второй -быстрота процедур установки ключа и синхропосылки. При этом алгоритм с высокой скоростью шифрования может оказаться недостаточно производительным в реальных приложениях, если процедура установки синхропосылки, выполняемая часто для каждого пакета данных (как, например, в IEEE 802.11 или IPSEC), будет медленной. Самые производительные программно-ориентированные шифры проекта eSTREAM по скорости шифрования потока байт на процессоре Intel Pentium 4 с тактовой частотой 3 ГГц приведены на рис. 1.

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

Проект eSTREAM состоит из двух фаз: первой, в которую принимались практически все поданные шифры, и второй, "участники" которой были отобраны из примитивов первой фазы на основе некоторых критериев. Уникальная особенность eSTREAM - это возможность обновлять и улучшать дизайн шифров при переходе из одной фазы в другую. В первой фазе шифры были подвергнуты интенсивному анализу. При этом почти не осталось шифров, которые бы избежали успешного криптоанализа. ABC не стал исключением. Но это позволило авторам благодаря имманентной гибкости дизайна предложить усовершенствованную версию ABC [3], устойчивую ко всем известным атакам. Шифр ABC является синхронным поточным шифром и использует 128-битный ключ и 128-битную синхропосылку. Он принят во вторую фазу проекта eSTREAM в группе программно-ориентированных шифров. Архитектура ABC состоит из трех основных компонентов (см. рис. 2) - A, B и C.

Линейный регистр сдвига A длиной 127 бит имеет максимально возможный период и выполняет функцию счетчика для остальных компонентов. Функция B - нелинейное одноцикловое 32-битное преобразование, зависящее от ключа, синхропосылки и счетчика. Нелинейный фильтр C, построенный по схеме рюкзака [4], также зависит от ключа и счетчика. Зависимость преобразований B и C от ключа делает известной атакующему лишь их общую форму, но не конкретные параметры. В процедурах инициализации используется основной генератор в режиме обратной связи.

По сути, архитектура ABC представляет собой так называемый неавтономный, или зависящий от счетчика (counter-dependent), псевдослучайный генератор. Гарантируемые свойства схемы основываются на теории применения pадического анализа к анализу основных компьютерных операций и их комбинаций, развитой в начале 90-х годов прошлого века [5]. К этим свойствам относятся:

• длина периода порядка 2159;
• равномерное распределение выходной последовательности 32-битных слов;
• высокая линейная сложность выходной последовательности.

ABC - гибкий и высокопроизводительный шифр. Его быстродействие определяется возможностью быстрого вычисления преобразования C ценой некоторых предвычислений на стадии инициализации и некоторого объема памяти для хранения таблиц с результатами предвычислений. Благодаря этому возможна балансировка между скоростью, с одной стороны, и объемом памяти и временем предвычислений - с другой. При этом реализация ABC не требует использования каких-либо ручных процессорно-специфичных оптимизаций, что максимально упрощает задачу кодирования. Вся оптимизация сводится к выбору точки упомянутой балансировки для целевого процессора. Единая реализация на языке ANSI C показывает высокую производительность на различных платформах. Она доступна на сайте авторов [3].

Скорость шифрования ABC в режиме потока байт на основных 32-битных платформах достигает 4 процессорных такта на байт, что для стандартного Intel Pentium 4 с частотой 3,2 ГГц эквивалентно скорости 6,5 Гбит/с. AES в режиме счетчика почти в 6 раз медленнее, а скоростной шифр SNOW 2.0 уступает ABC на 25%. Быстрая процедура установки синхропосылки обеспечивает также крайне высокую скорость шифрования в режиме пакетов.

Архитектура не имеет значения

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

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