Функция губки

Иллюстрация принципа работы функции губки. *P_i* — блоки, на которые разделена строка на входе, *Z_i* — блоки на выходе.

В криптографии функция губки (или просто губка) (англ. sponge construction или sponge function) — это класс алгоритмов с конечным внутренним состоянием, на вход которых поступает двоичная строка произвольной длины, и которые возвращают двоичную строку также произвольной длины f:{0,1}ⁿ → {0,1}^*. Функция губки может использоваться для создания хеш-функций, потоковых и блочных шифров, генераторов псевдослучайных чисел, имеющих произвольную длину входных данных.

Структура

Губка — это итеративная конструкция для создания функции с произвольной длиной на входе и произвольной длиной на выходе на основе преобразований f. Губка имеет внутреннее состояние S — с данными фиксированного размера b (бит). При этом данные разделены на 2 части — первая S₁ размера r, а вторая S₂ — размера c. Значение r называется битовой скоростью, а значение с — мощностью; b = r + c.

На фазе инициализации блок данных размера b заполняется нулями, а входные данные M разбиваются на блоки размера r. Дальнейшая работа губки производится в 2 этапа:

В фазе «впитывания» (absorbing) выполняется операция XOR очередного блока исходного сообщения с первой частью состояния S₁ размера r(бит), оставшаяся часть S₂ состояния ёмкостью c остается незатронутой. Результат помещается в S₁ , а затем состояние S обрабатывается функцией f — многораундовой бесключевой псевдослучайной перестановкой, и так повторяется до исчерпания блоков исходного сообщения.
В фазе «выжимания» (squeezing) состояние S подаётся на функцию f, после чего часть S₁ подаётся на выход. Эти действия повторяются, пока не будет получена последовательность нужной длины (например, длины хэша).

Последние биты c зависят от входных блоков лишь опосредованно и не выводятся в ходе фазы «выжимания» (squeezing).

Применение

Генератор псевдослучайных чисел, основанный на функции губки

Моделирование ГПСЧ с изменяемыми входными данными

Определим ГПСЧ с изменяемыми исходными данными как объект с состоянием, который поддерживает два типа запросов, в любом порядке:

Запрос подачи, feed(σ) — подает исходное значение, состоящее из непустой строки σ ϵ $Z_{2}^{+}$ , в состояние ГПСЧ;
Запрос принятия, fetch(l) — поручает ГПСЧ вернуть l бит.

Тогда исходный материал (seeding material), подаваемый на вход генератора — это конкатенация σ, полученных во всех запросах подачи.

Неформально требования к ГПСЧ с изменяемыми исходными данными могут быть определены следующим образом:

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

Определим идеальный ГПСЧ как конструкцию, использующую Случайный оракул

Конструкцию, которую мы определили, можно описать следующим образом. Она сохраняет как состояние последовательность всех запросов подачи и принятия, которые она получила, составляя историю h. При получении запроса подачи feed(σ) она обновляет историю подсоединением этого запроса. При получении запроса принятия fetch(l), она подает случайному оракулу строку, который в свою очередь шифрует историю строкой и возвращает биты от z до z+l-1 своего ответа, где z — число запрашиваемых бит в запросе подачи. Следовательно, конкатенация ответов на запросы подачи — всего лишь ответ случайного оракула на единичный запрос. Это продемонстрировано на рисунке. Назовем эту конструкцию режимом, сохраняющим историю, с функцией шифрования e(h). Определение режима с сохранением истории, следовательно, сходится к определению этой функции шифрования.

Так как выход ГПСЧ должен зависеть от всего полученного исходного материала, шифрующая функция e(h) должна быть инъективна с исходным материалом. Другими словами, для любых двух последовательностей запросов с различным исходным материалом, два отображения e(h) должны быть различны. Мы называем это полнота исходного материала (seed-completeness). В функции шифрования с полным исходным материалом на запрос принятия будут выданы различные ответы на разные входные строки. Отсюда следует, что ГПСЧ возвращает независимые биты.

Таким образом, предлагается следующее определение идеального ГПСЧ с изменяемыми входными данными.

Идеальный ГПСЧ с изменяемыми входными данными — это режим, сохраняющий историю, называемый случайным оракулом, с функцией шифрования e(h) с полным исходным материалом.

Создание ГПСЧ с использованием функции губки

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

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

При построении функции губки, входное сообщение m ϵ $Z_{2}^{*}$ должно быть поделено на блоки из r битов и заполнено. Обозначим, как p(m) функцию, которая делает это, и предположим, что эта функция добавляет только биты после m. Предположим, что мы хотим повторно использовать состояние губки, для которой входной строкой было сообщение m1 и для которой выходные биты были «выжаты» при l>0. Состояние функции губки в этой точке таково, как если бы частичное сообщение m’1 = р(m1) || 0^{r(⌈l/r⌉-1)} было «впитано». Обратите внимание, что нулевые блоки составляют дополнительные итерации из-за фазы сжатия. Перезапуск губки с этой точки означает, что входным будет сообщение m2, для которого m’1 является префиксным.

Чтобы определить ГПСЧ формально, мы должны указать функцию шифрования e(h) с полным исходным материалом, отображающую последовательность запросов подачи и принятия. Выход е(h) используется в качестве входа для функции губки.

На практике идея состоит в том, чтобы не вызвать функцию губки со всей е (h) каждый раз, как получаем запрос принятия. Вместо этого, конструкция использует функцию губки каскадным образом, повторно используя состояние, как описано в разделе 3.2.^[] Чтобы разрешить повторное использование состояния функции губки е (h) должна быть такой, что если h’ = h || fetch(l) || feed(σ), то p(e(h)) || 0^{r(⌈l/r⌉-1)} — префикс e(h’).

Чтобы связать конструкцию с практической реализацией, опишем для начала конструкцию с двумя ограничениями. Первое ограничение на длину запросов исходного значения. Для фиксированного целого k требуем, чтобы длина исходного материала σв любом запросе подачи feed(σ) была такова, что |p(σ)| = kr. Другими словами, после заполнения, исходный материал покрывает ровно k блоков по r бит. Второе ограничение в том, что первым запросом должен быть запрос подачи.

Конструкция является конструкцией с учетом состояний (stateful), если её состояние состоит из mϵ N бит, принятых с момента последнего запроса подачи. Начнем с нового исполнения функции губки, задаем m = 0. Обозначим как е строку, отображение е(h) запросов, добавленных к истории h.

Если пришел запрос fetch(l):

Выполнение производит l выходных битов, «выжимая» их из функции губки. Формально е будет адаптирована во время следующего запроса подачи.

Значение m изменено: m = m + l.

Если пришел запрос feed (σ):

Формально этот запрос подачи вызывает запрос к функции губки с е в качестве входных данных. Если это не первый запрос, то е обновлено только до последнего запроса подачи. Таким образом, результаты запросов получения с момента последнего запроса подачи должны быть включены в е, как если бы е ранее «впитывалась». Сначала е становится равной p(e), чтобы имитировать заполнение при переключении на фазу «выжимания» после предыдущего запроса подачи. Тогда ⌈m\r⌉ −1 блоков по r нулей добавляются к e для учета дополнительных вызовов функции f при последующих запросах подачи. Теперь m сбрасывается: m = 0. (Это часть влияет только на е — ничего не должно измениться в выполнении).

Затем «впитывается» σ. Формально это выражается путём добавления σ к е.

Наконец, выполнение переключает функцию губки на фазу «выжимания». Это означает, что «впитанные» данные должна быть заполнены и перестановка f применена к состоянию. (Формально, это не меняет е, так как заполнение по определению выполняется при переключении на фазу отжима).

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

Ограничение первого запроса, являющегося запросом подачи, может быть удалено, так как не имеет смысла генерировать псевдослучайные биты без первой подачи исходного материала. Если первый запрос — это принятие, то выполнение сразу заполняет (пустой строкой) вход, переключает функции губки на фазу «выжимания» и производит выходные биты с помощью «выжимания». Формально в следующем запросе подачи, это должно быть учтено в е присваиванием е значения р (пустая строка) ||0^r([m=r]-1).