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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
(перенаправлено с «Kuznechik»)
У этого термина существуют и другие значения, см. Кузнечик (значения).
Кузнечик
Создатель ФСБ России,
АО «ИнфоТеКС»
Опубликован 2015
Стандарты ГОСТ 34.12-2018, ГОСТ Р 34.12-2015, RFC 7801
Размер ключа 256 бит
Размер блока 128 бит
Число раундов 10
Тип Подстановочно-перестановочная сеть

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

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

Данный шифр утверждён (наряду с блочным шифром «Магма») в качестве стандарта в ГОСТ Р 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 года.

Обозначения

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

[math]\displaystyle{ Bin_8 : \Z_p \rightarrow V_8 }[/math] — биективное отображение, ставящее в соответствие элементу кольца [math]\displaystyle{ \Z_p }[/math] ([math]\displaystyle{ p=2^8 }[/math]) его двоичное представление.

[math]\displaystyle{ {Bin_8}^{-1}: V_8 \rightarrow \Z_p }[/math] — отображение, обратное к [math]\displaystyle{ Bin_8 }[/math].

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

[math]\displaystyle{ \delta^{-1}: \mathbb F \rightarrow V_8 }[/math] — отображение, обратное к [math]\displaystyle{ \delta }[/math]

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

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

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

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

[math]\displaystyle{ G(a)=\gamma(a_{15}, }[/math]…[math]\displaystyle{ ,a_0)||a_{15}|| }[/math]…[math]\displaystyle{ ||a_{1}. }[/math]

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

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

[math]\displaystyle{ F[k](a_1,a_0)=(HNAdd_2[k](a_1)\oplus a_0, a_1). }[/math]

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

Нелинейное преобразование задается подстановкой S = Bin8 S' Bin8−1.

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

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

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

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

[math]\displaystyle{ \gamma(a_{15}, }[/math]…[math]\displaystyle{ , a_0) = \delta^{-1}~(148 * \delta(a_{15}) + 32 * \delta(a_{14}) + 133 * \delta(a_{13}) + 16 * \delta(a_{12}) + }[/math] [math]\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) + }[/math] [math]\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)), }[/math]

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

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

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

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

[math]\displaystyle{ K_1=k_{255}|| }[/math]…[math]\displaystyle{ ||k_{128} }[/math]

[math]\displaystyle{ K_2=k_{127}|| }[/math]…[math]\displaystyle{ ||k_{0} }[/math]

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

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

[math]\displaystyle{ E(a)=Add_2[K_{10}]HNAdd_2[K_9] }[/math]…[math]\displaystyle{ HNAdd_2[K_2]HNAdd_2[K_1](a), }[/math] где a — строка размером 128 бит.

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

[math]\displaystyle{ D(a)=Add_2[K_{1}]N^{-1}H^{-1}Add_2[K_2] }[/math]…[math]\displaystyle{ N^{-1}H^{-1}Add_2[K_9]N^{-1}H^{-1}Add_2[K_{10}](a). }[/math]

Пример[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-преобразования

[math]\displaystyle{ N(00112233445566778899aabbccddeeff)=fc7765aeeaoc9a7ee8d7387d88d86cb6 }[/math]

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

[math]\displaystyle{ G(00000000000000000000000000000100)=94000000000000000000000000000001 }[/math]

[math]\displaystyle{ G(94000000000000000000000000000001) = a5940000000000000000000000000000 }[/math]

[math]\displaystyle{ G(a5940000000000000000000000000000) = 64a59400000000000000000000000000 }[/math]

[math]\displaystyle{ G(64a59400000000000000000000000000) = 0d64a594000000000000000000000000 }[/math]

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

[math]\displaystyle{ H(64a59400000000000000000000000000) = d456584dd0e3e84cc3166e4b7fa2890d }[/math]

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

[math]\displaystyle{ K=8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef. }[/math]

[math]\displaystyle{ K_1=8899aabbccddeeff0011223344556677, }[/math]

[math]\displaystyle{ K_2=fedcba98765432100123456789abcdef. }[/math]

[math]\displaystyle{ C_1=6ea276726c487ab85d27bd10dd849401, }[/math]

[math]\displaystyle{ Add_2[C_1](K_1)=e63bdcc9a09594475d369f2399d1f276, }[/math]

[math]\displaystyle{ NAdd_2[C_1[(K_1)=0998ca37a7947aabb78f4a5ae81b748a, }[/math]

[math]\displaystyle{ HNAdd_2[C_1](K_1)=3d0940999db75d6a9257071d5e6144a6, }[/math]

[math]\displaystyle{ F[C_1](K_1,K_2)=(HNAdd_2[C_1](K_1)\oplus K_2, K_1)=(c3d5fa01ebe36f7a9374427ad7ca8949, 8899aabbccddeeff0011223344556677). }[/math]


[math]\displaystyle{ C_2=dc87ece4d890f4b3ba4eb92079cbeb02, }[/math]

[math]\displaystyle{ F[C_2]F[C_1](K_1,K_2)=(37777748e56453377d5e262d90903f87, c3d5fa01ebe36f7a9374427ad7ca8949). }[/math]


[math]\displaystyle{ C_3=b2259a96b4d88e0be7690430a44f7f03, }[/math]

[math]\displaystyle{ F[C_3]F[C_2]F[C_1](K_1,K_2)=(f9eae5f29b2815e31f11ac5d9c29fb01, 37777748e56453377d5e262d90903f87). }[/math]


[math]\displaystyle{ C_4=7bcd1b0b73e32ba5b79cb140f2551504, }[/math]

[math]\displaystyle{ F[C_4]F[C_3]F[C_2]F[C_1](K_1,K_2)=(e980089683d00d4be37dd3434699b98f, f9eae5f29b2815e31f11ac5d9c29fb01). }[/math]


[math]\displaystyle{ C_5=156f6d791fab511deabb0c502fd18105, }[/math]

[math]\displaystyle{ F[C_5]F[C_4]F[C_3]F[C_2]F[C_1](K_1,K_2)=(b7bd70acea4460714f4ebe13835cf004, e980089683d00d4be37dd3434699b98f). }[/math]


[math]\displaystyle{ C_6=a74af7efab73df160dd208608b9efe06, }[/math]

[math]\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). }[/math]


[math]\displaystyle{ C_7=c9e8819dc73ba5ae50f5b570561a6a07, }[/math]

[math]\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). }[/math]


[math]\displaystyle{ C_8=f6593616e6055689adfba18027aa2a08, }[/math]

[math]\displaystyle{ (K_3,K_4)=F[C_8]F[C_7] }[/math]…[math]\displaystyle{ F[C_2]F[C_1](K_1,K_2)=(db31485315694343228d6aef8cc78c44, 3d4553d8e9cfec6815ebadc40a9ffd04). }[/math]


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

[math]\displaystyle{ K_1=8899aabbccddeeff0011223344556677, }[/math]

[math]\displaystyle{ K_2=fedcba98765432100123456789abcdef, }[/math]

[math]\displaystyle{ K_3=db31485315694343228d6aef8cc78c44, }[/math]

[math]\displaystyle{ K_4=3d4553d8e9cfec6815ebadc40a9ffd04, }[/math]

[math]\displaystyle{ K_5=57646468c44a5e28d3e59246f429f1ac, }[/math]

[math]\displaystyle{ K_6=bd079435165c6432b532e82834da581b, }[/math]

[math]\displaystyle{ K_7=51e640757e8745de705727265a0098b1, }[/math]

[math]\displaystyle{ K_8=5a7925017b9fdd3ed72a91a22286f984, }[/math]

[math]\displaystyle{ K_9=bb44e25378c73123a5f32f73cdb6e517, }[/math]

[math]\displaystyle{ K_{10}=72e9dd7416bcf45b755dbaa88e4a4043. }[/math]

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

Открытый текст [math]\displaystyle{ a=1122334455667700ffeeddccbbaa9988, }[/math]

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

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

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

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

Примечания

  1. ↑ Согласно ГОСТ Р 34.12-2015 и RFC 7801 шифр может именоваться на английском как Kuznyechik
  2. ↑ Согласно ГОСТ 34.12-2018 шифр может именоваться на английском как Kuznechik.
  3. ↑ Некоторые программные реализации шифра с открытым исходным кодом используют наименование Grasshopper
  4. ↑ «ГОСТ Р 34.12-2015» (недоступная ссылка). Дата обращения: 4 сентября 2015. Архивировано 24 сентября 2015 года.
  5. ↑ «О введении новых криптографических стандартов». Дата обращения: 4 сентября 2015. Архивировано 27 сентября 2016 года.
  6. ↑ «www.tc26.ru». Дата обращения: 14 декабря 2014. Архивировано 18 декабря 2014 года.
  7. ↑ Архивированная копия (недоступная ссылка). Дата обращения: 13 апреля 2016. Архивировано 24 апреля 2016 года.
  8. ↑ http://www.tc26.ru/standard/draft/GOSTR-bsh.pdf Архивная копия от 26 декабря 2014 на Wayback Machine см. Контрольные примеры
  9. ↑ Alex Biryukov, Léo Perrin, Aleksei Udovenko. Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Full Version) (8 мая 2016). Дата обращения: 21 мая 2021. Архивировано 4 марта 2021 года.
  10. ↑ Léo Perrin, Aleksei Udovenko. Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog (3 февраля 2017). Дата обращения: 14 сентября 2017. Архивировано 17 апреля 2021 года.
  11. ↑ Riham AlTawy and Amr M. Youssef. A Meet in the Middle Attack on Reduced Round Kuznyechik (17 апреля 2015). Дата обращения: 8 июня 2016. Архивировано 16 июля 2017 года.

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Кузнечик_(шифр)&oldid=5863013