KHAZAD

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Алгоритм блочного шифрування
Назва: KHAZAD
Розробник: Вінсент Реймен і Пауло Баррето
Створений: 2000 р.
Опублікований: 2000 р.
Розмір ключа: 128 біт
Розмір блоку: 64 біт
Число раундів: 8
Тип: SP-мережа

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

Попередником алгоритму KHAZAD вважається розроблений в 1995 р. Вінсентом Рейменом і Джоаном Дайменом шифр SHARK. Автори KHAZAD стверджують, що в основі алгоритму лежить стратегія розробки криптографічно стійких алгоритмів шифрування (Wide-Trail strategy), запропонована Джоаном Дайменом.

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

У шифрі широко використовують інволюційні перетворення, що мінімізує різницю між алгоритмами шифрування і розшифрування.

Опис шифру[ред. | ред. код]

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

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

KHAZAD, як і алгоритм AES (Rijndael), належить до сімейства блочних шифрів, що утворилися від шифру SHARK.[1][2]

Дане дерево описано в книзі «The Block Cipher Companion», автори Lars R. Knudsen, Matthew J. B. Robshaw

Основні відмінності від 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.

Розширення ключа[ред. | ред. код]

Комірка Фейстеля отримання раундового ключа ki

128-бітний (16-байтний) ключ розбивається на 2 рівні частини:

  •  — старші 8 байт (з 15-го по 8-ий)
  •  — молодші 8 байт (з 7-го по 0-ий)

Ключі обчислюються за схемою Фейстеля:

Тут:

 — функція раунду алгоритму з вхідним блоком і ключем .

 — 64-бітова константа, -тий байт якої становить .

Структура нелінійного перетворення і модифікація шифру[ред. | ред. код]

Оригінальний шифр[ред. | ред. код]

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

Таблична заміна одного байта в KHAZAD-0.[3] Тут номер стовпця — перші 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 тими ж авторами).[4]

Принцип вибору S-блоку[ред. | ред. код]

Будь-яка булева функція може бути подана у вигляді поліному Жегалкіна (алгебраїчна нормальна форма). Нелінійним порядком функції називається порядок полінома Жегалкіна, тобто максимальний з порядків її членів.

Якщо , введемо функцію ,

Блок заміни — це відображення . Також, на нього можна дивитися як на відображення .

, де

Нелінійний порядок S-блоку  —  — мінімальний нелінійний порядок серед усіх лінійних комбінацій компонентів :

-параметр S-блоку: значення називається диференціальною рівномірністю

Кореляція двох булевих функцій

-параметр S-блоку:

У шифрі KHAZAD-0 використовується псевдорандомний згенерований S-блок, що відповідає наступним вимогам:

  • повинен бути інволюцією
  • -параметр не повинен перевищувати значення
  • -параметр не повинен перевищувати значення
  • нелінійний порядок повинен бути максимальним, а саме, рівним 7

Модифікований шифр[ред. | ред. код]

Користуючись можливістю незначної зміни алгоритму протягом першого раунду конкурсу, автори Khazad також внесли зміни в свій алгоритм. В новому варіанті специфікації алгоритму вихідний алгоритм Khazad названий як Khazad-0, а назва Khazad присвоєна модифікованому алгоритму. (Панасенко С. П. «Алгоритми шифрування. Спеціальний довідник»)

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

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

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

Дана структура P — і Q-мініблоків еквівалентна S-блоку з наступною таблицею заміни:

Відповідність вихідних значень вхідним для міні-блоку 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






Результуючий 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).[5]

« Як видно, ніяких скільки-небудь серйозних проблем з криптостійкості алгоритму Khazad виявлено не було, що зазначено і експертами конкурсу NESSIE. Крім того, експертами відзначена досить висока швидкість шифрування даного алгоритму. Khazad був визнаний перспективним алгоритмом, вельми цікавим для подальшого вивчення, але не став одним з переможців конкурсу через підозри експертів, що структура алгоритму може містити приховані вразливості, які можуть бути виявлені в майбутньому. »

— Панасенко С. П. "Алгоритмы шифрования. Специальный справочник"[4]

Доступність[ред. | ред. код]

« Шифр KHAZAD не був (і ніколи не буде) запатентований. Він може використовуватися безкоштовно для будь-яких цілей. [6] »

Назва[ред. | ред. код]

Шифр названий на честь Казад-дума (Khazad-dûm) або Морії — величезного підземного королівства гномів в Імлистих горах Середзем'я з трилогії Дж. Р. Р. Толкіна «Володар перснів».

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Lars R. Knudsen, Matthew J.B. Robshaw. The Block Cipher Companion. — Springer, 2011. — С. 63. — ISBN 978-3-642-17341-7.
  2. Joan Daernen, Vincent Rijrnen. The Design of Rijndael. — Springer, 2002. — С. 160. — ISBN 3-540-42580-2.
  3. Описание шифра Khazad для первого этапа конкурса NESSIE. 
  4. а б Панасенко С. П. Алгоритмы шифрования. Специальный справочник. — СПб. : БХВ-Петербург, 2009. — С. 282—287. — ISBN 978-5-9775-0319-8.
  5. Frédéric Muller A new attack against khazad // in Proceedings of ASIACRYPT 2003. — С. 347–358.
  6. Paulo Sérgio L. M. Barreto, Vincent Rijmen. The Khazad Block Cipher. www.larc.usp.br. Процитовано 2016-11-30. 

Література[ред. | ред. код]

  • Панасенко С. П. Алгоритмы шифрования. Специальный справочник. —СПб.: БХВ-Петербург, 2009. — 576 с.: ил. ISBN 978-5-9775-0319-8

Посилання[ред. | ред. код]