Kuznechik

Kuznechik (або англ. Kuznyechik, або рос. Кузнечик) — симетричний алгоритм блочного шифрування з розміром блоку 128 бітів і довжиною ключа 256 бітів який входить в стандарту ГОСТ Р 34.12-2015 та ГОСТ 34.12-2018. Шифр використовує для генерації раундових ключів мережу замін-перестановок.

Алгоритм блокового шифрування
Назва:	Kuznechik
Розробник:
Створений:
Опублікований:
Розмір ключа:	250 біт
Розмір блоку:	128 біт
Число раундів:	10
Тип:	мережа замін-перестановок

Загальні дані

Даний шифр затверджений (поряд з блочним шифром «Магма») в якості стандарту в ГОСТ Р 34.12-2015 «Інформаційна технологія. Криптографічний захист інформації. Блочні шифри» Наказом від 19 червня 2015 року № 749-ст[1]. Стандарт вступив в дію з 1 січня 2016 року.[2]. Шифр розроблений Центром захисту інформації та спеціального зв'язку ФСБ Росії за участю ВАТ «Інформаційні технології та комунікаційні системи» (ВАТ «ІнфоТеКС»). Внесений Технічним комітетом зі стандартизації ТК 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,$ $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,$

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

Очікується, що новий блочний шифр Kuznechik буде стійкий до всіх видів атак на блочні шифри.

На конференції «CRYPTO-2015» Алекс Бірюков, Лео Перрін і Олексій Удовенко представили доповідь, в якій говориться про те, що незважаючи на твердження розробників, значення S-блоку шифру Kuznechik і геш-функції Streebog не є (псевдо) випадковими числами, а згенеровані на основі прихованого алгоритму, який їм вдалося відновити методами зворотного проектування[3]. Пізніше Лео Перрін і Олексій Удовенко опублікували два альтернативних алгоритми генерації S-блоку і довели його зв'язок з S-блоком білоруського шифру BelT[4]. У цьому дослідженні автори також стверджують, що, хоча причини використання такої структури залишаються неясні, використання прихованих алгоритмів для генерації S-блоків суперечить принципу відсутності козиря в рукаві, який міг би служити доказом відсутністі спеціально закладених вразливостей в дизайні алгоритму.

Riham AlTawy і Amr M. Youssef описали атаку «зустрічі посередині» на 5 раундів шифру Kuznechik, 256-бітний майстер-ключ відновлюється з складністю часу 2^140.3 і вимагає 2^153.3 пам'яті та 2¹¹³ даних.[5]

Примітки

«ГОСТ Р 34.12-2015»
«Про введення нових криптографічних стандартів»
Alex Biryukov, Léo Perrin, Aleksei Udovenko (2016). Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Full Version).
Léo Perrin, Aleksei Udovenko (2017). Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog.
Riham AlTawy and Amr M. Youssef (17 квітня 2015). A Meet in the Middle Attack on Reduced Round Kuznyechik.

Посилання

Див. також

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

[1] «ГОСТ Р 34.12-2015»

[2] «Про введення нових криптографічних стандартів»

[3] Alex Biryukov, Léo Perrin, Aleksei Udovenko (2016). Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Full Version).

[4] Léo Perrin, Aleksei Udovenko (2017). Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog.

[mitm-5] Riham AlTawy and Amr M. Youssef (17 квітня 2015). A Meet in the Middle Attack on Reduced Round Kuznyechik.