Соловьиная песня постквантового шифрования
Почти год назад я написал статью о постквантовой криптографии и в этом материале решил продолжить эту тему, поскольку с каждым годом приближается момент, когда криптография, какой мы её знаем сегодня, накроется медным тазом. С появлением квантовых вычислений значительно возрос интерес к асимметричным технологиям шифрования. В частности сегодня пытаются найти подходящую замену RSAи алгоритмам на основе дискретных логарифмов, которые тривиально легко будут взломаны с помощью алгоритма Шора. Хотя симметричное шифрование более устойчиво к квантовым вычислениям, с их широким распространением оно будет существенно скомпрометировано реализациями алгоритма Гровера, поскольку он может выполнять неструктурированный поиск за:
Таким образом размер симметричного ключа уменьшится в два раза, то есть эффективность ключа AES-256 будет уменьшена до 128 бит. Тогда автоматически возникает вопрос, будет ли AES-256 оставаться безопасным? Давайте разбираться.
Учитывая текущие физические и экономические вычислительные ограничения, обычно предполагается, что 128-битный ключ обеспечивает достаточный запас безопасности для защиты от атак методом перебора, независимо от современных достижений вычислительной техники. Аргументы людей, поддерживающих это предположение, в основном базируется на принципе Ландауэра, который, гласит, что существует минимальный предел количества энергии, необходимой для стирания одного бита информации. С момента формулировки предел Ландауэра часто оказывался предметом серьёзных исследований за последние полвека. Не столь уж давние результаты предполагают, что действительно не существует нижнего предела энергии, необходимой для вычислений. Это понимание мотивировало исследования вычислений с нулевой мощностью и подразумевает, что необходимо пересмотреть основанные на физике аргументы в пользу абсолютной безопасности 128-битных ключей.
Похоже, что из-за своих особенностей AES-256 принципиально не так безопасен, как AES-128. В частности, не существует известных атак на AES-128 быстрее, чем исчерпывающий поиск. Также известно, что AES-256 имеет некоторые уязвимости, хотя в настоящее время они не могут быть использованы с практической точки зрения. Поэтому разумно предположить, что при квантовой атаке максимальная эффективная безопасность AES-256 составит 128 бит, а может быть и существенно меньше. Как любит выражаться Брюс Шнайер: «Атаки всегда становятся лучше и никогда не ухудшаются».
Джорди Роуз, один из основателей компании, производящей квантовые компьютеры D-Wave Systems, отметил, что количество кубитов на процессор, проектируемый его компанией, увеличивается примерно вдвое каждый год. Возможно, ещё слишком рано говорить о том, действительно ли это заявление является квантовым расширением закона Мура. Однако, если это правда, последствия этого типа экспоненциального роста приведут к массовому росту параллельных квантовых вычислений.
Слияние этих факторов может привести к тому, что, например, пространство ключей для AES-256 может быть криптоаналитически уменьшено, а затем обработано квантовым эквивалентом массива процессоров с массовым параллелизмом. В этом свете можно предположить, что использование AES в качестве одного из стандартов шифрования постепенно приближается к своему логическому завершению. В любом случае очень многие исследователи плотно занимаются поиском вариантов его замены.
Каковы должны быть основные характеристики алгоритма шифрования для замены AES?
Прежде всего он должен быть быстрым, то есть построен на базе простых операций, требующих относительно небольшого количества циклов процессора. Не менее важным является масштабируемость алгоритма, чтобы системы на его основе могли эффективно работать в произвольном диапазоне размеров слов и адаптироваться к различным архитектурам, как современным, так и будущим. Конечно, самой важной характеристикой алгоритма должна быть его криптостойкость и устойчивость к известным атакам. Неплохо было бы обеспечить его относительную простоту понимания и реализации, чтобы провести прозрачную замену AES. Ну и напоследок, учитывая зоопарк современных устройств, необходима аппаратная независимость для достижения высокой производительности на различных типах устройств без всяких костылей типа аппаратного набора инструкций конкретной архитектуры.
Учитывая эти цели, одна из известных концепций заключается в использовании как минимум трёх относительно простых и отдельных нелинейных процессов, которые могли бы взаимодействовать таким образом, что запутывали бы их индивидуальный вклад. Более того, каждый компонент должен иметь собственный секретный независимый ключ.
Инновационная работа Дэниела Бернштейна из Университета Иллинойса над семейством потоковых шифров Salsa20 воплощает в себе этот минималистичный подход к разработке шифров с нуля. Неудачные попытки криптоанализа и последующее принятие Google в 2013 году его варианта ChaCha20 подтверждают аргумент Бернштейна об эффективности тщательно выполняющихся простых инструкций.
Рассмотрим одну из подобных разработок. Авторы шифра Харлан Бразерс, Люк Лонерган и Роберт Шмикер. Свой алгоритм они назвали Nightingale.
Компоненты шифра ограничены следующими криптографическими примитивами:
Бернштейн рекомендует избегать использования S-блоков, однако в этом алгоритме S-блок динамически не взаимодействует с ключом, и поэтому структура не подвержена атаке, которую он успешно реализовал на AES.
Итак, собственно, перейдём к описанию алгоритма где:
зашифрованный текст Ci
открытый текст Pi
ключевой поток Ki
маска М
S-блок S
выходной S-блок Si
опорный вектор RV
нелинейная функция побитового вращения R.
Тогда у нас есть:
На рисунках ниже показаны блок-схемы процессов шифрования и расшифрования. В этой версии алгоритма используются 64-битные блоки и 896 бит ключевого материала, хотя её можно реализовать и с 512 битами. Другие конфигурации могут уменьшить общую длину ключа до 384 бит.
Рисунок 1. Блок-схема процесса шифрования Nightingale
Рисунок 2. Блок-схема процесса расшифровки Nightingale
Поскольку алгоритм обрабатывает 64-битные блоки открытого текста, сообщения, размер которых не кратен 64 битам, необходимо дополнять. Чуть ниже будет показано, как интегрировали алгоритм в библиотеку OpenSSL. EVP OpenSSL по умолчанию добавляет заполнение, используя спецификацию синтаксиса криптографических сообщений IETF.
В алгоритме есть два основных источника нелинейности: высококачественный генератор псевдослучайных чисел (PRNG) и сессионный рандомизированный S-блок. Рассмотрим их более детально.
PRNG (128 бит)
Ключевой поток для алгоритма предоставляется перестановочным конгруэнтным генератором (PCG). Семейство генераторов PCG, разработанное Мелиссой О«Нил, выполняет две функции: перехода состояний, которая представляет собой линейный конгруэнтный генератор (LCG) и выходную функцию, которая применяет нелинейную перестановку к внутреннему состоянию.
Выходная функция построена на идее функций перестановки кортежей. Эти перестановки используют существующую случайность в наиболее значимых битах текущего состояния для улучшения статистических качеств при сохранении единообразия. Такой подход эффективно устраняет общеизвестные недостатки LCG и выводит поток, который является статистически трудно прогнозируемым.
Для этой версии Nightingale был выбран LCG, использующий 128-битное начальное значение, 128 бит внутреннего состояния и дающий 64-битный выходной сигнал с периодом 2128. Начальное значение получается из хэша общего сеансового ключа. Чтобы избежать предсказуемости, его выходная функция включает в себя операцию XOR внутреннего состояния. По скорости и статистическим характеристикам он превосходит некоторые хорошо зарекомендовавшие себя криптографически стойкие генераторы псевдослучайных чисел (CSPRNG). В отличие от некоторых из них, этот генератор проходит набор статистических тестов TestU01 BigCrush, однако следует подчеркнуть, что на данный момент он не считается CSPRNG прежде всего потому, что ещё не прошёл тщательный экспертный анализ. Однако, как минимум, его результат трудно предсказать, и, поскольку он используется нестандартным образом, обычные атаки на PRNG невозможны.
Например, стандартным предположением является то, что злоумышленник может получить открытый текст, соответствующий как минимум части зашифрованного текста. В контексте типичного шифра тогда было бы тривиально получить часть ключевого потока и тем самым попытаться узнать внутреннее состояние генератора и, если возможно, вектор инициализации. Это может успешно поставить под угрозу безопасность системы. Глядя на схему шифрования, мы видим, что в случае с Nightingale открытый текст существенно отделён от потока ключей, поэтому злоумышленник не сможет таким образом использовать частичное или даже полное знание открытого текста.
S-блок (512 бит)
S-блок в Nightingale — это быстрая и простая таблица, сопоставляющая каждый входной байт с выходным байтом с помощью случайной перестановки чисел от 0 до 255. Она генерируется уникальным образом во время каждого сеанса. В отличие от статического S-блока в AES, который взаимодействует с ключом посредством матрицы состояний и тщательно разработан для минимизации корреляции между входными и выходными битами, этот S-блок обладает свойствами эфемерности, неопределённости, не смешивается с ключом шифрования и не является единственным источником нелинейности шифра.
В начале каждого сеанса получаются записи, используя четыре 128-битных начальных числа, полученных из хэша обмена общими ключами, в качестве входных данных для LCG. Четыре начальных числа используются для создания матрицы G из четырёх независимых потоков g (1), g (2), g (3) и g (4), каждый из которых состоит из сорока 64-битных слов:
Транспонируем:
и склеиваем в строку:
{g (1)1, g (2)1, g (3)1, g (4)1, g (1)2, g (2)2, g (3)2, g (4)2, . . . , g (1)40, g (2)40, g (3)40, g (4)40}.
Наконец, эта последовательность 64-битных слов разделяется на 256 40-битных значений, которые используются для перемешивания чисел от 0 до 255. Полученная рандомизированная последовательность значений составляет элементы S-блока. Для индекса i = {0, 1, 2, . . ., 255} и уникального случайного 8-битного значения si, мы можем определить функцию S-блока как:
В процессе расшифрования используется обратный S-блок. Чтобы получить его, мы просто меняем местами назначения S-блоков в уравнении выше так, что для обратной функции S−1:
В этом алгоритме существует примерно 10507 возможных перестановок S-блока. Как минимум, понадобится 1684-битный ключ, чтобы теоретически охватить это огромное пространство перестановок. У нас есть произвольно назначенный 512-битный ключ для покрытия совершенно нереальной, хотя и небольшой, части этого пространства (≈ 10154 перестановок). S-блок можно удлинить или укоротить в зависимости от конкретного применения алгоритма.
Благодаря нелинейному взаимодействию нескольких компонентов для любого сеанса наличие идентичного входного и выходного байта не является уязвимой особенностью. Аналогичным образом, во всем пространстве перестановок вероятность найти пару последовательных значений в данном сеансе (≈ 1 — e-1) намного перевешивает небольшую вероятность дублирования значений перемешивания (≈10–12). Невозможно точно узнать, какую часть пространства перестановок мы собираем в любом сеансе. Даже если предположить, что подмножество возможных перестановок является репрезентативной выборкой всего пространства, S-блок находится в относительной изоляции как от входа, так и от выхода шифра. Он также подвергается операции XOR с разными ключами в каждом блоке. Поэтому в лучшем случае извлечение полезной информации о содержимом уникально сгенерированного S-блока кажется непрактичным.
Маска М (128 бит)
Исходя из первой схемы и первой формулы, маска предназначена для предварительной защиты от атаки с использованием выбранного открытого текста. 128 бит, полученные из хэша общего сеансового ключа, используются для заполнения LCG, который затем генерирует 64-битную маску. Это гарантирует, что выбранный злоумышленником открытый текст не будет передан в S-блок. Например, строку »аааааааа» можно преобразовать в любую комбинацию из 8 разных символов. В случае повторяющихся блоков открытого текста гарантируется, что этот открытый текст преобразуется различным образом для каждого блока b. Следовательно, начиная с b2, выход Si-1 S-блока в bi-1 подвергается операции XOR с маской и открытым текстом.
Опорный вектор RV (128 бит)
Предназначен для добавления уровня нелинейности к зашифрованному тексту путем запутывания связи между ключевым потоком и выходом S-блока. 128 бит, также полученные из хэша общего сеансового ключа, используются для заполнения LCG, который затем генерирует 64-битный RV. Чтобы усложнить взаимодействие RV с ключевым потоком и выходом S-блока, RV подвергается нелинейному поразрядному повороту вправо. Расстояние вращения определяется старшими шестью битами ключевого потока блока. Это вращение является кумулятивным, так что для расстояния вращения rot и функции вращения вправо Rrot получаем:
Предполагая отсутствие вращательной симметрии в RV, получаем, что в сочетании с выходными данными S-блока ключевой поток для каждого блока смешивается с одним из 64 различных случайных значений. Это ещё больше затрудняет любые попытки вскрыть внутреннее состояние функции LCG. Наконец, для первого блока каждого сеанса RV заменяет выходные данные S-блока несуществующего предыдущего блока.
В таком текущем виде Nightingale был интегрирован в библиотеку OpenSSL (версии 1.1.1-dev) путём вставки реализации в виде криптомодуля рядом с другими, доступными в библиотеке (например, RC4, AES, DES и т. д.), чтобы максимально упростить развертывание этого нового шифра. Кроме того, Nightingale интегрирован в высокоуровневый интерфейс EVP OpenSSL, что позволяет пользователю легко изменить шифр, используемый в его программе, просто выбрав другой криптомодуль.
Для обеспечения единообразия были проведены испытания, используя встроенный тест скорости OpenSSL. Результаты представлены в таблице ниже. Все испытания проводились на стенде с использованием процессора Intel Core i7 6800k с 16 ГБ памяти под управлением Ubuntu 16.10. Результаты отражены в тысячах обрабатываемых байтов в секунду.
Испытания на время показали, что на буферах размером более 64 байт Nightingale работает быстрее, чем все версии AES, использующие аппаратное ускорение без распараллеливания. Для буферов меньшего размера аппаратное ускорение AES, по-видимому, имеет преимущество из-за более низких затрат на запуск. При использовании кэширования и других оптимизаций памяти Nightingale превосходит AES с аппаратным ускорением примерно на 15% для больших буферов. По сравнению с программными реализациями AES-128 и AES—256, Nightingale работает соответственно в 5,8 и 8,6 раза быстрее для больших буферов.
Так как Nightingale достаточно новый алгоритм, ему ещё предстоит пройти более серьёзные экспертные тесты. Однако тест с помощью набора статистических тестов TestU01 он уже прошёл, показывая, что его выходные данные неотличимы от случайных. Результаты теста BigCrush для Nightingale можно посмотреть здесь. Эти результаты подразумевают неразличимость шифртекста при атаке на основе подобранного открытого текста, которая, в свою очередь, эквивалентна семантической безопасности. Тем не менее описанная версия алгоритма уязвима к переключению битов, поэтому в текущем виде его следует использовать в сочетании с имитовставками (MAC), такими как Poly1305, которые доказуемо безопасны. Хотя основной вариант Poly1305 использует AES, он позволяет пользователю легко использовать другие шифры. В текущей реализации OpenSSL алгоритм использует преимущества пакета EVP, так что аутентификация сообщений автоматически обрабатывается HMAC с использованием SHA-384. Последовательность операций не зависит от значений ключей, и нет подпрограмм, которые выполняются в нефиксированное время. Насколько мне известно, время обработки не зависит ни от значения ключа, ни от входного значения. По-видимому, это обеспечивает иммунитет к атакам по побочным каналам.
В дальнейшем авторы шифра планируют провести оптимизацию алгоритма и кода, векторизацию для использования набора инструкций AVX и повысить эффективность процедуры настройки. В отличие от AES, шифр не требует доступа к набору инструкций AES-NI для достижения оптимальной скорости. Поэтому предполагается, что при использовании в контексте виртуальных и контейнерных сред он должен обеспечивать более стабильную производительность, а также преимущества безопасности побочных каналов по сравнению с AES. Таким образом, Nightingale представляет собой одну из быстрых, безопасных и адаптируемых альтернатив AES. Расширяемая конструкция позволит ему соответствовать постоянно меняющимся требованиям безопасности в эпоху квантовых вычислений, а гибкость позволит оставаться предсказуемо безопасным в непредсказуемом будущем.
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS
