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

Из новостей

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

До конца 2020 года планируется закончить создание национального удостоверяющего центра структуры, которая будет выдавать сайтам вРунете отечественные цифровые сертификаты, пишет Медуза. Также, по данным этого издательства отечественные цифровые сертификаты будут использовать криптоалгоритмы Магма и Кузнечик. Кроме того, отечественные алгоритмы шифрования по требованию Центробанка станут обязательными к использованию в платежных системах уже с 2024 года, пишет РБК.

Добавим к этому новость от газеты Коммерсантъ, в которой Магма и Кузнечик упоминаются в контексте тестируемых алгоритмов для использования в виртуальных сим-картах eSim.

Упомянутые выше и другие основные алгоритмы, используемые в отечественной криптографии стандартизованы и описаны в ГОСТах.

Направления ГОСТов

Отечественная криптография базируется на четырех основных объектах, которые мы рассмотрим далее.

Цифровая подпись

ГОСТ 34.10-2018 описывает алгоритмы формирования и проверки электронной цифровой подписи с помощью операций в группе точек эллиптической кривой и функции хеширования. Длины секретного ключа 256 бит и 512 бит.

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

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

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

Суммой точек , эллиптической кривой называется точка , координаты которой определяются, как , , где .

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

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

Алгоритмы формирования и проверки электронной цифровой подписи.

Подпись создается по следующему алгоритму.

входные данные: сообщение и закрытый ключ подписи .

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

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

на основе случайно сгенерированного целого числа , это число называют секретным ключом. Затем вычисляется точка на эллиптической кривой . Точка имеет координаты .

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

выходные данные: цифровая подпись которую добавляют к сообщению.

Теперь перейдем к алгоритму проверки подписи.

входные данные: сообщение c цифровой подписью и ключ проверки подписи

полученная цифровая подпись проходит первичную проверку, если проверка не пройдена, то есть не выполнены неравенства , то подпись неверна.

вычисляется хеш-код сообщения , опять же с помощью алгоритма Стрибог.

определяется число , где целое число, которое соответсвует двоичному представлению хеш-кода . Причем если , то принимается за 1. Затем определяется .

вычисляется точка эллиптической кривой , из которой получается .

если , то подпись верна

выходные данные: подпись вена/неверна

Хеш-функция

ГОСТ 34.11-2018 посвящен функции хеширования. В данном документе содержится описание алгоритма вычисления хеш-функции, известной из предыдущих версий стандарта, как Стрибог.

Стрибог принимает на вход сообщение произвольной длины, которое впоследствии разбивается на блоки размером 512 бит(с дополнением блоков при необходимости). После чего входные данные преобразуются в хеш-код фиксированной длинны 256 или 512 бит.

Подробное описание алгоритма вместе с разбором используемых в нем преобразований можно найти в статье @NeverWalkAloner.

Шифры

ГОСТ 34.12-2018 охватывает блочные шифры. Именно в этом ГОСТе описаны алгоритмы шифрования Кузнечик и Магма алгоритмы блочного шифрования с длинами шифруемых блоков 128 бит и 64 бита соответсвенно и длиной ключа шифрования 256 бит у обоих.

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

Приведем упрощенную схему работы Кузнечика при зашифровании.

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

@sevastyan01 в своей статье подробно описал алгоритм Кузнечик.

Зашифрование блока Магмой проходит в 32 раунда, для каждого раунда из исходного ключа шифрования генерируется раундовый ключ, причем алгоритм генерации ключей отличается от генерации ключей в Кузнечике.

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

Режимы работы шифров

ГОСТ 34.13-2018 содержит описание следующих режимов работы блочных шифров.

Режим простой замены

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

Расшифрование происходит аналогичным образом. Причем если при зашифровании было применено дополнение, то при расшифровании применяется обратная операция.

Режим гаммирования

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

Схематично изобразим данный режим при зашифровании и расшифровании, они происходят аналогично друг другу.

Если общая длина гаммы не кратна длине блока, то последний блок гаммы усекается до размера блока. Блоки гаммы отличны друг от друга и имеют псевдослучайных характер.

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

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

Отличие режимов можно увидеть на схеме.

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

Режим простой замены с зацеплением

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

Режим выработки имитовставки

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

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

Интерес к таблице подстановок

Рассмотрим ГОСТ 34.10-2018. В алгоритмах формирования и проверки цифровой подписи на начальных шагах используется хеш-функция Стрибог, которая определена в ГОСТ 34.11-2018.

Заглянем теперь в ГОСТ 34.12-2018. В данном документе в качестве параметра алгоритма Кузнечик для нелинейного биективного преобразования приводится таблица подстановок

. Эта же таблица приведена в ГОСТ 34.11-2018, то есть используется и при хешировании.

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

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

Статьи с алгоритмами генерации таблицы :

Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 Alex Biryukov, L eo Perrin, and Aleksei Udovenko

Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog Lo Perrin and Aleksei Udovenko

Partitions in the S-Box of Streebog and Kuznyechik Lo Perrin

В конце каждой из статей приведены алгоритмы генерации таблицы подстановок, которые можно запустить в оригинальном виде с помощью SageMath.

Заключение

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

Данная статья написана в соавторстве с тимлидом @Restlin

Выбор кейса и наше видение его решения

Изначально выбор пал на кейс МВД: Разработка автономного программного решения лингвистического анализа и преобразования в тексте лица повествования.

Формулировка кейса:

Учитывая специфику деятельности определенных служб МВД России, при подготовке документов требуется преобразование в тексте лица повествования от первого лица в третье с учетом рода. Например, фраза в исходном тексте Я увидел, что Иванов пошёл ко мне в итоговом тексте должна быть преобразована в Он увидел, что Иванов пошёл к нему. Разработанное программное решение позволит в автоматическом режиме проводить процесс конвертации лица повествования, что позволит сотрудникам уделить больше времени на иные аспекты служебной деятельности. Кейс подготовлен Департаментом информационных технологий, связи и защиты информации МВД России.

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

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

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

1) локальное решение, работающее без доступа в сеть;

2) интегрированные офисные пакеты посредством макросов.

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

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

Формулировка кейса:

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

Почему он? У нас было понимание как работать с электронной подписью на Open source решениях: OpenSSL. Пригодился опыт Ильи в разработке СЭД - он знал о существовании php библиотеки tcpdf для генерации файла pdf с возможностью встроить электронную подпись. Плюс на текущем проекте pirs.online мы уже копали эту тему, и оттого данной задачей заниматься было приятно вдвойне.

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

Панические атаки и ведро валерьянки

В пятницу вечером мы остались в офисе, получили подробное техническое задание кейса и приступили к решению. Последнее вранье - мы начали неистово паниковать, так как в технических ограничениях к решению значилось требование в реализации на ASP.NET.

Написали в чат поддержки ЦП (хвала за неиссякаемое терпение Ирине с вопросом: что нам делать и можно ли сменить кейс? К счастью, организаторам удалось переубедить представителей Почты России снять это ограничение и только тогда мы смогли приступить к решению.

А что потом? Технические подробности

Дальше пошло по накатанной: первый чекпоинт и наши идеи по реализации, полученное одобрение экспертов и практически бессонная ночь работы.

Нам повезло: роли между командой у нас распределены четко, и каждый занимается своей задачей. Марина - презентация и вычитка спитча Ильи. Илья отвечает за спитч, архитектуру, бэк. Дима и Кирилл - фуллстеки.

С точки зрения технической реализации функционал прототипа выглядел просто:

• вход пользователя под одной из двух ролей: гость и администратор;

• формирование обращения администратору (почте РФ);

• рассмотрение обращения и формирование ответа;

• можно прикрепить файлы к обращению и ответу;

• создать сертификат пользователя в личном кабинете;

• подписать файлы ответа электронной подписью;

• выгрузить обращение с электронной подписью;

• проверить электронную подпись в обращении.

Структура базы данных прототипа уместилась всего в 3 таблицы, размещенных в PostgreSQL:

1. user - таблица пользователей с реквизитами и типами;

2. message - таблица обращений и ответов. По сути это переписка клиента и администратора;

3. file - таблица файлов, прикрепленных к обращениям и ответам.

Благодаря большому опыту команды с php-фреймворком Yii2 мы в короткие сроки разработали основной функционал приложения. А вот задача интеграции функционала по работе с электронными подписями была трудоемкой и нетривиальной.

Для работы с электронными подписями мы решили использовать OpenSSL, как открытый стандарт де-факто по работе с электронными подписями.

Как и ожидалось библиотека очень мощная, но из коробки не поддерживает отечественные алгоритмы шифрования. Какое-то время ушло на интеграцию и настройку криптографического движка (libengine-gost-openssl 1.1) на алгоритмы ГОСТ, в частности ГОСТ-2012. Затем мы создали и настроили удостоверяющий центр.

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

Пилим прототип дальше

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

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

Создание сертификата пользователя:

exec("openssl req -nodes -newkey gost2012_512 -keyout $eSignPath/client.key -pkeyopt paramset:A -out $eSignPath/client.csr -subj \"/C=RU/ST=Udm/L=Izhevsk/O=IT/OU=animals/CN=user-{$user->id}\" -config $caPath/openssl.cnf ");

exec("openssl ca -engine gost -keyfile $caPath/ca.key -cert $caPath/ca.crt -in $eSignPath/client.csr -out $eSignPath/client.crt -batch -config $caPath/openssl.cnf 2>&1", $output);

где $eSignPath - путь до папки с ключами пользователей, а $caPath - путь до папки удостоверяющего центра.

Удаление сертификата пользователя:

exec("openssl ca -config $caPath/openssl.cnf -keyfile $caPath/ca.key -cert $caPath/ca.crt -revoke $eSignPath/client.crt 2>&1", $output);

exec("openssl ca -gencrl -config $caPath/openssl.cnf -keyfile $caPath/ca.key -cert $caPath/ca.crt -out $caPath/crl.pem 2>&1", $output);

где $eSignPath - путь до папки с ключами пользователей, а $caPath - путь до папки удостоверяющего центра.

Подписание файла сертификатом пользователя:

exec("openssl smime -engine gost -sign -in $fp -out $fp.sig -nodetach -binary -signer $clientKeysPath/client.crt -inkey $clientKeysPath/client.key -outform SMIME 2>&1", $output);

где $fp - путь до файла, $clientKeysPath - путь до папки с ключами пользователя.

Проверка подписи файла:

$output = exec("openssl cms -engine gost -verify -in $sigPath -inform SMIME -CAfile $pathCA/ca.crt -out $fp -certsout $clientKeysPath/client.crt 2>&1");

где $fp - путь до файла, $clientKeysPath - путь до папки с ключами пользователя, $sigPath - путь до электронной подписи.

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

Появилась идея: Илья вспоминает, что в одной не самой популярной библиотеке tcpdf по формированию pdf файлов была возможность встраивания электронной подписи в pdf файл. А это значит, что можно из обращения создать pdf файл и сразу встроить в него электронную подпись.

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

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

$fields = [

'r' => 'api/sign',

'filePath' => $tempdoc,

'userId' => $user->id,

];

$query = http_build_query($fields);

$ch = curl_init();

$host = \Yii::$app->params['apiHost'] ?? '';

curl_setopt($ch, CURLOPT_URL, $host . '/index.php?' . $query);

curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);

$signature = curl_exec($ch);

/*if (empty($this->signature_data['extracerts'])) {

openssl_pkcs7_sign($tempdoc, $tempsign, $this->signature_data['signcert'], array($this->signature_data['privkey'], $this->signature_data['password']), array(), PKCS7_BINARY | PKCS7_DETACHED);

} else {

openssl_pkcs7_sign($tempdoc, $tempsign, $this->signature_data['signcert'], array($this->signature_data['privkey'], $this->signature_data['password']), array(), PKCS7_BINARY | PKCS7_DETACHED, $this->signature_data['extracerts']);

}*/

И все же мы успеваем в последний момент и к утру воскресенья прототип полностью работает!

Последний рывок и мы у цели

В середине дня воскресенья Илья подключается по Zoom к защите решения, жюри неумалимы, ну а мы ждем результатов.

Было страшновато: осознание, что ты соревнуешься с лучшими (в финал попали топ 5 команд из отборочных региональных туров) подстегивало выкладываться на полную.

Неожиданно результатов пришлось ждать до вечера, хотя на Северо-Западном хабе объявили победителей чуть ли не через час после защит. Время тянулось как доставка Почты России.

Офтоп: мы победители! 750 тысяч на команду, Карл! 750 за 2 дня, Карл! А значит едем на грандфинал Цифрового прорыва в Москву!

Репозиторий нашего решения