KHAZAD

KHAZAD

Розробники	Вінсент Реймен і Пауло Баррето
Уперше оприлюднений	2000 р.
Раундів	8
Тип	SP-мережа

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

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

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

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

Опис шифру

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

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

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

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

Основні відмінності від SHARK наведені в таблиці:

Основні відмінності між шифрами KHAZAD і SHARK

	SHARK	KHAZAD
Кількість раундів	6	8
Розклад (розширення) ключа	Афінне перетворення, отримане в результаті роботи шифру в режимі зворотнього зв'язку по шифрованому тексту	Схема Фейстеля, де функцією Фейстеля є раундова функція шифру
Неприведений многочлен поля ${\displaystyle \mathbb {GF} (2^{8})}$	${\displaystyle x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+1}$ (0x1F5)	${\displaystyle x^{8}+x^{4}+x^{3}+x^{2}+1}$ (0x11D)
Реалізація S-блоку	Відображення $u\rightarrow u^{-1}$у полі ${\displaystyle \mathbb {GF} (2^{8})}$ + афінне перетворення	Рекурсивна структура P — і Q-мініблоків
Реалізація матриці перемішування	Код Ріда-Соломона	Інволюційний MDS-код

Початковий варіант шифру KHAZAD (названий KHAZAD-0) зараз є застарілим. Поточний (фінальний) вид шифру був модифікований («tweaked»), щоб адаптувати його під апаратну реалізацію. У цій формі KHAZAD і був визнаний фіналістом NESSIE. Модифікація не торкнулася базової структури шифру. У ньому S-блок, який спочатку генерувався повністю випадково (без чіткого визначення будь-якої внутрішньої структури), замінений на рекурсивну структуру: новий блок заміни 8x8 складений з маленьких псевдовипадково генеруючих 4x4 міні-блоків (P- і Q-блоки).

Структура алгоритму

Структура алгоритму розшифрування

Структура алгоритму шифрування

Застосуванням до ключа процедури розширення ключа отримують набір раундових ключів 

Алгоритм включає 8 раундів, кожен з яких складається з 3 етапів:

• нелінійне перетворення $\gamma$
• лінійне перетворення $\theta$
• додавання раундового ключа $\sigma$

Перед першим раундом виконується відбілювання — $\sigma (k_{0})$. Операція $\theta$ не виконується в останньому раунді.

В операторному вигляді алгоритм записується наступним чином: Шифрування: ${\displaystyle (\sigma [k_{8}]\circ \gamma )\circ (\sigma [k_{7}]\circ \theta \circ \gamma )\circ ...\circ (\sigma [k_{1}]\circ \theta \circ \gamma )\circ \sigma [k_{0}]}$

Розшифрування : ${\displaystyle (\sigma [k_{0}]\circ \gamma )\circ (\sigma [\theta (k_{1})]\circ \theta \circ \gamma )\circ ...\circ (\sigma [\theta (k_{7})]\circ \theta \circ \gamma )\circ \sigma [k_{8}]}$

Набір раундовий ключів $k_{0}...k_{8}$ отримують шляхом застосування до ключа шифрування $K$ процедури розширення ключа.

Структура раунду

Перетворення раунду можна записати так: $\rho [k]=\sigma [k]\circ \theta \circ \gamma$ .

Нелінійне перетворення $\gamma$

У кожному раунді вхідний блок розбивається на менші блоки по 8 байт, які незалежно піддаються нелінійному перетворенню (зміні), тобто паралельно проходять через однакові S-блоки (кожен S-блок — 8x8 біт, тобто 8 біт на вході і 8 біт на виході). Блоки заміни у вихідному і модифікованому (tweaked) шифрі розрізняються. Блок заміни підібраний таким чином, щоб нелінійне перетворення було інволюційним, тобто $\gamma =\gamma ^{-1}$ або $\gamma (\gamma (x))=x$.

Лінійне перетворення ${\displaystyle \theta }$

8-байтний рядок даних множиться побайтно на фіксовану матрицю $H$ розміру 8 х 8, причому множення байт проводиться в полі Галуа $\mathbb {GF} (2^{8})$ з поліномом, що не приводиться  ${\displaystyle x^{8}+x^{4}+x^{3}+x^{2}+1}$ (0x11D).

$\theta (x)=x\times H$

Матриця 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

У вищезгаданому полі Галуа матриця $H$ є симетричною ($a_{ij}=a_{ji}$, $H=H^{T}$) і ортогональною ($H^{-1}=H^{T}$). Тобто $H^{-1}=H$ і перетворення, що задається цією матрицею є інволюцією: ${\textstyle \theta (\theta (x))=x\times H\times H=x\times H\times H^{-1}=x\times E=x}$, де $E$ — одинична матриця

Накладення раундового ключа ${\displaystyle \sigma [k_{i}]}$

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

Розширення ключа

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

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

• ${\displaystyle k_{-1}}$ — старші 8 байт (з 15-го по 8-ий)
• ${\displaystyle k_{-2}}$ — молодші 8 байт (з 7-го по 0-ий)

Ключі $k_{0}...k_{8}$ обчислюються за схемою Фейстеля:

$k_{i}=f(C_{i},k_{i-1})\oplus k_{i-2}$

Тут:

${\displaystyle f(x,y)}$ — функція раунду алгоритму з вхідним блоком $x$ і ключем $y$.

${\displaystyle C_{i}}$ — 64-бітова константа, $j$-тий байт якої становить $C_{i}^{j}=S(8i+j)$.

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

Оригінальний шифр

У первісному варіанті шифру (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 тими ж авторами).

Принцип вибору S-блоку

Будь-яка булева функція $f:GF(2)^{n}\rightarrow GF(2)$ може бути подана у вигляді поліному Жегалкіна (алгебраїчна нормальна форма). Нелінійним порядком функції $f$ називається порядок полінома Жегалкіна, тобто максимальний з порядків її членів.

Якщо $\alpha \in GF(2)^{n}$, введемо функцію $l_{\alpha }=\bigoplus _{i=0}^{n-1}\alpha _{i}\cdot x_{i}$, ${\displaystyle l_{\alpha }:GF(2)^{n}\rightarrow GF(2)}$

Блок заміни — це відображення $GF(2^{n})\rightarrow GF(2^{n})$. Також, на нього можна дивитися як на відображення $GF(2)^{n}\rightarrow GF(2)^{n}$.

${\displaystyle S[x]=(s_{0}(x),...,s_{n-1}(x))}$, де $GF(2)^{n}\rightarrow GF(2)^{n}$

Нелінійний порядок S-блоку $S$ — $\nu _{s}$ — мінімальний нелінійний порядок серед усіх лінійних комбінацій компонентів $S$: ${\displaystyle \nu _{s}\equiv \min _{\alpha \in GF(2)^{n}}\nu (l_{\alpha }\circ S)}$

${\displaystyle \delta }$-параметр S-блоку: ${\displaystyle \delta _{S}\equiv 2^{-n}\cdot \max _{a\neq 0,b}\{c\in GF(2^{n})\mid S[c\oplus a]\oplus S[c]=b\}}$значення $2^{n}\cdot \delta$ називається диференціальною рівномірністю ${\displaystyle S}$

Кореляція двох булевих функцій ${\displaystyle c(f,g)\equiv 2^{1-n}\cdot \{x\mid f(x)=g(x)\}-1}$

${\displaystyle \lambda }$-параметр S-блоку: ${\displaystyle \lambda _{S}\equiv \max _{(i,j)\neq (0,0)}\left\vert c(l_{i},l_{j}\circ S)\right\vert }$

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

• повинен бути інволюцією
• ${\displaystyle \delta }$-параметр не повинен перевищувати значення ${\displaystyle 8\times 2^{-8}}$
• ${\displaystyle \lambda }$-параметр не повинен перевищувати значення ${\displaystyle 16\times 2^{-6}}$
• нелінійний порядок $\nu$ повинен бути максимальним, а саме, рівним 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-блоки є інволюційними, тобто $S(S(x))=x$.

Безпека

Передбачається, що KHAZAD є криптостійким настільки, наскільки криптостійким може бути блоковий шифр з даними довжинами блоку і ключа.

Це передбачає, крім іншого, наступне:

• найбільш ефективною атакою на знаходження ключа шифру KHAZAD є повний перебір.
• отримання з даних пар відкритий текст—шифротекст, інформації про інші такі пари не може бути здійснено більш ефективно, ніж знаходження ключа методом повного перебору.
• очікувана складність пошуку ключа методом повного перебору залежить від бітової довжини ключа і дорівнює $2^{127}$ стосовно до шифру KHAZAD.

Такий великий запас надійності закладався в шифр з урахуванням всіх відомих атак.

Існують атаки лише на скорочений варіант шифру з 5 раундами (Frédéric Muller, 2003).

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

Доступність

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

Назва

Шифр названий на честь Казад-дума (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 [Архівовано 6 травня 2021 у Wayback Machine.] (original, KHAZAD-0). Original submission to NESSIE.
• Alex Biryukov. Analysis of Involutional Ciphers: Khazad and Anubis [Архівовано 4 березня 2016 у Wayback Machine.]. 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 [Архівовано 6 березня 2016 у Wayback Machine.]
• List of NESSIE submissions as originally submitted [Архівовано 13 жовтня 2016 у Wayback Machine.]
• Modifications to NESSIE submissions selected for 2nd Phase [Архівовано 13 жовтня 2016 у Wayback Machine.]
• Deliverables of the NESSIE project [Архівовано 13 жовтня 2016 у Wayback Machine.]
• NESSIE Public Report D14: Report on the Performance Evaluation of NESSIE Candidates I [Архівовано 20 січня 2022 у Wayback Machine.]
• NESSIE Public Report D18: Update on the selection of algorithms for further investigation during the second round. [Архівовано 20 січня 2022 у Wayback Machine.]