Реализовал шифр “Кузнечик” на ассемблере, входящем в комплект компилятора языка Go. Ассемблерный вариант довольно простой и работает в 128-битных регистрах архитектуры amd64, это даёт большой прирост производительности.

“Кузнечик” из ГОСТ Р 34.12-2015 – это современный российский блочный симметричный шифр. Несколько лет назад я реализовал его на языке Go. Вариант на языке высокого уровня – не слишком быстро работает, поэтому я переписал шифр на ассемблере, для архитектуры x64/amd64. Использовал ассемблер (точнее – псевдоассемблер), встроенный в Go.

Новый вариант называется GOSThopper и использует 128-битную арифметику, доступную на современных процессорах с архитектурой x64 (далее я буду называть её amd64, именно такое обозначение использует компилятор Go). Основная идея оптимизации такая: написать быструю реализацию обработки блока в “длинных” регистрах процессора – шифр как раз использует 128-битный блок, так что разрядность хорошо подходит. В системе команд процессоров amd64 (точнее, в некотором расширении системы команд, но это детали, так как сейчас данное расширение доступно практически везде) – есть нужный набор “атомарных” инструментов: быстрая загрузка данных из памяти, XOR, сдвиги и произвольный доступ к байтам.

Тут необходимо напомнить, как операции шифра “Кузнечик” оптимизируются чисто алгебраически. Структура шифра такова, что все его преобразования можно предвычислить для значений отдельных байтов и хранить в довольно больших (64K) таблицах (если говорить строго, то это матрицы коэффициентов, но здесь я буду называть их просто таблицами). Аналогичная оптимизация известна для всех AES-подобных шифров.

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

Assembly code listing screen copy.

Краткие пояснения к алгоритму (с. 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, поэтому его лучше собирать в другой директории. Внутри файлов – много дополнительных пояснений (англ.).

Вопросы, пожелания – приветствуются в комментариях или по электронной почте.



Комментировать »

Про технологию ESNI (и SNI) я не так давно написал несколько записок. Сейчас ESNI находится в процессе внедрения, интересно взглянуть на эффект, который данная технология будет иметь для систем инспекции трафика и блокирования доступа. Современные системы используют SNI (а также, в продвинутых вариантах, TLS-сертификаты) для обнаружения имён узлов, с которыми пытается установить соединение пользователь. ESNI скрывает эти имена из SNI (TLS-сертификаты скрыты в новой версии TLS 1.3), причём, текущая версия ESNI использует для этого ключи, опубликованные в DNS.

То есть, особенность ESNI в том, что в качестве дополнительного источника ключей, защищающих метаинформацию, используется независимая от TLS система – DNS. Это важный момент: для того, чтобы зашифровать “адрес обращения”, клиенту не нужно устанавливать дополнительные соединения – получить нужный ключ можно типовым запросом к системе доменных имён; вообще говоря, не обязательно при этом указывать имя того TLS-узла, с которым будет соединяться клиент.

Провайдер хостинга может использовать ключи, опубликованные под одним DNS-именем, для обеспечения доступа к “скрытым серверам” под совсем другими именами, это означает, что открытый запрос в DNS не будет раскрывать имя “целевого узла”. Например, Cloudflare сейчас использует одни и те же ключи для самых разных веб-узлов. Более того, “скрытый узел” может находиться за некоторым “фронтэндом”, имеющим другое, универсальное, имя – фактически, это Domain Fronting.

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

В открытой DNS, системы анализа трафика, которые видят весь трафик клиента, могут сопоставить запрос в DNS для извлечения ключа ESNI и последующее TLS-соединение. DNS-ответ с ключами даже можно заблокировать, сделав использование ESNI невозможным (но только при условии, что ключи не были получены другим способом). Однако автоматическое корректное сопоставление имени из DNS-запроса и сессии TLS – представляют серьёзную дополнительную задачу, которая тем сложнее, чем больше объём трафика, анализируемого системой фильтрации. (Конечно, уже само наличие ESNI может являться признаком подозрительного соединения.)

То есть, ESNI, в случае массового внедрения, довольно заметно повлияет на ландшафт систем инспекции трафика. А кроме того, данная технология может подстегнуть рост распространённости DNSSEC и DNS-over-TLS. Впрочем, пока что ESNI не поддерживается распространёнными веб-серверами, да и соответствующий RFC не вышел из статуса черновика.

(Как работает ESNI – можно посмотреть на моём тестовом сервере TLS 1.3, там реализована поддержка.)



Комментарии (2) »

На днях NIST опубликовал результаты первого этапа программы по стандартизации постквантовых криптосистем (распределения ключей и электронной подписи), во второй раунд прошло 26 предложений из 82 поступивших на рассмотрение в самом начале (к первому этапу из них было допущено 69). Это повод очередной раз вспомнить о том, что постквантовые криптосистемы сейчас составляют одно из основных направлений современной криптографии. Постквантовые – это такие криптосистемы, которые устойчивы к взлому с использованием универсального квантового компьютера. Давно известно, что распространённые сейчас асимметричные криптосистемы (RSA, ECDSA, используемые разновидности протокола Диффи-Хеллмана) полностью уязвимы к атакам, использующим квантовые алгоритмы “нахождения периода”, это, в принципе, алгоритм Шора.

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

Скорее всего, на начальном этапе та или иная постквантовая криптосистема будет использоваться параллельно с классической. То есть, результаты обмена ключами по постквантовому алгоритму и по классическому будут смешиваться при генерации симметричных ключей, это обеспечит стойкость в том случае, если постквантовая криптосистема окажется уязвимой для классических атак (такие атаки вполне могут появиться раньше самого квантового компьютера). В браузере Chrome уже проводился эксперимент по использованию постквантовой криптосистемы New Hope.

Думаю, можно предположить, что приняты будут постквантовые криптосистемы, основанные на свойствах эллиптических кривых. Собственно, несколько лет назад я специально разместил на dxdt.ru краткую заметку, на которую можно сослаться, когда процесс выбора криптосистем, как говорится, сойдётся. Заметка даже специфицирует конкретное направление (изогении). Эллиптические кривые хорошо подходят потому, что, во-первых, они являют собой фундаментальную теоретико-числовую структуру, имеющую огромное чисто математическое значение; во-вторых, эллиптические кривые хорошо изучены внутри теоретической криптографии; в-третьих, для них наработано большое число библиотек и прикладных алгоритмов, которые, к тому же, тщательно проверены и оптимизированы. (Эти преимущества перечислены и в публикации NIST.)

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



Комментарии (3) »

Нередко приходится встречать картинки под собирательным названием “как видит мир кошка”. Каждая такая картинка подразумевает сравнение с тем, как видит мир человек. Казалось бы, огромный объём данных, пытающихся описывать природу визуального восприятия мира человеком, в том числе, данных “популярных”, типа различных иллюзий, должен сразу поставить любую подобную картинку под сомнение. Человеческое зрительное восприятие связано прежде всего с психикой и предыдущим опытом, только потом – с устройством глаза. Вспомните разные шумные цветовые иллюзии, вроде прений о том, “какого цвета платье на фотографии” или “параллельны ли улицы на этих снимках”. Набор иллюзий у условной кошки – не известен, и уже поэтому представить, как видит мир кошка, не имея опыта конкретной кошки, человеку невозможно.

Вспомните про эксперименты с призматическими очками. Известно, что человеческий глаз даёт перевёрнутое изображение. То, где у мира условный “верх” и условный “низ” – определяет предыдущий опыт. Если взрослому человеку надеть очки, которые переворачивают картинку ещё раз, делая изображение на сетчатке ориентированным “правильно”, то он тут же начинает видеть мир перевёрнутым и испытывает трудности с навигацией по этому миру. Но если очки не снимать, то через несколько дней мозг адаптируется и переворачивает картину мира вновь: проблемы с ориентацией исчезают; до тех пор, конечно, пока подопытный человек не снимет призматические очки. Казалось бы, в данном случае, можно хорошо представить, как видит мир человек в подобных очках: просто показываем перевёрнутую картинку. О реальном же эффекте можно судить только по описанию ощущений, которое даёт испытуемый, и модель с переворотом изображения оказывается весьма грубой. Так, если верить отчётами, у испытуемого возникают переходные периоды, когда изображение переворачивается туда-сюда в результате каких-то манипуляций в поле зрения, например, движений руки или проявления хорошо знакомого феномена: “вещи всегда падают вниз, если их отпустить”. (Этот эффект похож на многие зрительные иллюзии, когда, приложив некоторое мысленное усилие, можно “перевернуть” или “обратить” наблюдаемую картинку.) В общем, оказывается, что другому человеку даже тут представить что-то в деталях, не надевая призматические очки, весьма непросто, а уж тем более, нарисовать точную модель.

А кошка? Предположим, что мозг кошки ещё “подцепляет” к каждому визуальному образу акустическую картинку (у кошек особые уши), а также (например) температурный фон и движение потоков воздуха (вибриссы никто не отменял). Все эти параметры формируют опыт, человеку недоступный, но для кошки – создающий то самое зрительное восприятие мира. Конечно, можно возразить, что акустика, температура объектов, потоки воздуха – это всё не имеет отношения к зрению. Однако, если бы это было так, то и человек в призматических очках всегда видел бы мир перевёрнутым.



Комментарии (1) »

Внёс некоторые дополнения на сервер tls13.1d.pw. Во-первых, появилась поддержка “пересогласования” (renegotiation) параметров соединения. В TLS 1.3 есть отдельный механизм, который позволяет серверу запросить у клиента другие параметры протокола Диффи-Хеллмана, конечно, при условии, что клиент их поддерживает. Для этого сервер, в самом начале процесса установления соединения, отправляет сообщение HelloRetryRequest. (Технические подробности есть в описании TLS.) Я давно планировал дописать на сервер поддержку классического варианта протокола Диффи-Хеллмана (DH), который есть в Firefox. Так как по умолчанию браузеры используют эллиптический вариант, включение классического – как раз требует пересогласования параметров. То есть, чтобы заработал классический DH, нужно реализовать пересогласование.

Чуть ранее – я добавил поддержку ESNI. Так вот, в процессе отладки механизма пересогласования выяснилось, что в библиотеке NSS, которая используется Firefox, содержится ошибка в реализации механизма HelloRetryRequest, которая не позволяет использовать вместе с ним ESNI (про ошибку разработчикам я сообщил; вроде, планируют исправить). Так что теперь действие полезного механизма ESNI в Firefox можно наблюдать только в тех случаях, когда сервер не использует пересогласования: для этого нужно обновить страницу tls13.1d.pw несколько раз – группы DH на сервере выбираются псевдослучайным образом, так что, если выбор совпал с перечнем ключей браузера, присланных по умолчанию, то пересогласования не будет, а сработает ESNI.

Соответственно, во-вторых, – это и есть реализация классического DH. Его ещё называют “мультипликативным” вариантом, DH “в конечном поле” и так далее, а если говорить не слишком научно, то это алгоритм в арифметике остатков. Chrome/Chromium поддерживают только эллиптический вариант, соответственно, там увидеть классический никак не удастся. А вот в Firefox – можно. На сервере я реализовал только одну группу, зато самую “большую”: FFDHE3072. В предыдущих версиях TLS – сервер мог выбрать произвольную группу для классического DH, в версии TLS 1.3 список зафиксировали. Я некоторое время назад писал про то, как выбираются параметры для этих групп. По сравнению с эллиптическими вариантами, запись ключа FFDHE3072 – весьма длинная, 384 байта. Вот так результат выглядит на скриншоте:

FFDHE screen

В-третьих, добавил ограниченную поддержку TLS Cookies: она ограниченная потому, что соответствующее расширение передаётся сервером и принимается от клиента, но корректность его использования клиентом пока никак не проверяется. TLS Cookies – это инструмент, позволяющий серверу проверить, что клиент действительно отвечает и намеревается установить TLS-соединение. Особенно полезны, когда используется безсессионный транспорт, как в DTLS.

(Вообще, использование пересогласования может поломать какие-то другие библиотеки, поддерживающие TLS 1.3, но пока что я таких не обнаружил.)



Комментировать »
Навигация по запискам: