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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Функция Губка»)
Перейти к: навигация, поиск

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

Структура[править | править вики-текст]

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

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

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

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

5. Генератор псевдослучайных чисел, основанный на функции губки
5.1. Моделирование ГПСЧ с изменяемыми входными данными

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

  • Запрос подачи , 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) с полным исходным материалом.

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

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

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

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

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

На практике идея состоит в том, чтобы не вызвать функцию губки со всей е (h) каждый раз, как получаем запрос принятия. Вместо этого, конструкция использует функцию губки каскадным образом, повторно используя состояние, как описано в разделе 3.2. Чтобы разрешить повторное использование состояния функции губки е (h) должна быть такой, что если h’ = h || fetch(l) || feed(σ), то p(e(h)) || 0r(⌈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 в каждый блок, содержащий исходный материал.

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

Реализации алгоритма[править | править вики-текст]

Ссылки[править | править вики-текст]

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