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

Иллюстрация принципа работы функции губки. 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).

Реализации алгоритма

• Keccak
• Luffa

Ссылки

1. Sponge Functions Ecrypt Hash Workshop 2007.
2. Хеш-функция Keccak и конструкция Sponge как универсальный криптопримитив
3. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition