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

У этого термина существуют и другие значения, см. Кузнечик (значения).

«Кузнечик» (англ. Kuznyechik^[1] или англ. Kuznechik^[2][3]) — симметричный алгоритм блочного шифрования с размером блока 128 бит и длиной ключа 256 бит, использующий для генерации раундовых ключей SP-сеть.

Кузнечик
Создатель	ФСБ России, АО «ИнфоТеКС»
Опубликован	2015
Стандарты	ГОСТ 34.12-2018, ГОСТ Р 34.12-2015, RFC 7801
Размер ключа	256 бит
Размер блока	128 бит
Число раундов	10
Тип	Подстановочно-перестановочная сеть

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

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

Протоколом № 54 от 29 ноября 2018 года, на основе ГОСТ Р 34.12-2015, Межгосударственным советом по метрологии, стандартизации и сертификации был принят межгосударственный стандарт ГОСТ 34.12-2018. Приказом Федерального агентства по техническому регулированию и метрологии от 4 декабря 2018 года № 1061-ст стандарт ГОСТ 34.12-2018 введен в действие в качестве национального стандарта Российской Федерации с 1 июня 2019 года.

Обозначения

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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)):

${\displaystyle S'=(252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,233,}$ ${\displaystyle 119,240,219,147,46,153,186,23,54,241,187,20,205,95,193,249,24,101,}$ ${\displaystyle 90,226,92,239,33,129,28,60,66,139,1,142,79,5,132,2,174,227,106,143,}$ ${\displaystyle 160,6,11,237,152,127,212,211,31,235,52,44,81,234,200,72,171,242,42,}$ ${\displaystyle 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,}$ ${\displaystyle 177,50,117,25,61,255,53,138,126,109,84,198,128,195,189,13,87,223,}$ ${\displaystyle 245,36,169,62,168,67,201,215,121,214,246,124,34,185,3,224,15,236,}$ ${\displaystyle 222,122,148,176,188,220,232,40,80,78,51,10,74,167,151,96,115,30,0,}$ ${\displaystyle 98,68,26,184,56,130,100,159,38,65,173,69,70,146,39,94,85,47,140,163,}$ ${\displaystyle 165,125,105,213,149,59,7,88,179,64,134,172,29,247,48,55,107,228,136,}$ ${\displaystyle 217,231,137,225,27,131,73,76,63,248,254,141,83,170,144,202,216,133,}$ ${\displaystyle 97,32,113,103,164,45,43,9,91,203,155,37,208,190,229,108,82,89,166,}$ ${\displaystyle 116,210,230,244,180,192,209,102,175,194,57,75,99,182).}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример[8]

Строка «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-преобразования

${\displaystyle N(00112233445566778899aabbccddeeff)=fc7765aeeaoc9a7ee8d7387d88d86cb6}$

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

${\displaystyle G(00000000000000000000000000000100)=94000000000000000000000000000001}$

${\displaystyle G(94000000000000000000000000000001)=a5940000000000000000000000000000}$

${\displaystyle G(a5940000000000000000000000000000)=64a59400000000000000000000000000}$

${\displaystyle G(64a59400000000000000000000000000)=0d64a594000000000000000000000000}$

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

${\displaystyle H(64a59400000000000000000000000000)=d456584dd0e3e84cc3166e4b7fa2890d}$

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

${\displaystyle K=8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef.}$

${\displaystyle K_{1}=8899aabbccddeeff0011223344556677,}$

${\displaystyle K_{2}=fedcba98765432100123456789abcdef.}$

${\displaystyle C_{1}=6ea276726c487ab85d27bd10dd849401,}$

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

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

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

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

${\displaystyle C_{2}=dc87ece4d890f4b3ba4eb92079cbeb02,}$

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

${\displaystyle C_{3}=b2259a96b4d88e0be7690430a44f7f03,}$

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

${\displaystyle C_{4}=7bcd1b0b73e32ba5b79cb140f2551504,}$

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

${\displaystyle C_{5}=156f6d791fab511deabb0c502fd18105,}$

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

${\displaystyle C_{6}=a74af7efab73df160dd208608b9efe06,}$

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

${\displaystyle C_{7}=c9e8819dc73ba5ae50f5b570561a6a07,}$

${\displaystyle 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).}$

${\displaystyle C_{8}=f6593616e6055689adfba18027aa2a08,}$

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

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

${\displaystyle K_{1}=8899aabbccddeeff0011223344556677,}$

${\displaystyle K_{2}=fedcba98765432100123456789abcdef,}$

${\displaystyle K_{3}=db31485315694343228d6aef8cc78c44,}$

${\displaystyle K_{4}=3d4553d8e9cfec6815ebadc40a9ffd04,}$

${\displaystyle K_{5}=57646468c44a5e28d3e59246f429f1ac,}$

${\displaystyle K_{6}=bd079435165c6432b532e82834da581b,}$

${\displaystyle K_{7}=51e640757e8745de705727265a0098b1,}$

${\displaystyle K_{8}=5a7925017b9fdd3ed72a91a22286f984,}$

${\displaystyle K_{9}=bb44e25378c73123a5f32f73cdb6e517,}$

${\displaystyle K_{10}=72e9dd7416bcf45b755dbaa88e4a4043.}$

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

Открытый текст ${\displaystyle a=1122334455667700ffeeddccbbaa9988,}$

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

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

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

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