Приветствую, Хабр! Структура криптографических алгоритмов, названная ее авторами «губкой» (sponge), была предложена в 2007 году. Название не случайно – у предложенных алгоритмов действительно есть сходство с обычной губкой, состоящее в том, что алгоритмы данной структуры выполняют преобразования в два основных этапа:

• «впитывание» – когда очередной блок обрабатываемых (например, хешируемых) данных накладывается на внутреннее состояние (для этого обычно используется операция XOR), которое как бы впитывает новые данные; после этого состояние перемешивается и процесс повторяется до исчерпания входных данных;

• «выжимание» – когда из внутреннего состояния извлекается (выжимается) его часть и используется в качестве некоторой порции выходного значения (например, фрагмента хеш-кода); после этого состояние перемешивается и процесс повторяется до извлечения требуемого объема выходных данных.

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

Исходная структура криптографической губки

В ее классическом виде структура криптографической губки была предложена для использования в хеш-функциях и описана в работе [1] (перечень ссылок приведен в конце статьи). Схема исходного варианта криптографической губки приведена на рисунке:

Как видно из схемы, внутреннее состояние размером b бит, b = r + c, предварительно инициализируется нулями. Размеры частей внутреннего состояния имеют следующий смысл:

• значение r (rate) определяет размер блока сообщения, впитываемого состоянием, и размер извлекаемого из состояния фрагмента хеш-кода;

• значение c (capacity) определяет теоретический уровень криптостойкости алгоритма: несколько упрощенно говоря, чем больше соотношение r/c, тем выше скорость работы алгоритма, чем больше значение c – тем выше его криптостойкость.

Перестановка внутреннего состояния P должна выполнять его тщательное перемешивание и обеспечить (в идеале) влияние каждого бита r-части состояния (на которую был перед этим наложен блок сообщения) на каждый бит c-части. От качества перестановки также зависит криптостойкость алгоритма; часто перестановка представляет собой многораундовое преобразование, причем раунд может быть достаточно простым для упрощения реализации алгоритма и снижения его ресурсоемкости, особенно при аппаратной реализации.

Сообщение перед разбиением на блоки обычно дополняется до размера, кратного r, тогда как последний извлеченный фрагмент хеш-кода может, наоборот, усекаться в случае, если общий размер выходного значения алгоритма (n) не кратен r.

В качестве примера алгоритмов, построенных по классической структуре криптографической губки, можно привести низкоресурсные хеш-функции семейства SPONGENT [2]. Алгоритмы данного семейства (особенно с минимальным размером выходного хеш-значения n = 88 бит) являются крайне нетребовательными к ресурсам за счет простейшего раунда внутренней перестановки:

Как видно из рисунка, раунд алгоритма SPONGENT состоит из трех операций, достаточно просто реализуемых аппаратно (для упрощения на рисунке приведено 20-битное внутреннее состояние и 3-битный счетчик, тогда как в реальном алгоритме минимальный размер состояния – 88, а счетчика – 6 бит):

1. Наложение на часть внутреннего состояния счетчика раундов Cnt и его инвертированного значения Cnt’.

2. Табличная замена фрагментов внутреннего состояния 4 × 4 бит S(x).

3. Фиксированная битовая перестановка.

Простота раунда в данном случае компенсируется большим количеством раундов, выполняемых во внутренней перестановке – от 45 до 385 раундов в зависимости от конкретного варианта алгоритма. Еще одним примером (значительно более известным) хеш-функций, построенных по классической структуре криптографической губки, является семейство хеш-функций, описанных в стандарте хеширования США SHA-3 [3]. Это не удивительно, поскольку именно авторы хеш-функции Keccak [4] (ставшей впоследствии стандартом хеширования SHA-3 с незначительными изменениями) изобрели структуру криптографической губки. Структура раунда перес��ановки внутреннего состояния алгоритма SHA-3, однако, значительно сложнее по сравнению с алгоритмом SPONGENT, но и количество раундов сильно меньше: не более 24.

Некоторые усовершенствования

Структура криптографической губки заинтересовала многих разработчиков криптоалгоритмов (этому немало способствовал выбор алгоритма Keccak в качестве основы для стандарта хеширования SHA-3), некоторые из которых пытались вносить различные усовершенствования в данную структуру. Приведу пару примеров подобных модификаций.

Ввод этапа инициализации внутреннего состояния и переменное количество раундов перестановки

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

В данном случае во внутренне состояние записывается вектор инициализации IV (фиксированный и различный для каждого из вариантов алгоритма Ascon-Hash), остальная часть заполняется нулями, после чего внутреннее состояние обрабатывается a раундами внутренней перестановки P (обозначено на рисунке как P_a). Только после этого начинается впитывание блоков сообщения.
Такой подход позволяет обеспечить различное заполнение внутреннего состояния для разных вариантов алгоритма. Причем поскольку преобразование производится над состоянием с фиксированным заполнением для каждого варианта алгоритма, значение состояния после инициализации может быть предвычислено и использовано сразу вместо выполнения этапа инициализации, который в этом случае может быть пропущен.
Еще одна модификация структуры, использованная в алгоритме Ascon-Hash, – это переменное количество раундов внутренней перестановки (P_a и P_b на рисунке выше, где количество раундов a и b является константным и может различаться для вариантов алгоритма) в зависимости от того, в какой момент применяется перестановка:

• a – на этапе инициализации и перед извлечением первого фрагмента хеш-кода;

• b – в остальных случаях.

Такой подход позволяет несколько увеличить быстродействие алгоритма за счет уменьшения количества раундов внутренней перестановки (b ≤ a) в случаях, когда это не ухудшает криптографические свойства алгоритма.

Различия в размерах впитываемых и выжимаемых фрагментов данных

Классическая структура криптографической губки предполагает, что значение r является константным в течение всего времени выполнения алгоритма, то есть размеры впитываемого блока данных и выжимаемого фрагмента хеш-кода являются идентичными. Авторы низкоресурсного алгоритма хеширования PHOTON предложили усовершенствование, состоящее в изменении размеров r и с (с сохранением общего размера внутреннего состояния b) после выполнения фазы впитывания [6]:

Размер извлекаемого фрагмента хеш-кода на рисунке обозначен как r’; он является параметром алгоритма и фиксируется для его конкретного варианта (как и размеры r и c, а также размер хеш-кода n). Размер оставшейся части внутреннего состояния c’ в этом случае определяется как b - r’.
Такое «переразбиение» внутреннего состояния на фрагменты другого размера может быть применено для тонкой настройки соотношения быстродействия алгоритма и уровня его криптостойкости. Данная возможность фактически используется только в наименее ресурсоемком варианте алгоритма PHOTON (а именно, в PHOTON-80/20/16 – варианты алгоритма PHOTON именуются как PHOTON-n/r/r’), в остальных описанных в [6] вариантах алгоритма r’ = r.

Кастомизация выходного значения
Вариант структуры с кастомизацией выходного значения был также предложен авторами алгоритма Ascon. Данный вариант предполагает, что хешируемое сообщение условно разбивается на две части различного назначения:

• префикс, который может быть фиксирован для нескольких сообщений и может обозначать, например, некий контекст, в рамках которого производится обмен данными;

• произвольное сообщение.

Такая структура используется в хеш-функции с переменным размером выходного значения Ascon-CXOF [7] (CXOF – Customizable eXtendable-Output Function). Используя префикс, можно кастомизировать выходное значение хеш-функции, то есть сделать его контекстно-зависимым. При этом, если префикс используется многократно, то результат его обработки можно вычислить заранее и, таким образом, сразу подставлять внутреннее состояние, являющееся результатом работы первых двух фаз алгоритма, экономя время на обработке идентичных префиксов.

«Дуплексная» структура и расширение сферы применения криптографических губок

В 2011 г. в работе [8] теми же авторами был предложен альтернативный вариант структуры криптографической губки, подразумевающий чередование фаз впитывания и выжимания («duplexing»):

Как видно из рисунка, данная структура имеет принципиальные отличия от классической; последовательность действий при ее использовании такова:

1. Фрагмент данных (например, шифруемого сообщения; при необходимости применяется дополнение) накладывается операцией XOR на внутреннее состояние (фаза впитывания).

2. Выполняется перестановка внутреннего состояния.

3. Из внутреннего состояния выжимается фрагмент выходного значения (например, шифртекста; при необходимости, фрагмент усекается).

4. Данные операции повторяются до тех пор, пока все входные данные не будут обработаны.

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

• аутентифицированного шифрования;

• потокового шифрования;

• генерации псевдослучайных последовательностей.

Мне не известны алгоритмы, которые бы использовали такую структуру в неизменном виде, тогда как усовершенствованные структуры на основе дуплексной применяются достаточно активно – рассмотрим пример далее.

Смешанная структура с инициализацией и финализацией

Структура криптографической губки, в которой используются и элементы классической структуры, и чередование фаз впитывания и выжимания, применена в низкоресурсном алгоритме аутентифицированного шифрования Ascon [5]. Данный алгоритм выполняет преобразования в четыре этапа:

1. Этап инициализации, на котором внутреннее состояние заполняется следующими исходными данными (после чего состояние перемешивается):

   · вектором инициализации IV, константным для каждого варианта алгоритма;

   · значением nonce N, модифицирующим результат обработки данных;

   · ключом шифрования K (ключ впоследствии накладывается на фрагменты внутреннего состояния повторно – см. упрощенную схему алгоритма на рисунке далее).

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

3. Поблочное зашифрование открытого текста: наложение на внутреннее состояние блока шифруемых данных, извлечение блока шифртекста и последующее перемешивание состояния. Здесь используется уже несколько измененная структура с чередованием фаз.

4. Этап финализации, в рамках которого на основе ключа шифрования и внутреннего состояния вычисляется значение кода аутентификации T. Это некоторый аналог фазы выжимания классической криптографической губки.

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

Основные преимущества криптографических губок

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

• данные структуры хорошо изучены и обладают доказанной стойкостью в различных применениях;

• структуры легко адаптируются для применения в криптоалгоритмах различного назначения;

• простой и элегантный дизайн;

• не требуется расширение ключа шифрования;

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

• для реализации процедуры расшифрования требуются незначительные дополнительные ресурсы, поскольку она использует те же операции, что и процедура зашифрования;

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

Можно предположить, что криптографические губки будут и далее активно применяться при разработке криптографических алгоритмов.