Криптография
Хэш-функции
Git, blockchain, TLS, PKI - везде хэш-функции. Bitcoin использует SHA-256 для доказательства работы - каждый блок содержит хэш предыдущего, создавая цепочку. Атака SHAttered в 2017 году создала два PDF-файла с одинаковым SHA-1 хэшем. Google это анонсировал, и индустрия за год мигрировала на SHA-256.
- **Git**: SHA-1 для идентификации объектов (коммиты, блобы, деревья). После SHAttered GitHub добавил обнаружение SHA-1 коллизий и начал переход на SHA-256.
- **Bitcoin**: двойной SHA-256 (SHA-256(SHA-256(block_header))) для proof-of-work. Сложность подбирается так, чтобы хэш начинался с N нулей.
- **TLS-сертификаты**: SHA-256 подпись в цепочке CA. Браузеры отвергают сертификаты, подписанные SHA-1, с 2017 года.
- **CRYSTALS-Kyber**: SHAKE-128/256 (XOF на основе SHA-3 Sponge) для генерации матриц в постквантовом алгоритме, стандартизированном NIST в 2024.
Три свойства криптографического хэша
Криптографическая хэш-функция H отображает произвольный вход в фиксированный вывод (дайджест). Три формальных свойства определяют криптографическую пригодность: preimage resistance, second preimage resistance и collision resistance.
Git использует SHA-1 для идентификации коммитов. SHA-1 collision resistance сломана в 2017 (атака SHAttered: два PDF с одним SHA-1). Но для Git это означает лишь теоретическую возможность создать два коммита с одним ID - не подделку чужих коммитов. GitHub мигрировал на SHA-256 в 2023.
Почему collision resistance сложнее obтрудиться, чем preimage resistance?
Конструкция Merkle-Damgard
Merkle-Damgard (MD) - итеративная конструкция, на которой построены MD5, SHA-1, SHA-256. Сообщение разбивается на блоки и обрабатывается последовательно через компрессионную функцию f с цепным значением IV.
Length extension attack: если сервер проверяет HMAC как H(secret || message), злоумышленник знающий H(secret || message) может вычислить H(secret || message || extension) без знания secret. SHA-256 уязвима. Именно поэтому HMAC строится как H(k XOR opad || H(k XOR ipad || m)), а не H(k || m).
Какая уязвимость присуща конструкции Merkle-Damgard?
Sponge-конструкция: основа SHA-3
Sponge-конструкция (SHA-3/Keccak, 2015) принципиально отличается от Merkle-Damgard. Состояние разделено на rate (r) и capacity (c). Фаза absorb XOR-ит входные блоки в rate-часть и применяет перестановку f. Фаза squeeze читает выход из rate-части.
SHAKE128 и SHAKE256 - XOF (eXtendable Output Functions) на основе Sponge. Выдают хэш произвольной длины. Используются в CRYSTALS-Kyber (постквантовое шифрование, стандарт NIST 2024) для генерации матриц и масок.
Почему SHA-3 не уязвима к length extension атаке в отличие от SHA-256?
Birthday Bound: математика коллизий
Birthday paradox: в группе из 23 человек вероятность совпадения дня рождения > 50%. Аналогично: среди ~2^(n/2) хэшей от случайных входов вероятность коллизии превышает 50%. Это фундаментальное ограничение для любой хэш-функции с n-битным выходом.
Практический вывод: для n-битной безопасности нужен 2n-битный хэш. SHA-256 даёт 128-битную collision resistance, SHA-512 - 256-битную. NIST требует SHA-256 или выше для сертификации до 2030 года.
SHA-256 обеспечивает 256-битную безопасность против всех атак
Против коллизий SHA-256 даёт только 128-битную безопасность из-за birthday bound. Против preimage - 256 бит.
Birthday paradox снижает стойкость к коллизиям вдвое относительно размера хэша. Для разных свойств хэша разная эффективная безопасность.
Какую collision resistance в битах обеспечивает SHA-256?
Ключевые идеи
- **Три свойства**: preimage resistance (2^n), second preimage resistance (2^n), collision resistance (2^(n/2)). Коллизии слабее из-за birthday paradox.
- **Merkle-Damgard** (SHA-256, SHA-1, MD5): уязвима к length extension attack. HMAC решает проблему правильной конструкцией.
- **Sponge** (SHA-3): capacity-часть изолирована от входа - нет length extension. SHAKE дают XOF произвольной длины.
- **Birthday bound**: для n-битного хэша collision resistance = 2^(n/2). SHA-256 = 128-битная collision security.
Связанные темы
Хэш-функции - строительный блок для MAC, подписей и протоколов:
- SHA-2 и SHA-3 — Конкретные алгоритмы семейства: SHA-256, SHA-384, SHA-512, SHA3-256. Детали внутренней структуры и когда что выбирать.
- HMAC и MAC — HMAC строится на хэш-функции, но исправляет length extension. MAC обеспечивает аутентификацию сообщений.
- Цифровые подписи — Подпись применяется к хэшу сообщения, а не к самому сообщению. Безопасность подписи зависит от collision resistance хэша.
Вопросы для размышления
- Почему подпись документа применяется к хэшу, а не к самому документу? Что произойдёт при коллизии хэша?
- Атака SHAttered создала коллизию SHA-1 за 2^63 операций. Какой реальный ущерб это наносит системам, использующим SHA-1 для подписей?
- Чем SHAKE-256 отличается от SHA3-256 и когда стоит использовать XOF вместо фиксированного хэша?