SHAKE256

SHAKE256 — это криптографическая хеш-функция с переменной длиной выхода, принадлежащая к семейству SHA-3 (Secure Hash Algorithm 3). Она основана на конструкции губки (sponge construction) и использует алгоритм Keccak, который был выбран Национальным институтом стандартов и технологий США (NIST) в 2012 году в качестве нового стандарта хеширования. В отличие от классических хеш-функций, таких как SHA-256, SHAKE256 не имеет фиксированной длины выхода: она может генерировать дайджест (хеш-значение) произвольной длины, что делает её универсальным инструментом для задач, требующих как хеширования, так и генерации псевдослучайных последовательностей.

История и стандартизация

Разработка SHAKE256 началась в рамках конкурса NIST на новый стандарт хеширования, объявленного в 2007 году после выявления уязвимостей в SHA-1. В 2012 году победителем был объявлен алгоритм Keccak, созданный бельгийскими криптографами Гвидо Бертони, Жоаном Дайменом, Микаэлем Питерсом и Жилем ван Ассхе. В 2015 году NIST опубликовал стандарт FIPS PUB 202, в который вошли четыре фиксированные хеш-функции (SHA-3-224, SHA-3-256, SHA-3-384, SHA-3-512) и две функции с переменной длиной выхода — SHAKE128 и SHAKE256. SHAKE256 была определена как более безопасная версия с уровнем защищённости, сопоставимым с SHA-512, но с возможностью адаптации длины выхода под конкретные нужды.

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

SHAKE256 основана на конструкции губки, которая состоит из двух фаз: впитывания (absorbing) и выжимания (squeezing). В отличие от традиционных итеративных хеш-функций, использующих сжатие, губка поглощает входные данные блоками, а затем выдаёт выходные данные произвольной длины.

Параметры алгоритма

• Состояние (state): 1600 бит (200 байт), организованных в трёхмерный массив размером 5×5×64 бита.
• Скорость (rate): 1088 бит (136 байт) для SHAKE256. Это количество бит, которое обрабатывается за один цикл.
• Ёмкость (capacity): 512 бит (64 байта). Эта часть состояния остаётся неизменной во время впитывания и выжимания и определяет стойкость алгоритма.
• Число раундов: 24 раунда преобразования Keccak-f[1600] для каждого блока.

Фаза впитывания

Входное сообщение дополняется до длины, кратной размеру блока (rate). Для SHAKE256 используется специфическое дополнение: к сообщению добавляется байт 0x1F (для обозначения принадлежности к семейству SHAKE), затем минимальное количество нулевых бит, чтобы длина стала кратной rate, и завершающий байт 0x80. После дополнения сообщение разбивается на блоки по 1088 бит. Каждый блок последовательно накладывается операцией XOR на первые 1088 бит состояния, после чего выполняется 24 раунда преобразования Keccak-f[1600].

Фаза выжимания

После обработки всех входных блоков начинается фаза выжимания. Первые 1088 бит состояния выдаются как первые 136 байт выхода. Если запрошенная длина выхода превышает 136 байт, выполняется дополнительный раунд Keccak-f[1600], и следующие 1088 бит состояния выдаются как следующий блок. Процесс повторяется до тех пор, пока не будет сгенерировано необходимое количество байт.

Криптографические свойства

Стойкость

SHAKE256 обеспечивает следующие уровни безопасности:

• Стойкость к коллизиям: до 256 бит (для выхода длиной не менее 512 бит). Это означает, что для нахождения двух сообщений с одинаковым хешем требуется около 2^256 операций.
• Стойкость к прообразу: до 256 бит (для выхода длиной не менее 256 бит). Нахождение сообщения по заданному хешу требует около 2^256 операций.
• Стойкость ко второму прообразу: до 256 бит.

Важно отметить, что если запрошенная длина выхода меньше 256 бит, стойкость соответственно снижается. Например, для 128-битного выхода стойкость к коллизиям составляет 64 бита.

Устойчивость к атакам

SHAKE256, как и весь семейство SHA-3, устойчива к известным типам атак, включая:

• Атаки удлинения сообщения: конструкция губки не позволяет злоумышленнику, зная хеш сообщения, вычислить хеш сообщения с добавленным суффиксом без знания исходного сообщения.
• Дифференциальные атаки: 24 раунда Keccak-f[1600] обеспечивают достаточное перемешивание для предотвращения эффективных дифференциальных атак.
• Квантовые атаки: алгоритм Гровера может сократить сложность поиска прообраза до O(2^(n/2)), но для SHAKE256 с 256-битной стойкостью это всё равно требует 2^128 операций, что считается практически невозможным при текущем уровне развития квантовых компьютеров.

Применение

Криптографические протоколы

SHAKE256 используется в ряде современных криптографических стандартов и протоколов:

• Ed25519 и Ed448: схемы цифровой подписи на основе эллиптических кривых, где SHAKE256 используется для хеширования сообщений и генерации ключей.
• Kyber: алгоритм постквантовой криптографии, выбранный NIST для стандартизации в 2022 году, использует SHAKE256 для генерации псевдослучайных последовательностей.
• Dilithium: ещё один постквантовый алгоритм подписи, также основанный на SHAKE256.
• X.509: сертификаты могут использовать SHAKE256 для подписей.

Генерация псевдослучайных чисел

Благодаря возможности выжимания произвольного количества данных, SHAKE256 может использоваться как криптографически стойкий генератор псевдослучайных чисел (DRBG). Например, в стандарте NIST SP 800-90A она определена как один из источников случайности.

Хеширование сообщений

SHAKE256 применяется для создания дайджестов сообщений в системах, где требуется высокая стойкость, но при этом длина хеша может варьироваться. Например, в блокчейн-проектах, где требуется хеширование транзакций с определённым уровнем безопасности.

Аутентификация

В протоколах аутентификации, таких как HMAC-SHAKE256, функция используется для создания кодов аутентичности сообщений (MAC). HMAC-SHAKE256 определена в стандарте NIST SP 800-185.

Сравнение с другими хеш-функциями

SHA-256

SHA-256 — классическая хеш-функция с фиксированным выходом 256 бит. SHAKE256 обеспечивает аналогичный уровень стойкости, но позволяет генерировать выход произвольной длины. Кроме того, SHAKE256 устойчива к атакам удлинения сообщения, в отличие от SHA-256. Однако SHA-256 имеет более высокую скорость на некоторых аппаратных платформах благодаря оптимизированным реализациям.

SHA-512

SHA-512 имеет выход 512 бит и стойкость 256 бит. SHAKE256 с выходом 512 бит обеспечивает такую же стойкость, но при этом может быть более гибкой. Однако SHA-512 может быть быстрее на 64-битных процессорах.

SHA-3-256

SHA-3-256 — фиксированная версия SHA-3 с выходом 256 бит. Она использует те же параметры, что и SHAKE256, но с другим дополнением (0x06 вместо 0x1F). SHAKE256 с выходом 256 бит функционально эквивалентна SHA-3-256, но с дополнительной возможностью изменения длины.

Реализации

SHAKE256 реализована во многих криптографических библиотеках:

• OpenSSL: начиная с версии 1.1.1, поддерживает SHAKE256 через интерфейс EVP.
• Libsodium: предоставляет функции для SHAKE256.
• Bouncy Castle: реализация для Java и C#.
• PyCryptodome: библиотека для Python.
• RustCrypto: набор реализаций для Rust.

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

Основным недостатком SHAKE256 является её сравнительно низкая скорость на программных реализациях по сравнению с SHA-256 и SHA-512. Это связано с большим внутренним состоянием (1600 бит) и 24 раундами преобразования на каждый блок. Однако на аппаратных платформах, особенно с поддержкой инструкций SHA-3 (например, Intel SHA-NI), скорость может быть сопоставима.

Другим ограничением является сложность реализации: конструкция губки требует большего объёма памяти для хранения состояния, чем традиционные хеш-функции. Это может быть критично для встраиваемых систем с ограниченными ресурсами.

Источники

1. National Institute of Standards and Technology. FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. 2015.
2. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. The Keccak Reference. 2011.
3. National Institute of Standards and Technology. NIST SP 800-185: SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash. 2016.
4. National Institute of Standards and Technology. NIST SP 800-90A: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. 2015.
5. Bernstein, D. J., Lange, T. Post-Quantum Cryptography. Springer, 2017.