Алгоритм DFC

Алгоритм DFC (Decorrelated Fast Cipher, быстрый шифр без взаимосвязей) разработан в 1998 г. специально для участия в конкурсе AES несколькими французскими специалистами под руководством известного криптолога Сержа Воденэ. Алгоритм создан благодаря сотрудничеству двух организаций: телекоммуникационного гиганта France Telecom и высшего учебного заведения Ecole Normale Superieure (ENS).

Основные характеристики и структура алгоритма

Согласно требованиям конкурса AES, алгоритм шифрует данные блоками по 128 битов. При этом алгоритм DFC использует ключи не только трех фиксированных размеров, предусмотренных конкурсом (128, 192 и 256 битов), но и переменного размера от 0 до 256 битов.

То есть значение 0 меняется на В7Е15162, значение 1 замещается значением 8AED2A6A и т. д. Всего в таблице 64 записи — по количеству возможных 6-битных значений. Таблица является псевдослучайной, в качестве ее заполнения авторы использовали шестнадцатеричную запись дробной части математической константы е.

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

Достоинства и недостатки алгоритма

Как и еще один участник конкурса AES — алгоритм шифрования НРС, алгоритм DFC оптимизирован под 64-битные платформы (за которыми уже ближайшее будущее — по мнению авторов алгоритма), поэтому основным достоинством алгоритма является высокая скорость шифрования на 64-битных платформах. Кроме того, алгоритм DFC может быть использован и «на другом конце» ряда возможных платформ — в смарт-картах с минимальными ресурсами, поскольку требует менее ста байтов oneративной памяти (в том числе благодаря возможности генерации ключей раундов «на лету», т. е. по мере необходимости) и менее 2 Кбайт энергонезависимой памяти. Однако DFC не вышел во второй раунд конкурса, поскольку недостатки оказались более существенными.

Низкая скорость шифрования на всех платформах, кроме 64-битных.

Сами разработчики алгоритма обнаружили класс слабых ключей шифрования, при расширении которых формируются ключи раундов с нулевой половиной; вероятность попадания ключа в этот класс невелика и равна 2~192 . Также авторы алгоритма предположили наличие еще одного класса возможно слабых ключей.

Структура алгоритма базируется на ряде теоретических работ Сержа Воденэ, в которых формируется математическая модель алгоритмов шифрования с доказуемой высокой криптостойкостью против линейного и дифференциального криптоанализа. Однако соавторы более успешных алгоритмов, представленных на конкурс (вышедшего во второй раунд конкурса алгоритма Serpent и победителя конкурса— алгоритма Rijndael), Ларе Кнудсен и Винсент Риджмен в своей совместной работе, посвященной алгоритму DFC, доказали, что теория, лежащая в основе данного алгоритма, не гарантирует безопасности против дифференциального криптоанализа. Они же привели пример атаки, вскрывающей 6-раундовую версию алгоритма DFC при наличии 2 пар выбранных открытых текстов и соответствующих им шифртекстов путем выполнения порядка 2 вычислений описанной выше функции раунда. Данная атака вряд ли осуществима на практике; кроме того, атаке подвержена «усеченная» версия алгоритма; однако наличие этой атаки говорит о потенциальной слабости алгоритма DFC.

Впоследствии история алгоритма DFC продолжилась. Во-первых, известный криптолог Дон Копперсмит (Don Coppersmith) обнаружил еще один класс слабых ключей шифрования, приводящих к тому, что результат шифрования любого блока эквивалентен исходному, т. е. незашифрованному блоку; такой результат возникал в случае, если значение ключа второго раунда алгоритма оказывалось нулевым (что происходит с вероятностью 2"1 8). Кроме того, была обнаружена еще одна слабость в процедуре расширения ключа, правда, не приводящая к такому плачевному результату, как предыдущая. Поэтому авторы алгоритма предложили новую версию алгоритма (DFCv2) с незначительными изменениями в процедуре расширения ключа, устраняющими все описанные здесь проблемы с ключами. Кроме того, была предложена новая реализация алгоритма, еще быстрее работающая на 64-битных платформах. На результаты конкурса AES это уже не повлияло.

По материалам книги Сергея Панасенко «Алгоритмы шифрования»

Алгоритмы шифрования