В криптографии , А губки функции или губки конструкция представляет собой любая из класса алгоритмов с конечным внутренним состоянием , которые принимают входные битовый поток любой длины и производить выходную битовый поток любой требуемой длины. Функции губки имеют как теоретическое, так и практическое применение. Их можно использовать для моделирования или реализации многих криптографических примитивов , включая криптографические хэши , коды аутентификации сообщений , функции генерации масок , потоковые шифры , генераторы псевдослучайных чисел и аутентифицированное шифрование.. [1]
Строительство [ править ]
Функция губки состоит из трех компонентов: [2]
- Состояние , содержащее биты ,
- функция , преобразующая память состояний (часто это псевдослучайная перестановка значений состояния)
- функция заполнения Pad
Государственная память разделена на две секции: битрейт и оставшейся часть емкости .
Pad добавляет во входную строку достаточное количество битов, так что длина дополненного ввода кратна | Битрейт | . Таким образом, дополненный ввод можно разбить на | Битрейт | -битовые блоки.
Операция [ править ]
Функция губки работает следующим образом:
- Состояние инициализируется нулем
- Входная строка дополняется. Это означает, что ввод преобразуется в блоки | Битрейт | биты с помощью Pad .
- для каждого | Битрейт | -bit Блок дополненного ввода:
- Битрейт заменяется блоком XOR битрейта (с использованием побитового XOR )
- Состояние заменяется на f ( Состояние )
Этот процесс «поглощает» (в метафоре губки ) все блоки дополненной входной строки.
Теперь выходные данные функции губки готовы к производству ("выдавлены") следующим образом:
- Поток часть памяти состояния выводится
- повторяйте, пока не будет выведено достаточно бит:
- Состояние заменяется на f ( Состояние )
- Поток часть памяти состояния выводится
Если меньше чем | Битрейт | биты остаются для вывода, тогда битрейт будет усечен ( будет выведена только часть битрейта ).
Другая метафора описывает память состояний как « пул энтропии », при этом ввод «вливается в» пул, а функция преобразования называется «перемешивание пула энтропии». [3]
Обратите внимание, что входные биты никогда не подвергаются операции XOR в части емкости памяти состояний, и никакие биты емкости никогда не выводятся напрямую. Степень, в которой Емкость изменяется вводом, полностью зависит от функции преобразования f. В хэш-приложениях устойчивость к столкновениям или атакам прообраза зависит от емкости , а ее размер ( | Вместимость | ) обычно вдвое превышает желаемый уровень сопротивления.
Дуплексная конструкция [ править ]
Также возможно попеременное поглощение и сжатие. [4] Эта операция называется дуплексным построением или дуплексом. Это может быть основой однопроходной аутентифицированной системы шифрования.
- Государство инициализируется в ноль
- Битрейт подвергается операции XOR с первым | Битрейт | -битовый блок ввода
- Состояние заменяется на f ( Состояние )
- Битрейт теперь первый | Битрейт | биты вывода.
- Битрейт подвергается операции XOR со следующим | Битрейт | -битовый блок ввода
- Состояние заменяется на f ( Состояние )
- Битрейт теперь следующий | Битрейт | биты вывода.
- …
Режим перезаписи [ править ]
Можно не выполнять операции XOR во время поглощения, сохраняя при этом выбранный уровень безопасности . [4] В этом режиме, в фазе поглощения, следующий блок ввода перезаписывает битрейтную часть состояния. Это позволяет сохранять меньшее состояние между шагами. Поскольку часть битрейта в любом случае будет перезаписана, ее можно отбросить заранее, только часть емкости должна быть сохранена.
Приложения [ править ]
Функции губки имеют как теоретическое, так и практическое применение. В теоретическом криптоанализе случайная функция губки - это конструкция губки, где f - случайная перестановка или преобразование, в зависимости от ситуации. Случайные губчатые функции охватывают больше практических ограничений криптографических примитивов, чем широко используемая случайная модель оракула , в частности конечное внутреннее состояние. [5]
Конструкция губки также может быть использована для создания практических криптографических примитивов. Например, криптографическая губка Keccak с 1600-битным состоянием была выбрана NIST в качестве победителя в конкурсе SHA-3 . Сила Keccak проистекает из сложной многоэтапной перестановки f , разработанной его авторами. [6] RC4 -redesign называется Шпритц относится к губке-конструкции , чтобы определить алгоритм.
В других примерах функция губки может использоваться для построения аутентифицированного шифрования со связанными данными (AEAD) [3], а также схем хеширования паролей . [7]
Ссылки [ править ]
- ^ Команда Keccak. "Двусторонняя печать губки" (PDF) .
- ^ Гвидо Бертони, Джоан Дэемен, Микаэль Петерс и Жиль Ван Аше. «Функции губки» . Ecrypt Hash Workshop 2007.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ a b Ривест, Рон; Шульдт, Джейкоб (27.10.2014). «Spritz - губчатый поточный шифр и хэш-функция в стиле RC4» (PDF) . Проверено 29 декабря 2014 .
- ^ a b Гвидо Бертони, Джоан Дэмен, Микаэль Петерс и Жиль Ван Аше. «Дуплексирование губки: однопроходное шифрование с проверкой подлинности и другие приложения» (PDF) . CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Гвидо Бертони, Джоан Дэемен, Микаэль Петерс и Жиль Ван Аше. «О неразличимости конструкции губки» . EuroCrypt 2008.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Бутин, Чад (2 октября 2012). «NIST выбирает победителя конкурса алгоритмов безопасного хеширования (SHA-3)» . NIST . Проверено 4 октября 2012 года .
- ^ van Beirendonck, M .; Trudeau, L .; Giard, P .; Балацукас-Стимминг, А. (29.05.2019). Ядро Lyra2 FPGA для криптовалют на основе Lyra2REv2 . Международный симпозиум IEEE по схемам и системам (ISCAS). Саппоро, Япония: IEEE. С. 1–5. arXiv : 1807.05764 . DOI : 10.1109 / ISCAS.2019.8702498 .
