KHAZAD

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

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

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

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

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

Опис шифру

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
Розклад (розширення) ключа	Афінне перетворення, отримане в результаті роботи шифру в режимі зворотнього зв'язку по шифрованому тексту	Схема Фейстеля, де функцією Фейстеля є раундова функція шифру
Неприведений многочлен поля ${\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.[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-блоку

Будь-яка булева функція $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).[5]

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

Доступність

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

Назва

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

Див. також

SHARK
AES

Примітки

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

Література

Панасенко С. П. Алгоритмы шифрования. Специальный справочник. —СПб.: БХВ-Петербург, 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[autogenerated1-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-3] Описание шифра Khazad для первого этапа конкурса NESSIE.

[:0-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.

[:1-6] Paulo Sérgio L. M. Barreto, Vincent Rijmen. The Khazad Block Cipher. www.larc.usp.br. Архів оригіналу за 2 вересня 2012. Процитовано 30 листопада 2016.