Кузнечик гост: Кузнечик (шифр) — Википедия – просто о сложном / Habr

19.07.2020

Содержание

Кузнечик (шифр) — Википедия

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

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

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

Согласно ГОСТ Р 34.12-2015 и RFC 7801 шифр может именоваться на английском как Kuznyechik, а согласно ГОСТ 34.12-2018 как Kuznechik. К тому же некоторые реализации шифра с открытым исходным кодом используют наименование Grasshopper.

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

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

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

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

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

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

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

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

G(a)=γ(a15,{\displaystyle G(a)=\gamma (a_{15},}…,a0)||a15||{\displaystyle ,a_{0})||a_{15}||}…||a1.{\displaystyle ||a_{1}.}

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

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

F[k](a1,a0)=(HNAdd2[k](a1)⊕a0,a1).{\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)):

== S′=(252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,233,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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 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,{\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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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).{\displaystyle 116,210,230,244,180,192,209,102,175,194,57,75,99,182).} ==

Линейное преобразование[править | править код]

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

γ(a15,{\displaystyle \gamma (a_{15},}…,a0)=δ−1 (148∗δ(a15)+32∗δ(a14)+133∗δ(a13)+16∗δ(a12)+{\displaystyle ,a_{0})=\delta ^{-1}~(148*\delta (a_{15})+32*\delta (a_{14})+133*\delta (a_{13})+16*\delta (a_{12})+} 194∗δ(a11)+192∗δ(a10)+1∗δ(a9)+251∗δ(a8)+1∗δ(a7)+192∗δ(a6)+{\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})+} 194∗δ(a5)+16∗δ(a4)+133∗δ(a3)+32∗δ(a2)+148∗δ(a1)+1∗δ(a0)),{\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})),}

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

Генерация ключа[править | править код]

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

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

K1=k255||{\displaystyle K_{1}=k_{255}||}…||k128{\displaystyle ||k_{128}}

K2=k127||{\displaystyle K_{2}=k_{127}||}…||k0{\displaystyle ||k_{0}}

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

Алгоритм зашифрования[править | править код]

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

Алгоритм расшифрования[править | править код]

D(a)=Add2[K1]N−1H−1Add2[K2]{\displaystyle D(a)=Add_{2}[K_{1}]N^{-1}H^{-1}Add_{2}[K_{2}]}…N−1H−1Add2[K9]N−1H−1Add2[K10](a).{\displaystyle N^{-1}H^{-1}Add_{2}[K_{9}]N^{-1}H^{-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{\displaystyle N(00112233445566778899aabbccddeeff)=fc7765aeeaoc9a7ee8d7387d88d86cb6}

Пример G-преобразования[править | править код]

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

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

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

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

Пример H-преобразования[править | править код]

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

Пример генерации ключа[править | править код]

K=8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef.{\displaystyle K=8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef.}

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

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

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

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

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

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

F[C1](K1,K2)=(HNAdd2[C1](K1)⊕K2,K1)=(c3d5fa01ebe36f7a9374427ad7ca8949,8899aabbccddeeff0011223344556677).{\displaystyle F[C_{1}](K_{1},K_{2})=(HNAdd_{2}[C_{1}](K_{1})\oplus K_{2},K_{1})=(c3d5fa01ebe36f7a9374427ad7ca8949,8899aabbccddeeff0011223344556677).}

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

F[C2]F[C1](K1,K2)=(37777748e56453377d5e262d90903f87,c3d5fa01e

В ГОСТе сидел «Кузнечик» / Habr

В июне этого года в России был принят новый стандарт блочного шифрования — ГОСТ Р 34.12-2015. Этот стандарт помимо старого доброго ГОСТ 28147-89, который теперь называется «Магма» и имеет фиксированный набор подстановок, содержит описание блочного шифра «Кузнечик». О нем я и расскажу в этом посте.

В отличие от ГОСТ 28147-89 новый шифр представляет собой не сеть Фейстеля, а т.н. SP-сеть: преобразование, состоящее из нескольких одинаковых раундов, при этом каждый раунд состоит из нелинейного и линейного преобразований, а также операции наложения ключа. В отличие от сети Фейстеля, при использовании SP-сети преобразуется весь входной блок, а не его половина. Такая структура иногда также называется AES-like (похожей на AES), однако, в отличие от последнего у «Кузнечика» есть ряд своих «фишек»:

линейное преобразование может быть реализовано в с помощью регистра сдвига;
ключевая развертка реализована с помощью сети Фейстеля, в которой в качестве функции используется раундовое преобразование исходного алгоритма.

Длина входного блока «Кузнечика» — 128 бит, ключа — 256 бит.

Преобразования

Шифрование основано на последовательном применении нескольких однотипных раундов, каждый из которых содержит три преобразования: сложение с раундовым ключом, преобразование блоком подстановок и линейное преобразование.

128-битный входной вектор очередного раунда складывается побитно с раундовым ключом:

Нелинейное преобразование представляет собой применение к каждому 8-битному подвектору 128-битного входного вектора фиксированной подстановки:

В «Кузнечике» используется та же подстановка, что и в хэш-функции «Стрибог».

Линейное преобразование, как я уже сказал, может быть реализовано не только как обычно в блочных шифрах — матрицей, но и с помощью РСЛОС — линейного регистра сдвига с обратной связью, который движется 16 раз.

Сам регистр реализуется над полем Галуа по модулю неприводимого многочлена степени 8: :

Раундовое преобразование можно изобразить следующим образом:

Выработка раундовых ключей

Рассмотрим теперь процедуру генерации раундовых ключей из мастер-ключа. Первые два получаются разбиением мастер-ключа пополам. Далее для выработки очередной пары раундовых ключей используется 8 итераций сети Фейстеля, где, в свою очередь, в качестве раундовых ключей используется счетчиковая последовательность, прошедшая через линейное преобразование алгоритма:

Раунд ключевой развертки можно представить следующим образом:

А всю процедуру выработки раундовых ключей так:

Шифрование и расшифрование

В результате, шифрование одного 128-битного входного блока описывается следующим уравнением:

А в виде блок-схемы может быть представлено так:

Расшифрование реализуется обращением базовых преобразований и применением их в обратном порядке:

Ссылки

Очередные странности в алгоритмах ГОСТ Кузнечик и Стрибог

Привет, %username%!

Криптографические алгоритмы в России не проходят через открытые конкурсы, их просто спускают нам свыше. И рано или поздно это сильно нам аукнется. Эта статья об очередном исследовании наших ГОСТов.

В 2016м году исследователи показали, что таблица перестановки в российских алгоритмах хеширования и шифрования Кузнечик и Стрибог имеет структуру, сильно далёкую от случайной. Это уже после того, как в Стрибоге была найдена тривиальная ошибка, уменьшающая его стойкость с 2⁵¹² до 2²⁶⁶.

29 января 2019 года была опубликовано новое исследование «Partitions in the S-Box of Streebog and Kuznyechik», которое недвусмысленно намекает на теоретическую возможность

бекдора в этих алгоритмах.

Итак, S-Box — или таблица замены, является ключевым элементом безопасности во многих алгоритмах симметричного шифрования и хеширования. Пример такой таблицы приведен на рисунке.

В общем случае эта таблица сопоставляет одной последовательности бит другую. А вот по какому принципу — всегда большой вопрос.

Государственные структуры нередко ограничиваются их публикацией без какого либо рационального объяснения. В случае с DES АНБ предложило изменить S-Box до того как алгоритм стал стандартом. Только через много лет выяснилось, что это изменение на самом деле повышало стойкость DES к дифференциальному криптоанализу.

В случае с новыми ГОСТами не всё так радужно. Авторы декларировали, что таблица замен выбрана случайным образом. Вот слайд из презентации алгоритма, на котором указано, что авторы выбирали таблицу случайным образом. Так, чтобы у неё не было явной структуры, которая помогла бы произвести эффективный криптоанализ. (Красным — то, что выбрали)

Вот эта таблица

Но, во-первых, как оказалось, она сгенерирована не случайным образом, а с помощью хитрого алгоритма, который расковыряли еще в 2015м.

Во-вторых, авторы не оставили попыток выяснить причину такого подхода к конструированию S-Box и натолкнулись на очень интересные результаты.

Оказалось, что алгоритмов, которые формируют таблицу замены, больше чем один. Разные группы исследователей описали абсолютно разные алгоритмы, которые не имеют почти ничего общего, но приходят к одной и той же таблице.

Это навело авторов оригинального исследования на мысль покопаться в структуре этих алгоритмов поглубже и найти общие элементы, что им с успехом удалось.

TKlog

TKlog — конструкция перестановки, которую авторы криптоанализа назвали в честь российской конторы ТК-26, где и были созданы Кузнечик со Стрибогом. Её описание сильно выходит за рамки данной статьи, желающие могут обратиться к оригиналу. Если в двух словах, то её ключевым свойством является использование дискретного логарифмирования, прям как в асимметричной криптографии.

Что важно, так это тот факт, что оба варианта функции замены из ГОСТовских алгоритмов являются частным случаем конструкции TKlog. Как и еще одна функция замены из белорусского алгоритма BelT. Функции разные, но сводятся к одной.

Скрытый текст

Тот факт, что разных вариантов преобразования TKlog крайне мало, говорит о преднамеренном использовании именно этой, нерандомизированной структуры вместо случайной, показанной нам на слайде.

Разбиения на смежные классы

Ключевым свойством преобразования TKlog является то, что оно работает с так называемыми смежными классами (cosets). И сопоставляет одни другим.

Проблема в том, что эти смежные классы бывают мультипликативными, как во всех обычных алгоритмах. А бывают аддитивными.

Так вот, единственный известный случай, когда аддитивные смежные классы использовались в функции замены блочных шифров — специальное создание бекдора. Информация об этом находится в работе 2016 года.

Такие бекдоры называются NOBUS, сокр. от «NObody But US», это уязвимости, которые могут эксплуатировать только сами авторы алгоритмов.

Вместо заключения

Авторы криптоанализа не представили новых атак на существующие алгоритмы ГОСТ, но задались справедливым вопросом целесообразности всего этого цирка с якобы случайной таблицей перестановки.

АНБ не так давно попыталось протолкнуть в стандарты свои легковесные симметричные алгоритмы Simon и Speck. И самого факта наличия таблиц замены с дизайном, описания которого предоставлено не было, хватило чтобы их отовсюду прогнали ссаными тряпками.

У нас такой возможности нет.

P.S. не забываем, что Стрибог использовался для генерации параметров новых ГОСТовских эллиптических кривых. С помощью него хэшировали мистическую константу W.

ГОСТ Р 34.12 ’15 на SSE2, или Не так уж и плох Кузнечик / Habr

/* Узел замены pi стандарта шифрования ГОСТ 34.12 Р 2015. */
const uint8_t Pi[256] = {
    0xfc, 0xee, 0xdd, 0x11, 0xcf, 0x6e, 0x31, 0x16, 0xfb, 0xc4, 0xfa, 0xda, 0x23, 0xc5, 0x04, 0x4d,
    0xe9, 0x77, 0xf0, 0xdb, 0x93, 0x2e, 0x99, 0xba, 0x17, 0x36, 0xf1, 0xbb, 0x14, 0xcd, 0x5f, 0xc1,
    0xf9, 0x18, 0x65, 0x5a, 0xe2, 0x5c, 0xef, 0x21, 0x81, 0x1c, 0x3c, 0x42, 0x8b, 0x01, 0x8e, 0x4f,
    0x05, 0x84, 0x02, 0xae, 0xe3, 0x6a, 0x8f, 0xa0, 0x06, 0x0b, 0xed, 0x98, 0x7f, 0xd4, 0xd3, 0x1f,
    0xeb, 0x34, 0x2c, 0x51, 0xea, 0xc8, 0x48, 0xab, 0xf2, 0x2a, 0x68, 0xa2, 0xfd, 0x3a, 0xce, 0xcc,
    0xb5, 0x70, 0x0e, 0x56, 0x08, 0x0c, 0x76, 0x12, 0xbf, 0x72, 0x13, 0x47, 0x9c, 0xb7, 0x5d, 0x87,
    0x15, 0xa1, 0x96, 0x29, 0x10, 0x7b, 0x9a, 0xc7, 0xf3, 0x91, 0x78, 0x6f, 0x9d, 0x9e, 0xb2, 0xb1,
    0x32, 0x75, 0x19, 0x3d, 0xff, 0x35, 0x8a, 0x7e, 0x6d, 0x54, 0xc6, 0x80, 0xc3, 0xbd, 0x0d, 0x57,
    0xdf, 0xf5, 0x24, 0xa9, 0x3e, 0xa8, 0x43, 0xc9, 0xd7, 0x79, 0xd6, 0xf6, 0x7c, 0x22, 0xb9, 0x03,
    0xe0, 0x0f, 0xec, 0xde, 0x7a, 0x94, 0xb0, 0xbc, 0xdc, 0xe8, 0x28, 0x50, 0x4e, 0x33, 0x0a, 0x4a,
    0xa7, 0x97, 0x60, 0x73, 0x1e, 0x00, 0x62, 0x44, 0x1a, 0xb8, 0x38, 0x82, 0x64, 0x9f, 0x26, 0x41,
    0xad, 0x45, 0x46, 0x92, 0x27, 0x5e, 0x55, 0x2f, 0x8c, 0xa3, 0xa5, 0x7d, 0x69, 0xd5, 0x95, 0x3b,
    0x07, 0x58, 0xb3, 0x40, 0x86, 0xac, 0x1d, 0xf7, 0x30, 0x37, 0x6b, 0xe4, 0x88, 0xd9, 0xe7, 0x89,
    0xe1, 0x1b, 0x83, 0x49, 0x4c, 0x3f, 0xf8, 0xfe, 0x8d, 0x53, 0xaa, 0x90, 0xca, 0xd8, 0x85, 0x61,
    0x20, 0x71, 0x67, 0xa4, 0x2d, 0x2b, 0x09, 0x5b, 0xcb, 0x9b, 0x25, 0xd0, 0xbe, 0xe5, 0x6c, 0x52,
    0x59, 0xa6, 0x74, 0xd2, 0xe6, 0xf4, 0xb4, 0xc0, 0xd1, 0x66, 0xaf, 0xc2, 0x39, 0x4b, 0x63, 0xb6,
};

/* Узел замены, обратный к pi, стандарта шифрования ГОСТ 34.12 Р 2015. */
const uint8_t InversedPi[256] = {
    0xa5, 0x2d, 0x32, 0x8f, 0x0e, 0x30, 0x38, 0xc0, 0x54, 0xe6, 0x9e, 0x39, 0x55, 0x7e, 0x52, 0x91,
    0x64, 0x03, 0x57, 0x5a, 0x1c, 0x60, 0x07, 0x18, 0x21, 0x72, 0xa8, 0xd1, 0x29, 0xc6, 0xa4, 0x3f,
    0xe0, 0x27, 0x8d, 0x0c, 0x82, 0xea, 0xae, 0xb4, 0x9a, 0x63, 0x49, 0xe5, 0x42, 0xe4, 0x15, 0xb7,
    0xc8, 0x06, 0x70, 0x9d, 0x41, 0x75, 0x19, 0xc9, 0xaa, 0xfc, 0x4d, 0xbf, 0x2a, 0x73, 0x84, 0xd5,
    0xc3, 0xaf, 0x2b, 0x86, 0xa7, 0xb1, 0xb2, 0x5b, 0x46, 0xd3, 0x9f, 0xfd, 0xd4, 0x0f, 0x9c, 0x2f,
    0x9b, 0x43, 0xef, 0xd9, 0x79, 0xb6, 0x53, 0x7f, 0xc1, 0xf0, 0x23, 0xe7, 0x25, 0x5e, 0xb5, 0x1e,
    0xa2, 0xdf, 0xa6, 0xfe, 0xac, 0x22, 0xf9, 0xe2, 0x4a, 0xbc, 0x35, 0xca, 0xee, 0x78, 0x05, 0x6b,
    0x51, 0xe1, 0x59, 0xa3, 0xf2, 0x71, 0x56, 0x11, 0x6a, 0x89, 0x94, 0x65, 0x8c, 0xbb, 0x77, 0x3c,
    0x7b, 0x28, 0xab, 0xd2, 0x31, 0xde, 0xc4, 0x5f, 0xcc, 0xcf, 0x76, 0x2c, 0xb8, 0xd8, 0x2e, 0x36,
    0xdb, 0x69, 0xb3, 0x14, 0x95, 0xbe, 0x62, 0xa1, 0x3b, 0x16, 0x66, 0xe9, 0x5c, 0x6c, 0x6d, 0xad,
    0x37, 0x61, 0x4b, 0xb9, 0xe3, 0xba, 0xf1, 0xa0, 0x85, 0x83, 0xda, 0x47, 0xc5, 0xb0, 0x33, 0xfa,
    0x96, 0x6f, 0x6e, 0xc2, 0xf6, 0x50, 0xff, 0x5d, 0xa9, 0x8e, 0x17, 0x1b, 0x97, 0x7d, 0xec, 0x58,
    0xf7, 0x1f, 0xfb, 0x7c, 0x09, 0x0d, 0x7a, 0x67, 0x45, 0x87, 0xdc, 0xe8, 0x4f, 0x1d, 0x4e, 0x04,
    0xeb, 0xf8, 0xf3, 0x3e, 0x3d, 0xbd, 0x8a, 0x88, 0xdd, 0xcd, 0x0b, 0x13, 0x98, 0x02, 0x93, 0x80,
    0x90, 0xd0, 0x24, 0x34, 0xcb, 0xed, 0xf4, 0xce, 0x99, 0x10, 0x44, 0x40, 0x92, 0x3a, 0x01, 0x26,
    0x12, 0x1a, 0x48, 0x68, 0xf5, 0x81, 0x8b, 0xc7, 0xd6, 0x20, 0x0a, 0x08, 0x00, 0x4c, 0xd7, 0x74,
};

ГОСТ Р 34.13–2015: стандарт строгого режима

Национальным стандартом Российской Федерации ГОСТ Р 34.12–2015 [1, 3] определены два базовых алгоритма шифрования – “Кузнечик» и “Магма», которые могут применяться в криптографических методах обработки и защиты информации, в том числе для обеспечения конфиденциальности, аутентичности и целостности информации при ее передаче, обработке и хранении в автоматизированных системах. В данной статье мы расскажем об основных эксплуатационных и криптографических характеристиках режимов работы блочных шифров, определяемых национальным стандартом Российской Федерации ГОСТ Р 34.13–2015 [2], введенным в действие приказом Федерального агентства по техническому регулированию и метрологии от 19 июня 2015 г. № 750-ст.

Александр
Бондаренко

Эксперт технического комитета по стандартизации ТК 26

Григорий
Маршалко

Эксперт технического комитета по стандартизации ТК 26, эксперт ISO/IEC JTC1/SC 27

Василий
Шишкин

Эксперт технического комитета по стандартизации ТК 26, эксперт ISO/IEC JTC1/SC 27, к.ф.-м.н.

Первоначально алгоритм криптографического преобразования (блочного алгоритма шифрования) и режимы работы данного алгоритма определялись единым национальным стандартом ГОСТ 28147–89, принятым в 1989 г. Через четыре года – в 1993 г. – в Российской Федерации был принят стандарт ГОСТ Р ИСО/МЭК 10116–93 [6], являвшийся аутентичным переводом соответствующего стандарта ISO/IEC. Список режимов в данном стандарте был расширен по сравнению с ГОСТ 28147–89, однако не содержал алгоритма выработки имитовставки. В течение последующих лет произошло бурное развитие многих областей криптографии, в том числе изучающих режимы работы блочных алгоритмов шифрования. С целью гармонизации нового поколения национальных стандартов в области криптографии с международной системой ISO/IEC [5] было принято решение определить режимы работы блочных шифров, включая режим выработки имитовставки, в отдельном стандарте ГОСТ Р 34.13–2015 [2]. При подготовке этого стандарта описание режимов было существенно переработано с целью обеспечения возможности параллельной обработки данных. Кроме этого режим выработки имитовставки был изменен на режим, обладающий более высокими эксплуатационными характеристиками.

Режим простой замены (Electronic Codebook, ECB)

Данный режим шифрования заключается в разбиении открытого текста на блоки длиной 128 бит для алгоритма «Кузнечик» или 64 бит для алгоритма «Магма» и замене полученных блоков открытого текста на соответствующие блоки шифрованного текста с использованием преобразования, задаваемого алгоритмом блочного шифрования. При расшифровании информации применяется обратная процедура (при этом используется обратное преобразование). На рис. 1 проиллюстрированы процедуры зашифрования и расшифрования в режиме простой замены.

Режим простой замены является наиболее простым и интуитивно понятным. При использовании алгоритма блочного шифрования в данном режиме информация может преобразовываться с использованием распараллеливания на необходимое (или возможное) число потоков зашифрования (расшифрования), т.к. преобразования блоков открытого текста в блоки зашифрованного текста между собой никак не связаны. Тем самым можно существенно повысить производительность работы алгоритмов блочного шифрования в режиме простой замены. Однако данный режим имеет значительный недостаток, заключающийся в том, что одинаковые блоки открытого текста преобразуются в одинаковые блоки зашифрованного текста. Таким образом, в зашифрованном тексте могут встречаться повторяющиеся блоки, свидетельствующие об одинаковых блоках открытого текста, что очевидным образом раскрывает его структуру. В связи с этим существенным недостатком зашифрование более одного блока открытого теста в режиме простой замены представляется нецелесообразным.

Режим гаммирования (Counter, CTR)

Данный режим работы имеет два параметра:

s – целочисленная величина, определяющая длину блока открытого текста. Для алгоритма «Кузнечик» параметр s не может превосходить значение 128, а для алгоритма «Магма» – 64;
IV – уникальная несекретная двоичная последовательность (инициализационный вектор, синхропосылка), определяемая для каждого открытого текста и ключа. Для алгоритма «Кузнечик» размер синхропосылки IV равен 64 битам, а для алгоритма «Магма» размер синхропосылки IV равен 32 битам.

Режим заключается в разбиении открытого текста на блоки длины s и в итеративном сложении полученных блоков открытого текста с усеченным до длины s результатом зашифрования блока, состоящего из синхропосылки IV и очередного значения счетчика. На рис. 2 проиллюстрирована процедура зашифрования в режиме гаммирования.

Нетрудно заметить, что процедура расшифрования в режиме гаммирования заключается в прибавлении той же последовательности, только уже к зашифрованному тексту. Данная процедура проиллюстрирована на рис. 3.

Необходимо отметить, что данный режим работы алгоритмов блочного шифрования является одним из наиболее часто используемых, поскольку лишен описанного выше недостатка режима простой замены и допускает распараллеливание, что существенно повышает его производительность. Например, первый поток осуществляет преобразование CRT₁, CRT₂, …, CRT_r, с помощью которых осуществляется шифрование блоков открытого текста – P₁, P₂, …, P_r, второй поток осуществляет преобразование CRT_r+1, CRT_r+2, …, CRT_2r, с помощью которых осуществляется шифрование блоков открытого текста – P_r+1, P_r+2, …, P_2r, и т.д. Зачастую в режиме гаммирования параметр s выбирают равным длине блока алгоритма блочного шифрования, то есть для алгоритма «Кузнечик» s = 128, а для алгоритма «Магма» – s = 64, в этом случае нет необходимости производить усечение. Также стоит отметить, что синхропосылка, используемая в режиме гаммирования, может быть передана в открытом виде получателю информации, т.е. на нее не налагаются требования по обеспечению конфиденциальности. Заметим, что в режиме гаммирования при зашифровании и расшифровании используется только прямое криптографические преобразование Ek.

Режим простой замены с зацеплением (Cipher Block Chaining, CBC)

Данный режим работы имеет два параметра:

m – целочисленная величина, определяющая длину регистра сдвига R;
IV – уникальная несекретная двоичная последовательность (инициализационный вектор, синхропосылка), определяемая для каждого открытого текста и ключа и имеющая размер, равный m битам.

В режиме простой замены с зацеплением очередной блок зашифрованного текста получается путем зашифрования результата покомпонентного сложения значения очередного блока открытого текста со значением n разрядов регистра сдвига R со старшими номерами. Затем регистр сдвигается на n разрядов в сторону разрядов со старшими номерами. В разряды с младшими номерами записывается значение блока зашифрованного текста. На рис. 4 проиллюстрирована процедура зашифрования в режиме простой замены с зацеплением. Для алгоритма «Кузнечик» параметр n равен 128, для алгоритма «Магма» параметр n равен 64. Данный режим, так же как и режим гаммирования, получил к настоящему моменту широкое практическое распространение и является составной частью ряда более сложных режимов шифрования, например режимов выработки имитовставки.

Процедура расшифрования в режиме простой замены с зацеплением заключается в расшифровании блоков зашифрованного текста и сложения полученного результата со значением n разрядов регистра сдвига R со старшими номерами. На рис. 5 проиллюстрирована процедура расшифрования в режиме простой замены с зацеплением.

Нетрудно видеть, что в режиме простой замены с зацеплением зашифрование каждого последующего блока открытого текста зависит от результата зашифрования предыдущего блока (синхропосылки). Однако если в режиме простой замены с зацеплением параметр m определить равным kn, то можно осуществить распараллеливание данного режима работы. На рис. 6 проиллюстрировано распараллеливание процедуры зашифрования в режиме простой замены с зацеплением при k = 2.

На указанной картинке желтым цветом выделен первый поток, красным цветом выделен второй поток.

Режим гаммирования с обратной связью по выходу (Output Feedback, OFB) и с обратной связью по шифртексту (Cipher Feedback, CFB)

Данные режимы работы являются достаточно специфическими вариантами режима гаммирования и в настоящее время редко используются, поэтому мы оставим их за рамками данной статьи. Отметим лишь, что определенные в стандарте варианты этих режимов работы алгоритмов блочного шифрования также поддаются распараллеливанию по аналогии с режимом простой замены с зацеплением.

Режим выработки имитовставки (Message Authentication Code Algorithm)

В мировой практике существует множество конструкций выработки имитовставки типа CBC-MAC, описанных в том числе в таких нормативных документах по стандартизации, как ISO/IEC 9797, FIPS 113, ANSI X9.9, ANSI X9.19. Для включения в новую версию национального стандарта была выбрана наиболее изученная к настоящему моменту конструкция OMAC1 (CMAC) [4], обладающая кроме этого высокими эксплуатационными характеристиками.

Более подробную информацию о режимах работы алгоритмов блочного шифрования можно найти на сайте Технического комитета по стандартизации «Криптографическая защита информации» (ТК 26): http://www.tc26.ru.

Процедура вычисления значения имитовставки похожа на процедуру зашифрования в режиме простой замены с зацеплением при m = n и инициализации начального заполнения регистра сдвига значением 0n: на вход алгоритма шифрования подается результат покомпонентного сложения очередного блока текста и результата зашифрования на предыдущем шаге. Основное отличие заключается в процедуре обработки последнего блока: на вход алгоритма блочного шифрования подается результат покомпонентного сложения последнего блока, результата зашифрования на предыдущем шаге и одного из производных ключей. Конкретный производный ключ выбирается в зависимости от того, является ли последний блок исходного сообщения полным или нет. Значением имитовставки является результат применения процедуры усечения к выходу алгоритма шифрования при обработке последнего блока. На рис. 7 проиллюстрирована процедура выработки имитовставки.

В настоящее время экспертами Технического комитета по стандартизации «Криптографическая защита информации» (ТК 26) проводятся работы по созданию методических рекомендаций, определяющих допустимые объемы материала для обработки на одном ключе при использовании некоторых вариантов режимов работы блочных шифров в соответствии с ГОСТ Р 34.13–2015.

Литература

ГОСТ Р 34.12–2015. «Информационная технология. Криптографическая защита информации. Блочные шифры».
ГОСТ Р 34.13–2015. «Информационная технология. Криптографическая защита информации. Режимы работы блочные шифров».
Бондаренко А., Маршалко Г., Шишкин В. ГОСТ Р 34.12–2015: чего ожидать от нового стандарта? // Information Security/Информационная безопасность. – 2015. – № 4. – С. 48–50.
ISO 9797-1:2011. Information technology – Security techniques – Message Authentication Codes (MACs) Part 1: Mechanisms using a block cipher.
ISO/IEC 10116:2006 Information technology – Security techniques – Modes of operation for an n-bit block cipher.
ГОСТ Р ИСО/МЭК 10116-93. Информационная технология. Режимы работы для алгоритма n-разрядного блочного шифрования.

Кузнечик (шифр) — Википедия. Что такое Кузнечик (шифр)

Блочный шифр «Кузнечик» (входит в стандарт ГОСТ Р 34.12-2015) — симметричный алгоритм блочного шифрования с размером блока 128 битов и длиной ключа 256 битов и использующий для генерации раундовых ключей сеть Фейстеля.

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

Обозначения

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

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

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

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

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

G(a)=γ(a15,{\displaystyle G(a)=\gamma (a_{15},}…,a0)||a15||{\displaystyle ,a_{0})||a_{15}||}…||a1.{\displaystyle ||a_{1}.}

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

F[k](a1,a0)=(HNAdd2[k](a1)⊕a0,a1).{\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)):

S′=(252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,233,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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 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,{\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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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,{\displaystyle 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).{\displaystyle 116,210,230,244,180,192,209,102,175,194,57,75,99,182).}

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

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

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

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

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

K1=k255||{\displaystyle K_{1}=k_{255}||}…||k128{\displaystyle ||k_{128}}

K2=k127||{\displaystyle K_{2}=k_{127}||}…||k0{\displaystyle ||k_{0}}

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

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

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

Пример^[5]

Таблица соответствия строк в двоичном и в шестнадцатеричном виде:

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{\displaystyle N(00112233445566778899aabbccddeeff)=fc7765aeeaoc9a7ee8d7387d88d86cb6}

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

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

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

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

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

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

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

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