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

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



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

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

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

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

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

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



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

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

Эти квантовые методы должны использовать какие-то свойства взламываемого шифра, которые хорошо проецируются именно на возможности квантовых вычислений. Пример. Предположим, что для для заданного шифра можно построить некоторую периодическую функцию, разбивающую всё пространство ключей на интервалы. Период этой функции может эффективно определить квантовый компьютер (это типичная задача, так, на поиске периода основан квантовый алгоритм Шора факторизации чисел). Знание периода позволяет путём анализа нескольких пар, состоящих из открытого текста и соответствующего ему шифротекста, определить, в какой именно из интервалов попадает секретный ключ, а дальше уже перебирать значения только из этого интервала, который, предположим, невелик. (Можно переформулировать: пусть обнаруживается период функции, определяющей возможные ключи – в таком случае, зная период, можно будет проверить только их, прыгая по значениям.) Пары открытых текстов и шифротекстов часто известны на практике. Скажем, HTTPS, использующий TLS в качестве транспорта, подразумевает передачу куки-файлов или известных заголовков запросов. При этом режим счётчика (GCM и пр.) основан на зашифровании последовательных значений. Это грубое изложение, но оно математически сходно с атаками, которые уже несколько лет обсуждаются в публикациях, применительно к различным режимам симметричных шифров.

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



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

В криптографической библиотеке для Arduino используется российский шифр “Магма” (ГОСТ 34.12-2015). Я сравнил свою реализацию “Магмы” из библиотеки с другим “малым” шифром – Speck, который был предложен в 2013 году специалистами АНБ. Чтобы сравнение было точнее, я также реализовал Speck, использовав inline-ассемблер (ссылка на исходный код – в конце записки).

Прежде всего – краткое описание шифра Speck. Это новый блочный шифр, специально разработанный для программной реализации в микроконтроллерах, то есть, вычислителях с сильно ограниченными ресурсами. Как и многие другие современные шифры (а также и “Магма”), Speck построен на базе простой “раундовой” функции, которая последовательно вызывается с разными ключами, проводя преобразование блока данных. В Speck эта же функция используется для разворачивания основного ключа в последовательность ключей раундов. Это первое существенное отличие от “Магмы”, в котором разворачивание ключа сводится к копированию (см. описание “Магмы”). Спецификация Speck вводит несколько вариантов шифра, имеющих разную разрядность блока и ключа. Я использовал наиболее близкий к “Магме” вариант: 64-битный блок и 128-битный ключ (256-битного, по ключу, варианта Speck для 64-битного блока – нет, поэтому сравнить шифры на одной длине ключа нельзя). От варианта к варианту в Speck различаются количество раундов и часть параметров раундовой функции (разрядность логических сдвигов).

На картинке ниже – подробная схема раунда Speck (шифрование).

Входной блок разбивается на две части. Это, опять же, одно из распространённых и хорошо проверенных решений в схемах шифров. Левая часть (A1 на схеме) циклически сдвигается вправо на 8 разрядов, суммируется с правой частью (A0) по модулю 232 (то есть, как два 32-разрядных числа “естественным образом”, без переноса и знака; операция обозначена символом ⊞). На следующем шаге выполняется сложение по модулю 2 (XOR, ⊕) с раундовым ключом. После чего результат обработки полублока суммируется (опять же, XOR) со вторым полублоком, который перед этим циклически сдвигается на три разряда влево.

В шифре “Магма” используется схема Фейстеля, в которой полублоки, после применения раундовых преобразований, переставляются. Раунд шифра Speck также можно привести к схеме Фейстеля, разделив на два этапа. Первый этап включает преобразования левой части, за которыми следует перестановка полублоков. Схема:

Второй этап – состоит в применении сдвига и XOR к результату первого этапа. Схема:

То есть, с некоторой долей условности можно сказать, что Speck построен из двух, применяемых последовательно, конструкций Фейстеля.

Раунды выполняются циклически. Для используемого варианта шифра число повторений равняется 27. Таким образом, требуется 27 раундовых ключей, каждый разрядностью 32 бита. Схема их получения из исходного, 128-битного, ключа состоит в последовательном применении той же раундовой функции к ключу, предварительно разбитому на слова, разрядность которых совпадает с разрядностью полублока. То есть, 128-битный ключ (16 байтов) даёт нам четыре слова по 32 бита. Эти слова служат левым и правым полублоком в раундовой функции. Ключом (Ki на схеме) при этом является номер раунда. Другими словами: первый раундовый ключ – это младшие 32 бита исходного, основного ключа (используются прямо). Второй раундовый ключ – младшие 32-бита результата применения раундовой функции к младшим 64 битам основного ключа (очевидно, что сюда, в качестве правого полублока, входит первый раундовый ключ); и так далее, подробнее можно посмотреть в исходном коде.

Переходим к сравнению шифров. Ассемблерная реализация позволяет посчитать примерное число тактов, необходимых для выполнения преобразований шифра. Для Speck подсчёт дал 1951 такт – столько занимает полная реализация, с обращением к памяти, где хранятся раундовые ключи и блок открытого текста, с выгрузкой результата. Сюда не входит код получения последовательности раундовых ключей (развёртывания ключа). 1951 такт, в пересчёте на байт данных (блок состоит из 8 байтов), даёт: 1951/8 = 244 такта на байт (приблизительно). В исходной работе, со спецификацией Speck, авторы приводят результат от 118 до 160 тактов для аналогичного 8-разрядного микроконтроллера, но здесь не учитываются операции по загрузке/выгрузке блоков, так что результаты довольно близки (кроме того, мой вариант можно оптимизировать).

Реализация “Магмы” из библиотеки для Arduino показывает следующие результаты: 9092 такта полный код, соответственно, 1136 (приблизительно) тактов на байт (отмечу, что показатели близки к реализациям AES). Существенный вклад в это число вносит реализация подстановок, где много обращений к памяти с достаточно сложными преобразованиями указателей. Этот код можно оптимизировать, вплоть до того, что сами подстановки разместить в регистрах (для 16 полубайтовых подстановок, закрывающих одну позицию во входном полублоке, достаточно восьми байтовых регистров; однако вся таблица подстановок в регистрах типичного микроконтроллера вряд ли поместится – для неё нужно 64 регистра). Правда, вычисление номера регистра и обращение к нему потребует дополнительных усилий, объём кода заметно возрастёт, а для “Магмы” он и так не маленький. Тем не менее, вряд ли выигрыш по тактам составит более двух раз. Из-за подстановок – “Магма” медленнее, чем Speck, тут ничего нельзя поделать.

Другим параметром, по которому можно сравнить шифры, является объём требуемой памяти данных. Для Speck нужно 108 байтов для раундовых ключей. Реализация “Магмы” требует 128 байтов (здесь больше раундов – 32). При этом, если требуется экономия памяти, “Магма” позволяет прямо использовать в качестве раундовых ключей слова из состава основного ключа. Со Speck такой фокус не пройдёт, потому что здесь сложная функция разворачивания ключа. Однако оптимизация всё равно возможна: раундовые ключи можно вычислять в процессе выполнения раундов шифра. Впрочем, такой вариант приведёт к тому, что минимум в два раза возрастёт число тактов, поэтому Speck приблизится к “Магме”. Для хранения таблицы подстановок “Магма” требует ещё 8*8=64 байта.

Реализация “Магмы” существенно превышает показатели Speck по объёму кода. И тот, и другой шифр вполне укладываются в разумные рамки, но код шифра Speck – очень компактный. Побайтового сравнения объёмов я не привожу.

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

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

Приложение: исходный код реализации Speck для Arduino (только зашифрование), также содержит дополнительные функции для шифрования тестового вектора и проверки правильности работы.



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

В продолжение предыдущей заметки – посмотрим, как устроены симметричные блочные шифры. Примером послужит шифр “Магма”, в версии ГОСТ Р 34.12-2015, с картинками. Симметричными называют шифры, для которых ключ расшифрования можно легко получить из ключа зашифрования. В современных симметричных шифрах – эти ключи просто совпадают. Блочный шифр, в отличие от потокового, работает с блоками данных фиксированной длины (разрядности), измеряемой в битах. Например, шифр AES работает с блоками разрядности 128 бит. А “Магма” – 64 бита.

Получив на вход блок открытого текста и ключ, преобразование, называемое шифром, выводит блок шифротекста, той же разрядности. Соответствие между блоками открытого текста и блоками шифротекста задаёт значение ключа. “Магма” использует ключ длиной 256 бит. Современные шифры строятся из некоторых элементарных операций над блоками. Наборы таких операций обычно объединяют в раунды. Раунды повторяются несколько раз.

В “Магме” 64-битный блок разделяется на две равные части, над которыми производятся операции раунда. Эти операции включают в себя (в порядке выполнения): сложение с ключом раунда; подстановки; циклический сдвиг; сложение с половиной блока. Заканчивается раунд перестановкой полублоков местами. Раунд показан на схеме ниже:

Magma Round

A1 и A0 – две части входного блока: соответственно, они содержат по 32 разряда каждая. На вход цепочки раундовых операций поступает значение полублока A0. Для каждого раунда используется свой ключ. На схеме ключ обозначен Ki. Раундовый ключ также имеет длину 32 бита (разряда), то есть, совпадает с разрядностью половины блока. Сложение блока со значением ключа (операция обозначена символом ⊞) выполняется по модулю 232 – это эквивалентно “естественному”, для вычислительной техники, сложению двух 32-битных чисел (без знака). Над результатом сложения выполняются подстановки по таблице подстановок. Таблицы часто называют S-boxes. “Магма” использует 4-битные подстановки, отдельные для каждого полубайта из 32-битного блока. Логика тут следующая: 32-битный блок разбивается на 8 4-битных частей, каждое из получившихся значений (0..15, так как битов – четыре) заменяется на соответствующее ему значение из таблицы подстановок; таблиц восемь – по одной для каждой позиции 4-битного значения внутри 32-битного блока.

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

Значение 32-битного блока после подстановок циклически сдвигается влево на 11 разрядов (то есть, биты сдвигаются влево, а выбывшие разряды вдвигаются справа в том же порядке). После операции сдвига, значение поразрядно суммируется с блоком A1 по модулю 2, это логическая операция XOR (обозначена символом ⊕ на схеме).

В заключении раунда – A1 и A0 меняются местами. То есть, A0 переходит в следующий раунд без изменений, но становится на место A1. Всего раундов 32. Последний раунд отличается тем, что 32-битные блоки не меняются местами, а просто объединяются: A0 присоединяется к A1 справа. Это замыкает всю конструкцию, позволяя использовать её без изменений для расшифрования: операция расшифрования отличается только обратным порядком раундовых ключей.

Раундовых ключей – 32. Каждый имеет разрядность 32 бита. Эти ключи получаются из основного ключа шифрования при помощи алгоритма развёртывания ключа. В “Магме” этот алгоритм очень простой. Исходный ключ содержит 32 байта (256/8=32). 32 байта – это 8 раундовых ключей, каждый по четыре байта; на 32 раунда – ключи копируются, с той лишь разницей, что последние восемь используются в обратном порядке. Схема:

Round Keys

Работа шифра выражается в “перемешивании” битов открытого текста, схему перемешивания определяет ключ (и таблицы подстановок, но мы считаем, что они неизменны). Преобразования можно визуализировать. На картинке ниже – разным значениям битов соответствуют синий и жёлтый цвета, раунды выполняются сверху вниз (самая верхняя строка – открытый текст).

Magma Operation

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

Avalanche-1

Хорошо видно, что уже на седьмом раунде различия между значениями блоков сравнимы (визуально) с типичным расстоянием между двумя случайными 64-битными значениями. При этом решающий вклад в “разделение” блоков вносят подстановки (собственно, в этом их основное назначение). Попробуем выключить подстановки (кроме последнего раунда; без подстановок, естественно, данный шифр использовать нельзя).

No S-boxes

Результат – плачевный. Несмотря на то, что это лишь схема для двух открытых текстов, понятно, что ни о каком “лавинном эффекте” от замены одного бита говорить уже не приходится. Сходного результата можно добиться и использованием “плохих” таблиц подстановок (но нестойкие таблицы, в общем случае, не обязательно приводят к такому эффекту).

Попробуем изменить другой параметр – число разрядов, на которые циклически сдвигается блок в каждом раунде. Используем сдвиг на 12 разрядов, вместо 11 (подстановки и другие преобразования – без изменений).

Wrong Rotation

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



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

Old Cracked EngineБольше и больше пишут про “квантовые каналы” связи, которые “абсолютно” защищены “квантовой криптографией”, и только они смогут спасти от “квантового компьютера”. Здесь интересны несколько моментов.

1.

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

2.

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

3.

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

4.

Квантовые компьютеры. Симметричные системы (шифры), вроде AES, сохраняют стойкость: сейчас считается, что появление квантовых компьютеров достаточной мощности приведёт лишь максимум к “квадратичной” оптимизации перебора. Это очень оптимистичная, в отношении квантового компьютера, оценка, потому что речь идёт о квантовых операциях, реализующих алгоритм поиска – а это совсем другое дело, по сравнению с классическим CPU. То есть, для сохранения стойкости, разрядность ключа симметричного шифра нужно будет увеличить в два раза. Соответственно, AES с 256-битным ключом обеспечит достаточную степень защиты (эквивалентную 128 битам). Если стороны успели в защищённом режиме обменяться гигабайтом ключевого потока, то его, даже при расточительном использовании в качестве ключей AES, хватит надолго. (256 бит – это 32 байта, которые можно смело использовать для шифрования AES примерно 2^32 блоков, каждый блок – это 16 байтов, то есть, одного ключа хватит для 16 * 2^32 ≈ 64 гигабайт передаваемых данных; и это только один ключ, 64 байта из гигабайта).

5.

Квантовые компьютеры достаточной разрядности – полностью побеждают распространённые сейчас асимметричные криптосистемы. Если только такие компьютеры возможны. Как ни странно, первыми падут суперсовременные криптосистемы на эллиптических кривых: это связано с тем, что они имеют малую разрядность, а способность квантового компьютера взламывать такие системы находится в прямой зависимости от числа доступных кубитов. То есть, компьютера, взламывающего ECDSA с ключами в 256 бит, ещё недостаточно для того, чтобы атаковать RSA с разрядностью в 2048 бит. Так что тут у RSA есть преимущество. Другое дело, что как только сумеют построить квантовый компьютер с разрядностью в 256 кубитов, масштабирование на 2048 – вряд ли потребует долгих лет.

6.

Тем не менее, утверждение, что квантовый компьютер убивает всю современную криптографию – не соответствует действительности. Выше уже отмечено, что симметричные шифры страдают не сильно, не критически: 256-битный ключ – обычное дело уже сейчас. К асимметричным системам, надо сказать, при защите действительно важной информации всегда относились насторожено – так что для защиты совершенно секретной информации такие криптосистемы не используют. (Электронная почта, банк-клиенты – это другое дело.) Без сомнения, производительный квантовый компьютер позволит достаточно быстро расшифровать все записанные ранее сообщения, ключи для которых были выработаны при помощи шифрования RSA, современных разновидностей протоколов Диффи-Хеллмана (DH). Например, сюда относится весь трафик TLS – он становится полностью прозрачен. Ещё раз отмечу: это относится и к ранее записанным сессиям. Сейчас сплошь и рядом приходится слышать, что, якобы, ключи DH “сохраняются только у клиента и сервера”. Это не так. Полное представление ключей сохраняется в трафике, их просто сложно вычислить из этого представления (я писал об этом ранее), но квантовый компьютер задачу решает.

Про “квантовую проблему” давно известно. Поэтому сейчас очень активно разрабатывают классические криптосистемы, обладающие “квантовой стойкостью”. Это постквантовая криптография. Так как основную угрозу составляет возможное раскрытие симметричных ключей, защищающих трафик, прежде всего будут внедряться постквантовые протоколы обмена ключами (выработки общего секрета). Это, например, варианты протокола Диффи-Хеллмана, работающие на другом математическом аппарате. В экспериментальной версии браузера Google Chrome в реализацию TLS уже добавлен постквантовый протокол генерации общего секрета. Так что не стоит доверять громким заявлениям, будто “появление квантового компьютера уничтожает классическую криптографию” – квантового компьютера пока что нет и на горизонте, а постквантовые криптосистемы уже добрались до реализации в экспериментальном браузере (но до массового внедрения, конечно, там тоже далеко).

7.

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



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

ksks7 (Техничная записка из области популярной криптологии, которая, думаю, будет полезна и на dxdt.ru.)

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

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

Когда говорят о прогрессивной секретности (PFS), которой позволяет добиться использование DH, то имеется в виду вовсе не то, что ключи невозможно восстановить после того, как сессия завершилась, а лишь то, что утечка долговременного ключа не раскрывает сессионных ключей. Не более того. Обычно, долговременный ключ в TLS – это ключ, используемый для аутентификации сервера, при помощи электронной подписи. Если прогрессивная секретность отсутствует, то восстановление сеансовых ключей, если у вас есть долговременный секретный ключ (это будет, соответственно, RSA) оказывается тривиальной задачей – просто расшифровываем исходные данные из трафика.

Трафик приложений в TLS зашифровывается симметричным алгоритмом, который и использует сеансовые ключи. То есть, в принципе, для того, чтобы раскрыть трафик, можно “просто” правильно подобрать симметричные сеансовые ключи. Однако эта задача вовсе не эквивалентна восстановлению ключей из записанного обмена параметрами DH. Скорее всего, с DH разобраться легче (теоретически; а на практике – приходится надеяться на уязвимости, которых, впрочем, немало).

Для детального понимания ситуации нужно рассмотреть следующий случай: предположим, что стороны, обменивающиеся данными в рамках защищённой сессии, используют заранее известный им разовый (относительно сессии) набор секретных сеансовых симметричных ключей и, скажем, AES. То есть, симметричные ключи не генерируются при помощи обмена в рамках DH, а известны заранее. По каналу связи они не передаются, канал не используется для их генерации. (Аутентификацию оставим за скобками.) Пусть используется добротный режим потокового шифрования: генерируется ключевой поток (гамма), совпадающей по длине с открытым текстом, а шифротекст является результатом операции XOR над открытым текстом и ключевым потоком. Примерно так работает GCM (аутентификацию мы договорились оставить за скобками) и всякий другой “режим счётчика”. Так как полученный ключевой поток будет, вообще говоря, вычислительно неотличим от псевдослучайной функции, то для записавшей трафик стороны ситуация окажется, условно говоря, семантически неотличима от абсолютно стойкого шифрования.

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

Конечно, это достаточно техничный момент. Тем не менее, он актуален для современного использования TLS. Например, если у кого-нибудь есть супер-пупер-сверхкомпьютер, который позволяет за разумное время решать произвольную задачу дискретного логарифмирования (то есть, “обращать” DH), то этот кто-то может замечательно читать ключи DH из записанного трафика – потому что эти ключи там есть.

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



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

BirdВ продолжение заметки про сеансовые ключи TLS, генерируемые по протоколу Диффи-Хеллмана (DH). Этот протокол, в классическом случае, работает на “обычной” конечной группе (современный вариант использует группу точек эллиптической кривой – см. ниже). Группа DH задаётся единственным числом – модулем. Это обязательно большое простое число. На практике веб-серверы так настроены, что используют ту или иную типовую группу (или типовой модуль, что эквивалентно). Модуль не является секретным. То есть, известна группа, используемая большинством веб-серверов, поддерживающих DH (для Рунета это более 60% веб-серверов). Эта группа является 1024-битной, что не так много.

Вся практическая полезность DH строится на сложности задачи дискретного логарифмирования (отыскания по известным A,G такого e, что A = G^e). Так вот, один из моментов, на который обратили внимание авторы атаки на TLS Logjam, состоит в том, что если у вас много ресурсов, то, в теории, для 1024-битной группы можно уже сейчас предвычислить её арифметические структуры, потратив пару лет работы суперкомпьютера и сохранив результаты в специальных таблицах. После этого вычислять дискретный логарифм можно достаточно быстро (за часы, а возможно, даже в режиме онлайн), особенно, если вы используете специальную многопроцессорную систему. Это означает, что можно расшифровать записанный ранее трафик TLS-сессий (а также других протоколов, использующих DH). Дело в том, что сеансовый ключ, если вы умеете отыскивать дискретный логарифм, элементарно вычисляется из ключа DH, который передаётся в открытом виде. Предвычислить нужную структуру можно только для известной группы, поэтому важно, чтобы TLS-серверы использовали типовые параметры. При этом, для тех, у кого ресурсов мало (кто не является специализированным агентством, например), группа остаётся вполне стойкой.

Лирическое отступление: как упоминалось выше, есть современная разновидность DH, работающая на группе точек эллиптической кривой – ECDH. Этот протокол также распространён в современных реализациях TLS. Из-за особенностей групповой операции на эллиптической кривой, отыскание дискретного логарифма в такой группе сложнее, поэтому, во-первых, можно использовать более короткие ключи, и, во-вторых, использовать общую кривую. На практике самый распространённый случай – кривая secp256r1, предлагающая 256 бит. Естественно, на ум сразу приходят теории о том, что АНБ известна пара-тройка секретных теорем, которые позволяют резко уменьшить вычислительную сложность дискретного логарифмирования на кривой secp256r1 (которая, кстати, в АНБ и сконструирована).

Самое занятное, что если группу классического DH в TLS легко поменять – модуль и генератор передаются в сообщении сервера и могут быть любыми, – то для эллиптических кривых всё сильно сложнее: параметры здесь фиксированы заранее, клиент и сервер могут договориться только о самой кривой, выбрав её из ограниченного списка. Для эллиптической криптографии уже находили эффективные оптимизации: например, существуют так называемые суперсингулярные кривые, на которых дискретное логарифмирование оказывается разрешимым на практике. (Поэтому данный тип кривых нельзя применять в качестве основы для “классического” ECDH или алгебраически родственной криптосистемы ECDSA; что, кстати, не означает неприменимость этих кривых в криптографии вообще – предложены алгоритмы электронной подписи, использующие именно суперсингулярные кривые, но это другая история.) В общем, если вы умеете “логарифмировать” на эллиптической кривой, то ECDH точно также теряет надёжность, а памяти для хранения оптимизации, вполне возможно, требуется меньше (из-за меньшей разрядности группы).



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

RailsВ работе исследователей, которые обнаружили уязвимость TLS Logjam, обсуждается возможность вычисления системами АНБ дискретного логарифма в некоторых группах, используемых в различных реализациях алгоритма Диффи-Хеллмана. (Задача дискретного логарифмирования, для правильно выбранных параметров, является вычислительно трудной, на этой трудности и основана практическая полезность протокола Диффи-Хеллмана.) Например, в решениях VPN, использующих IPsec (а это распространённая практика), для генерации общего ключа служат группы, заданные в рекомендациях (RFC). То есть, параметры известны заранее, это позволяет сильно ускорить процесс вычисления логарифма, выполнив предварительные вычисления.

АНБ, в теории, могло построить особый компьютерный кластер. В его основе – специализированные вычислители (ASIC), которые оптимизированы для выполнения конкретной задачи (вычисление арифметической структуры заданной группы). Если использовать современные технологии микроэлектронного производства, то узкоспециализированных вычислительных ядер в небольшом элементе кластера (в размере сервера типа blade, скажем) можно разместить тысячи (вспомните про современные видеокарты: там тысячи ядер, составляющих графический процессор, размещаются на одной небольшой плате). Предварительные вычисления для дискретного логарифмирования хорошо распараллеливаются. Миллионы ядер, допустим, позволяют вычислять структуру группы для 1024-битного модуля за год. После того, как предварительные вычисления сделаны, можно очень быстро (за минуты) раскрывать секретные ключи, полученные по протоколу Диффи-Хеллмана, из записанного трафика. А “предвычислитель” может заняться другой группой, потратив на неё ещё год, – это не так страшно, потому что одни и те же параметры в Сети действуют десятилетиями.

Повторюсь: группы, которые использует большинство узлов VPN, известны заранее – они внесены в рекомендации, их всего несколько (три-пять, в зависимости от протокола). Соответственно, при необходимости расшифровки трафика, записанные снифером параметры отправляются в центр обработки данных АНБ, там из них вычисляют ключ, возвращают его обратно на перехватывающий узел и – всё, теперь можно в пассивном режиме читать IPsec VPN. Именно такая схема обозначена на слайдах из презентаций АНБ. В общем-то, выглядит всё логично: бюджеты большие, а превращение некоторой их части в суперкомпьютер, раскрывающий хотя бы половину трафика VPN, – такое несложно обосновать, просто сравнив возможности “до и после”. Ситуация с прослушиванием в режиме онлайн становится возможной не потому, что алгоритм плохой, а потому, что повсеместно используются рекомендуемые параметры алгоритма (это известная схема, которая всегда служила источником напряжённости в спорах о том, какую и “чью” криптографию нужно применять). Интересно, кстати, что если VPN-трафик скрывает какие-то весьма ценные данные, но узлы используют нестандартные настройки, то трафик можно записать, потратить год времени на вычисление конкретных ключей – ну, чтобы оборудование не простаивало, – и потом расшифровать трафик, нивелировав всю прогрессивную секретность.



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