SHA-3

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

История

Конкурс NIST

В 2005 году были опубликованы первые успешные атаки на SHA-1, что подорвало доверие к этому стандарту. Хотя SHA-2 (SHA-224/256/384/512) на тот момент считался стойким, NIST решил провести открытый конкурс на разработку нового хеш-алгоритма, чтобы застраховаться на случай будущих уязвимостей SHA-2. Конкурс начался в 2007 году, на него было подано 64 заявки. После серии раундов отбора и публичного криптоанализа в 2012 году победителем был объявлен алгоритм Keccak, разработанный группой криптографов (Гвидо Бертони, Жоан Деймен, Михаэль Петерс и Жиль Ван Аше).

Стандартизация

В августе 2015 года NIST опубликовал стандарт FIPS PUB 202, официально утвердив SHA-3. В стандарт вошли четыре хеш-функции (SHA3-224, SHA3-256, SHA3-384, SHA3-512) и две функции расширяемого вывода (SHAKE128 и SHAKE256). SHA-3 не предназначен для полной замены SHA-2, а предлагается как альтернатива, особенно полезная в устройствах с ограниченными ресурсами и в приложениях, где требуется устойчивость к атакам на основе коллизий.

Устройство и принцип работы

Губчатая конструкция

В отличие от SHA-1 и SHA-2, которые построены на основе конструкции Меркла-Дамгора, SHA-3 использует губчатую конструкцию (sponge construction). Она состоит из двух фаз:

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

Такая архитектура позволяет SHA-3 быть более гибким: одна и та же функция может выдавать хеш любой длины, а также работать как потоковый шифр или генератор псевдослучайных чисел.

Функция перестановки Keccak-f

Основой SHA-3 является семейство перестановок Keccak-f, которые работают с трёхмерным массивом битов (5×5×w, где w — 1, 2, 4, 8, 16, 32 или 64). Для SHA-3 используется w=64, что даёт состояние размером 1600 бит. Перестановка состоит из 24 раундов, каждый из которых включает пять шагов:

• θ (theta): побитовый XOR с соседними столбцами для диффузии.
• ρ (rho): циклический сдвиг строк.
• π (pi): перестановка битов внутри массива.
• χ (chi): нелинейное преобразование (замена битов на основе их соседей).
• ι (iota): добавление константы раунда для разрушения симметрии.

Эта конструкция обеспечивает высокую устойчивость к известным криптоаналитическим атакам.

Виды и параметры

Стандартные хеш-функции (SHA3-224, SHA3-256, SHA3-384, SHA3-512)

Эти функции являются прямыми аналогами SHA-2 по длине выхода, но имеют разную внутреннюю ёмкость (c). Ёмкость — это часть состояния, которая не модифицируется входными данными и определяет стойкость к атакам:

Функции расширяемого вывода (SHAKE128, SHAKE256)

SHAKE (Secure Hash Algorithm Keccak) позволяют получать хеш произвольной длины (кратной 8 битам). Они имеют фиксированную скорость (1344 бита для SHAKE128 и 1088 бит для SHAKE256) и разную ёмкость (256 и 512 бит соответственно). SHAKE128 обеспечивает 128-битный уровень безопасности, SHAKE256 — 256-битный.

Применение

Криптовалюты и блокчейн

SHA-3 используется в некоторых криптовалютах, например, в Ethereum (консенсусный алгоритм Ethash основан на Keccak-256, который является модификацией SHA-3) и в Monero (использует CryptoNight, частично основанный на Keccak). Также SHA-3 применяется для хеширования транзакций и создания адресов.

Цифровые подписи и сертификаты

Стандарт NIST рекомендует SHA-3 для использования в алгоритмах цифровой подписи (DSA, ECDSA, EdDSA). Некоторые центры сертификации начали включать SHA-3 в свои корневые сертификаты.

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

SHA-3 считается устойчивым к атакам с использованием квантовых компьютеров (квантовый алгоритм Гровера позволяет ускорить поиск коллизий, но не отменяет стойкость губчатой конструкции). Поэтому SHA-3 часто используется в постквантовых криптосистемах, например, в подписи SPHINCS+.

Встраиваемые системы и аппаратное обеспечение

Благодаря компактной реализации и низкому энергопотреблению SHA-3 популярен в смарт-картах, RFID-метках, датчиках Интернета вещей (IoT) и других устройствах с ограниченными ресурсами.

Критика и сравнение с SHA-2

Производительность

На программном уровне SHA-3 в среднем медленнее SHA-2 на 20-50% на современных процессорах. Это связано с более сложной внутренней структурой и отсутствием аппаратного ускорения в большинстве CPU (в отличие от SHA-2, для которого существуют инструкции SHA-NI). Однако на аппаратном уровне (FPGA, ASIC) SHA-3 может быть быстрее и компактнее.

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

SHA-3 спроектирован с большим запасом прочности. На 2024 год не опубликовано ни одной практической атаки на полный раундовый SHA-3, превосходящей полный перебор. Для SHA-2 также нет публичных атак, но теоретически его конструкция Меркла-Дамгора более уязвима для некоторых типов атак (например, атаки удлинения сообщения).

Атака удлинения сообщения

SHA-2 подвержен атаке удлинения сообщения: зная хеш сообщения, можно вычислить хеш сообщения с добавленным суффиксом без знания исходного текста. SHA-3 устойчив к этой атаке благодаря губчатой конструкции, что делает его предпочтительным для HMAC и некоторых протоколов аутентификации.

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

• Алгоритм Keccak был назван в честь японского чая «кетчак» (keccak), который авторы пили во время разработки.
• В стандарте NIST были внесены небольшие изменения в оригинальный Keccak: увеличено количество раундов с 12 до 24 и изменена функция дополнения (padding). Это сделано для повышения запаса безопасности.
• SHA-3 является первым криптографическим стандартом, который включает функции расширяемого вывода (SHAKE), что позволяет использовать его не только как хеш-функцию, но и как генератор псевдослучайных чисел или потоковый шифр.

Источники

• National Institute of Standards and Technology. (2015). FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions.
• Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2013). The Keccak reference.
• NIST. (2007). Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3).
• Bernstein, D. J., & Lange, T. (2017). Post-quantum cryptography. Springer.