Хэш и хэш-функции¶
Хэш (от англ. hash, дословно — «рубленая мякоть») — это фиксированной длины последовательность битов, получаемая из входных данных произвольного объёма с помощью специального алгоритма — хэш-функции. Ключевое свойство хэширования: результат имеет постоянный размер независимо от объёма исходных данных, а обратное преобразование (восстановление исходных данных по хэшу) практически невозможно. Хэши широко применяются в информатике, криптографии и информационной безопасности.
¶Хэш-функции
Хэш-функция — это математическая функция, отображающая входное сообщение произвольной длины в выходное значение (хэш, дайджест, отпечаток) фиксированной длины. Основные свойства, которые предъявляются к криптографическим хэш-функциям:
- Детерминированность — одно и то же входное сообщение всегда даёт один и тот же хэш.
- Необратимость — вычислить исходное сообщение по его хэшу вычислительно нецелесообразно.
- Авангардная устойчивость (устойчивость к столкновениям) — трудно подобрать два разных сообщения с одинаковым хэшем.
- Лавинный эффект — изменение одного бита входных данных приводит к существенному изменению выходного значения.
¶Основные алгоритмы
| Алгоритм | Год | Длина хэша, бит | Статус |
|---|---|---|---|
| MD5 | 1992 | 128 | Устарел, криптографически небезопасен |
| SHA-1 | 1995 | 160 | Устарел, коллизии найдены (2017) |
| SHA-2 (SHA-256, SHA-512) | 2001 | 256 / 512 | Актуален |
| SHA-3 (Keccak) | 2015 | 224–512 | Актуален |
| BLAKE2 / BLAKE3 | 2012 / 2020 | до 512 | Актуален |
| ГОСТ Р 34.11-2012 (Стрибог) | 2012 | 256 / 512 | Национальный стандарт РФ |
В России действует национальный стандарт ГОСТ Р 34.11-2012 («Стрибог»), разработанный Академией криптографии Российской Федерации и введённый взамен ГОСТ Р 34.11-94. Алгоритм поддерживает длину выхода 256 и 512 бит и применяется в криптографических средствах, сертифицированных в России.
¶Способы хэширования
¶Простое (некриптографическое) хэширование
Используется в хэш-таблицах для быстрого поиска данных. Требования к таким функциям иные: важна скорость, а не необратимость. К ним относятся CRC32, MurmurHash, xxHash. Коллизии (совпадения хэшей разных данных) допускаются и разрешаются методами цепочек или открытой адресации.
¶Криптографическое хэширование
Применяется там, где важна необратимость и устойчивость к подбору: цифровые подписи, пароли, целостность файлов, блокчейны. Криптографическая хэш-функция строится на основе блочных шифров (MD5, SHA-1, SHA-2 на базе AES-подобных конструкций) либо на основе перестановочных операций (SHA-3 на базе «губки» Keccak).
¶Применение
¶Целостность данных
Хэш позволяет обнаружить изменение файла. Передача файла сопровождается передачей его хэша; получатель вычисляет хэш заново и сравнивает. Распространённые утилиты: md5sum, sha256sum, certutil в Windows.
¶Хранение паролей
Вместо самих паролей в базе данных хранятся их хэши. Для защиты от перебора применяются медленные функции (bcrypt, scrypt, Argon2) и «соль» — случайное значение, добавляемое к паролю перед хэшированием, чтобы одинаковые пароли давали разные хэши.
¶Цифровые подписи
Подпись сообщения часто вычисляется не от самого сообщения, а от его хэша — это ускоряет процесс и позволяет подписывать сообщения любой длины.
¶Блокчейны
В блокчейне Bitcoin хэш-функция SHA-256 используется для связывания блоков в цепочку и для майнинга: майнер подбирает nonce, чтобы хэш блока удовлетворял заданному условию (имел определённое количество ведущих нулей).
¶Идентификация файлов
Хэши используются как уникальные идентификаторы файлов в системах контроля версий, пиринговых сетях (BitTorrent использует SHA-1 для идентификации раздач) и базах данных вредоносного ПО.
¶Коллизии и атаки
Коллизия — это случай, когда два разных входных сообщения дают одинаковый хэш. Для криптографических функций это критично. В 2004 году китайские исследователи Вэй Ван и Сяоюнь Ван продемонстрировали практическую атаку на MD5, а в 2017 году группа Google и Института Макса Планка объявила о первом реальном столкновении для SHA-1 (проект SHAttered). В результате SHA-1 был официально признан небезопасным, а стандарты (например, RFC 6234) рекомендуют переходить на SHA-2 и SHA-3.
¶Интересные факты
- Хэш-функции названы по аналогии с «рубленой» кашей: данные перемешиваются до неузнаваемости.
- Даже небольшое изменение входных данных полностью меняет результат: хэш слова «привет» не имеет отношения к хэшу слова «привет!».
- В криптографии длина хэша определяет устойчивость к атаке «дня рождения»: для 128-битного хэша ожидаемое число попыток для нахождения коллизии — около 2⁶⁴.
Источники:
- Менялов В. С., Смирнов А. В. «Криптографические хэш-функции»
- ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хэширования»
- NIST FIPS 180-4: Secure Hash Standard (SHS)
- Stevens M. et al. «The first collision for full SHA-1» (SHAttered, 2017)
- Schneier B. «Applied Cryptography»
