Функция губки - Sponge function
В криптографии , А губки функции или губки конструкция представляет собой любая из класса алгоритмов с конечным внутренним состоянием , которые принимают входные битовый поток любой длины и производить выходную битовый поток любой требуемой длины. Функции губки имеют как теоретическое, так и практическое применение. Их можно использовать для моделирования или реализации многих криптографических примитивов , включая криптографические хэши , коды аутентификации сообщений , функции генерации масок , потоковые шифры , генераторы псевдослучайных чисел и аутентифицированное шифрование .
строительство
Функция губки состоит из трех компонентов:
- Состояние , содержащее биты ,
- функция , преобразующая память состояний (часто это псевдослучайная перестановка значений состояния)
- функция заполнения Pad
Государственная память разделена на две секции: битрейт и оставшейся часть емкости .
Pad добавляет во входную строку достаточное количество битов, так что длина заполненных входных данных кратна | Битрейт | . Таким образом, дополненный ввод можно разбить на | Битрейт | -битовые блоки.
Операция
Функция губки работает следующим образом:
- Состояние инициализируется нулем
- Входная строка дополняется. Это означает, что ввод преобразуется в блоки | Битрейт | бит с помощью Pad .
- для каждого | Битрейт | -bit Блок дополненного ввода:
- Битрейт заменяется блоком XOR битрейта (с использованием побитового XOR )
- Состояние заменяется на f ( Состояние )
Этот процесс «поглощает» (в метафоре губки ) все блоки дополненной входной строки.
Теперь выходные данные функции губки готовы к производству ("выдавлены") следующим образом:
- Поток часть памяти состояния выводится
- повторяйте, пока не будет выведено достаточно бит:
- Состояние заменяется на f ( Состояние )
- Поток часть памяти состояния выводится
Если меньше чем | Битрейт | биты остаются для вывода, тогда битрейт будет усечен ( будет выведена только часть битрейта ).
Другая метафора описывает память состояний как « пул энтропии », при этом ввод «вливается в» пул, а функция преобразования называется «перемешивание пула энтропии».
Обратите внимание, что входные биты никогда не подвергаются операции XOR в части емкости памяти состояний, и никакие биты емкости никогда не выводятся напрямую. Степень , в которой емкость изменяется при входе целиком и полностью зависит от функции преобразования F. В хэш-приложениях устойчивость к столкновениям или атакам с прообразом зависит от емкости , а ее размер ( | Вместимость | ) обычно вдвое превышает желаемый уровень сопротивления.
Дуплексная конструкция
Также возможно попеременное поглощение и сжатие. Эта операция называется дуплексным построением или дуплексом. Это может быть основой однопроходной аутентифицированной системы шифрования.
- Государство инициализируется в ноль
- Битрейт XORed с первым | Битрейт | -битовый блок ввода
- Состояние заменяется на f ( Состояние )
- Битрейт теперь первый | Битрейт | биты вывода.
- Битрейт подвергается операции XOR со следующим | Битрейт | -битовый блок ввода
- Состояние заменяется на f ( Состояние )
- Битрейт теперь следующий | Битрейт | биты вывода.
- …
Режим перезаписи
Во время поглощения можно не выполнять операции XOR, сохраняя при этом выбранный уровень безопасности . В этом режиме в фазе поглощения следующий блок входа перезаписывает битрейтную часть состояния. Это позволяет сохранять меньшее состояние между шагами. Поскольку часть битрейта в любом случае будет перезаписана, ее можно отбросить заранее, только часть емкости должна быть сохранена.
Приложения
Функции губки имеют как теоретическое, так и практическое применение. В теоретическом криптоанализе случайная функция губки - это конструкция губки, где f - случайная перестановка или преобразование, в зависимости от ситуации. Случайные губчатые функции охватывают больше практических ограничений криптографических примитивов, чем широко используемая случайная модель оракула , в частности конечное внутреннее состояние.
Конструкция губки также может быть использована для создания практических криптографических примитивов. Например, криптографическая губка Keccak с 1600-битным состоянием была выбрана NIST в качестве победителя в конкурсе SHA-3 . Сила Keccak проистекает из сложной, многоэтапной перестановки f , разработанной его авторами. RC4 -redesign называется Шпритц относится к губке-конструкции , чтобы определить алгоритм.
В других примерах можно использовать функцию губки для построения аутентифицированного шифрования со связанными данными (AEAD), а также схемы хеширования паролей .
