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

Иллюстрация конструкции губки — Конструкция губки для хэш-функций. *P _i* — блоки входной строки, *Z _i* — хешированные выходные блоки.

В криптографии губчатая функция или конструкция губки — это любой из классов алгоритмов с конечным внутренним состоянием , которые принимают входной поток битов любой длины и создают выходной поток битов любой желаемой длины. Функции губки имеют как теоретическое, так и практическое применение. Их можно использовать для моделирования или реализации многих криптографических примитивов , включая криптографические хэши , коды аутентификации сообщений , функции генерации масок , потоковые шифры , генераторы псевдослучайных чисел и шифрование с проверкой подлинности . ^[1]

Строительство

Функция губки состоит из трех компонентов: ^[2]

память состояний S , содержащая b битов,
функция $f:\{0,1\}^{b}\rightarrow \{0,1\}^{b}$
функция заполнения P

S разделен на две части: одну размером r (битрейт) и оставшуюся часть размера c (емкость). Эти секции обозначаются R и C соответственно.

f производит псевдослучайную перестановку $2^{b}$ государства С. из

P добавляет к входной строке достаточно битов, чтобы длина дополненных входных данных была целым кратным битрейту r . Это означает, что входной сигнал сегментируется на блоки по r бит.

Операция

Функция губки «поглощает» (в метафоре губки ) все блоки дополненной входной строки следующим образом:

S инициализируется нулем
для каждого r -битного блока B из P (строка)
- R заменяется на R XOR B (с использованием побитового XOR )
- S заменяется на f ( S )

Вывод функции губки теперь готов к созданию («сжатию») следующим образом:

повторить
- выведите R- часть S
- S заменяется на f ( S ), если вывод не заполнен.

менее r Если для вывода осталось бит, то R будет усечен ( только часть R будет выведена ).

Другая метафора описывает память состояний как « бассейн энтропии », в который «вливаются» входные данные, а функция преобразования называется «перемешиванием пула энтропии». ^[3]

Обратите внимание, что входные биты никогда не подвергаются операции XOR в части C памяти состояний, и никакие биты C никогда не выводятся напрямую. Степень, в которой C изменяется входными данными, полностью зависит от функции преобразования f. В хэш-приложениях устойчивость к коллизиям или атакам на прообразы зависит от C , а его размер («емкость» c ) обычно в два раза превышает желаемый уровень сопротивления.

Дуплексная конструкция

Также можно поочередно всасывать и сжимать. ^[1] Эта операция называется дуплексным построением или дуплексированием. Это может быть основой однопроходной системы шифрования с аутентификацией.

Состояние S инициализируется нулем.
для каждого r -битного блока B входа
- R объединяется с помощью XOR с B
- S заменяется на f ( S )
- R теперь является выходным блоком размером r бит.

Режим перезаписи

Во время поглощения можно пропустить операции XOR, сохраняя при этом выбранный уровень безопасности . ^[1] В этом режиме, на этапе поглощения, следующий блок ввода перезаписывает R- часть состояния. Это позволяет сохранять меньшее состояние между шагами. Поскольку часть R в любом случае будет перезаписана, ее можно заранее отбросить, C. необходимо сохранить только часть

Приложения

Функции губки имеют как теоретическое, так и практическое применение. В теоретическом криптоанализе случайная губчатая функция представляет собой губчатую конструкцию, где f — случайная перестановка или преобразование, в зависимости от обстоятельств. Случайные губчатые функции охватывают больше практических ограничений криптографических примитивов, чем широко используемая случайная модель оракула , в частности конечное внутреннее состояние. ^[4]

Конструкция губки также может быть использована для создания практических криптографических примитивов. Например, криптографическая губка Keccak с 1600-битным состоянием была выбрана NIST победителем в конкурсе SHA-3 . Сила Кечака проистекает из сложной многораундовой перестановки f , которую разработали ее авторы. ^[5] Редизайн RC4 под названием Spritz относится к конструкции губки для определения алгоритма.

В качестве других примеров можно использовать губчатую функцию для создания аутентифицированного шифрования со связанными данными (AEAD), ^[3] а также схемы хеширования паролей . ^[6]

Ссылки

^ Jump up to: ^а ^б ^с Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; ван Аш, Джайлз. «Дуплексная обработка губки: однопроходное шифрование с аутентификацией и другие приложения» (PDF) . Проверено 27 марта 2023 г.
^ Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; ван Аш, Джайлз. «Губка и дуплексные конструкции» . Проверено 27 марта 2023 г.
^ Jump up to: ^а ^б Ривест, Рон; Шульдт, Джейкоб (27 октября 2014 г.). «Spritz — губчатый потоковый шифр и хэш-функция, подобный RC4» (PDF) . Проверено 29 декабря 2014 г.
^ Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; ван Аш, Джайлз. «О недифференцируемости конструкции губки» (PDF) . Проверено 27 марта 2023 г.
^ Бутин, Чад (2 октября 2012 г.). «NIST выбирает победителя конкурса алгоритмов безопасного хеширования (SHA-3)» . НИСТ . Проверено 4 октября 2012 г.
^ ван Бейрендонк, М.; Трюдо, Л.; Джард, П.; Балацукас-Стимминг, А. (29 мая 2019 г.). Ядро Lyra2 FPGA для криптовалют на основе Lyra2REv2 . Международный симпозиум IEEE по схемам и системам (ISCAS). Саппоро, Япония: IEEE. стр. 1–5. arXiv : 1807.05764 . дои : 10.1109/ISCAS.2019.8702498 .

Внешние ссылки

[duplex-1] Jump up to: ^а ^б ^с Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; ван Аш, Джайлз. «Дуплексная обработка губки: однопроходное шифрование с аутентификацией и другие приложения» (PDF) . Проверено 27 марта 2023 г.

[2] Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; ван Аш, Джайлз. «Губка и дуплексные конструкции» . Проверено 27 марта 2023 г.

[Rivest2014-3] Jump up to: ^а ^б Ривест, Рон; Шульдт, Джейкоб (27 октября 2014 г.). «Spritz — губчатый потоковый шифр и хэш-функция, подобный RC4» (PDF) . Проверено 29 декабря 2014 г.

[4] Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; ван Аш, Джайлз. «О недифференцируемости конструкции губки» (PDF) . Проверено 27 марта 2023 г.

[5] Бутин, Чад (2 октября 2012 г.). «NIST выбирает победителя конкурса алгоритмов безопасного хеширования (SHA-3)» . НИСТ . Проверено 4 октября 2012 г.

[lyra2ToC-6] ван Бейрендонк, М.; Трюдо, Л.; Джард, П.; Балацукас-Стимминг, А. (29 мая 2019 г.). Ядро Lyra2 FPGA для криптовалют на основе Lyra2REv2 . Международный симпозиум IEEE по схемам и системам (ISCAS). Саппоро, Япония: IEEE. стр. 1–5. arXiv : 1807.05764 . дои : 10.1109/ISCAS.2019.8702498 .

[1]

[2]

[3]

[4]

[5]

[6]