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.
Основні відмінності від SHARK наведені в таблиці: +Основні відмінності між шифрами KHAZAD і SHARKSHARKKHAZADКількість раундів68Розклад (розширення) ключаАфінне перетворення, отримане в результаті роботи шифру в режимі зворотнього зв'язку по шифрованому текстуСхема Фейстеля, де функцією Фейстеля є раундова функція шифруНеприведений многочлен поля (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-формат)134568B73154867B4513B76854317B8668B71345867B3154B76845137B865431 У вищезгаданому полі Галуа матриця є симетричною (, ) і ортогональною (). Тобто і перетворення, що задається цією матрицею є інволюцією: , де — одинична матриця
Накладення раундового ключа Над 64-бітний блок даних і 64-бітним раундовим ключем виконується побітова операція XOR.
Розширення ключа
128-бітний (16-байтний) ключ розбивається на 2 рівні частини: — старші 8 байт (з 15-го по 8-ий) — молодші 8 байт (з 7-го по 0-ий)
Ключі обчислюються за схемою Фейстеля:
Тут:
— функція раунду алгоритму з вхідним блоком і ключем .
— 64-бітова константа, -тий байт якої становить .
Структура нелінійного перетворення і модифікація шифру
Оригінальний шифр У первісному варіанті шифру (KHAZAD-0) таблична заміна представлялася класичним S-блоком і описувалася наступною матрицею: +Таблична заміна одного байта в KHAZAD-0. Тут номер стовпця — перші 4 біта входу в hex-представленні, номер рядка — другі 4 біта. Значення комірки на їх перетині — вихід S-блоку.0123456789ABCDEF0A7D3E671D0AC4D793AC991FC1E4754BD18CA57AFB63B8DDD4E5B3C5BEA9880CA2239DF29DA2BA8CB4C4B22AA244170A6F935AE2B0367DE433FF6020088B5EAB7F7847C2C57D2DC6D7E0D5394C32827065FAD5675C55480E52EA425B5D305851593C4E6388A7214E7C6DE508E92D17793459ACE72D0362B6B9BF966B3F0712AE4034463E8DBCFECCCC1A1C0D61DF4613B10D868A09B10A696C49FA76C49E9B6E99C2B798BCA8F851FB4F8112E00251C2A3D054F7BB2B3290AF19A3F7739D1574EECA9F0F1B75C86849C4A971A65F6ED09BB2683EB6F81D046A430117E187F58DE3238044166621EFED531D935180264F2F156CD82C8BAF0FEFE9E8FD89D7C7B5A42F95130BF3E037
Дана таблиця повністю еквівалентна тій, що використовується в алгоритмі Anubis (ще один алгоритм, розроблений та поданий на конкурс NESSIE тими ж авторами).
Принцип вибору S-блоку Будь-яка булева функція може бути подана у вигляді поліному Жегалкіна (алгебраїчна нормальна форма). Нелінійним порядком функції називається порядок полінома Жегалкіна, тобто максимальний з порядків її членів.
Якщо , введемо функцію ,
Блок заміни — це відображення . Також, на нього можна дивитися як на відображення .
, де
Нелінійний порядок S-блоку — — мінімальний нелінійний порядок серед усіх лінійних комбінацій компонентів :
-параметр S-блоку: значення називається диференціальною рівномірністю
Кореляція двох булевих функцій
-параметр S-блоку:
У шифрі KHAZAD-0 використовується псевдорандомний згенерований S-блок, що відповідає наступним вимогам: повинен бути інволюцією -параметр не повинен перевищувати значення -параметр не повинен перевищувати значення нелінійний порядок повинен бути максимальним, а саме, рівним 7
Модифікований шифр Користуючись можливістю незначної зміни алгоритму протягом першого раунду конкурсу, автори Khazad також внесли зміни в свій алгоритм. В новому варіанті специфікації алгоритму вихідний алгоритм Khazad названий як Khazad-0, а назва Khazad присвоєна модифікованому алгоритму. (Панасенко С. П. «Алгоритми шифрування. Спеціальний довідник»)У модифікованій версії шифру S-блок 8x8 змінений і представлений рекурсивною структурою, що складається з міні-блоків P і Q, кожен з яких є маленьким блоком заміни з 4 бітами на вході і виході (4x4).
Рекурсивна структура блоку заміни в модифікованому шифрі KHAZAD: Дана структура P — і Q-мініблоків еквівалентна S-блоку з наступною таблицею заміни: +Відповідність вихідних значень вхідним для міні-блоку Pu0123456789ABCDEFP(u)3FE054BCDA967821
+Відповідність вихідних значень вхідним для міні-блоку Qu0123456789ABCDEFQ(u)9E56A23CF04D7B18
+ Результуючий S-блок у модифікованому шифрі KHAZAD. Тут номер стовпця — перші 4 біта входу, номер рядка — другий 4 біт. Значення комірки на їх перетині — вихід S-блоку. 0123456789ABCDEF0BA542F7453D3D24D50AC8DBF70529A4C1EAD597D133515BA6DE48A899DB32B7FC2E39E919BE2BB416EA5CB6B95A1F3B1023CCC41D14C363DA5D5FDC7DCD7F5A6C5C4F726FFEDE89D6F8E19A0F0890F07AFFB508150D040164DF7679DD3D163F376D386B973E93555717B8C7288F62A3E5E274670C65686103C157D6D958D866D73AC83C8FA96A798ECB8C7AE694BABA9670A47F29B522E5EEBE2B8112831B0E23F54521CEA492CF9E6B62817821A8BFE8A09C9874EBE12EE4E0EB90A41E85600025F4F1940BCE775EF3431D4D0867EADFD29303B9FF8DC6130605C511777C7A78361C39591856EB3B02420B292A3C0446210B4844393C2F4ABD8F2DBC9C6A40CFA2804F1FCAAA42
З таблиць легко помітити, що в первісному варіанті, так і в модифікованому S-блоки є інволюційними, тобто .
Безпека Передбачається, що KHAZAD є криптостійким настільки, наскільки криптостійким може бути блоковий шифр з даними довжинами блоку і ключа.
Це передбачає, крім іншого, наступне: найбільш ефективною атакою на знаходження ключа шифру KHAZAD є повний перебір. отримання з даних пар відкритий текст—шифротекст, інформації про інші такі пари не може бути здійснено більш ефективно, ніж знаходження ключа методом повного перебору. очікувана складність пошуку ключа методом повного перебору залежить від бітової довжини ключа і дорівнює стосовно до шифру KHAZAD.
Такий великий запас надійності закладався в шифр з урахуванням всіх відомих атак.
Існують атаки лише на скорочений варіант шифру з 5 раундами (Frédéric Muller, 2003).
Доступність
Назва Шифр названий на честь Казад-дума (Khazad-dûm) або Морії — величезного підземного королівства гномів в Імлистих горах Середзем'я з трилогії «Володар перснів».
Див. також SHARK Advanced Encryption Standard (AES)
Примітки
Література Панасенко С. П. Алгоритмы шифрования. Специальный справочник. —СПб.: БХВ-Петербург, 2009. — 576 с.: ил. ISBN 978-5-9775-0319-8
Посилання Офіційна сторінка шифру KHAZAD Paulo S. L. M. Barreto and Vincent Rijmen. The KHAZAD Legacy-Level Block Cipher (tweaked, KHAZAD). In First Open NESSIE Workshop, KU-Leuven, 2000. Modificated submission to NESSIE selected for 2nd Phase. Paulo S. L. M. Barreto and Vincent Rijmen. The KHAZAD Legacy-Level Block Cipher (original, KHAZAD-0). Original submission to NESSIE. Alex Biryukov. Analysis of Involutional Ciphers: Khazad and Anubis . In T. Johansson, editor, Fast Software Encryption — 2003, Lectures Notes in Computer Science. Springer, 2003. Frédéric Muller. A New Attack against Khazad. Advances in Cryptology List of NESSIE submissions as originally submitted Modifications to NESSIE submissions selected for 2nd Phase Deliverables of the NESSIE project NESSIE Public Report D14: Report on the Performance Evaluation of NESSIE Candidates I NESSIE Public Report D18: Update on the selection of algorithms for further investigation during the second round.