CLEFIA

CLEFIA
Создатель	Тайзо Ширай, Кёдзи Шибутани, Тору Акишита, Шихо Мориаи, Тэцу Ивата
Создан	2007 г.
Опубликован	22 марта 2007 г.
Размер ключа	128, 192, 256 бит
Размер блока	128 бит
Число раундов	18/22/26 (зависит от размера ключа)
Тип	Сеть Фейстеля

CLEFIA (от фр. clef «ключ») — блочный шифр с размером блока 128 битов, длиной ключа 128, 192 или 256 битов и количеством раундов 18, 22, 26 соответственно. Этот криптоалгоритм относится к «легковесным» алгоритмам и использует сеть Фейстеля как основную структурную единицу. CLEFIA был разработан корпорацией Sony и представлен в 2007 году. Авторами являются сотрудники компании Тайдзо Сираи, Кёдзи Сибутани, Тору Акисита, Сихо Мориаи, а также доцент Нагойского университета Тэцу Ивата.

Основное назначение данного шифра — использование в качестве безопасной альтернативы AES в сфере защиты авторских прав и DRM-систем, а также применение в RFID-метках и смарт-картах.

Является одним из самых эффективных криптоалгоритмов при аппаратной реализации: аппаратная реализация CLEFIA может достигать эффективности 400,96 Kbps на эквивалентную логическую ячейку^[англ.] шифратора, что является самым высоким показателем среди алгоритмов, включённых в стандарты ISO на 2008 год^[1].

Алгоритм стал одним из первых шифров, применяющим технологию DSM (англ. Diffusion Switching Mechanism) для увеличения защищённости от линейного и дифференциального криптоанализа^[2][3].

Схема шифрования данных

Обозначения

${\displaystyle 0x}$	Префикс для двоичной строки в шестнадцатеричной форме
${\displaystyle a_{(b)}}$	${\displaystyle b}$ показывает длину ${\displaystyle a}$ в битах
${\displaystyle a\mid b}$	Конкатенация
${\displaystyle a\leftarrow b}$	Обновление значения ${\displaystyle a}$ значением ${\displaystyle b}$
${\displaystyle a\oplus b}$	Побитовое исключающее ИЛИ
${\displaystyle a\times b}$	Умножение в ${\displaystyle GF(2^{n})}$

Алгоритм состоит из двух составных частей: части обработки ключа и части обработки данных. Число раундов CLEFIA зависит от длины ключа и составляет соответственно 18, 22 или 26 раундов, при этом используется 36, 44 и 52 подключа. Алгоритм использует ключевое забеливание^[англ.] с дополнительным подключами перед обработкой данных и после неё.

Базовым этапом шифрования данных в CLEFIA является применение обобщённой сети Фейстеля с 4 или 8 ветвями, которая используется как в части обработки данных, так и в части обработки ключа (рисунок 1). В общем случае, если обобщённая сеть Фейстеля имеет d-ветвей и r-раундов, она обозначается как ${\displaystyle GFN_{d,r}}$(англ. generalized Feistel network). Далее рассмотрен алгоритм работы сети Фейстеля в случае использования 4-х ветвей и блока данных в 128 бит.

В ${\displaystyle GFN_{4,r}}$, кроме 4-x 32-х битных входов (${\displaystyle X_{i}}$) и 4-x 32-х битных выходов (${\displaystyle Y_{i}}$), также используются раундовые ключи ${\displaystyle RK_{i}}$. Их количество составляет ${\displaystyle 4r/2=2r}$ в связи с тем, что для каждого раунда требуется в два раза меньше ключей, чем ветвей. ${\displaystyle RK_{i}}$ генерируются в части обработки ключа^[4].

Каждая ячейка Фейстеля задействует также две различные ${\displaystyle F}$-функции: ${\displaystyle F_{0},F_{1}}$. ${\displaystyle F}$-функции относятся к SP-типу функций и используют:

• блок подстановок (S-блок, англ. s-box);
• матрицы распространения^[англ.] в поле Галуа (англ. MDS matrix).

F-функции

Две ${\displaystyle F}$-функции ${\displaystyle F_{0}}$ и ${\displaystyle F_{1}}$, используемые в ${\displaystyle GFN_{d,r}}$, включают в себя нелинейные 8-битные S-блоки ${\displaystyle S_{0}}$ и ${\displaystyle S_{1}}$, рассмотренные далее, и матрицы ${\displaystyle M_{0}}$ и ${\displaystyle M_{1}}$ размером ${\displaystyle 4\times 4}$. В каждой ${\displaystyle F}$-функции эти S-блоки используются в различном порядке, и применяется своя матрица распространения для умножения в поле Галуа. На рисунках показана содержательная часть ${\displaystyle F}$-функций^[4]. ${\displaystyle F}$-функции определяются следующим образом:

${\displaystyle F_{0},F_{1}:{\begin{cases}\{0,1\}^{32}\times \{0,1\}^{32}\rightarrow \{0,1\}^{32}\\(RK_{(32)},x_{(32)})\rightarrow y_{(32)}\end{cases}}}$

Функция ${\displaystyle F_{0}}$
 Шаг 1. ${\displaystyle T=RK\oplus x}$
 Шаг 2. ${\displaystyle T_{0}=S_{0}(T_{0}),\ T_{1}=S_{1}(T_{1}),\ T_{2}=S_{0}(T_{2}),\ T_{3}=S_{1}(T_{3}),\ {\mbox{where}}\ T=T_{0}|T_{1}|T_{2}|T_{3},\ T_{i}\in \{0,1\}^{8}}$
 Шаг 3. ${\displaystyle {\begin{pmatrix}y_{0}\\y_{1}\\y_{2}\\y_{3}\end{pmatrix}}=M_{0}{\begin{pmatrix}T_{0}\\T_{1}\\T_{2}\\T_{3}\end{pmatrix}},\ {\mbox{where}}\ y=y_{0}|y_{1}|y_{2}|y_{3},\ y_{i}\in \{0,1\}^{8}}$

Функция ${\displaystyle F_{1}}$
 Шаг 1. ${\displaystyle T=RK\oplus x}$
 Шаг 2. ${\displaystyle T_{0}=S_{1}(T_{0}),\ T_{1}=S_{0}(T_{1}),\ T_{2}=S_{1}(T_{2}),\ T_{3}=S_{0}(T_{3}),\ {\mbox{where}}\ T=T_{0}|T_{1}|T_{2}|T_{3},\ T_{i}\in \{0,1\}^{8}}$
 Шаг 3. ${\displaystyle {\begin{pmatrix}y_{0}\\y_{1}\\y_{2}\\y_{3}\end{pmatrix}}=M_{1}{\begin{pmatrix}T_{0}\\T_{1}\\T_{2}\\T_{3}\end{pmatrix}},\ {\mbox{where}}\ y=y_{0}|y_{1}|y_{2}|y_{3},\ y_{i}\in \{0,1\}^{8}}$

S-блоки

В CLEFIA используется два разных типа S-блоков, размером по 8 бит каждый. Они сгенерированы так, чтобы минимализировать занимаемую ими площадь при аппаратной реализации. Первый (${\displaystyle S_{0}}$) состоит из 4-битных случайных S-блоков. Во втором (${\displaystyle S_{1}}$) используется обратная функции над полем ${\displaystyle GF(2^{8})}$. В таблицах ниже представлены выходные значения в шестнадцатеричной системе счисления для S-блоков. Старшие 4-бита для 8-битного ввода S-блока обозначают строку, а младшие 4-бита обозначают столбец. Например, если введено значение ${\displaystyle 0x32}$, то блок ${\displaystyle S_{0}}$ выводит ${\displaystyle 0x2e}$^[3].

Первый S-блок

${\displaystyle S_{0}}$ создан с помощью применения четырёх 4-битных S-блоков ${\displaystyle SS_{0},SS_{1},SS_{2},SS_{3}}$ следующим образом:

${\displaystyle S_{0}:{\begin{cases}\{0,1\}^{8}\rightarrow \{0,1\}^{8}\\x_{(8)}\rightarrow y_{(8)}\end{cases}}}$

Алгоритм получения выходных данных при использования блока ${\displaystyle S_{0}}$
 Шаг 1. ${\displaystyle t_{0}=SS_{0}(x_{0}),\ t1=SS_{1}(x_{1}),\ {\mbox{where }}x=x_{0}|x_{1},\ x_{i}\in \{0,1\}^{4}}$
 Шаг 2. ${\displaystyle u_{0}=t_{0}\oplus 0x2\times t_{1},\ u_{1}=0x2\times t_{0}\oplus t_{1}}$
 Шаг 3. ${\displaystyle y_{0}=SS_{2}(u_{0}),\ y_{1}=SS_{3}(u_{1}),\ {\mbox{where }}y=y_{0}|y_{1},\ y_{i}\in \{0,1\}^{4}}$

Умножение в ${\displaystyle 0x2\times t_{i}}$ выполняется в ${\displaystyle GF(2^{4})}$ над многочленами, которое определяется неприводимым полиномом ${\displaystyle z^{4}+z+1}$. В таблице можно найти соответствующий полученный S-box ${\displaystyle S_{0}}$.

Таблица ${\displaystyle S_{0}}$ .0 .1 .2 .3 .4 .5 .6 .7 .8 .9 .a .b .c .d .e .f 0. 57 49 d1 c6 2f 33 74 fb 95 6d 82 ea 0e b0 a8 1c 1. 28 d0 4b 92 5c ee 85 b1 c4 0a 76 3d 63 f9 17 af 2. bf a1 19 65 f7 7a 32 20 06 ce e4 83 9d 5b 4c d8 3. 42 5d 2e e8 d4 9b 0f 13 3c 89 67 c0 71 aa b6 f5 4. a4 be fd 8c 12 00 97 da 78 e1 cf 6b 39 43 55 26 5. 30 98 cc dd eb 54 b3 8f 4e 16 fa 22 a5 77 09 61 6. d6 2a 53 37 45 c1 6c ae ef 70 08 99 8b 1d f2 b4 7. e9 c7 9f 4a 31 25 fe 7c d3 a2 bd 56 14 88 60 0b 8. cd e2 34 50 9e dc 11 05 2b b7 a9 48 ff 66 8a 73 9. 03 75 86 f1 6a a7 40 c2 b9 2c db 1f 58 94 3e ed a. fc 1b a0 04 b8 8d e6 59 62 93 35 7e ca 21 df 47 b. 15 f3 ba 7f a6 69 c8 4d 87 3b 9c 01 e0 de 24 52 c. 7b 0c 68 1e 80 b2 5a e7 ad d5 23 f4 46 3f 91 c9 d. 6e 84 72 bb 0d 18 d9 96 f0 5f 41 ac 27 c5 e3 3a e. 81 6f 07 a3 79 f6 2d 38 1a 44 5e b5 d2 ec cb 90 f. 9a 36 e5 29 c3 4f ab 64 51 f8 10 d7 bc 02 7d 8e

Таблица ${\displaystyle SS_{i}(0\leq i<4)}$ ${\displaystyle x}$ 0 1 2 3 4 5 6 7 8 9 a b c d e f ${\displaystyle SS_{0}(x)}$ e 6 c a 8 7 2 f b 1 4 0 5 9 d 3 ${\displaystyle SS_{1}(x)}$ 6 4 0 d 2 b a 3 9 c e f 8 7 5 1 ${\displaystyle SS_{2}(x)}$ b 8 5 e a 6 4 c f 7 2 3 1 0 d 9 ${\displaystyle SS_{3}(x)}$ a 2 6 d 3 4 5 e 0 7 8 9 b f c 1

Второй S-блок

Блок ${\displaystyle S_{1}}$ определяется как:

${\displaystyle S_{1}:{\begin{cases}\{0,1\}^{8}\rightarrow \{0,1\}^{8}\\x_{(8)}\rightarrow y_{(8)}\end{cases}}}$ ${\displaystyle y={\begin{cases}g(f(x)^{-1}),&{\mbox{if}}\quad f(x)\neq 0\\g(0),&{\mbox{if}}\quad f(x)=0\end{cases}}}$

При этом обратная функция находится в поле ${\displaystyle GF(2^{8})}$, которое задано неприводимым полиномом ${\displaystyle z^{8}+z^{4}+z^{3}+z^{2}+1}$. ${\displaystyle f(\cdot ){\mbox{ и }}g(\cdot )}$ — аффинные преобразования над ${\displaystyle GF(2)}$, определённые следующим образом:

${\displaystyle f:{\begin{cases}\{0,1\}^{8}\rightarrow \{0,1\}^{8}\\x_{(8)}\rightarrow y_{(8)}\end{cases}}}$ ${\displaystyle {\begin{pmatrix}y_{0}\\y_{1}\\y_{2}\\y_{3}\\y_{4}\\y_{5}\\y_{6}\\y_{7}\end{pmatrix}}={\begin{pmatrix}0&0&0&1&1&0&0&0\\0&1&0&1&0&0&0&1\\0&0&0&0&0&0&0&1\\0&0&0&0&0&1&1&0\\0&1&1&0&0&1&0&1\\0&1&0&1&1&1&0&0\\0&1&1&0&0&0&0&0\\1&0&0&0&0&0&0&1\end{pmatrix}}{\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\\x_{6}\\x_{7}\end{pmatrix}}+{\begin{pmatrix}0\\0\\0\\1\\1\\1\\1\\0\end{pmatrix}}}$

${\displaystyle g:{\begin{cases}\{0,1\}^{8}\rightarrow \{0,1\}^{8}\\x_{(8)}\rightarrow y_{(8)}\end{cases}}}$ ${\displaystyle {\begin{pmatrix}y_{0}\\y_{1}\\y_{2}\\y_{3}\\y_{4}\\y_{5}\\y_{6}\\y_{7}\end{pmatrix}}={\begin{pmatrix}0&0&0&0&1&0&1&0\\0&1&0&0&0&0&0&1\\0&1&0&1&1&0&0&0\\0&0&1&0&0&0&0&0\\0&0&1&1&0&0&0&0\\0&0&0&0&0&0&1&0\\1&0&0&1&0&0&0&0\\0&1&0&0&0&1&0&0\end{pmatrix}}{\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\\x_{6}\\x_{7}\end{pmatrix}}+{\begin{pmatrix}0\\1\\1\\0\\1\\0\\0\\1\end{pmatrix}}}$

Здесь используется, что ${\displaystyle x=x_{0}|x_{1}|x_{2}|x_{3}|x_{4}|x_{5}|x_{6}|x_{7}}$ и ${\displaystyle y=y_{0}|y_{1}|y_{2}|y_{3}|y_{4}|y_{5}|y_{6}|y_{7},\ x_{i},\ y_{i}\in \{0,1\}}$. Таким образом получается блок ${\displaystyle S_{1}}$.

Таблица ${\displaystyle S_{1}}$

	.0	.1	.2	.3	.4	.5	.6	.7	.8	.9	.a	.b	.c	.d	.e	.f
0.	6c	da	c3	e9	4e	9d	0a	3d	b8	36	b4	38	13	34	0c	d9
1.	bf	74	94	8f	b7	9c	e5	dc	9e	07	49	4f	98	2c	b0	93
2.	12	eb	cd	b3	92	e7	41	60	e3	21	27	3b	e6	19	d2	0e
3.	91	11	c7	3f	2a	8e	a1	bc	2b	c8	c5	0f	5b	f3	87	8b
4.	fb	f5	de	20	c6	a7	84	ce	d8	65	51	c9	a4	ef	43	53
5.	25	5d	9b	31	e8	3e	0d	d7	80	ff	69	8a	ba	0b	73	5c
6.	6e	54	15	62	f6	35	30	52	a3	16	d3	28	32	fa	aa	5e
7.	cf	ea	ed	78	33	58	09	7b	63	c0	c1	46	1e	df	a9	99
8.	55	04	c4	86	39	77	82	ec	40	18	90	97	59	dd	83	1f
9.	9a	37	06	24	64	7c	a5	56	48	08	85	d0	61	26	ca	6f
a.	7e	6a	b6	71	a0	70	05	d1	45	8c	23	1c	f0	ee	89	ad
b.	7a	4b	c2	2f	db	5a	4d	76	67	17	2d	f4	cb	b1	4a	a8
c.	b5	22	47	3a	d5	10	4c	72	cc	00	f9	e0	fd	e2	fe	ae
d.	f8	5f	ab	f1	1b	42	81	d6	be	44	29	a6	57	b9	af	f2
e.	d4	75	66	bb	68	9f	50	02	01	3c	7f	8d	1a	88	bd	ac
f.	f7	e4	79	96	a2	fc	6d	b2	6b	03	e1	2e	7d	14	95	1d

Матрицы распространения

Матрицы распространения заданы следующим образом:

${\displaystyle M_{0}:{\begin{pmatrix}0x01&0x02&0x04&0x06\\0x02&0x01&0x06&0x04\\0x04&0x06&0x01&0x02\\0x06&0x04&0x02&0x01\end{pmatrix}}}$

${\displaystyle M_{1}:{\begin{pmatrix}0x01&0x08&0x02&0x0a\\0x08&0x01&0x0a&0x02\\0x02&0x0a&0x01&0x08\\0x0a&0x02&0x08&0x01\end{pmatrix}}}$

Умножения матрицы и векторов выполняются в поле ${\displaystyle GF(2^{8})}$, определённое неприводимым полиномом ${\displaystyle z^{8}+z^{4}+z^{3}+z^{2}+1}$.

Общая структура шифрования

Таким образом, на основе обобщённой сети Фейстеля (4 входа для блока данных; 2r входа для раундовых ключей; 4 выхода для шифротекста):

${\displaystyle GFN_{4,r}:{\begin{cases}\{\{0,1\}^{32}\}^{2r}\times \{\{0,1\}^{32}\}^{2r}\rightarrow \{\{0,1\}^{32}\}^{4}\\(RK_{0(32)},...,RK_{2r-1(32)},X_{0(32)},X_{1(32)},X_{2(32)},X_{3(32)})\rightarrow (Y_{0(32)},Y_{1(32)},Y_{2(32)},Y_{3(32)})\end{cases}}}$

Алгоритм шифрования и расшифрования данных:

Шифрование (${\displaystyle GFN_{4,r}}$)
 Шаг 1. ${\displaystyle T_{0}=X_{0},\ T_{1}=X_{1},\ T_{2}=X_{2},\ T_{3}=X_{3}}$
 Шаг 2. ${\displaystyle {\mbox{for }}i=0{\mbox{ to }}r-1{\mbox{ do:}}}$
   Шаг 2.1. ${\displaystyle T_{1}=T_{1}\oplus F_{0}(RK_{2i},T_{0}),}$
   Шаг 2.2. ${\displaystyle T_{3}=T_{3}\oplus F_{1}(RK_{2i+1},T_{2}),}$
 Шаг 3. ${\displaystyle Y_{0}=T_{3},\ Y_{1}=T_{0},\ Y_{2}=T_{1},\ Y_{3}=T_{2}}$

Расшифрование (${\displaystyle GFN_{4,r}^{-1}}$)
 Шаг 1. ${\displaystyle T_{0}=X_{0},\ T_{1}=X_{1},\ T_{2}=X_{2},\ T_{3}=X_{3}}$
 Шаг 2. ${\displaystyle {\mbox{for }}i=0{\mbox{ to }}r-1{\mbox{ do:}}}$
   Шаг 2.1. ${\displaystyle T_{1}=T_{1}\oplus F_{0}(RK_{2(r-i)-2},T_{0}),}$
   Шаг 2.2. ${\displaystyle T_{3}=T_{3}\oplus F_{1}(RK_{2(r-i)-1},T_{2}),}$
 Шаг 3. ${\displaystyle Y_{0}=T_{1},\ Y_{1}=T_{2},\ Y_{2}=T_{3},\ Y_{3}=T_{0}}$

Число раундов ${\displaystyle r}$ составляет 18, 22 и 26 для 128-битных, 192-битных и 256-битных ключей соответственно. Общее количество ${\displaystyle RK_{i}}$ зависит от длины ключа, поэтому часть обработки данных требует 36, 44 и 52 раундовых ключей для 128-битных, 192-битных и 256-битных ключей соответственно.

Результат от ${\displaystyle GFN_{4,r}}$ также подвергается ключевому забеливанию^[англ.].

Использование ключевого забеливания

В часть обработки данных CLEFIA, состоящую из ${\displaystyle ENC_{r}}$ для шифрования и ${\displaystyle DEC_{r}}$ для расшифрования, входят процедуры исключающее «или» между текстом и отбеливающими ключами в начале и в конце алгоритма.

Таким образом, пусть ${\displaystyle P,C\in \{0,1\}^{128}}$ — открытый текст и зашифрованный текст, и пусть ${\displaystyle P_{i},C_{i}\in \{0,1\}^{32}\ (0\leq i<4)}$ — части открытого текста и зашифрованного текста, где ${\displaystyle P=P_{0}|P_{1}|P_{2}|P_{3}}$ и ${\displaystyle C=C_{0}|C_{1}|C_{2}|C_{3}}$, и пусть ${\displaystyle WK_{0},WK_{1},WK_{2},WK_{3}\in \{0,1\}^{32}}$ — отбеливающие ключи, а ${\displaystyle RK_{i}\in \{0,1\}^{32}\ (0\leq i<2r)}$ — раундовые ключи, предоставляемые частью обработки ключа. Тогда алгоритм шифрования с использованием ключевого забеливания:

Функция шифрования ${\displaystyle ENC_{r}}$
 Шаг 1. ${\displaystyle T_{0}=P_{0},\ T_{1}=P_{1}\oplus WK_{0},\ T_{2}=P_{2},\ T_{3}=P_{3}\oplus WK_{1}}$
 Шаг 2. ${\displaystyle T_{0},T_{1},T_{2},T_{3}\leftarrow GFN_{4,r}(RK_{0},...,RK_{2r-1},T_{0},T_{1},T_{2},T_{3})}$
 Шаг 3. ${\displaystyle C_{0}=T_{0},\ C_{1}=T_{1}\oplus WK_{2},\ C_{2}=T_{2},\ C_{3}=T_{3}\oplus WK_{3}}$

Функция расшифрования ${\displaystyle DEC_{r}}$
 Шаг 1. ${\displaystyle T_{0}=C_{0},\ T_{1}=C_{1}\oplus WK_{2},\ T_{2}=C_{2},\ T_{3}=C_{3}\oplus WK_{3}}$
 Шаг 2. ${\displaystyle T_{0},T_{1},T_{2},T_{3}\leftarrow GFN_{4,r}^{-1}(RK_{0},...,RK_{2r-1},T_{0},T_{1},T_{2},T_{3})}$
 Шаг 3. ${\displaystyle P_{0}=T_{0},\ P_{1}=T_{1}\oplus WK_{0},\ P_{2}=T_{2},\ P_{3}=T_{3}\oplus WK_{1}}$

Алгоритм обработки ключа

Часть обработки ключей в шифре CLEFIA поддерживает 128, 192 и 256-битные ключи и в результате выдаёт отбеливающие ключи ${\displaystyle WK_{i}(0\leq i<4)}$ и раундовые ключи ${\displaystyle RK_{j}(0\leq j<2r)}$ для части обработки данных. Пусть ${\displaystyle K}$ будет ключом, а ${\displaystyle L}$ — промежуточным ключом (получается с помощью сокращённой части обработки данных), тогда часть обработки ключа состоит в трёх этапах:

1. Генерация ${\displaystyle L}$ из ${\displaystyle K}$.
2. Генерация ${\displaystyle WK_{i}}$ из ${\displaystyle K}$.
3. Генерация ${\displaystyle RK_{j}}$ из ${\displaystyle K}$ и ${\displaystyle L}$.

Чтобы сгенерировать ${\displaystyle L}$ из ${\displaystyle K}$, часть обработки ключа для 128-битного ключа использует 128-битную ${\displaystyle GFN_{4,12}}$(4 входа по 32 бита), в то время как для 192/256-битных ключей используется 256-битная ${\displaystyle GFN_{8,10}}$(8 входов по 32 бита). Далее приведёно описание алгоритма в случае 128-битного ключа.

Функция перестановки бит

Данный алгоритм использует функцию перестановки бит DoubleSwap (обозначение: ${\displaystyle \Sigma }$):

${\displaystyle \Sigma :{\begin{cases}\{0,1\}^{128}\rightarrow \{0,1\}^{128}\\X_{(128)}\rightarrow Y_{(128)}\end{cases}}}$
${\displaystyle Y=\Sigma (X)=X[7-63]|X[121-127]|X[0-6]|X[64-120]}$

Причём ${\displaystyle X[a-b]}$ обозначает битовую строку, вырезанную с ${\displaystyle a}$-го бита по ${\displaystyle b}$-й бит из ${\displaystyle X}$.

Генерация констант

Схема ${\displaystyle GFN_{d,r}}$ требует на вход раундовые ключи в количестве ${\displaystyle r\cdot {\frac {d}{2}}=2r}$ (если ${\displaystyle d=4}$), и, когда эта схема применяется в части обработки ключа, шифр CLEFIA применяет заранее сгенерированные константы как раундовые ключи. Также дополнительные константы необходимы при втором этапе, при генерации ${\displaystyle WK_{i}}$ и ${\displaystyle RK_{j}}$, и их количество равно ${\displaystyle r\cdot {\frac {d}{2}}}$ (но в данном случае константы ${\displaystyle d}$ и ${\displaystyle r}$ из части обработки данных).

Эти 32-х битные константы обозначаются как ${\displaystyle CON_{i}^{(k)}}$, где ${\displaystyle i}$ — номер константы, ${\displaystyle k}$ — используемое количество бит для ключа(может быть 128, 196, 256). Тогда количество констант будет 60, 84, 92 для 128, 192, 256 битовых ключей соответственно.

Пусть ${\displaystyle P_{(16)}=0xb7e1(=(e-2)\cdot 2^{16})}$ и ${\displaystyle Q_{(16)}=0x243f(=(\pi -3)\cdot 2^{16})}$. Тогда алгоритм для генерации (в таблице количество итераций ${\displaystyle l^{(k)}}$ и начальные значения ${\displaystyle IV^{(k)}}$):

Шаг 1. ${\displaystyle T_{0}=IV^{(k)}}$
Шаг 2. ${\displaystyle {\mbox{for }}i=0{\mbox{ to }}l^{(k)}-1{\mbox{ do:}}}$
  Шаг 2.1. ${\displaystyle CON_{2i}^{(k)}=(T_{i}\oplus P_{(16)})|({\overline {T_{i}}}\lll 1)}$
  Шаг 2.2. ${\displaystyle CON_{2i+1}^{(k)}=({\overline {T_{i}}}\oplus Q_{(16)})|(T_{i}\lll 8)}$
  Шаг 2.3. ${\displaystyle T_{i+1}=T_{i}\times 0x0002^{-1}}$

Где ${\displaystyle {\overline {a}}}$ — логическое отрицание, ${\displaystyle a\lll b}$ — циклический левый сдвиг на ${\displaystyle b}$-бит; а умножение происходит в поле ${\displaystyle GF(2^{16})}$ и определённо неприводимым многочленом ${\displaystyle z^{16}+z^{15}+z^{13}+z^{11}+z^{5}+z^{4}+1(=0x1a831)}$.

Обработка ключа в случае 128-битного ключа

128-разрядный промежуточный ключ ${\displaystyle L}$ генерируется путём применения ${\displaystyle GFN_{4,12}}$, который принимает на вход двадцать четыре 32-разрядные константы ${\displaystyle CON_{i}^{(128)}(0\leq i<24)}$ в качестве раундовых ключей и ${\displaystyle K=K_{0}|K_{1}|K_{2}|K_{3}}$ в качестве данных для шифрования. Затем ${\displaystyle K}$ и ${\displaystyle L}$ используются для генерации ${\displaystyle WK_{i}(0\leq i<4)}$ и ${\displaystyle RK_{j}(0\leq j<36)}$ в следующих шагах:

Генерация ${\displaystyle L}$ из ${\displaystyle K}$:
 Шаг 1. ${\displaystyle L=GFN_{4,12}(CON_{0}^{(128)},...,CON_{23}^{(128)},K_{0},K_{1},K_{2},K_{3})}$

Генерация ${\displaystyle WK_{i}}$ из ${\displaystyle K}$:
 Шаг 2. ${\displaystyle WK_{0}|WK_{1}|WK_{2}|WK_{3}\leftarrow K}$

Генерация ${\displaystyle RK_{j}}$ из ${\displaystyle K}$ и ${\displaystyle L}$:
 Шаг 3. ${\displaystyle {\mbox{for }}i=0{\mbox{ to }}8{\mbox{ do:}}}$
   Шаг 3.1. ${\displaystyle T=L\oplus (CON_{24+4i}^{(128)}|CON_{24+4i+1}^{(128)}|CON_{24+4i+2}^{(128)}|CON_{24+4i+3}^{(128)})}$
   Шаг 3.2. ${\displaystyle L=\Sigma (L)}$
   Шаг 3.3. ${\displaystyle {\mbox{if }}\ i\ {\mbox{mod}}\ 2==1:\ T=T\oplus K}$
   Шаг 3.4. ${\displaystyle RK_{4i}|RK_{4i+1}|RK_{4i+2}|RK_{4i+3}\leftarrow T}$

Особенности шифра

CLEFIA может быть эффективно реализована как в аппаратном, так и в программном обеспечении. В таблице показаны основные преимущества технологий, использованных в этом шифре^[3].

Аспекты проектирования для эффективной реализации

${\displaystyle GFN}$	${\displaystyle F}$-функции небольшого размера (32-битный вход/выход) Нет необходимости в обратимости ${\displaystyle F}$-функций
SP-тип ${\displaystyle F}$-функций	Возможность быстрой табличной реализации в программном обеспечении
DSM	Сокращение количества раундов
S-блоки	Очень маленькая занимаемая площадь ${\displaystyle S_{0}}$ и ${\displaystyle S_{1}}$ в аппаратном обеспечении
Матрицы	Использование элементов только с малым весом Хэмминга[англ.]
Часть обработки ключа	Совместное использование структуры с частью обработки данных Требуется только 128-битный регистр для 128-битного ключа Небольшая площадь функции DoubleSwap

Преимуществами и особенностями в алгоритма CLEFIA являются:

• Обобщённую сеть Фейстеля ${\displaystyle GFN}$;
• DSM (англ. Diffusion Switching Mechanism);
• Два S-бокса.

Особенности реализации GFN

CLEFIA использует обобщённую структуру Фейстеля с 4 ветвями, которая рассматривается как расширение традиционной структуры Фейстеля с 2 ветвями. Существует много типов обобщённых структур Фейстеля. В алгоритме CLEFIA используется второй тип этой структуры (схема 1)^[5]. Структура второго типа имеет две F-функции в одном раунде для четырёх линий данных.

Структура типа 2 имеет следующие особенности:

• ${\displaystyle F}$-функции меньше, чем у традиционной структуры Фейстеля;
• множественные ${\displaystyle F}$-функции могут обрабатываться одновременно;
• как правило, требует больше раундов, чем традиционная структура Фейстеля.

Первая особенность является большим преимуществом для программных и аппаратных реализаций; а вторая особенность подходит для эффективной реализации, особенно в аппаратном обеспечение. Но при этом, заметно увеличивается количество раундов из-за третьей особенности. Однако преимущества структуры второго типа превосходят недостатки для данной конструкции блочного шифр, так как используется новая методика программирования, использующая DSM и два типа S-боксов, что позволяет эффективно сократить количество раундов.

Использование Diffusion Switching Mechanism

CLEFIA использует две разные матрицы распространения для повышения устойчивости к дифференциальным атакам и линейным атакам с использованием механизма DSM (схема 2). Эта методика проектирования была первоначально разработана для традиционных сетей Фейстеля^[3]. Эта техника была перенесена на ${\displaystyle GFN_{d,r}}$, что является одним из уникальных свойств этого шифра. Также, благодаря DSM можно увеличить гарантированное количество активных S-блоков при том же количество раундов.

Следующая таблица показывает гарантированное количество активных S-блоков в шифре CLEFIA. Данные получены при помощи компьютерного моделирования с использованием алгоритма поиска исчерпывающего типа^[3]. Столбцы «D» и «L» в таблице показывают гарантированное количество активных S-блоков при дифференциальном и линейном криптоанализе соответственно. Из этой таблицы можно видеть, что влияние DSM проявляется уже при ${\displaystyle r\geq 3}$, и гарантированное количество S-боксов увеличиваются примерно на 20 % — 40 %, в отличие от структуры без DSM. Следовательно, количество раундов может быть уменьшено, что означает, что производительность улучшается.

Гарантированное число активных S боксов
Количество раундов 1 — 13 Раунды Дифф. и Лин. (без DSM) Дифф. (с DSM) Лин. (с DSM) 1 0 0 0 2 1 1 1 3 2 2 5 4 6 6 6 5 8 8 10 6 12 12 15 7 12 14 16 8 13 18 18 9 14 20 20 10 18 22 23 11 20 24 26 12 24 28 30 13 24 30 32
Количество раундов 14 — 26 Раунды Дифф. и Лин. (без DSM) Дифф. (с DSM) Лин. (с DSM) 14 25 34 34 15 26 36 36 16 30 38 39 17 32 40 42 18 36 44 46 19 36 44 46 20 37 50 50 21 38 52 52 22 42 55 55 23 44 56 58 24 48 59 62 25 48 62 64 26 49 65 66

В таблице красным выделена строка, указывающая на минимальное требуемое количество раундов, чтобы шифр был устойчив к криптоанализу методом полного перебора(см. также). Синим цветом выделены строки, количество раундов которых используется в алгоритме CLEFIA с 128/192/256-битовыми ключами соответственно.

Особенности двух S-боксов

CLEFIA использует два разных типа 8-битных S-блоков: один основан на четырёх 4-битных случайных S-блоках; а другой основан на обратной функции в ${\displaystyle GF(2^{8})}$, которая имеет максимально возможную трудоёмкость атаки для дифференциального криптоанализа ${\displaystyle DP_{max}}$ и линейного криптоанализа ${\displaystyle LP_{max}}$. Оба S-блока выбраны для эффективной реализации, особенно в аппаратном обеспечении.

Для параметров безопасности ${\displaystyle DP_{max}}$ ${\displaystyle S_{0}}$ составляет ${\displaystyle 2^{-4.67}}$, а его ${\displaystyle LP_{max}}$ составляет ${\displaystyle 2^{-4.38}}$. Для ${\displaystyle S_{1}}$ ${\displaystyle DP_{max}}$ и ${\displaystyle LP_{max}}$ оба равны ${\displaystyle 2^{-6.00}}$^[6].

Криптостойкость

Дифференциальный криптоанализ

По таблице количества активных S боксов с DSM(в пункте Использование Diffusion Switching Mechanism) минимальное число раундов равно 12. Таким образом, используя 28 активных S-блоков для 12-раундового CLEFIA и ${\displaystyle DP_{max}^{S_{0}}=2^{-4.67}}$(см. также), определяем, что вероятность характеристики ${\displaystyle DCP_{max}^{12r}\leq 2^{28\cdot (-4.67)}=2^{-130.76}}$. Это означает, что трудоёмкость атаки выше ${\displaystyle 2^{128}}$ и для атакующего нет полезной дифференциальной характеристики в 12 раундов. Кроме того, поскольку ${\displaystyle S_{1}}$ имеет более низкий ${\displaystyle DP_{max}}$, ожидается, что фактическая верхняя граница ${\displaystyle DCP}$ будет ниже, чем приведённая выше оценка^[3]. В результате мы считаем, что полный цикл CLEFIA защищён от дифференциального криптоанализа (в CLEFIA используется 18 раундов).

Линейный криптоанализ

Для оценки сложности линейного криптоанализа применяется подход на основе подсчёта активных S-блоков при заданном количестве раундов. Поскольку ${\displaystyle LP_{max}^{S_{0}}=2^{-4.38}}$, используя 30 активных S-блоков для 12-раундового CLEFIA, ${\displaystyle LCP_{max}^{12r}\leq 2^{30\cdot (-4.38)}=2^{-131.40}}$. Это даёт вывод, что злоумышленнику трудно найти достаточное количество пар текст-шифротекст, которые можно использовать для успешной атаки на CLEFIA. В результате полнофункциональный CLEFIA достаточно защищён от линейного криптоанализа^[6].

Невозможный дифференциальный криптоанализ

Считается, что невозможная дифференциальная атака^[англ.] является одной из самых мощных атак против CLEFIA. Найдены следующие два невозможных дифференциальных пути^[7]:

${\displaystyle (0,\alpha ,0,0){\overset {9r}{\nrightarrow }}(0,\alpha ,0,0)\ {\mbox{и}}\ (0,0,0,\alpha ){\overset {9r}{\nrightarrow }}(0,0,0,\alpha )\quad p=1}$

где ${\displaystyle \alpha \in \{0,1\}^{32}}$ — любая ненулевая величина. Таким образом, используя описанный выше отличительный признак, можно смоделировать атаку (для каждой длины ключа), которая будет восстанавливать текущий ключ. В следующей таблице приведены данные о сложностях, необходимых для невозможных дифференциальных атак. Согласно этой таблице ожидается, что у CLEFIA с полным циклом есть достаточный запас безопасности против этой атаки.

Трудоёмкость невозможного дифференциального криптоанализа

Количество раундов	Длина ключа	Ключевое забеливание	Количество открытых текстов	Временная сложность
10	128,192,256	+	${\displaystyle 2^{101.7}}$	${\displaystyle 2^{102}}$
11	192,256	+	${\displaystyle 2^{103.5}}$	${\displaystyle 2^{188}}$
12	256	-	${\displaystyle 2^{103.8}}$	${\displaystyle 2^{252}}$

Сравнение с другими шифрами

CLEFIA обеспечивает компактную и быструю реализацию одновременно без ущерба для безопасности. По сравнению с AES, наиболее широко используемым 128-битным блочным шифром, CLEFIA имеет преимущество в аппаратной реализации. CLEFIA может реализовывать скорость 1,6 Гбит/с с площадью менее 6 тысяч эквивалентных логических ячеек^[англ.], а пропускная способность на шлюз является самой высокой в мире на 2008 год (в случае аппаратной реализации)^[1].

В таблице ниже приведена сравнительная характеристика шифра CLEFIA по отношению к некоторым другим известным шифрам^[1]:

Реализация с оптимизацией по площади

Алгоритм	Размер блока(биты)	Размер ключа(биты)	Количество раундов	Пропускная способность(Mpbs)	Площадь (Kgates)	Эффективность (Kpbs/gates)
CLEFIA	128	128	18	1,605.94	5.98	268.63
			36	715.69	4.95	144.59
AES	128	128	10	3,422.46	27.77	123.26
Camellia	128	128	23	1,488.03	11.44	130.11
SEED	128	128	16	913.24	16.75	54.52
			52	517.13	9.57	54.01
CAST-128	64	128	17	386.12	20.11	19.20
MISTY1	64	128	9	915.20	14.07	65.04
			30	570.41	7.92	72.06
TDEA	64	56, 112, 168	48	355.56	3.76	94.50

Реализация с оптимизацией по скорости

Алгоритм	Размер блока(биты)	Размер ключа(биты)	Количество раундов	Пропускная способность(Mpbs)	Площадь (Kgates)	Эффективность (Kpbs/gates)
CLEFIA	128	128	18	3,003.00	12.01	250.06
			36	1,385.10	9.38	147.71
AES	128	128	10	7,314.29	45.90	159.37
Camellia	128	128	23	2,728.05	19.95	136.75
SEED	128	128	16	1,556.42	25.14	61.90
			52	898.37	12.33	72.88
CAST-128	64	128	17	909.35	33.11	27.46
MISTY1	64	128	9	1,487.68	17.22	86.37
			30	772.95	10.12	76.41
TDEA	64	56, 112, 168	48	766.28	5.28	145.10

Применение

В 2019 году организации ISO и IEC включили алгоритмы PRESENT и CLEFIA в международный стандарт облегчённого шифрования ISO/IEC 29192-2:2019^[8].

Существует библиотека CLEFIA_H на языке программирования C, реализующая шифр CLEFIA^[9].

Примечания

Ссылки

• CLEFIA веб-сайт (англ.)
• Sony Introduces CLEFIA (англ.)
• Differential Improved Impossible Cryptanalysis of CLEFIA (англ.)
• Реализация библиотеки CLEFIA_H на языке C (англ.)
• Пример реализации алгоритма на языке C
• Пример реализации кодека и хэш-функции CLEFIA на языке С