Шифр “Кузнечик” на языке Go: ассемблер и оптимизация
(Реализация шифра “Кузнечик”.)
(Дополнение от 02/01/2024: новая версия с поддержкой arm64.)
Реализовал шифр “Кузнечик” на ассемблере, входящем в комплект компилятора языка Go. Ассемблерный вариант довольно простой и работает в 128-битных регистрах архитектуры amd64, это даёт большой прирост производительности.
“Кузнечик” из ГОСТ Р 34.12-2015 – это современный российский блочный симметричный шифр. Несколько лет назад я реализовал его на языке Go. Вариант на языке высокого уровня – не слишком быстро работает, поэтому я переписал шифр на ассемблере, для архитектуры x64/amd64. Использовал ассемблер (точнее – псевдоассемблер), встроенный в Go.
Новый вариант называется GOSThopper и использует 128-битную арифметику, доступную на современных процессорах с архитектурой x64 (далее я буду называть её amd64, именно такое обозначение использует компилятор Go). Основная идея оптимизации такая: написать быструю реализацию обработки блока в “длинных” регистрах процессора – шифр как раз использует 128-битный блок, так что разрядность хорошо подходит. В системе команд процессоров amd64 (точнее, в некотором расширении системы команд, но это детали, так как сейчас данное расширение доступно практически везде) – есть нужный набор “атомарных” инструментов: быстрая загрузка данных из памяти, XOR, сдвиги и произвольный доступ к байтам.
Тут необходимо напомнить, как операции шифра “Кузнечик” оптимизируются чисто алгебраически. Структура шифра такова, что все его преобразования можно предвычислить для значений отдельных байтов и хранить в довольно больших (64K) таблицах (если говорить строго, то это матрицы коэффициентов, но здесь я буду называть их просто таблицами). Аналогичная оптимизация известна для всех AES-подобных шифров.
После того, как таблицы подготовлены и загружены в память – работа алгоритма, реализующего шифр, сводится к выбору элементов из таблицы и сложению этих элементов при помощи операции XOR. То, какой элемент таблицы использовать, определяется значениями текущего байта входного текста, ключа и номером раунда. Элементы в таблицах – 128-битные, совпадающие по длине с блоком. То есть, при должной сноровке, алгоритм становится очень быстрым. Особенно сильно можно ускориться, если использовать регистровую арифметику подходящей разрядности, что я и попытался сделать. Ссылки на полные исходные тексты даны в конце записки. Но, фактически, весь ассемблерный код сводится к фрагменту, представленному на скриншоте (синтаксис у ассемблера Go своеобразный).
Краткие пояснения к алгоритму (с. 19-33): выполняем сложение блока (PXOR) с ключом текущего раунда, результат помещаем в регистр X0 (так обозначаются 128-битные регистры XMMn); извлекаем младший (под нулевым номером) байт длинного регистра (PEXTRB), умножаем его на 16 (SHLQ) и складываем (ADD) с базовым адресом таблицы (он ранее загружен в регистр DX); полученное смещение (оно находится в регистре AX) теперь указывает на нужный элемент таблицы предвычисленных значений, извлекаем этот элемент и суммируем с предыдущим (PXOR со значением в X2, первый элемент последовательности просто записывается в X2 – с. 25). Написано “в лоб”, нет дополнительных проверок валидности адресов и размеров массивов (предполагается, что эти параметры контролируются снаружи данной процедуры).
Ассемблерный код выполняет только преобразование блока, а вычисление таблиц, разворачивание ключей – всё это осталось в коде на Go.
Итак, новая реализация в несколько раз быстрее предыдущих. Простой тест на процессоре Intel i5-9600K показывает скорость около 180 мегабайт в секунду для зашифрования и около 140 Мбайт/сек для расшифрования (процедура расшифрования существенно отличается от зашифрования, использует дополнительную таблицу, а кроме того, я её совсем не оптимизировал, потому что для основных современных режимов использования блочных шифров процедура расшифрования не нужна). Так или иначе, 180 мегабайт – это неплохой результат. Предыдущая версия, только на Go, но с unsafe-конструкциями, показывает на том же процессоре лишь около 45 Мбайт/сек. На небольших массивах данных – скорость ассемблерной версии ещё заметно возрастает, поскольку процессор эффективно использует кэш-память.
Как я уже не раз упомянул, это ассемблер архитектуры amd64, поэтому на других платформах, например, на различных ARM, данный ассемблерный код использовать не получится. Так что пришлось дополнить модуль “заглушками”, а точнее – реализациями шифра на “чистом Go”. Компилятор Go позволяет прозрачно генерировать межплатформенный код, для этого используются специальные директивы, в данном случае: // +build !amd64. Другими словами, в файле с исходным кодом, предназначенным для всех платформ, кроме amd64, указывается директива “// +build !amd64”, а для amd64 – код выносится в файлы с постфиксом _amd64. (Конкретно: docipher_amd64.go – содержит объявления функций; docipher_amd64.s – код на ассемблере.) Соответственно, данный модуль успешно компилируется на разных платформах, я проверил на ARM. Однако скорость работы на платформах, отличных от amd64, будет ниже на порядки (в сто раз и даже более) – это связано с тем, что используется простая реализация шифра (файл docipher.go). Но amd64 – более чем распространённая архитектура, поэтому новый быстрый шифр может оказаться полезен. (Не исключено, кстати, что возможны весьма экзотические конфигурации, когда платформа amd64 не содержит каких-то “длинных” команд, но это нужно проверять отдельно.)
Нередко спрашивают: как простым способом использовать реализацию шифра для обработки некоторого потока данных? Понятно, что непосредственно шифр применять нельзя, нужна некая обёртка, называемая “режимом использования шифра“. Для упрощения реализации примеров “из жизни” я добавил в модуль пару простых функций, реализующих зашифрование и расшифрование в режиме счётчика (CM_Encrypt(), CM_Decrypt()). Это готовый инструмент для работы с потоком данных: то есть, в качестве аргументов функции передаются вектор инициализации, ключ и слайс (массив) данных; функция возвращает обработанный слайс той же длины. Важное замечание: конкретный вектор инициализации нельзя повторно использовать для зашифрования с одним и тем же ключом; учитывайте и тот факт, что начальное значение увеличивается внутри процедуры на единицу с каждым обработанным блоком (см. исходный код).
В реализации режима счётчика нет аутентификации (это важно!). Для аутентифицированного варианта можно использовать штатный режим GCM из Go-пакета crypto/cipher. В модуле есть нужный интерфейс, поэтому шифр элементарно подключается к GCM. Примеры есть в исходном коде, а краткое описание дано ниже.
Тут необходима ещё одна оговорка: “Кузнечик” не стандартизован для применения в режиме GCM. В российских криптографических ГОСТах пока что вообще нет аналогичного режима (AEAD), но, вероятно, он вскоре появится, и это, конечно, будет не GCM, а вариант разработанного российскими специалистами режима, который сейчас называется MGM (Multilinear Galois Mode).
Логика использования в режиме счётчика:
CM_CipherText := gosthopper.CM_Encrypt(0x1234567, Key, SourceText)
[...]
CM_PlainText := gosthopper.CM_Decrypt(0x1234567, Key, CM_CipherText)
(Здесь 0x1234567 – это вектор инициализации, начальное значение счётчика, собственно говоря. Данное значение использовано для примера, оно не является секретным, но, повторюсь, нельзя повторно использовать одно значение с тем же ключом. Важно учитывать, что значение счётчика увеличивается с каждым блоком на единицу внутри процедуры, поэтому для нового вызова с тем же ключом – начальное значение тоже должно увеличиться, как минимум, на число_блоков + 1, иначе возникнет повтор. То есть, данные функции являются только демонстраторами общего принципа, а управление инциализацией режима счётчика представляет отдельную задачу.)
Логика в режиме GCM (import “crypto/cipher”; AD – дополнительные данные, которые передаются в открытом виде):
kCipher, err := gosthopper.NewCipher(Key)
[...]
kuznecGCM, err := cipher.NewGCM(kCipher)
[...]
GCM_sealed := kuznecGCM.Seal(nil, GCM_nonce, PT, AD)
[...]
GCM_opened, err := kuznecGCM.Open(nil, GCM_nonce, GCM_sealed, AD)
Режим GCM в пакете crypto/cipher реализован полностью, но тоже требует инициализации (GCM_nonce). В целом, GCM является более совершенным режимом, чем простой режим счётчика (собственно, GCM – это улучшенная разновидность режима счётчика).
(Обычное напоминание: я, по возможности, всё проверил, но это всего лишь экспериментальная реализация, поэтому какого-то серьёзного исследования кода этого модуля не проводилось, так что там, во-первых, могут быть ошибки; во-вторых – точно нет целого ряда вспомогательных механизмов, обеспечивающих защиту ключей в памяти и т.д., и т.п.)
Исходный код:
основной файл – gosthopper.go;
реализация шифра на ассемблере – docipher_amd64.s;
объявления функций – docipher_amd64.go;
реализация только на Go для платформ, отличных от amd64 – docipher.go.
Всё вместе в одном архиве: gosthopper1.tar.gz.
Подробные примеры использования и тесты: test_gosthopper.go
Пакет называется gosthopper. Для того, чтобы его использовать, нужно тем или иным способом разместить (например, просто скопировать) файлы с исходными кодами в директорию пакетов вашей инсталляции Go. (См. переменную окружения GOPATH.) Файл test_gosthopper.go относится к пакету main, поэтому его лучше собирать в другой директории. Внутри файлов – много дополнительных пояснений (англ.).
Вопросы, пожелания – приветствуются в комментариях или по электронной почте.
Адрес записки: https://dxdt.ru/2019/02/18/8702/
Похожие записки:
- "Двухфакторная" аутентификация и Google Authenticator
- DARPA и "недетерминированные" системы на борту
- DNSSEC и DoS-атаки
- Статья про защиту DNS-доступа
- Компиляторы в песочницах и сравнение программ
- Зрение ИИ LLM на скриншотах
- Реплика: алгоритм Шора
- Помехи GNSS и распределённые "геосервисы"
- Stack Overflow и OpenAI
- Реплика: перемешивающие сети Google и фильтрация
- Техническое: poison-расширение и SCT-метки в Certificate Transparency
Комментарии читателей блога: 4
1 <t> // 7th December 2020, 14:27 // Читатель jno написал:
https://www.amd.com/system/files/TechDocs/43479.pdf
Support for the new instructions is indicated by use of the CPUID instruction:
1. XOP—ECX bit 11 as returned by CPUID function 8000_0001h.
2. FMA4—ECX bit 16 as returned by CPUID function 8000_0001h
2 <t> // 21st May 2024, 18:48 // Читатель anon написал:
Пропишите, пожалуйста, явную лицензию (хотелось бы BSD/MIT/ISC), а то “дистрибьюшен унилимитед” введёт людей (юристов) в заблуждение при вставке кода в любой серьёзный проект.
3 <t> // 21st May 2024, 21:07 // Александр Венедюхин:
Попробую что-нибудь добавить. Например, Public Domain.
4 <t> // 22nd May 2024, 21:11 // Читатель anon написал:
public domain имеет свои проблемы (юристы его не любят), его не всегда можно использовать в открытых\закрытых проектах, если цель – разрешить распространение и в исходниках, и в бинарной форме – лучше явно указать BSD/MIT/ISC – так и юристы будут довольны и вы получите заслуженные credits – мало ли что
Написать комментарий