Кузнечик (шифр)

Кузнечик (входит в ГОСТ Р 34.12-2015)
Размер ключа	256 битов
Размер блока	128 битов
Число раундов	10
Тип	Подстановочно-перестановочная сеть

Блочный шифр «Кузнечик» (входит в стандарт ГОСТ Р 34.12-2015) — симметричный алгоритм блочного шифрования с размером блока 128 битов и длиной ключа 256 битов и использующий для генерации раундовых ключей сеть Фейстеля.

Общие сведения

Данный шифр утверждён (наряду с блочным шифром «Магма») в качестве стандарта в ГОСТ Р 34.12-2015 «Информационная технология. Криптографическая защита информации. Блочные шифры» приказом от 19 июня 2015 года № 749-ст. Стандарт вступил в действие с 1 января 2016 года.. Шифр разработан Центром защиты информации и специальной связи ФСБ России с участием ОАО «Информационные технологии и коммуникационные системы» (ОАО «ИнфоТеКС»). Внесён Техническим комитетом по стандартизации ТК 26 «Криптографическая защита информации».

Обозначения

$\mathbb {F}$ — поле Галуа $GF(2^{8})$ по модулю неприводимого многочлена $x^{8}+x^{7}+x^{6}+x+1$.

$Bin_{8}:\mathbb {Z} _{p}\rightarrow V_{8}$ — биективное отображение, ставящее в соответствие элементу кольца $\mathbb {Z} _{p}$ ($p=2^{8}$) его двоичное представление.

${Bin_{8}}^{-1}:V_{8}\rightarrow \mathbb {Z} _{p}$ — отображение, обратное к $Bin_{8}$.

$\delta :V_{8}\rightarrow \mathbb {F}$ — биективное отображение, ставящее в соответствие двоичной строке элемент поля $\mathbb {F}$.

$\delta ^{-1}:\mathbb {F} \rightarrow V_{8}$ — отображение, обратное к $\delta$

Описание алгоритма

Для шифрования, расшифрования и генерации ключа используются следующие функции:

$Add_{2}[k](a)=k\oplus a$, где $k$, $a$ — двоичные строки вида $a=a_{15}||$…$||a_{0}$ ($||$ — символ конкатенации строк).

$N(a)=S(a_{15})||$…$||S(a_{0}).~~N^{-1}(a)$ — обратное к $N(a)$ преобразование.

$G(a)=\gamma (a_{15},$…$,a_{0})||a_{15}||$…$||a_{1}.$

$G^{-1}(a)$ — обратное к $G(a)$ преобразование, причём $G^{-1}(a)=a_{14}||a_{13}||$…$||a_{0}||\gamma (a_{14},a_{13},$…$,a_{0},a_{15}).$

$H(a)=G^{16}(a)$, где $G^{16}$ — композиция преобразований $G^{15}$ и $G$ и т. д.

$F[k](a_{1},a_{0})=(HNAdd_{2}[k](a_{1})\oplus a_{0},a_{1}).$

Нелинейное преобразование

Нелинейное преобразование задается подстановкой S = Bin₈ S' Bin₈⁻¹.

Значения подстановки S' заданы в виде массива S' = (S'(0), S'(1), …, S'(255)):

$S'=(252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,233,$ $119,240,219,147,46,153,186,23,54,241,187,20,205,95,193,249,24,101,$ $90,226,92,239,33,129,28,60,66,139,1,142,79,5,132,2,174,227,106,143,$ $160,6,11,237,152,127,212,211,31,235,52,44,81,234,200,72,171,242,42,$ $104,162,253,58,206,204,181,112,14,86,8,12,118,18,191,114,19,71,156,$${\displaystyle }$$183,93,135,21,161,150,41,16,123,154,199,243,145,120,111,157,158,178,$ $177,50,117,25,61,255,53,138,126,109,84,198,128,195,189,13,87,223,$ $245,36,169,62,168,67,201,215,121,214,246,124,34,185,3,224,15,236,$ $222,122,148,176,188,220,232,40,80,78,51,10,74,167,151,96,115,30,0,$ $98,68,26,184,56,130,100,159,38,65,173,69,70,146,39,94,85,47,140,163,$ $165,125,105,213,149,59,7,88,179,64,134,172,29,247,48,55,107,228,136,$ $217,231,137,225,27,131,73,76,63,248,254,141,83,170,144,202,216,133,$ $97,32,113,103,164,45,43,9,91,203,155,37,208,190,229,108,82,89,166,$

$116,210,230,244,180,192,209,102,175,194,57,75,99,182).$

Линейное преобразование

Задается отображением $\gamma$:

$\gamma (a_{15},$…$,a_{0})=\delta ^{-1}~(148*\delta (a_{15})+32*\delta (a_{14})+133*\delta (a_{13})+16*\delta (a_{12})+$ $194*\delta (a_{11})+192*\delta (a_{10})+1*\delta (a_{9})+251*\delta (a_{8})+1*\delta (a_{7})+192*\delta (a_{6})+$ $194*\delta (a_{5})+16*\delta (a_{4})+133*\delta (a_{3})+32*\delta (a_{2})+148*\delta (a_{1})+1*\delta (a_{0})),$

где операции сложения и умножения осуществляются в поле $\mathbb {F}$.

Генерация ключа

Алгоритм генерации ключа использует итерационные константы $C_{i}=H(Bin_{128}(i))$, i=1,2,…32. Задается общий ключ $K=k_{255}||$…$||k_{0}$.

Вычисляются итерационные ключи

$K_{1}=k_{255}||$…$||k_{128}$

$K_{2}=k_{127}||$…$||k_{0}$

$(K_{2i+1},K_{2i+2})=F[C_{8(i-1)+8}]$…$F[C_{8(i-1)+1}](K_{2i+1},K_{2i}),i=1,2,3,4.$

Алгоритм зашифрования

$E(a)=Add_{2}[K_{10}]HNAdd_{2}[K_{9}]$…$HNAdd_{2}[K_{2}]HNAdd_{2}[K_{1}](a),$ где a — строка размером 128 бит.

Алгоритм расшифрования

$D(a)=Add_{2}[K_{1}]H^{-1}N^{-1}Add_{2}[K_{2}]$…$H^{-1}N^{-1}Add_{2}[K_{9}]H^{-1}N^{-1}Add_{2}[K_{10}](a).$

Пример

Строка «a» задается в шестнадцатеричном виде и имеет размер 16 байт, причём каждый байт задается двумя шестнадцатеричными числами.

Таблица соответствия строк в двоичном и в шестнадцатеричном виде:

0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f

Пример N-преобразования

$N(00112233445566778899aabbccddeeff)=fc7765aeeaoc9a7ee8d7387d88d86cb6$

Пример G-преобразования

$G(00000000000000000000000000000100)=94000000000000000000000000000001$

$G(94000000000000000000000000000001)=a5940000000000000000000000000000$

$G(a5940000000000000000000000000000)=64a59400000000000000000000000000$

$G(64a59400000000000000000000000000)=0d64a594000000000000000000000000$

Пример H-преобразования

$H(64a59400000000000000000000000000)=d456584dd0e3e84cc3166e4b7fa2890d$

Пример генерации ключа

$K=8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef.$

$K_{1}=8899aabbccddeeff0011223344556677,$

$K_{2}=fedcba98765432100123456789abcdef.$

$C_{1}=6ea276726c487ab85d27bd10dd849401,$

$Add_{2}[C_{1}](K_{1})=e63bdcc9a09594475d369f2399d1f276,$

$NAdd_{2}[C_{1}[(K_{1})=0998ca37a7947aabb78f4a5ae81b748a,$

$HNAdd_{2}[C_{1}](K_{1})=3d0940999db75d6a9257071d5e6144a6,$

$F[C_{1}](K_{1},K_{2})=(HNAdd_{2}[C_{1}](K_{1})\oplus K_{2},K_{1})=(c3d5fa01ebe36f7a9374427ad7ca8949,8899aabbccddeeff0011223344556677).$

$C_{2}=dc87ece4d890f4b3ba4eb92079cbeb02,$

$F[C_{2}]F[C_{1}](K_{1},K_{2})=(37777748e56453377d5e262d90903f87,c3d5fa01ebe36f7a9374427ad7ca8949).$

$C_{3}=b2259a96b4d88e0be7690430a44f7f03,$

$F[C_{3}]F[C_{2}]F[C_{1}](K_{1},K_{2})=(f9eae5f29b2815e31f11ac5d9c29fb01,37777748e56453377d5e262d90903f87).$

$C_{4}=7bcd1b0b73e32ba5b79cb140f2551504,$

$F[C_{4}]F[C_{3}]F[C_{2}]F[C_{1}](K_{1},K_{2})=(e980089683d00d4be37dd3434699b98f,f9eae5f29b2815e31f11ac5d9c29fb01).$

$C_{5}=156f6d791fab511deabb0c502fd18105,$

$F[C_{5}]F[C_{4}]F[C_{3}]F[C_{2}]F[C_{1}](K_{1},K_{2})=(b7bd70acea4460714f4ebe13835cf004,e980089683d00d4be37dd3434699b98f).$

$C_{6}=a74af7efab73df160dd208608b9efe06,$

$F[C_{6}]F[C_{5}]F[C_{4}]F[C_{3}]F[C_{2}]F[C_{1}](K_{1},K_{2})=(1a46ea1cf6ccd236467287df93fdf974,b7bd70acea4460714f4ebe13835cf004).$

$C_{7}=c9e8819dc73ba5ae50f5b570561a6a07,$

$F[C_{7}]F[C_{6}]F[C_{5}]F[C_{4}]F[C_{3}]F[C_{2}]F[C_{1}](K_{1},K_{2})=(3d4553d8e9cfec6815ebadc40a9ffd04,1a46ea1cf6ccd236467287df93fdf974).$

$C_{8}=f6593616e6055689adfba18027aa2a08,$

$(K_{3},K_{4})=F[C_{8}]F[C_{7}]$…$F[C_{2}]F[C_{1}](K_{1},K_{2})=(db31485315694343228d6aef8cc78c44,3d4553d8e9cfec6815ebadc40a9ffd04).$

В итоге получаем итерационные ключи:

$K_{1}=8899aabbccddeeff0011223344556677,$

$K_{2}=fedcba98765432100123456789abcdef,$

$K_{3}=db31485315694343228d6aef8cc78c44,$

$K_{4}=3d4553d8e9cfec6815ebadc40a9ffd04,$

$K_{5}=57646468c44a5e28d3e59246f429f1ac,$

$K_{6}=bd079435165c6432b532e82834da581b,$

$K_{7}=51e640757e8745de705727265a0098b1,$

$K_{8}=5a7925017b9fdd3ed72a91a22286f984,$

$K_{9}=bb44e25378c73123a5f32f73cdb6e517,$

$K_{10}=72e9dd7416bcf45b755dbaa88e4a4043.$

Пример алгоритма зашифрования

Открытый текст $a=1122334455667700ffeeddccbbaa9988,$

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

Ожидается, что новый блочный шифр «Кузнечик» будет устойчив ко всем видам атак на блочные шифры.

На конференции «CRYPTO 2015» Алекс Бирюков, Лео Перрин и Алексей Удовенко представили доклад, в котором говорится о том, что несмотря на утверждения разработчиков, значения S-блока шифра Кузнечик и хэш-функции Стрибог не являются (псевдо)случайными числами, а сгенерированы на основе скрытого алгоритма, который им удалось восстановить методами обратного проектирования. Позднее Лео Перрин и Алексей Удовенко опубликовали два альтернативных алгоритма генерации S-блока и доказали его связь с S-блоком белорусского шифра BeIT. В этом исследовании авторы также утверждают, что, хотя причины использования такой структуры остаются неясны, использование скрытых алгоритмов для генерации S-блоков противоречит принципу отсутствия козыря в рукаве, который мог бы служить доказательством отсутствия специально заложенных уязвимостей в дизайне алгоритма.

Riham AlTawy и Amr M. Youssef описали атаку «встречи посередине» на 5 раундов шифра Кузнечик, имеющую вычислительную сложность 2¹⁴⁰ и требующую 2¹⁵³ памяти и 2¹¹³ данных.

Ссылки

• В ГОСТе сидел «Кузнечик»