Kuznechik

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

Kuznechik

Раундів	10
Тип	мережа замін-перестановок

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

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

Позначення

${\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 }$${\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}]H^{-1}N^{-1}Add_{2}[K_{2}]}$…${\displaystyle 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-перетворення

${\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,}$

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

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

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

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

Примітки

1. (PDF). Архів оригіналу (PDF) за 25 вересня 2018. Процитовано 25 вересня 2018.
2. . Архів оригіналу за 27 вересня 2016. Процитовано 10 квітня 2018.
3. Alex Biryukov, Léo Perrin, Aleksei Udovenko (2016). (PDF). Архів оригіналу (PDF) за 16 липня 2017. Процитовано 10 квітня 2018.
4. Léo Perrin, Aleksei Udovenko (2017). (PDF). Архів оригіналу (PDF) за 17 квітня 2021. Процитовано 10 квітня 2018.
5. Riham AlTawy and Amr M. Youssef (17 квітня 2015). (PDF). Архів оригіналу (PDF) за 16 липня 2017. Процитовано 10 квітня 2018.

Посилання

• В ГОСТе сидел «Кузнечик» [ 12 квітня 2018 у Wayback Machine.]
• Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 [ 16 липня 2017 у Wayback Machine.]
• Пошаговая работа ГОСТ Р 34.12-2015 в режиме ECB [ 11 квітня 2018 у Wayback Machine.]

Див. також

• Геш-функція
• Калина (шифр)
• Стандарти криптографії