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

Теория криптографии

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

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

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

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

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

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

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

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 объединяется с B по операции XOR
- S заменяется на f ( S )
- R теперь представляет собой выходной блок размером r бит.

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

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

Приложения

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

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

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

Ссылки

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

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

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

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

[Rivest2014-3] Ривест, Рон; Шульдт, Якоб (2014-10-27). "Spritz – губчатый RC4-подобный потоковый шифр и хэш-функция" (PDF) . Получено 2014-12-29 .

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

[5] Бутин, Чад (2 октября 2012 г.). "NIST выбирает победителя конкурса Secure Hash Algorithm (SHA-3)". NIST . Получено 4 октября 2012 г.

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