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

 

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

Автор: admin от 11-10-2016, 21:35, посмотрело: 152

На Хабре уже как минимум дважды упоминался новый отечественный стандарт блочного шифрования ГОСТ Р 34.12 2015 «Кузнечик», ru_crypt в своем посте рассмотрел основные механизмы и преобразования нового стандарта, а sebastian_mg занимался пошаговой трассировкой базового преобразования. Но многие вопросы остались без ответа. Насколько быстр новый ГОСТ? Можно ли его оптимизировать, эффективно реализовать, ускорить аппаратно?


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


О стандарте ГОСТ Р 34.12 '15


Приказом от 19 июня 2015 года №749 в качестве нового стандарта блочного шифрования утвержден ГОСТ Р 34.12 2015. Стандарт разработан Центром защиты информации и специальной связи ФСБ России с участием ОАО «ИнфоТеКС», внесен Техническим комитетом по стандартизации ТК 26 «Криптографическая защита информации», и вступил в действие с 1 января 2016 года.


Официальное pdf-издание стандарта качаем здесь, а эталонную реализацию — здесь (обе ссылки ведут на официальный сайт ТК 26).


Этот стандарт содержит описания двух блочных шифров: «Магмы» с длиной блока в 64 бита и «Кузнечика» с длиной блока в 128 бит; при этом «Магма» — всего лишь новое название для старого, всем хорошо известного блочного шифра ГОСТ 28147 '89 (на самом деле, не совсем новое, именно под этим кодовым названием разрабатывался прежний стандарт блочного шифрования вплоть до 1994 года) с зафиксированными узлами замены. «Наконец–то, история нас чему–то научила», — скажете вы, и будете правы.


В этой статье пойдет речь про другой шифр, имеющий длину блока 128 бит, и носящий кодовое имя «Кузнечик». По городской ленде, имя шифра вовсе не связано с зеленым насекомым, а образовано первыми слогами фамилий авторов этого шифра: Кузьмин, Нечаев и компания.


Описание «Кузнечика»


Отличия «Кузнечика» от «Магмы»


Новый шифр существенно отличается от старого, среди его основных достоинств можно выделить



  • вдвое увеличенную длину блока (128 бит, или 16 байт, против 64 бит, или 8 байт),

  • нетривиальное ключевое расписание (сеть Фейстеля как ключевое расписание против использования частей секретного ключа в качестве цикловых ключей),

  • сокращенное число циклов (10 циклов против 32 циклов),

  • принципиально иное устройство самого шифра (LSX-шифр против сети Фейстеля).


Базовое преобразование


Шифр принадлежит к классу LSX-шифров: его базовое преобразование (функция шифрования блока) представляется десятью циклами последовательных преобразований L (линейное преобразование), S (подстановка) и X (смешивание с цикловым ключом):


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

[i]Полный цикл базового преобразования[/i]


Алгебраически шифртекст C зависит от открытого текста P следующим образом:


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


то есть за девятью полными циклами следует последний неполный (только смешивание с ключом). Преобразование X смешивает промежуточный текст очередного цикла с соответствующим цикловым ключом простым сложением по модулю 2:


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

Преобразование S применяет одну и ту же фиксированную подстановку ГОСТ Р 34.12 '15 на SSE2, или Не так уж и плох Кузнечик к каждому байту промежуточного текста:


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


Преобразование L представимо линейной формой над полем GF(256), построенным с помощью неприводимого многочлена


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


и сводится к умножению вектора–строки промежуточного текста на некоторую матрицу над этим полем (каждый байт текста и матрицы является многочленом поля, представленным своими коэффициентами):


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




Ключевое расписание


Действительно, многие ошибки, допущенные при разработке старшего шифра, были исправлены, в том числе уязвимое ключевое расписание. Напомню читателю, что в шифре ГОСТ 28147 '89 в качестве цикловых ключей использовались восемь 32-битных частей 256-битного секретного ключа в прямом порядке на циклах шифрования с первого по восьмой, с девятого по шестнадцатый, с семнадцатого по двадцать четвертый; и в обратном порядке на циклах с двадцать пятого по тридцать второй:


K_0, K_1, dots, K_6, K_7, K_0, K_1, dots, K_6, K_7, K_0, K_1, dots, K_6, K_7, K_7, K_6, dots, K_1, K_0.


И именно такое слабое ключевое расписание позволило осуществить атаку с отражением на полный ГОСТ, снизив его стойкость с 256 бит до 225 бит (при любых узлах замены, с 2^32 материала на одном ключе; почитать про эту атаку можно здесь).


В новом стандарте выработка цикловых ключей осуществляется по схеме Фейстеля, при этом первыми двумя цикловыми ключами являются половины 256-битного секретного ключа, а каждая следующая пара цикловых ключей получается в результате применения восьми циклов преобразования Фейстеля к предыдущей паре цикловых ключей, где в качестве цикловой функции используется то же LSX преобразование, что и в базовом преобразовании, а в качестве цикловых ключей в схеме используется фиксированный набор констант:


left( K_{2i + 1}, K_{2i + 2} right) = F^8 left( K_{2i - 1}, K_{2i} right); text{ где } F left( x, y right) = left( LSX_i(y) oplus x, y right).




Устройство узла замены


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


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

[i]Слой подстановок, S-преобразование[/i]



Однако, все тайное рано, или поздно, становится явным, и способ выбора узла замены не исключение. Команде криптографов из Люксембурга, возглавляемой Алексом Бирюковым, удалось обнаружить определенного рода закономерности в статистических характеристиках узла замены, что, в свою очередь, позволило им восстановить способ его получения. Подробнее об этом способе можно почитать в их статье, опубликованной на iacr.org.


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

[i]Секретная структура узла замены[/i]


Алгоритмическая оптимизация


Команде исследователей из ОАО «ИнфоТеКС», а конкретно Михаилу Бородину и Андрею Рыбкину, удалось позаимствовать алгоритмическую оптимизацию умножения вектора на столбец у скоростных реализаций шифра AES (Rijndael), которая позволяет заменить классическую реализацию умножения за O(n^2) умножений в поле на O(n) сложений по модулю два векторов длины O(n) с использованием предвычисленных таблиц, и о которой было доложено на конференции РусКрипто, если мне не изменяет память, в 2014 году.


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


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


на матрицу A


A = begin{pmatrix} a_{0, 0} & a_{0, 1} & cdots & a_{0, n-1} a_{1, 0} & a_{1, 1} & cdots & a_{1, n-1} vdots & vdots & ddots & vdots a_{n-1, 0} & a_{n-1, 1} & cdots & a_{n-1, n-1} end{pmatrix}_{n times n} in left( GF(256) right)^{n times n}


получился вектор V:


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


Традиционный способ вычисления компонент этого вектора заключается в последовательном скалярном умножении строки вектора U на столбцы матрицы A:


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


Вычисление каждой из n компонент вектора V подразумевает n операций умножения в поле и n-1 операцию сложения по модулю 2, так трудоемкость вычисления всех компонент составляет O(n^2). Да, конечно, можно не умножать в поле каждый раз, можно заранее вычислить таблицы логарифма и экспоненты; можно даже заранее вычислить произведения всех возможных байт на элементы матрицы (матрица ведь фиксирована и не меняется в процессе шифрования), и хранить ~256 таблиц по 256 байт-произведений. В матрице есть одинаковые элементы? Отлично, число таблиц можно сократить, но асимптотическая сложность не изменится.


А можно пойти другим путем. Вместо того, чтобы вычислять каждую компоненту вектора-произведения как сумму n однобайтовых прозведений, воспользуемся особенностью умножения вектора на матрицу и будем вычислять сразу все компоненты вектора как сумму n векторов:


V = left( bigoplus_j m_j a_{j, 0}, bigoplus_j m_j a_{j, 1}, dots, bigoplus_j m_j a_{j, n-1} right) = bigoplus_j m_j left( a_{j, 0}, a_{j, 1}, dots, a_{j, n-1} right).


Казалось бы, что изменилось? Те же операции, но в другом порядке. Замечу, однако, что, во-первых, повысилась разрядность слагаемых с одного байта до n байт, и такие суммы можно (и нужно) вычислять в длинных регистрах, а, во-вторых, каждое слагаемое является покомпонентным произведением одного (!) байта вектора на фиксированную строку матрицу.


Вот здесь поподробнее: можно заранее вычислить произведения вида


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


то есть умножить известную строку i матрицы A на все возможные значения байта i вектора U, и вместо умножения очередного байта на эту строку просто считывать произведение из таблицы. Тогда умножение вектора на матрицу сводится к считыванию n строк-произведений из заранее вычисленной таблицы и побитовое сложение этих строк для получения результирующего вектора V. Вот так, достаточно просто, можно сильно упростить умножение вектора на матрицу до O(n), если сложение векторов считать элементарными операциями.


В случае ГОСТ Р 34.12 '15 n = 16, так, вектора имеют длины в 16 байт, или 128 бит, и очень здорово помещаются в длинные XMM регистры, а для их сложения предусмотрены дополнительные процессорные инструкции, например, pxor.


Все очень здорово, но как быть с узлом замены? Читатель наверняка заметит, что при наличии побайтовых узлов замены, которые в общем случае не векторизуются, все алгоритмические прелести такого вычисления L-преобразования нивелируются стоимостью загрузки векторов в регистры до преобразования и их выгрузки после преобразования. Хороший вопрос.


Хороший, и очень изящно решаемый. Оказывается, узлы замены можно просто «склеить» с L-преобразованием, заменив вычисляемые заранее строки произведения с


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


на


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


Тогда один полный цикл шифрования сводится к



  • смешиванию с ключом (pxor),

  • применению склеенного преобразования LS (в наилучшем случае это 16 загрузок 128-битных векторов из кэша и 15 сложений pxor).


Конечно, такие оптимизации не бесплатны, для их использования потребуется, во-первых, вычислить и хранить в кэше единовременну одну из двух таблиц со строками-произведениями, каждая из которых содержит 256 * 16 * 16 байт, или 64 КБ. Почему таблиц две? Потому что обратное преобразование, используемое при расшифровании, потребует умножения на обратную к L матрицу, и повлечет за собой новые произведения.


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


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


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


Замечу, что композиция преобразований


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


тождественна композиции


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


в силу линейности преобразования L. Тогда расшифрование можно осуществить следующим образом:


P = X_{K_0} S^{-1} circ left( X_{L^{-1} (K_1)} L^{-1} S^{-1} right) circ dots circ left( X_{L^{-1} (K_8)} L^{-1} S^{-1} right) circ X_{L^{-1} (K_9)} L^{-1} S^{-1} S (C)


Здесь каждое из преобразований, обратных к SL, можно осуществлять по схеме, аналогичной к рассмотренной. Вычисленные таблицы строк-произведений постить не буду, — они слишком большие даже для спойлеров; их можно найти, например, здесь.


Оптимизация с использованием SSE2


В принципе, с базовыми преобразованиями все понятно, осталось все эти оптимизации положить на asm.
Для работы с блоками предлагаю использовать набор инструкций SSE2, будем использовать инструкции movdqu и movdqa для загрузки и выгрузки данных в регистры, инструкции pxor, pand, pandn для булевых операций, инструкции psrlw и psllw для побитовых сдвигов, pextrw для выгрузки байт регистра.


Да, есть еще одна тонкость реализации ГОСТ Р 34.12 '15. Кроме общеалгоритмических оптимизаций вроде описанных выше, для дальнейшего ускорения производительности нужно учитывать особенности ассемблера и особенности планировщика, который инструкции может поставить на параллельное исполнение на разных исполняющих устройствах.


Учет особенностей адресной арифметики


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


pextrb  xmmX,  eax, i                  ; выделение байта i (SSE 4.1) в 32--битный регистр eax
movzxd  rcx,   eax                     ; перемещение выделенного байта в 64--битный регистр rcx
add     rcx,   rcx                     ; удвоение значения байта
pxor    xmmY,  [rbx + 8*rcx + 0xi000]  ; вычисление смещения по таблице

В регистрах при этом хранятся:



  • rbx содержит адрес базового смещения таблицы,

  • xmmX содержит входной блок,

  • xmmY содержит выходной блок (аккумулятор, сумму),

  • eax и rcx используются для выделения и удвоения байта смещения.


Следует иметь в виду, что предвычисленная таблица устроена следующим образом:


uint8_t table[16][256][16],

то есть значения строк-произведений хранятся в этой таблице непрерывно, друг за другом, внешний индекс i соответствует i-ой строке матрице L-преобразования, средний индекс j равен i-ому байту входного блока, а внутренний индекс k соответствует индексу байта очередного слагаемого:


Xi = table[i][input[i]][0] ... [16]

Таким образом, адрес первого байта очередного слагаемого Xi выражается следующим образом:


[Xi] = rbx + (0x1000 * i) + (16 * input[i]),

где



  • (0x1000 * i) соответсвует смещению текущей строки (table[i]),

  • (16 * input[i]) соответсвует смещению текущего слагаемого Xi (table[i][input[i]]).


Так, значение текущего байта приходится умножать на 16, но адресная арифметика позволяет использовать максимальное значение коэффициента-множителя равное восьми. Поэтому компилятору приходится перекладывать значение байта в rcx, удваивать его, и только затем вычислять адрес Xi.


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


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

[i]Предварительное вычисление приведенных смещений (слагаемые в адресе очередного Xi)[/i]


Здесь числами 0..15 обозначены соответствующие байты входного блока, а 00 и FF соответствуют нулевому байту и его инверсии.


С помощью маски 00FF 00FF 00FF 00FF 00FF 00FF 00FF 00FF и инструкций pand и pandn четные и нечетные байты входного блока выделяются в регистры левых и правых смещений соответственно; затем c помощью инструкций psrlw и psllw смещения приводятся (домножаются на 16) к значениям, пригодным для использования в адресной арифметике.
Так, каждое L-преобразование дополняется следующими строками:


pand    xmmR,  xmmZ                    ; выделение правых смещений
pandn   xmmL,  xmmZ                    ; выделение левых смещений
psllw   xmmR,  4                       ; приведение правых смещений
psrlw   xmmL,  4                       ; приведение левых смещений

и предварительной загрузкой маски в регистр xmmZ. Зато вычисление адресов слагаемых Xi теперь может быть осуществлено всего за две инструкции:


pextrw  eax,   i                       ; выделение приведенного смещения i
pxor    xmmY,  [rbx + rax + 0xi000]    ; вычисление смещения по таблице с помощью адресной арифметики

Учет специфики микроархитектуры


Большинство современных процессоров Intel и AMD имеют два, или более, исполняющих АЛУ, способных одновременно производить арифметические действия с различными регистрами, и планировщик, способный распределить блок выполняемых инструкций по различным АЛУ для параллельного выполнения с целью экономии процессорного времени.


Так, чередуя команды, использующие различные регистры, можно помочь процессору выполнять код параллельно. Склеенное LS-преобразование является двоичной суммой шестнадцати различных 128-битных чисел Xi, и, скорее всего, на современных процессорах может быть осуществлена в два параллельных потока (на одном ядре) с использованием двух аккумуляторов: левого и правого кэшей.



Заключение


Все описанные техники ускорения базового преобразования позволяют существенно повысить производительность шифра; в качестве конкретного примера могу привести числа, полученные на одном ядре Intel Core i7-2677M Sandy Bridge @ 1.80 GHz, это 120 МБ/с в версии с SSE инструкциями против 1.3 МБ/с в неоптимизированной версии.


Дальше — больше, ГОСТу можно придать дополнительное ускорение:



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

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


Поиграть с различными реализациями базового преобразования ГОСТ Р 34.12 '15 можно, собрав у себя этот проект. Написан он на C99, на совершенство кода и абсолютную оптимальность он не претендует, но автор будет рад любой конструктивной критике. Для сборки потребуется CMake 3.2.1+ и компилятор, поддерживающий C99. Шифр реализован в трех версиях, по стандарту без существенных оптимизаций (compact), с предвычислениями, но без SIMD инструкций (optimised) и с использованием инструкций SSE2 (SIMD).


Непосредственные шаги сборки можно посмотреть в скрипте Travis CI в корне проекта, в комплект входят модульные тесты на контрольные примеры из стандарта (ключевое расписание, шифрование и расшифрование блока) на CTest и примитивный способ измерять производительность с использованием std::chrono на C++11.



Источник: Хабрахабр

Категория: Информационная безопасность » Криптография

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *