Алгоритмы Khufu и Khafre

Автор данных алгоритмов — Ральф Меркль (Ralph С. Merkle) — широко известен как один из изобретателей криптосистем с открытым ключом, т. е. асимметричного шифрования и электронной цифровой подписи. Существенно меньшую известность получили алгоритмы симметричного шифрования, разработанные Ральфом Мерклем: Khufu и Khafre.

История создания алгоритмов

Ральфу Мерклю показалось несправедливым, что подавляющее большинство существовавших в то время (конец 1980-х гг.) алгоритмов симметричного шифрования было адаптировано под аппаратные реализации, несмотря на то, что аппаратная реализация алгоритма шифрования является, прежде всего, более дорогостоящей, чем программная, т. е. менее доступной для подавляющего большинства потенциальных пользователей. В результате Ральф Меркль (тогда являвшийся сотрудником исследовательского центра корпорации Xerox) создал семейство алгоритмов симметричного шифрования, взяв за основу два следующих постулата (описанных в спецификации алгоритмов Khufu и Khafre 1264]).

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

I

?     Алгоритм шифрования должен использовать именно те элементарные операции, которые оптимизированы для использования в программных реализациях. Меркль приводит в пример таблицы замен алгоритма DES, в котором, как известно, 32-битный шифруемый субблок после его расширения до 48 битов разделяется на 8 фрагментов по 6 битов, каждый из которых «прогоняется» через отдельную таблицу замен (заменяющую 6-битное входное значение 4-битным), в результате чего получается 32-битный субблок, обрабатываемый в дальнейшем. Тогда как аппаратный шифратор может выполнять все 8 замен параллельно, программная реализация алгоритма DES, работающая на однопроцессорном компьютере, выполняет замены последовательно, что занимает несравнимо большее время. Меркль считает, что алгоритм, адаптированный для программных реализаций, должен выполнять прямую замену данных без разбивки на фрагменты. Соответственно, в каждом раунде алгоритмов Khufu и Khafre

таблица замен используется только один раз для замещения 8-битного входного значения 32-битным.

были разработаны в 1990 г. Необычные названия алгоритмов произошли от имен фараонов Древнего Египта — Хуфу (Хеопса) и Хафра, причем, Хафр являлся сыном Хуфу [395].

В следующем году корпорация Xerox получила патент на алгоритмы Khufu и Khafre [265], их коммерческое использование было запрещено держателем патента.

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

Структура алгоритма Khufu

Алгоритм Khufu шифрует данные блоками по 64 бита с использованием ключа шифрования переменного размера— от 64 до 512 битов; размер ключа должен быть кратен 64 битам [264].

Алгоритм выполняет R раундов преобразований, где R — переменное число, кратное 8. В каждом раунде производятся следующие действия (рис. 3.109):

1.    Младший байт левой половины шифруемого блока (64-битный блок делится на два субблока по 32 бита) «прогоняется» через таблицу замен с получением 32-битного значения. В каждом октете (октетом в применении к данному алгоритму называется 8 раундов преобразований) используется своя таблица замен (таблицы замен будут подробно описаны далее).

2.     Результат предыдущего шага накладывается операцией «исключающее или» (XOR) на правый субблок.

3.    Над левым субблоком выполняется циклический сдвиг влево на различное число битов:

•                8 — в раундах № 3 и 4 каждого октета;

•                24 — в раундах № 7 и 8 каждого октета;

•                 16 — во всех остальных раундах.

4.     Субблоки меняются местами.

Перед первым раундом выполняется наложение операцией XOR 32-битных подключей К0 и Кх на левый и правый субблоки соответственно. Аналогич-_ ные действия с подключами К2 и К3 выполняются после заключительного раунда алгоритма. Процедура расширения ключа (т. е. вычисления подключей на основе ключа шифрования) будет описана далее.

Количество раундов алгоритма R не является фиксированным, допускаются значения R от 8 до 64 включительно, кратные восьми; т. е. выполняется

от 1 до 8 октетов преобразований. Понятно, что 64-раундовое шифрование является максимально стойким, но, однако, неэффективно с точки зрения быстродействия. Автор алгоритма считает оптимальным выполнение 16, 24 или 32 раундов [264].

Процедура расширения ключа и таблицы замен

Интересной особенностью алгоритма Khufu является зависимость таблиц замен от ключа шифрования. Таким образом, задача процедуры расширения ключа состоит не только в выработке подключей К0…К3, но и в получении таблиц замен, соответствующих значению ключа.

Опишем процедуру расширения ключа:

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

2.    Этот блок данных шифруется алгоритмом Khufu в режиме сцепления блоков шифра (см. разд. 1.4) с использованием фиксированной стандартной таблицы замен и нулевых значений подключей К0…К3. В результате получается 64-байтная псевдослучайная последовательность, зависящая от ключа шифрования. При необходимости этот шаг повторяется до получения последовательности требуемого размера.

3.    Из последовательности, сгенерированной на шаге 2, «набираются» значения подключей К0…К3.

4.     На основе той же последовательности вычисляются значения таблиц замен для каждого раунда:

• вычисляемая таблица замен инициализируется фиксированной исходной таблицей замен (см. далее);

Рис. 3.110. Пример таблицы замен алгоритма Khufu

• в цикле по столбцам вычисляемой таблицы замен от 0-го до 3-го включительно (поскольку таблица замен замещает 8-битное значение 32- битным, ее можно представить в виде байтовой таблицы из 4 столбцов и 256 строк; фрагмент примера таблицы, приведенного в патенте [265], см. на рис. 3.110) выполняется цикл по строкам, в котором каждый текущий байт (т. е. байт на пересечении текущей строки и текущего столбца внешнего цикла) меняется местами с одним из следующих байтов того же столбца, определяемым случайным образом (т. е. определяемым значением текущего байта псевдослучайной последовательности); результат— исходная таблица замен с «хаотично» переставленными байтами каждого столбца.

Упомянутая выше стандартная таблица замен формируется следующим образом:

1.    Формируется исходная таблица замен, значение каждого байта которой эквивалентно номеру строки, в которой находится данный байт (т. е., например, все 4 байта 0-й строки имеют значение 0).

2.     Выполняется перестановка байтов каждого столбца исходной таблицы аналогично шагу 4 процедуры расширения ключа, где в качестве псевдослучайной последовательности используется известный набор из миллиона случайных чисел фирмы RAND Corporation, опубликованный в 1955 г. [319].

В упомянутом выше патенте [265] приведен исходный код алгоритмов Khufu и Khafre на языке Си.

Алгоритм Khafre

Алгоритм Khafre очень похож на Khufu. Между этими алгоритмами есть два принципиальных различия [264]:

?      таблица замен алгоритма Khafre не зависит от ключа шифрования и является фиксированной — используется описанная выше стандартная таблица замен;

?      добавлена дополнительная операция наложения ключа в каждом октете алгоритма (рис. 3.111).

В отличие от Khufu, алгоритм Khafre не ограничивает ни максимальное количество раундов алгоритма, ни максимальный размер ключа. Однако, как и для Khufu, размер ключа должен быть кратен 64 битам, а количество раундов — кратным 8. Процедура расширения ключа аналогична алгоритму Khufu. Однако, поскольку нет зависимости таблицы замен от ключа, из зависящей от ключа псевдослучайной последовательности только «набираются» значения используемых подключей К$…КП_Х, где п— количество подключей:

Сравнение алгоритмов

Как видно из описаний алгоритмов, алгоритм Khufu выполняет достаточно длительную процедуру расширения ключа шифрования с целью не только вычисления подключей, но и модификации таблиц замен. А у алгоритма Khafre процедура расширения ключа является существенно более простой и быстрой. Однако собственно шифрование данных алгоритмом Khafre выполняется существенно медленнее по причине того, что отсутствие зависимости таблиц замен от ключа в этом случае требует существенного увеличения количества раундов алгоритма для достижения того же уровня криптостойко- сти, что и у алгоритма Khufu с заданным количеством раундов. Зависимость таблиц замен алгоритма Khufu от ключа шифрования делает таблицы замен секретными для криптоаналитика и, соответственно, существенно усиливает стойкость алгоритма против дифференциального криптоанализа [28].

Отсюда следует и специфика использования этих алгоритмов [28, 264]:

?      алгоритм Khufu должен использоваться там, где необходимо скоростное шифрование больших объемов данных с редкой сменой ключа;

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

Алгоритм Snefru

Данное семейство алгоритмов представлено еще одним криптографическим алгоритмом — Snefru (также названным по имени фараона Древнего Египта), который представляет собой хэш-функцию, вычисляющую 128- или 256- битные хэш-значения [395].

В 1990 г. известные криптологи Эли Бихам и Эди Шамир нашли практически реализуемый метод атаки на алгоритм Snefru, использующий дифференциальный криптоанализ для нахождения коллизий (т. е. различных сообщений с совпадающим хэш-значением, см. [77]).

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

Криптоанализ алгоритмов

Как и многие другие алгоритмы, претендующие на замену стандарта DES, алгоритмы Khufu и Khafre подверглись многим исследованиям с целью проверки их криптостойкости. Начало положил сам изобретатель алгоритмов Khufu и Khafre, описавший в спецификации алгоритмов [264] несколько вариантов атак на 8-раундовый алгоритм Khufu. Из более поздних исследований наиболее значительными явились следующие результаты.

?      В упомянутой выше работе [77] Бихам и Шамир показали возможность вскрытия методом дифференциального криптоанализа 16-раундового алгоритма Khafre при наличии 3*216 выбранных открытых текстов и соответствующих им шифртекстов выполнением всего около 1500 операций шифрования. При наличии такого же количества известных открытых текстов и соответствующих им шифртекстов атака потребует около 238 шифрований. Подобным же образом вскрывается и 24-раундовый алгоритм Khafre— при наличии 2 0 шифртекстов выполнением около 253 операций шифрования.

?     Эксперты из французской компании France Telecom предложили атаку на 16-раундовую версию алгоритма Khufu, позволяющую вычислить секретный ключ на основе 243 выбранных открытых текстов выполнением 243 операций шифрования [161].

?     В 1999 г. была опубликована работа [64], в которой была описана более простая в реализации, чем предыдущие, атака на Khufu и Khafre на основе невозможных дифференциалов.

?     В том же году профессор Калифорнийского Университета Дэвид Вагнер изобрел новый вид атак на алгоритмы шифрования, в которых анализируется эволюция зависимостей между двумя парами выбранных открытых текстов (атака методом бумеранга— см. разд. 1.6). Для выполнения этой атаки на 16-раундовый алгоритм Khufu требуется адаптивный выбор по-

1 О                                                                                                                                                                                                                                                                                                                  1 о

рядка 2 открытых текстов и порядка 2 операций шифрования. На данный момент эта атака является наиболее практически реализуемым методом вскрытия алгоритма Khufu.

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

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100