Khufu

Khufu — в криптографии симметричный блочный 64-битовый криптоалгоритм, разработанный Ральфом Мерклом в 1990 году, назван в честь египетского фараона Хеопса.

Khufu
Создатель	Ральф Меркл
Создан	1990 г.
Опубликован	1990 г.
Размер ключа	512 бит
Размер блока	64 бит
Число раундов	8-32 (до 64)
Тип	Сеть Фейстеля

Историческая справка

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

Так в конце 1990-х годов группа криптографов из компании Xerox разработала шифр — Khufu, названный в честь египетского фараона Хеопса. В дальнейшем алгоритм был представлен в 1990 году на конференции CRYPTO.

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

Предпосылки создания алгоритма

Алгоритм Khufu — блочный алгоритм, в основе которого лежит сеть Фейстеля, построен на основе следующих постулатов:

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

Теоретической основой алгоритма Khufu является опыт, полученный при разработке алгоритма DES. Поэтому при проектировании алгоритма были учтены следующие предпосылки:

1. 56-битовый размер ключа DES слишком мал и должен быть увеличен.
2. Интенсивное использование перестановок в DES удобно только для аппаратных реализаций, но затрудняет программные реализации. Наиболее быстрые реализации DES выполняют перестановки табличным образом. Просмотр таблицы может обеспечить те же характеристики «рассеяния», что и собственно перестановки и может сделать реализацию более гибкой.
3. S-блоки DES, всего с 64 4-битовыми элементами, слишком малы, поэтому нужно увеличить S-блоки. Более того, все восемь S-блоков используются одновременно. Это удобно для аппаратуры, но для программной реализации это кажется ненужным ограничением, поэтому целесообразнее реализовывать больший размер S-блока. Кроме того, должно быть реализовано последовательное (а не параллельное) использование S-блоков при заменах.
4. Начальная и заключительная перестановки бессмысленны с точки зрения криптографии, поэтому они должны быть устранены.
5. Все быстрые реализации DES заранее рассчитывают ключи для каждого этапа. При данном условии нет смысла усложнять эти вычисления.
6. Критерии проектирования S-блоков должны быть общедоступны.

Алгоритм

Параметры алгоритма

Общая схема алгоритма

Алгоритм шифрует данные блоками, размер блоков равен 64 битам. Затем в процессе шифрования каждый блок разбивается на 2 подблока, каждый размером 32 бита.

Хотя части ключа (подключи K₀..K₃) используются для сложения с подблоками только в начале и в конце выполнения алгоритма, основная цель ключа — генерация S-блоков. Алгоритм предоставляет способ генерации S-блоков по ключу.

Алгоритм имеет следующие параметры:

1. Размер блока шифрования состоит из 64 битов.
2. Размер ключа шифрования должен лежать в пределах от 64 бит до 512 бит. При этом размер ключа обязательно должен быть кратен 64.
3. S-блок имеет 8 входных битов и 32 выходных бита. Является переменным. В каждом октете используется свой S-блок.

Алгоритм построения S-блоков

Алгоритм состоит из генерации подключей и стандартной таблицы замен. На основе стандартной таблицы замен строятся S-блоки для каждого октета преобразований.

Построение стандартной таблицы замен

• В начале данной процедуры инициализируется таблица размером 256 строк на 5 столбцов. В 1-м столбце указаны все возможные значения байтов (от 00 до FF соответственно). Четыре остальные столбца заполняются аналогичными значениями. Ниже приведён фрагмент такой таблицы, в которой указаны 1-я, 2-я и 256-я строка соответственно.

Фрагмент инициализируемой стандартной таблицы

байт	4 байта
00	00	00	00	00
01	01	01	01	01
FF	FF	FF	FF	FF

• Внутри одного столбца происходят перестановки байтов (процедура аналогичная перестановке байтов в S-блоке при его создании), где в качестве псевдослучайной последовательности используется набор из миллиона случайных чисел фирмы RAND Corporation, опубликованный в 1995 году.

Фрагмент стандартной таблицы после итераций

байт	4 байта
00	FA	A1	22	41
01	71	88	B3	15
FF	44	11	C4	E1

• После данных итераций происходит формирование стандартной таблицы замен. Фрагмент данной таблицы указан выше.

Генерация подключей и S-блоков

Основная идея алгоритма Khufu заключается в зависимости подключей и S-блоков от раундового ключа, при этом, в процессе выполнения каждого раунда алгоритм Khufu использует только одну замену последних 8-бит левого подблока на 32 бита в отличие от алгоритма DES. Рассмотрим алгоритм построения S-блоков и подключей. Он строится в несколько этапов:

1. На первом этапе происходит запись ключа в отведённые для этого 64 байта, при этом неиспользуемые биты обнуляются (напомним, что возможный размер ключа лежит в пределах от 8 до 64 байт).
2. На втором этапе данный блок шифруется алгоритмом Khufu в режиме сцепления блоков шифра. В качестве подключей (K₀..K₃) для каждого блока берётся нулевая последовательность, а в качестве таблиц замен берётся стандартная таблица, которая была описана выше. На выходе получается псевдослучайная 64-байтная последовательность, зависящая только от ключа шифрования. Возможно, что для генерации таблиц и подключей может понадобиться большее количество байт, поэтому данный шаг может быть воспроизведён несколько раз.
3. На третьем этапе из данного набора бит выбираются значения подключей (K₀..K₃).
4. На четвёртом этапе строятся S-блоки для каждого октета преобразований:
   • Каждый вычисляемый S-блок инициализируется исходной стандартной таблицей замен, которая описана выше.
   • В исходной стандартной таблице замен в цикле по столбцам (от 0-го до 3-го байта, соответственно) выполняется цикл по строкам (от 0-го до 255-го байта), в котором каждый текущий байт (байт, стоящий на пересечении текущей строки и текущего столбца) меняется местами с одним из следующих байтов того же столбца, определяемым случайным образом (зависит от текущего байта псевдослучайной последовательности); результат — исходная таблица с «хаотично» переставленными байтами каждого столбца.

Процедура шифрования

Процедура шифрования алгоритма Khufu

Шифрование происходит над отдельно взятым блоком данных размером 64 бита. В начале процедуры над данным блоком выполняются следующие действия:

• 64-битный блок данных делится на два блока по 32 бита (в дальнейшем будем называть их L и R соответственно).
• Над каждым из подблоков осуществляется побитовое XOR с подключами K₀ и K₁ соответственно (для левого подблока — K₀, для правого — K₁).

После чего выполняется шифрование. Количество повторений шагов равно количеству раундов алгоритма.

• На первом шаге младший байт (последние 8 бит) левого подблока проходит через S-блок, на основе которого получается 4-байтное (32-битное) значение. Причём в каждом октете операций используется S-блок, предназначенный для данного октета.
• На втором шаге значение, полученное на предыдущем этапе складывается побитово (XOR) с правым подблоком текста.
• На третьем шаге выполняется циклический сдвиг влево на различное число бит левого подблока, которое зависит от номера раунда в октете:
  1. 8 — если номер равен 3 или 4
  2. 24 — если номер равен 7 или 8
  3. 16 — во всех остальных случаях
• На четвёртом шаге левый и правый подблоки меняются местами.

После этого все шаги повторяются заново, включая смену S-блока каждые 8 раундов.

В конце процедуры после прохождения всех предусмотренных раундов выполняется сложение аналогичное сложению с подключами K₀ и K₁, но с другими подключами K₂ и K₃ соответственно.

Использование и устойчивость

Зависимость S-блоков и подключей делает их секретными для криптоаналитика, что существенно увеличивает стойкость алгоритма против дифференциального криптоанализа. Отсюда следует основная спецификация данного алгоритма: алгоритм Khufu должен использоваться там, где необходимо скоростное шифрование больших объёмов данных с редкой сменой ключа.

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

Для того чтобы каждый выходной бит зависел от каждого входного в алгоритме DES, необходимо произвести 5 раундов. В алгоритме Khufu для аналогичной зависимости необходимо 9 раундов. Фактор безопасности $p$ при этом равняется следующему выражению: $p=qr/qsr$, где параметры $qr$ — количество раундов, $qsr$ — количество раундов, необходимое для полного шифрования. Таким образом, для алгоритма DES $p=16/5=3.2$ , а для алгоритма Khufu соответствующий параметр равен $p=16/9=1.8$. В данном случае, относительно этого сравнения алгоритм Khufu уступает алгоритму DES. Однако, S-блоки алгоритма Khufu — секретны, в отличие от алгоритма DES.

Атаки на шифр

Наилучшая атака на шифр Khufu произведёна Гилбертом и Шово. Атака произведена на 16-раундовый Khufu. Для того чтобы полностью вскрыть скрытую информацию, потребовалось 2³¹ выбранных открытых текстов. Но этот результат не удалось расширить на большее количество раундов. В случае использования большего ключа алгоритм будет попросту неэффективным.

Шифр устойчив к атаке методом грубой силы. 512-битовый ключ обеспечивает сложность вскрытия 2⁵¹² что делает шифр устойчив к данному методу.

См. также

• A Million Random Digits with 100,000 Normal Deviates

Литература

• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Панасенко С. П. Глава 3 // Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — С. 288—295. — 576 с. — ISBN 978-5-9775-0319-8
• Жданов О.Н., Золоторёв В.В. Методы и средства криптографической защиты информации: Учебное пособие.. — Красноярск: БХВ-Петербург, 2007. — 217 с.
• Biham E., Biryukov A., Shamir A. Miss in the Middle Attacks on IDEA and Khufu (англ.) // Fast Software Encryption: 6th International Workshop, FSE’99 Rome, Italy, March 24–26, 1999 Proceedings / L. R. Knudsen — Berlin, Heidelberg, New York City, London: Springer Berlin Heidelberg, 1999. — P. 124—138. — (Lecture Notes in Computer Science; Vol. 1636) — ISBN 978-3-540-66226-6 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-48519-8_10
• Merkle R. Fast Software Encryption Functions (англ.) // Advances in Cryptology — CRYPTO ’90: 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes, S. A. Vanstone — Berlin, Heidelberg, New York City, London: Springer Berlin Heidelberg, 1991. — P. 476—501. — (Lecture Notes in Computer Science; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-38424-3_34