Криптография
Семейство SHA
2008 год: исследователи создали поддельный промежуточный CA-сертификат с подписью на базе MD5. Этот сертификат был бы признан легитимным любым браузером. 2017 год: Google создал два разных PDF с одинаковым SHA-1. Индустрия мигрировала за год. Сегодня SHA-256 и SHA-3 - ответ на этот опыт.
- **Bitcoin**: double SHA-256 для proof-of-work. Сложность настроена так, что в мире производится ~500 экзахэшей SHA-256 в секунду (2024).
- **TLS-сертификаты**: CA/Browser Forum запретил SHA-1 с 2017, SHA-256 обязателен. Let's Encrypt выдаёт ~3 млн сертификатов в день, все с SHA-256.
- **CRYSTALS-Kyber (ML-KEM)**: стандарт NIST 2024 для постквантового KEM использует SHAKE-128/256 для генерации матриц и NTT. Уже встроен в OpenSSL 3.2+.
- **Android Keystore**: SHA-256 для подписи APK. Google Play требует SHA-256 для новых приложений с 2017 года.
MD5: полностью сломан
MD5 разработан Роном Ривестом в 1991 году, 128-битный хэш. Первые теоретические атаки появились в 1993 году. В 2004 году Ван Сяоюнь опубликовала practical collision attack. В 2008 году команда Сауэра создала поддельный CA-сертификат с MD5-подписью - это означало полный взлом PKI.
MD5 категорически запрещён для криптографических целей: подписи, аутентификация, хэширование паролей. NIST вывел MD5 из одобренных алгоритмов. Единственное допустимое использование - некриптографические checksums (проверка целостности без угрозы атаки).
В чём критичность атаки на MD5 2008 года с CA-сертификатом?
SHA-1: атака SHAttered
SHA-1 (NIST, 1993) - 160-битный хэш на основе Merkle-Damgard. В 2017 году Google и CWI Amsterdam опубликовали SHAttered: первую practical chosen-prefix collision. Два разных PDF-файла с одинаковым SHA-1. Вычисления заняли 9 квинтиллионов SHA-1-операций (~6500 CPU-лет или 110 GPU-лет).
После SHAttered: браузеры перестали принимать TLS-сертификаты с SHA-1 подписью. GitHub добавил SHA-1 collision detection. Git переходит на SHA-256 объектный формат (git hash-object --object-format=sha256). CA/Browser Forum запретил SHA-1 в сертификатах с 2017 года.
Почему SHAttered атака на SHA-1 опасна для цифровых подписей?
SHA-256: рабочая лошадка современной криптографии
SHA-256 (NIST, 2001) - 256-битный хэш из семейства SHA-2. Merkle-Damgard с 512-битными блоками и 64 раундами на основе функций Ch, Maj, Sigma. Семейство SHA-2 включает SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256.
Intel и AMD добавили SHA-NI инструкции (SHA256MSG1, SHA256MSG2, SHA256RNDS2) в 2013 и 2017 годах соответственно. Это ускоряет SHA-256 в 3-6 раз. Apple M1/M2 также имеют аппаратное ускорение SHA-256 - один из причин быстрых Git-операций на Mac.
Почему SHA-256 из семейства SHA-2 всё ещё считается безопасным, несмотря на ту же Merkle-Damgard конструкцию, что и SHA-1?
SHA-3/Keccak: новая парадигма
SHA-3 (Keccak) выиграл конкурс NIST SHA-3 Competition в 2012 году (из 51 кандидата). Авторы: Bertoni, Daemen, Peeters, Van Assche. Стандартизирован в 2015 (FIPS 202). Принципиально иная конструкция - Sponge вместо Merkle-Damgard.
SHA-3 медленнее SHA-256 на CPU без аппаратного ускорения (~150 MB/s vs 250 MB/s), но быстрее в аппаратуре и не требует специальных инструкций. SHAKE используется в постквантовых алгоритмах CRYSTALS-Kyber и CRYSTALS-Dilithium (NIST стандарты 2024).
Что такое SHAKE128 и SHAKE256?
Ключевые идеи
- **MD5 сломан**: коллизии за секунды. Запрещён для криптографических применений. Допустим только для некриптографических checksums.
- **SHA-1 сломан**: атака SHAttered (2017) = практическая chosen-prefix коллизия. Запрещён в TLS-сертификатах и подписях.
- **SHA-256**: рабочий стандарт, 128-битная collision resistance, аппаратное ускорение SHA-NI. Семейство SHA-2 не имеет известных практических атак.
- **SHA-3/Keccak**: Sponge-конструкция, нет length extension, SHAKE дают XOF. Основа постквантовых стандартов NIST 2024.
Связанные темы
SHA-семейство используется как строительный блок повсюду:
- HMAC и MAC — HMAC строится на хэш-функции. HMAC-SHA256 - стандарт для аутентификации сообщений в TLS, JWT, API подписях.
- Хэш-функции: основы — Математические свойства (preimage, collision, birthday bound) - теоретическая база для понимания практик SHA-семейства.
- Постквантовая криптография — CRYSTALS-Kyber и Dilithium используют SHAKE-128/256 (SHA-3 XOF) как основной примитив.
Вопросы для размышления
- Если SHA-256 тоже построен на Merkle-Damgard как SHA-1, почему в нём не найдено аналогичных коллизий за 20+ лет?
- Bitcoin использует SHA-256(SHA-256(x)). Что это даёт по сравнению с одним SHA-256 и есть ли в этом смысл?
- SHAKE-256 выдаёт хэш произвольной длины. Безопаснее ли 512-битный вывод SHAKE-256 чем SHA3-512?