Кузнечик

Кузнечик

Общий
Дизайнеры	АО «ИнфоТеКС»
Впервые опубликовано	2015
Сертификация	ГОСТ и ФСС
Деталь шифрования
Размеры ключей	256-битная сеть Фейстеля
Размеры блоков	128 бит
Структура	Сеть замены-перестановки
Раунды	10
Лучший публичный криптоанализ
Атака «встреча посередине» на протяжении 5 раундов.

Кузнечик ( русский : Кузнечик , буквально «кузнечик») — симметричный блочный шифр . Он имеет размер блока 128 бит и длину ключа 256 бит. Определено в Национальном стандарте РФ ГОСТ Р 34.12-2015. а также в RFC 7801.

Название шифра можно перевести с русского как кузнечик , однако в стандарте прямо сказано, что английское название шифра — Кузнечик ( / k ʊ z n ˈ ɛ tʃ ɪ k / ). Разработчики утверждают, что, назвав шифр Кузнечик, они следуют тенденции труднопроизносимых названий алгоритмов, заложенной Рейндалом и Кечаком . Также ходит слух, что шифр был назван в честь его создателей: А.С. Кузьмина, A. A. Nechaev and Company (Russian: Куз ьмин, Неч аев и К омпания).

Стандарт ГОСТ Р 34.12-2015 определяет новый шифр в дополнение к старому блочному шифру ГОСТ (теперь называемому «Магма») как единый и не объявляет старый шифр устаревшим.

Кузнечик основан на сети подстановки-перестановки , хотя ключевое расписание использует сеть Фейстеля .

Обозначения

$\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))$, я=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),$ где а — 128-битная строка.

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

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

Криптоанализ

Рихам Аль-Тави и Амр М. Юсеф описывают атаку «встреча посередине» на сокращенный Кузнечик с 5 раундами, которая позволяет восстановить ключ с временной сложностью 2. ¹⁴⁰ , сложность памяти 2 ¹⁵³ и сложность данных 2 ¹¹³ .

Алекс Бирюков , Лео Перрен и Алексей Удовенко опубликовали статью, в которой показывают, что S-блоки Кузнечика и Стрибога были созданы не псевдослучайно , а с использованием скрытого алгоритма, который они смогли перепроектировать .

Позже Лео Перрен и Алексей Удовенко опубликовали две альтернативные декомпозиции S-box и доказали ее связь с S-box белорусского шифра БелТ. Авторы статьи отмечают, что, хотя причина использования такой структуры остается неясной, генерация S-блоков с помощью скрытого алгоритма противоречит концепции чисел «ничего в рукаве» , которые могут доказать, что в их конструкцию не было намеренно введено никаких недостатков. .

Рихам Аль-Тави, Онур Думан и Амр М. Юсеф опубликовали две ошибочные атаки на Кузнечика, которые показывают важность защиты реализаций шифра.

Принятие

VeraCrypt (форк TrueCrypt ) включил Кузнечик в качестве одного из поддерживаемых алгоритмов шифрования.

Исходный код

• https://web.archive.org/web/20160424051147/http://tc26.ru/standard/draft/PR_GOSTR-bch_v4.zip
• https://web.archive.org/web/20180406230057/https://fossies.org/windows/misc/VeraCrypt_1.22_Source.zip/src/Crypto/kuznyechik.c (альтернативная ссылка на случай, если первая ссылка не работает) )