Khufu и Khafre

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

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

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

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

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

Алгоритмы Khufu и Khafre были разработаны в 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].

clip_image002

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

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

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

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

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

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

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

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

clip_image004

Рис. 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. Однако, поскольку нет зависимости таблицы замен от ключа, из за­висящей от ключа псевдослучайной последовательности только «набира­ются» значения используемых подключей К$…КП_Х, где п— количество подключей: clip_image006

clip_image008

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

Как видно из описаний алгоритмов, алгоритм 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 требуется адаптивный выбор порядка 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