SHA-256 или SHA-3: структура Меркла — Дамгора или губка

Сравнение SHA-256 и SHA-3 — это сравнение рабочей лошадки семейства SHA-2 со стандартом на основе Keccak, который NIST опубликовал в 2015 году. Ни одна из этих функций не взломана, и до взлома им далеко, а при выходе длиной 256 бит обе обеспечивают одинаковую номинальную стойкость. Различаются они внутренним устройством, и от него зависят возможность удлинения сообщения, скорость и то, как функции используются внутри новых алгоритмов.

Коротко о главном

Пропускная способность измерена командой openssl speed -evp на одном ядре Apple M4 Max, у которого есть аппаратная поддержка обоих семейств.

Устройство

SHA-256 обрабатывает сообщение блоками по 64 байта и подаёт каждый блок в функцию сжатия вместе с предыдущим 256-битным состоянием; итоговое состояние и есть дайджест. Поскольку дайджест — это всё внутреннее состояние целиком, любой, кто знает SHA-256(x) и длину x, может продолжить хеширование и вычислить SHA-256(x ‖ padding ‖ y), не зная x. Такое удлинение сообщения безвредно для подписей и HMAC, но ломает наивные MAC вроде SHA-256(key ‖ message).

SHA-3 — это губка: она впитывает входные данные в 1600-битное состояние с помощью перестановки Keccak-f и выжимает выход из части этого состояния. У SHA3-256 скорость (rate) составляет 1088 бит состояния, а ёмкость (capacity) — 512 бит; ёмкость никогда не попадает в выход, поэтому удлинение сообщения невозможно, а SHA3-256(key ‖ message) — корректный MAC (именно для этого NIST стандартизирует KMAC). Та же губка даёт функции с расширяемым выходом SHAKE128 и SHAKE256, с помощью которых постквантовые алгоритмы разворачивают seed в матрицы и шум.

NIST выбрал Keccak в 2012 году по итогам пятилетнего конкурса, который начался, когда атаки на MD5 и SHA-1 вызвали опасения за SHA-2 с её похожей структурой. Эти опасения не подтвердились: лучшие атаки на SHA-256 находят коллизии примерно для 31 шага из 64, а у полной функции слабостей не обнаружено. Поэтому SHA-3 — страховка, а не замена.

Скорость

На Apple M4 Max инструкции есть для обоих семейств, и всё же на длинных входных данных SHA-256 почти втрое быстрее: около 2,85 ГБ/с против 1,01 ГБ/с у SHA3-256 в OpenSSL 3.6.5, а у SHA3-512 — 0,53 ГБ/с. На процессорах x86 с расширениями SHA картина похожая; на процессорах без инструкций для хеширования SHA-3 и SHA-256 ближе друг к другу, а BLAKE2 или BLAKE3 быстрее обеих. В большинстве приложений любая из этих функций намного быстрее окружающего её ввода-вывода; разница важна при хешировании очень больших файлов, в деревьях Меркла и блокчейнах.

SHA3-256 — не Keccak-256

В Ethereum начали использовать Keccak ещё до того, как FIPS 202 стал окончательным, а затем в FIPS 202 изменили дополнение (добавили биты разделения доменов). У двух функций общая перестановка, но их дайджесты никак не связаны между собой. keccak256 в Solidity, RPC-метод web3_sha3, а также все адреса Ethereum, селекторы функций и дайджесты EIP-712 используют Keccak-256. Если в коде для Ethereum вызвать SHA3-256 из библиотеки, результаты будут неверными, причём без какой-либо ошибки.

import { createHash } from "node:crypto";
import { keccak_256 } from "@noble/hashes/sha3.js";

const input = Buffer.from("abc");
console.log("SHA-256   ", createHash("sha256").update(input).digest("hex"));
console.log("SHA3-256  ", createHash("sha3-256").update(input).digest("hex"));
console.log("Keccak-256", Buffer.from(keccak_256(input)).toString("hex"));

SHA-256    ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
SHA3-256   3a985da74fe225b2045c172d6bd390bd855f086e3e9d525b46bfe24511431532
Keccak-256 4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45

Значения SHA-256 и SHA3-256 совпадают с примерами для «abc» из FIPS 180-4 и FIPS 202.

Что когда выбирать

• Совместимость с протоколами (TLS, сертификаты, JWT, SSH, Git, менеджеры пакетов, Bitcoin): SHA-256, потому что именно её вычисляет другая сторона.
• Хеширование с ключом: подходит HMAC-SHA256, как и HMAC с любым другим хешем SHA-2; если вы предпочитаете простую конструкцию с ключом, KMAC или SHA-3 с ключом обходятся без двойного прохода HMAC.
• Разворачивание seed, детерминированные псевдослучайные потоки, выход переменной длины: SHAKE256 или SHAKE128.
• Постквантовые алгоритмы: то, что жёстко задаёт стандарт; ML-KEM и ML-DSA используют SHA3 и SHAKE, поэтому библиотеки, которые их реализуют, уже содержат SHA-3.
• Ethereum: Keccak-256 и никогда не SHA3-256 из FIPS.
• Второй хеш с принципиально другим устройством для эшелонированной защиты (например, двойное хеширование долгосрочных архивов): SHA-3 вместе с SHA-256.
• Максимальная скорость без требования FIPS: BLAKE2 или BLAKE3 на процессорах без инструкций для хеширования.

Заметки о миграции

Смена хеш-функции меняет все дайджесты, поэтому это изменение формата, а не просто замена библиотеки.

1. Указывайте версию в идентификаторе: записывайте алгоритм рядом с каждым дайджестом (sha256:, sha3-256:, multihash, OID), как это делают системы с адресацией по содержимому, например реестры контейнеров и SRI.
2. На переходный период публикуйте оба дайджеста: вычисляйте оба, проверяйте тот, который известен потребителю, и выводите старый из обращения, когда потребители обновятся.
3. Проверьте предположения об удлинении сообщения: если код строит MAC как hash(secret ‖ message), переход на SHA-3 это исправит, но переход на HMAC исправит это и для SHA-256.
4. Следите за усечением и кодировками: дайджесты передаются в шестнадцатеричном виде, в base64 или base64url, и несовпадение кодировок встречается чаще, чем несовпадение алгоритмов.
5. Не переходите только из-за квантовой угрозы: против алгоритма Гровера обе функции сохраняют стойкость к нахождению прообраза не ниже 128 бит, а проект плана перехода NIST оставляет в силе обе.

Источники

• FIPS 180-4, стандарт безопасного хеширования (Secure Hash Standard)
• FIPS 202, стандарт SHA-3
• NIST SP 800-185: функции cSHAKE, KMAC, TupleHash и ParallelHash
• NIST SP 800-107 Rev. 1, применение одобренных алгоритмов хеширования
• NIST IR 8547 ipd, таблица 7 (стойкость хеш-функций)
• RFC 2104, HMAC