Губка (sponge construction)¶

Губка (sponge construction) — это семейство криптографических конструкций, используемых для построения хеш-функций, потоковых шифров, генераторов псевдослучайных чисел и других примитивов. В отличие от классической конструкции Меркла — Дамгора, губка не требует финального сжатия и может обрабатывать входные данные произвольной длины, а также выдавать выходные данные произвольной длины (как хеш, так и шифротекст). Конструкция была предложена в 2007 году Гидо Бертони, Жоаном Деменом, Михилом Питерсом и Жилем ван Ассхе в рамках конкурса SHA-3 и легла в основу алгоритма Keccak, ставшего победителем конкурса и стандартом SHA-3 в США (FIPS 202, 2015 год).

¶История

До появления губки доминирующей конструкцией для хеш-функций была схема Меркла — Дамгора (MD). Она использовалась в MD5, SHA-1, SHA-2. Однако у MD были выявлены уязвимости: атаки на коллизии (например, для MD5 и SHA-1), а также атаки на расширение длины (length extension attack), которые позволяли злоумышленнику, зная хеш сообщения, вычислить хеш сообщения с добавленным префиксом без знания самого сообщения.

В 2006 году Национальный институт стандартов и технологий США (NIST) объявил конкурс на новый стандарт хеш-функции (SHA-3). В 2007 году команда разработчиков (Бертони, Демен, Питерс, ван Ассхе) представила алгоритм Keccak, основанный на новой конструкции — губке. В 2012 году Keccak был объявлен победителем конкурса, а в 2015 году опубликован как стандарт FIPS 202. С тех пор конструкция губки получила широкое распространение в криптографии, включая использование в блокчейн-технологиях (например, в Ethereum для хеширования Ethash), в постквантовой криптографии (например, в алгоритмах подписи SPHINCS+) и в легковесной криптографии (например, в стандарте ASCON, победившем в конкурсе NIST на легковесные шифры в 2023 году).

¶Принцип работы

Конструкция губки основана на итеративном применении фиксированной перестановки (или преобразования) к внутреннему состоянию. Внутреннее состояние делится на две части: «биты пропускной способности» (rate, r) и «биты ёмкости» (capacity, c). Суммарный размер состояния b = r + c. Обычно b = 1600 бит для Keccak, но возможны варианты (например, 400, 800 бит для лёгких реализаций).

Процесс работы состоит из двух фаз:

1. Абсорбция (Absorbing): входные данные разбиваются на блоки размером r бит. Каждый блок складывается по модулю 2 (XOR) с первыми r битами текущего состояния, после чего к состоянию применяется перестановка f. Если длина входных данных не кратна r, выполняется дополнение (padding) до размера r. Для Keccak используется дополнение «10*1»: добавляется единица, затем необходимое количество нулей, затем ещё одна единица.

1. Выжимание (Squeezing): после обработки всех входных блоков выходные данные извлекаются из первых r бит состояния. Если требуется больше выходных бит, чем r, то после извлечения очередного блока снова применяется перестановка f, и извлекается следующий блок r бит. Процесс продолжается до получения необходимой длины выхода.

Таким образом, конструкция напоминает губку, которая впитывает в себя данные (абсорбция), а затем выдаёт их (выжимание). Отсюда и название.

¶Ключевые параметры

• Пропускная способность (rate, r): количество бит, обрабатываемых за один раунд абсорбции или выжимания. Чем больше r, тем выше скорость, но ниже безопасность.
• Ёмкость (capacity, c): количество бит, которые не участвуют в прямом обмене с входом/выходом. Они определяют стойкость к атакам. Для хеш-функций обычно c = 2n, где n — требуемая длина хеша (например, для SHA3-256 c = 512 бит).
• Перестановка f: это внутреннее преобразование, которое должно быть обратимым и обладать хорошими криптографическими свойствами (стойкость к дифференциальному и линейному криптоанализу). В Keccak перестановка состоит из 24 раундов, каждый из которых включает пять шагов: θ (тета), ρ (ро), π (пи), χ (хи), ι (йота). Эти шаги обеспечивают диффузию, нелинейность и перемешивание битов.

¶Преимущества перед конструкцией Меркла — Дамгора

1. Устойчивость к атаке на расширение длины: в губке выходные данные зависят от всего входного сообщения, включая дополнение, поэтому атака на расширение длины невозможна.
2. Гибкость: одна и та же конструкция может использоваться для хеширования, шифрования (потоковый режим), генерации случайных чисел, аутентификации. Это позволяет создавать универсальные криптографические библиотеки.
3. Произвольная длина выхода: можно получить хеш любой длины (например, 512 бит, 1024 бит), не меняя алгоритм, а лишь увеличивая число циклов выжимания.
4. Параллелизация: при больших размерах состояния (например, b=1600) можно обрабатывать несколько блоков одновременно, хотя в стандартной реализации Keccak это не используется.
5. Доказательства безопасности: для губки существуют формальные доказательства стойкости в модели случайной перестановки, что делает её надёжной при условии, что перестановка f ведёт себя как случайная.

¶Применение

¶Хеш-функции

• SHA-3 (FIPS 202): стандартные хеш-функции SHA3-224, SHA3-256, SHA3-384, SHA3-512, а также функции с расширяемым выходом SHAKE128 и SHAKE256 (SHAKE — Secure Hash Algorithm with Keccak). SHAKE позволяют получать хеш произвольной длины.
• Keccak (исходный алгоритм) используется в некоторых криптовалютах (например, в Ethereum для майнинга до перехода на Proof-of-Stake).

¶Шифрование

• Duplex construction — вариант губки, в котором абсорбция и выжимание чередуются. Это позволяет реализовать аутентифицированное шифрование (AEAD) в одном проходе. Примеры: Keyak, Ketje, NORX (последний не является стандартом, но использовался в конкурсе CAESAR).

¶Постквантовая криптография

• SPHINCS+ — алгоритм цифровой подписи, устойчивый к квантовым атакам. Он использует губку для хеширования и генерации случайных чисел.
• Falcon и Dilithium (победители конкурса NIST) не используют губку напрямую, но в некоторых реализациях применяют SHAKE для хеширования.

¶Легковесная криптография

• ASCON — победитель конкурса NIST на легковесные шифры (2023). Основан на конструкции губки с малым размером состояния (320 бит). Используется для IoT-устройств, RFID-меток и смарт-карт.

¶Блокчейн и криптовалюты

• Ethash — алгоритм доказательства работы (Proof-of-Work) в Ethereum (до перехода на Proof-of-Stake). Использовал Keccak-256 (модифицированная версия SHA3-256) для хеширования заголовков блоков.
• IOTA — использует губку в своей хеш-функции Curl, хотя впоследствии были выявлены уязвимости.

¶Критика и ограничения

1. Скорость: для больших размеров состояния (b=1600) перестановка f требует значительных вычислительных ресурсов. В сравнении с SHA-2 (особенно на аппаратных реализациях с поддержкой AES-NI) SHA-3 может быть медленнее.
2. Сложность реализации: перестановка Keccak включает 24 раунда с пятью шагами, что усложняет оптимизацию для микроконтроллеров с ограниченной памятью.
3. Атаки на уменьшенные раунды: для некоторых вариантов Keccak с меньшим числом раундов (например, 12 вместо 24) были найдены коллизии, но полный 24-раундовый Keccak считается безопасным.
4. Несовместимость с SHA-2: SHA-3 не является заменой SHA-2 по скорости, а скорее альтернативой с другими свойствами безопасности.

¶Интересные факты

• Название «Keccak» происходит от японского слова «кэккаку» (結果), что означает «результат» или «итог».
• В конкурсе SHA-3 участвовало 64 алгоритма, из которых 5 вышли в финал: BLAKE, Grøstl, JH, Keccak и Skein. Keccak победил благодаря своей простоте, гибкости и хорошим показателям безопасности.
• Губка может быть использована не только для хеширования, но и для построения детерминированных генераторов случайных чисел (DRBG) по стандарту NIST SP 800-90A.
• В 2023 году NIST опубликовал стандарт на легковесные криптографические алгоритмы, где ASCON (основанный на губке) стал основным.

¶Источники

• Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2007). Sponge functions. ECRYPT Hash Workshop.
• National Institute of Standards and Technology. (2015). SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions (FIPS PUB 202).
• Daemen, J., & Rijmen, V. (2002). The Design of Rijndael: AES — The Advanced Encryption Standard. Springer.
• NIST. (2023). Lightweight Cryptography Standardization Process: Finalists.
• Bernstein, D. J., et al. (2019). SPHINCS+: Practical Stateless Hash-Based Signatures. In: Advances in Cryptology – EUROCRYPT 2019.