KHAZAD

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
KHAZAD
Создатель:

Винсент Рэймен и Пауло Баррето

Создан:

2000 г.

Опубликован:

2000 г.

Размер ключа:

128 бит

Размер блока:

64 бит

Число раундов:

8

Тип:

Подстановочно-перестановочная сеть

KHAZAD — в криптографии симметричный блочный шифр, разработанный двумя криптографами: бельгийцем Винсентом Рэйменом (автор шифра Rijndael) и бразильцем Пауло Баррето. В алгоритме используются блоки данных размером 64 бита (8 байт) и ключи размером 128 бит. KHAZAD был представлен на европейском конкурсе криптографических примитивов NESSIE в 2000 году, где в модифицированной (tweaked) форме стал одним из алгоритмов-финалистов (но не победителем).

Предшественником алгоритма KHAZAD считается разработанный в 1995 г. Винсентом Рэйменом и Йоаном Дайменом шифр SHARK. Авторы KHAZAD утверждают, что в основе алгоритма лежит стратегия разработки криптографически стойких алгоритмов шифрования (WIDE-TRAIL strategy), предложенная Йоаном Дайменом.

Алгоритм KHAZAD имеет консервативные параметры и создан для замены существующих шифров с 64 битным блоком, таких как IDEA и DES, обеспечивая более высокий уровень безопасности при высокой скорости выполнения.

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

Описание шифра[править | править вики-текст]

KHAZAD - итеративный блочный шифр с размером блока 64 бита и 128-битным ключом. Входной блок данных представляется в виде строки из 8 байт.

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

KHAZAD принадлежит тому же семейству блочных шифров, что и алгоритм AES (Rijndael). Он имеет много общего с шифром SHARK.

Основные различия между шифрами KHAZAD и SHARK
SHARK KHAZAD
Количество раундов 6 8
Расписание (расширение) ключа Аффинное преобразование, полчученное в результате работы шифра в режиме обратной связи по шифрованному тексту Схема Фейстеля, где функцией Фейстеля является раундовая функция шифра
Неприводимый многочлен поля (0x1F5) (0x11D)
Реализация S-блока Отображение в поле + аффинное преобразование Рекурсивная структура P- и Q-миниблоков
Реализация матрицы перемешивания Код Рида-Соломона Инволюционный MDS-код

Первоначальный вариант шифра KHAZAD (названный KHAZAD-0) сейчас является устаревшим. Текущий (финальный) вид шифра был модифицирован ("tweaked"), чтобы адаптировать его под аппаратную реализацию. В этой форме KHAZAD и был признан финалистом NESSIE. Модификация не затронула базовую структуру шифра. В нём S-блок, который первоначально генерировался полностью случайно (без чёткого определения какой-либо внутренней структуры), заменен на рекурсивную структуру: новый блок замены 8x8 составлен из маленьких псевдослучайно генерируемых 4x4 мини-блоков (P- и Q-блоки).

Структура алгоритма[править | править вики-текст]

Применением к ключу процедуры расширения ключа получают набор раундовых ключей .

Алгоритм включает 8 раундов, каждый из которых состоит из 3 этапов:

  • нелинейное преобразование
  • линейное преобразование
  • добавление раундового ключа

Перед первым раундом выполняется отбеливание - . Операция не выполняется в последнем раунде.

Шифрование:

Расшифрование:

Набор раундовых ключей получают путём применения к ключу шифрования процедуры расширения ключа.

Структура раунда[править | править вики-текст]

Раундовое преобразование можно записать так: (в операторном виде)

Нелинейное преобразование [править | править вики-текст]

В каждом раунде входной блок разбивается на 8 байт, которые независимо подвергаются нелинейному преобразованию (замене), т.е. параллельно проходят через одинаковые S-блоки (каждый S-блок - 8x8 бит, т.е. 8 бит на входе и 8 бит на выходе). Блоки замены в оригинальном и модифицированном (tweaked) шифре различаются. Блок замены подобран таким образом, чтобы нелинейное преобразование было инволюционным, т.е. или .

Линейное преобразование [править | править вики-текст]

8-байтная строка данных умножается побайтно на фиксированную матрицу размера 8 х 8, причём умножение байт производится в поле Галуа с неприводимым полиномом (0x11D).

Матрица H (hex-формат)
1 3 4 5 6 8 B 7
3 1 5 4 8 6 7 B
4 5 1 3 B 7 6 8
5 4 3 1 7 B 8 6
6 8 B 7 1 3 4 5
8 6 7 B 3 1 5 4
B 7 6 8 4 5 1 3
7 B 8 6 5 4 3 1

В вышеупомянутом поле Галуа матрица является симметричной (, ) и ортогональной (). То есть и преобразование, задаваемое этой матрицей является инволюцией: , где - единичная матрица

Наложение раундового ключа [править | править вики-текст]

Над 64-битным блоком данных и 64-битным раундовым ключом выполняется побитовая операция XOR.

Расширение ключа[править | править вики-текст]

128-битный (16-байтный) ключ разбивается на 2 равные части: - старшие 8 байт (с 15-го по 8-ой), - младшие 8 байт (с 7-го по 0-ой).

Ключи вычисляются следующим образом:

Здесь:

- функция раунда алгоритма с входным блоком и ключом .

- 64-битная константа, -ый байт которой .

Структура нелинейного преобразования и модификация шифра[править | править вики-текст]

Оригинальный шифр[править | править вики-текст]

В первоначальном варианте шифра (KHAZAD-0) табличная замена представлялась классическим S-блоком и описывалась следующей матрицей:

Табличная замена одного байта в KHAZAD-0. Здесь номер столбца - первые 4 бита входа в hex-представлении, номер строки - вторые 4 бита. Значение ячейки на их пересечении - выход S-блока.
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 A7 D3 E6 71 D0 AC 4D 79 3A C9 91 FC 1E 47 54 BD
1 8C A5 7A FB 63 B8 DD D4 E5 B3 C5 BE A9 88 0C A2
2 39 DF 29 DA 2B A8 CB 4C 4B 22 AA 24 41 70 A6 F9
3 5A E2 B0 36 7D E4 33 FF 60 20 08 8B 5E AB 7F 78
4 7C 2C 57 D2 DC 6D 7E 0D 53 94 C3 28 27 06 5F AD
5 67 5C 55 48 0E 52 EA 42 5B 5D 30 58 51 59 3C 4E
6 38 8A 72 14 E7 C6 DE 50 8E 92 D1 77 93 45 9A CE
7 2D 03 62 B6 B9 BF 96 6B 3F 07 12 AE 40 34 46 3E
8 DB CF EC CC C1 A1 C0 D6 1D F4 61 3B 10 D8 68 A0
9 B1 0A 69 6C 49 FA 76 C4 9E 9B 6E 99 C2 B7 98 BC
A 8F 85 1F B4 F8 11 2E 00 25 1C 2A 3D 05 4F 7B B2
B 32 90 AF 19 A3 F7 73 9D 15 74 EE CA 9F 0F 1B 75
C 86 84 9C 4A 97 1A 65 F6 ED 09 BB 26 83 EB 6F 81
D 04 6A 43 01 17 E1 87 F5 8D E3 23 80 44 16 66 21
E FE D5 31 D9 35 18 02 64 F2 F1 56 CD 82 C8 BA F0
F EF E9 E8 FD 89 D7 C7 B5 A4 2F 95 13 0B F3 E0 37

Данная таблица полностью эквивалентна используемой в алгоритме Anubis (ещё один алоритм, разработанный и представленный на конкурс NESSIE теми же авторами).[1]

Модифицированный шифр[править | править вики-текст]

В модифицированной версии шифра S-блок 8x8 изменен и представлен рекурсивной структурой, состоящей из мини-блоков P и Q, каждый из которых является маленьким блоком замены с 4 битами на входе и выходе (4x4).

Рекурсивная структура блока замены в модифицированном шифре KHAZAD:

Рекурсивная структура блока замены в модифицированном шифре KHAZAD
Соответствие выходных значений входным для мини-блока P
u 0 1 2 3 4 5 6 7 8 9 A B C D E F
P(u) 3 F E 0 5 4 B C D A 9 6 7 8 2 1
Соответствие выходных значений входным для мини-блока Q
u 0 1 2 3 4 5 6 7 8 9 A B C D E F
Q(u) 9 E 5 6 A 2 3 C F 0 4 D 7 B 1 8






Данная структура P- и Q-миниблоков эквивалентна S-блоку со следующей таблицей замены:

Результирующий S-блок в модиицированном шифре KHAZAD. Здесь номер столбца - первые 4 бита входа, номер строки - вторые 4 бита. Значение ячейки на их пересечении - выход S-блока.
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 BA 54 2F 74 53 D3 D2 4D 50 AC 8D BF 70 52 9A 4C
1 EA D5 97 D1 33 51 5B A6 DE 48 A8 99 DB 32 B7 FC
2 E3 9E 91 9B E2 BB 41 6E A5 CB 6B 95 A1 F3 B1 02
3 CC C4 1D 14 C3 63 DA 5D 5F DC 7D CD 7F 5A 6C 5C
4 F7 26 FF ED E8 9D 6F 8E 19 A0 F0 89 0F 07 AF FB
5 08 15 0D 04 01 64 DF 76 79 DD 3D 16 3F 37 6D 38
6 B9 73 E9 35 55 71 7B 8C 72 88 F6 2A 3E 5E 27 46
7 0C 65 68 61 03 C1 57 D6 D9 58 D8 66 D7 3A C8 3C
8 FA 96 A7 98 EC B8 C7 AE 69 4B AB A9 67 0A 47 F2
9 B5 22 E5 EE BE 2B 81 12 83 1B 0E 23 F5 45 21 CE
A 49 2C F9 E6 B6 28 17 82 1A 8B FE 8A 09 C9 87 4E
B E1 2E E4 E0 EB 90 A4 1E 85 60 00 25 F4 F1 94 0B
C E7 75 EF 34 31 D4 D0 86 7E AD FD 29 30 3B 9F F8
D C6 13 06 05 C5 11 77 7C 7A 78 36 1C 39 59 18 56
E B3 B0 24 20 B2 92 A3 C0 44 62 10 B4 84 43 93 C2
F 4A BD 8F 2D BC 9C 6A 40 CF A2 80 4F 1F CA AA 42

Из таблиц легко заметить, что как в первоначальном варианте, так и в модифицированном S-блоки являются инволюционными, т.е. .

Безопасность[править | править вики-текст]

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

Это подразумевает, помимо прочего, следующее:

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

Такой большой запас надежности закладывался в шифр с учётом всех известных атак.

Существуют атаки лишь на усеченный вариант шифра с 5 раундами (Frédéric Muller, 2003).[2] Сам алгоритм на данный момент можно считать безопасным.

Доступность[править | править вики-текст]

Шифр KHAZAD не был (и никогда не будет) запатентован. Он может использоваться бесплатно для любых целей.[3]

Название[править | править вики-текст]

Шифр назван в честь Кхазад-дума (Khazad-dûm) или Мории - огромного подземного королевства гномов в Мглистых горах Средиземья из трилогии Дж. Р. Р. Толкиена "Властелин колец".

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Панасенко С. П. Алгоритмы шифрования. Специальный справочник.. — СПб.: БХВ-Петербург, 2009. — С. 282 - 287. — 576 с. — ISBN 978-5-9775-0319-8.
  2. Frédéric Muller A new attack against khazad // in Proceedings of ASIACRYPT 2003. — С. 347–358.
  3. Paulo Sérgio L. M. Barreto, Vincent Rijmen. The Khazad Block Cipher. www.larc.usp.br. Проверено 30 ноября 2016.

Ссылки[править | править вики-текст]