Приветствую, Хабр!

Совсем недавно – в августе текущего года – Институт стандартов и технологий США NIST выпустил стандарт NIST SP 800-232 [1], описывающий четыре низкоресурсных криптографических алгоритма на базе семейства алгоритмов Ascon:

• алгоритм аутентифицированного шифрования с присоединенными данными Ascon-AEAD128;

• три алгоритма хеширования: Ascon-Hash256 (классическая хеш-функция), Ascon-XOF128 (хеш-функция с переменным размером выходного значения) и Ascon-CXOF128 (хеш-функция с кастомизацией и переменным размером выходного значения).

Предыдущий опыт показывает, что криптографические стандарты США после их принятия обычно широко используются во всем мире, поэтому данный документ может представлять значительный интерес и достоин детального разбора (краткий обзор стандарта NIST SP 800-232 уже был опубликован на Хабре ранее здесь), который я и предлагаю вам в двух частях в этой (и следующей) статье.

Строго говоря, вышедший документ стандартом не является, его статус – «специальная публикация» (Special Publication), что, скорее, является аналогом рекомендаций по стандартизации. Однако название документа – «Легковесные криптографические стандарты на основе Ascon для устройств с ограничениями» (Ascon-Based Lightweight Cryptography Standards for Constrained Devices) – говорит об обратном, поэтому в отношении данной публикации я применяю термин «стандарт».

Выход стандарта NIST SP 800-232 стал логическим завершением конкурса по выбору низкоресурсных алгоритмов для их последующей стандартизации, подготовку к которому NIST проводил с 2013 года (т. е. получается, что процесс стандартизации в данном случае занял более 10 лет!). Данному конкурсу также были посвящены публикации на Хабре (например, здесь), поэтому не будем уделять ему излишнее внимание в данной статье.

Алгоритмы, описанные в стандарте, хотя и базируются на семействе алгоритмов Ascon, но всё же отличаются от тех алгоритмов, которые были поданы на конкурс NIST и описаны в спецификации Ascon [2].

Прежде всего, в стандарт попало только подмножество оригинальных алгоритмов, а также был добавлен алгоритм Ascon-CXOF128, не описанный в исходной спецификации [2]. Есть и другие отличия, на которых мы не будем останавливаться в данной статье, посвященной именно вышедшему стандарту.

Структура алгоритмов 

Все 4 алгоритма, стандартизованные в NIST SP 800-232, основаны на структуре криптографической губки, которая была описана мной подробно в предыдущей статье на Хабре, поэтому здесь я не буду дублировать описание данной структуры и ее свойств. Но поскольку специфика различных типов алгоритмов требует различий в применяемых вариантах криптографической губки, схемы используемых структур будут приведены далее.

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

Опишем перестановку внутреннего состояния подробно.

Основное преобразование алгоритмов – внутренняя перестановка

Перестановка внутреннего состояния p является основным преобразованием алгоритмов семейства Ascon, практически идентичным для всех алгоритмов данного семейства (с точностью до количества раундов и порядка использования раундовых констант).

При выполнении перестановки p внутреннее состояние S (размером 320 бит) представляется в виде пяти слов по 64 бита S₀, …, S₄:

S = S₀||S₁||S₂||S₃||S₄

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

1. Наложение раундовых констант p_С^.

2. Табличная замена p_S.

3. Линейное преобразование p_L.

Упрощенно последовательность данных операций можно представить так:

Наложение раундовых констант (преобразование p_C) выполняется путем применения операции XOR, с помощью которой раундовая константа RC_j (где j – номер раунда, начиная с нулевого) накладывается на фрагмент состояния S₂ (остальные фрагменты состояния не меняются).

Раундовые константы и порядок их применения различаются для каждого из раундов преобразования, а также зависят от общего числа раундов преобразования:

RC_j = Const_16-rnd+j,

где Const₀, …, Const₁₅ – исходные константы, значения которых в шестнадцатеричном виде приведены в таблице:

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

Операция табличной замены p_S состоит в применении фиксированной таблицы замен Sub к каждому 5-битному фрагменту состояния S (в данном случае в качестве заменяемого фрагмента используются значения битов, находящихся на одной и той же позиции в фрагментах состояния S₀, …, S₄, т. е. (в случае представления состояния, как показано на рисунке выше) заменяются «вертикальные» фрагменты «толщиной» в 1 бит).

Выходные значения Sub(x) для всех возможных входных значений x от 0 до 1F включительно (в шестнадцатеричном виде) приведены поочередно в таблице:

Табличная замена может быть реализована различным образом в зависимости от имеющихся на целевой платформе ресурсов:

• параллельное применение к каждому 5-битному фрагменту состояния приведенной выше таблицы замен (64 замены по 5 бит);

• вычисление результата замен с помощью побитовых логических операций применительно ко всему состоянию S вместо применения таблицы замен напрямую.

Второй из перечисленных вариантов возможен, поскольку замена Sub является результатом выполнения определенных побитовых логических операций над 5-битным входным значением, как показано на следующем рисунке (знаком × на рисунке обозначена побитовая логическая операция «и», а x₀, …, x₄ и y₀, …, y₄ – биты входного (x) и выходного (y = Sub(x)) значений 5-битного фрагмента соответственно); в этом случае (при наличии соответствующей аппаратной поддержки) вычисления могут производиться над 64-битными фрагментами состояния S₀, …, S₄ целиком (здесь также есть возможности для промежуточных вариантов реализации в зависимости от разрядности целевой платформы).

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

Линейное преобразование p_L обеспечивает рассеивание данных по каждому из 64-битных фрагментов состояния. Данные фрагменты S₀, …, S₄ обрабатываются следующим образом:

S₀ = S₀ ⊕ (S₀ >>> 19) ⊕ (S₀ >>> 28);

S₁ = S₁ ⊕ (S₁ >>> 61) ⊕ (S₁ >>> 39);

S₂ = S₂ ⊕  (S₂ >>> 1) ⊕ (S₂ >>> 6);

S₃ = S₃ ⊕  (S₃ >>> 10) ⊕ (S₃ >>> 17);

S₄ = S₄ ⊕ (S₄ >>> 7) ⊕  (S₄ >>> 41),

где >>> – операция циклического сдвига (вращения) вправо на указанное количество бит.

Теперь опишем подробно верхнеуровневую структуру стандартизованных алгоритмов Ascon; начнем с алгоритма аутентифицированного шифрования Ascon-AEAD128.

Алгоритм Ascon-AEAD128

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

1. Шифруемый открытый текст P переменного размера (может отсутствовать).

2. Присоединенные данные A (не шифруются, но участвуют в вычислении тега) переменного размера (могут отсутствовать).

3. Секретный ключ K размером 128 бит.

4. Значение нонса N (позволяет варьировать результатом зашифрования и вычисления тега) размером 128 бит.

Значения K и N также участвуют в вычислении тега, при этом нонс не является секретным, в отличие от ключа K.
Выходными данными алгоритма являются шифртекст C, размер которого равен размеру открытого текста P, и значение тега T размером 128 бит.
Алгоритм Ascon-AEAD128 основан на модифицированной и усиленной (в частности, включающей инициализацию и финализацию – см. далее) структуре «криптографической губки» с чередованием фаз «впитывания» и «выжимания». Данная структура была описана в предыдущей статье.
Последовательность операций при выполнении зашифрования с вычислением тега можно разделить на 4 этапа (упрощенная схема приведена на рисунке ниже):

1. Инициализация внутреннего состояния.

2. Обработка присоединенных данных.

3. Обработка (зашифрование) открытого текста.

4. Финализация и вычисление тега.

Внутреннее состояние алгоритма S размером 320 бит представляется в виде двух частей различного размера: S = Sr ||Sc (данное представление используется на уровне процедур зашифрования и расшифрования, а на уровне перестановки внутреннего состояния, как было сказано выше, S представляется в виде конкатенации пяти слов по 64 бита S₀, …, S₄, т. е.: S = Sr ||Sc = S₀ || S₁ || S₂ ||S₃ ||S₄), где:

• размер части Sr эквивалентен размеру обрабатываемого блока данных и равен 128 бит;

• размер части Sc равен 192 бита.

Инициализация внутреннего состояния выполняется в 3 шага:

Шаг 1. Состояние S заполняется результатом конкатенации константного вектора инициализации IV = 0x00001000808C0001 и значений секретного ключа K и нонса N:

S = IV || K || N.

Шаг 2. К состоянию S применяются 12 раундов описанной выше перестановки внутреннего состояния p (что на рисунке обозначено как p₁₂).

Шаг 3. На состояние операцией XOR накладывается значение ключа K, дополненное 192 битовыми нулями слева.

Обработка присоединенных данных производится поблочно; перед обработкой присоединенные данные дополняются битовой единицей и (при необходимости) битовыми нулями до размера, кратного 128 битам.

Каждый 128-битный блок присоединенных данных (предположим, что данные состоят из J блоков, которые обозначим как A₁, …, A_J) обрабатывается следующим образом:

Шаг 1. Текущий блок присоединенных данных A_i, i = 1, …, J, накладывается на часть состояния Sr операцией XOR.

Шаг 2. К состоянию S применяются 8 раундов перестановки внутреннего состояния p (обозначается как p₈).

Присоединенные данные могут быть нулевого размера, в этом случае J = 0. После завершения обработки последнего блока A_J (а также при J = 0) на состояние операцией XOR накладывается модифицирующая константа, являющаяся результатом конкатенации 319 битовых нулей и битовой единицы (на рисунке не показано).
Зашифрование открытого текста также выполняется поблочно. Дополнение открытого текста до размера, кратного 128 битам, выполняется аналогично дополнению присоединенных данных.

Каждый 128-битный блок открытого текста (обозначим X блоков открытого текста как P₁, …, P_X) зашифровывается путем выполнения следующих операций:

Шаг 1. Текущий блок открытого текста P_i, i = 1, …, X, накладывается на часть состояния Sr операцией XOR.

Шаг 2. Текущее значение Sr становится i-м блоком шифртекста, т. е. C_i = Sr.

Шаг 3. К состоянию S применяются 8 раундов перестановки p (данный шаг не выполняется после обработки последнего блока открытого текста P_X).

Последний блок шифртекста C_X усекается до размера последнего блока открытого текста до дополнения (в результате общий размер шифртекста C = C₁ ||…|| C_X становится эквивалентным размеру открытого текста P до его дополнения).

Финализирующая часть процедуры зашифрования и вычисления тега выполняется с помощью следующих шагов:

Шаг 1. На состояние S накладывается операцией XOR 320-битная последовательность, представляющая собой результат конкатенации следующих данных:

· 128 битовых нулей;

· 128-битного значения ключа K;

· 64 битовых нулей.

Шаг 2. К состоянию S применяются 12 раундов перестановки p.

Шаг 3. Аутентифицирующий 128-битный тег T вычисляется как результат применения операции XOR к младшей 128-битной части состояния S и 128 битам ключа K.

Как было сказано выше, выходными данными алгоритма аутентифицированного шифрования являются шифртекст C и тег T.
Рассмотрим процедуру расшифрования с проверкой тега алгоритма AsconAEAD-128; ее упрощенная схема приведена на рисунке:

Три из четырех этапов процедуры расшифрования с проверкой тега алгоритма Ascon-AEAD128 полностью эквиваленты таковым в процедуре зашифрования с вычислением тега. К таким этапам относятся:

• инициализация внутреннего состояния;

• обработка присоединенных данных;

• финализация и вычисление тега (не включая его проверку – см. далее).

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

Шаг 1. На текущее значение части состояния Sr операцией XOR накладывается текущий блок шифртекста C_i, i = 1, …, X, где X – количество блоков шифртекста.

Шаг 2. После предыдущего шага Sr представляет собой текущий блок открытого текста: Pⁱ = Sr.

Шаг 3. Содержимое Sr заменяется содержимым текущего блока шифртекста C_i.

Шаг 4. К состоянию S применяются 8 раундов перестановки внутреннего состояния p (данный шаг не выполняется после обработки последнего блока шифртекста C_X).

Если последний блок шифртекста C_X является неполным, то его обработка несколько отличается от обработки предыдущих блоков (на шагах 1-3, шаг 4 к последнему блоку не применяется):

Шаг 1. Блок C_X накладывается операцией XOR на старший фрагмент Sr соответствующего размера.

Шаг 2. Блоком открытого текста P_X становится подвергшийся модификации на предыдущем шаге фрагмент Sr (размеры последних блоков шифртекста и открытого текста идентичны).

Шаг 3. Содержимое Sr заменяется содержимым C_X, дополненным справа единичным битом и (при необходимости) нулевыми битами до достижения 128-битного размера.

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

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

В следующей части статьи рассмотрим алгоритмы хеширования, описанные в стандарте NIST SP 800-232, а также опишем различные ограничения и рекомендации, изложенные в данном стандарте.