Функция Губка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Применение[править | править исходный текст]

Атаки на нахождение коллизий (двух произвольных сообщений, дающих одинаковый хэш) и вторых прообразов (сообщения, дающего такой же хэш, что и имеющееся) имеют важное практическое и теоретическое значение, но наряду с неинвертируемостью не обеспечивают полной оценки стойкости хэш-функции. Существует целый ряд экзотических атак — на удлинение сообщения, атаки на частичные коллизии с подобранным префиксом и др. Чтобы доказать стойкость функции губка ко всем возможным атакам, авторы приняли ещё одно радикальное решение: считать единственным и достаточным общим критерием стойкости неразличимость хэш-функции от случайного оракула.

Случайный оракул (Random Oracle) — это идеализированная функция, описывающая работу машины с практически бесконечным объёмом памяти, которая на любой запрос может выдать идеально случайное число и запомнить пару "запрос-ответ". Если такой же запрос будет когда-либо повторён, то ответ будет не генерироваться заново, а взят из запомненного списка. Если перестановка f, лежащая в основе функции губка идеальна, то и хэш-функция доказуемо неразличима от RO, значит никакие из возможных атак действовать не будут.

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

1. MAC -код аутентичности сообщения
MAC - код аутентичности сообщения

Простое добавление секретного ключа на вход хэш-функции Keccak/Sponge превращает её в код аутентификации сообщений. Это было невозможно в обычных хэш-функциях SHA-1 или SHA-2 и требовало громоздкой конструкции HMAC.







2. Потоковый шифр
Потоковый шифр

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







3. Потоковый шифр с произвольным доступом
Потоковый шифр с произвольным доступом

Добавление на вход ключа, вектора инициализации и номера блока позволяет получить потоковый шифр с произвольным доступом — аналог блочного шифра в режиме счётчика (AES-CTR). Это может быть использовано совместно с MAC для шифрования сообщений или пакетов данных.







4. Генерация симметричных ключей из паролей
Генерация симметричных ключей из паролей

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





Реализации алгоритма[править | править исходный текст]

Ссылки[править | править исходный текст]

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