18-09-2023
В криптографии, функция или конструкция губки (англ. 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 этапа:
Последние биты c зависят от входных блоков лишь опосредованно и не выводятся в ходе фазы «выжимания» (squeezing).
Атаки на нахождение коллизий (двух произвольных сообщений, дающих одинаковый хэш) и вторых прообразов (сообщения, дающего такой же хэш, что и имеющееся) имеют важное практическое и теоретическое значение, но наряду с неинвертируемостью не обеспечивают полной оценки стойкости хэш-функции. Существует целый ряд экзотических атак — на удлинение сообщения, атаки на частичные коллизии с подобранным префиксом и др. Чтобы доказать стойкость функции губка ко всем возможным атакам, авторы приняли ещё одно радикальное решение: считать единственным и достаточным общим критерием стойкости неразличимость хэш-функции от случайного оракула.
Случайный оракул (Random Oracle) — это идеализированная функция, описывающая работу машины с практически бесконечным объёмом памяти, которая на любой запрос может выдать идеально случайное число и запомнить пару «запрос-ответ». Если такой же запрос будет когда-либо повторён, то ответ будет не генерироваться заново, а взят из запомненного списка. Если перестановка f, лежащая в основе функции губка идеальна, то и хэш-функция доказуемо неразличима от RO, значит никакие из возможных атак действовать не будут.
Именно эти теоретические результаты, основанные на одном из самых строгих доказательств неразличимости от случайного оракула в конкурсе SHA-3, дают удивительные практические возможности для простого использования хэш-функции Keccak в качестве практически универсального криптопримитива.
Простое добавление секретного ключа на вход хэш-функции Keccak/Sponge превращает её в код аутентификации сообщений. Это было невозможно в обычных хэш-функциях SHA-1 или SHA-2 и требовало громоздкой конструкции HMAC.
Добавление секретного ключа с открытым вектором инициализации и вывод гаммы произвольной длины превращает функцию губка в потоковый шифр.
Добавление на вход ключа, вектора инициализации и номера блока позволяет получить потоковый шифр с произвольным доступом — аналог блочного шифра в режиме счётчика (AES-CTR). Это может быть использовано совместно с MAC для шифрования сообщений или пакетов данных.
Использование входа и выхода переменной длины может применяться для генерации симметричных ключей из паролей, из протоколов согласования ключа по асимметричным алгоритмам, для связывания сообщения с электронной подписью, рандомизированного хэширования, для дистилляции случайных данных из шумов. Если периодически уничтожать использованные предыдущие состояния, то из такой конструкции легко построить генератор псевдослучайных чисел.
Функция Губка.
