Хэш-функция
Хэш-функция — это математическая функция или алгоритм, преобразующий произвольный набор данных (входное сообщение, файл, пароль) в битовую строку фиксированной длины, называемую хэш-суммой, хэш-кодом или дайджестом. Основное свойство хэш-функции — необратимость: по полученному хэшу практически невозможно восстановить исходные данные. Хэш-функции широко применяются в криптографии, информатике, системах хранения данных и цифровых подписях.
Основные свойства
Хэш-функции должны удовлетворять ряду требований, обеспечивающих их практическую применимость и безопасность:
- Детерминированность: для одного и того же входного сообщения функция всегда возвращает одинаковый хэш.
- Высокая скорость вычисления: алгоритм должен работать быстро для любых объёмов входных данных.
- Лавинный эффект: незначительное изменение входных данных (например, изменение одного бита) приводит к кардинально отличающемуся хэшу, не похожему на исходный.
- Стойкость к коллизиям: практически невозможно найти два разных входных сообщения, дающих одинаковый хэш (слабая коллизионная стойкость — трудно найти пару сообщений с одинаковым хэшем; сильная — трудно найти любое второе сообщение для заданного хэша).
- Необратимость (однонаправленность): по известному хэшу вычислительно невозможно восстановить исходное сообщение, кроме как полным перебором всех возможных вариантов.
История
Первые упоминания о хэш-функциях относятся к 1950-м годам, когда они использовались для организации хэш-таблиц в программировании (Ганс Петер Лун, 1953). Однако криптографические хэш-функции начали активно развиваться в 1970-х годах с появлением алгоритмов MD2, MD4 и MD5 (Рон Ривест, 1989–1991). MD5 долгое время был стандартом, но к 2004 году были найдены коллизии, и его признали небезопасным.
В 1993 году Национальный институт стандартов и технологий США (NIST) опубликовал SHA-0, затем SHA-1 (1995). К 2005 году были обнаружены атаки на SHA-1, что привело к разработке SHA-2 (2001) — семейства алгоритмов с длинами хэша 224, 256, 384 и 512 бит. В 2015 году NIST утвердил SHA-3 (Keccak), победивший в конкурсе на новый стандарт.
Классификация
Хэш-функции делятся на две основные категории:
Криптографические хэш-функции
Предназначены для обеспечения безопасности: цифровые подписи, аутентификация сообщений, хранение паролей. Обладают высокой стойкостью к коллизиям и необратимостью. Примеры: SHA-256, SHA-3, BLAKE2, ГОСТ Р 34.11-2012 («Стрибог»).
Некриптографические хэш-функции
Используются для быстрого поиска, проверки целостности данных, построения хэш-таблиц. Не требуют высокой криптостойкости, но должны быть быстрыми и равномерно распределять хэши. Примеры: CityHash, xxHash, MurmurHash, CRC32.
Устройство и принцип работы
Большинство современных криптографических хэш-функций основаны на итеративной конструкции Меркла — Дамгора. Входное сообщение разбивается на блоки фиксированной длины (обычно 512 или 1024 бита). Если последний блок короче, к нему добавляется паддинг (заполнение) до нужного размера. Каждый блок последовательно обрабатывается с использованием компрессионной функции, которая принимает текущее состояние (инициализированное константой) и блок данных, выдавая новое состояние. После обработки всех блоков получается итоговый хэш.
Алгоритмы семейства SHA-3 используют другую конструкцию — губку (sponge), где данные сначала впитываются (absorb), затем выжимаются (squeeze) в хэш произвольной длины.
Применение
Хранение паролей
Вместо хранения паролей в открытом виде системы хранят их хэши. При вводе пароля вычисляется хэш и сравнивается с сохранённым. Для повышения безопасности применяют соль (случайное значение, добавляемое к паролю перед хэшированием) и медленные хэш-функции (bcrypt, scrypt, Argon2).
Цифровые подписи и сертификаты
Хэш сообщения подписывается закрытым ключом, а получатель проверяет подпись, сравнивая хэш с вычисленным. Это гарантирует целостность и авторство данных.
Блокчейн и криптовалюты
В блокчейне биткоина (Bitcoin) используется SHA-256 для создания цепочки блоков и майнинга (доказательство работы). Каждый блок содержит хэш предыдущего блока, что делает цепочку неизменной.
Контрольные суммы
CRC32, MD5, SHA-1 применяются для проверки целостности файлов при передаче или хранении (например, в архивах, дистрибутивах ПО).
Хэш-таблицы
В программировании хэш-функции отображают ключи на индексы в массиве, обеспечивая быстрый доступ к данным (среднее время O(1)).
Аутентификация сообщений
HMAC (Hash-based Message Authentication Code) — механизм, использующий хэш-функцию с секретным ключом для проверки подлинности и целостности сообщения.
Примеры популярных хэш-функций
| Алгоритм | Длина хэша (бит) | Год создания | Статус безопасности |
|---|---|---|---|
| MD5 | 128 | 1991 | Небезопасен (коллизии) |
| SHA-1 | 160 | 1995 | Небезопасен (атаки с 2005) |
| SHA-256 | 256 | 2001 | Безопасен (рекомендуется) |
| SHA-3 (Keccak) | 224/256/384/512 | 2015 | Безопасен |
| ГОСТ Р 34.11-2012 | 256 или 512 | 2012 | Безопасен (российский стандарт) |
| BLAKE2 | 256 или 512 | 2012 | Безопасен, быстрее SHA-3 |
Критика и уязвимости
- Коллизии: для MD5 и SHA-1 найдены практические атаки, позволяющие создавать пары сообщений с одинаковым хэшем. Это делает их непригодными для криптографических целей.
- Атака «дня рождения»: вероятность найти коллизию для n-битного хэша составляет примерно 2^(n/2) попыток. Для 128-битного MD5 это 2^64 — вычислимо для современных суперкомпьютеров.
- Радужные таблицы: предвычисленные таблицы хэшей для распространённых паролей позволяют быстро восстанавливать пароли. Защита — использование соли.
- Квантовые угрозы: алгоритм Гровера теоретически позволяет ускорить поиск коллизий в 2 раза (для n-битного хэша — 2^(n/2) вместо 2^n). Однако для 256-битных хэшей это всё ещё практически невозможно.
Интересные факты
- Самая известная хэш-функция без ключа — SHA-256, используемая в биткоине. Для её вычисления применяются специализированные ASIC-майнеры.
- В 2017 году Google объявила о первой успешной атаке на SHA-1 (коллизия двух разных PDF-файлов), что ускорило переход на SHA-256.
- Хэш-функция «Стрибог» (ГОСТ Р 34.11-2012) названа в честь бога ветра в славянской мифологии.
---
Источники:
- Национальный институт стандартов и технологий (NIST). «FIPS PUB 180-4: Secure Hash Standard (SHS)». 2015.
- Национальный институт стандартов и технологий (NIST). «FIPS PUB 202: SHA-3 Standard». 2015.
- Федеральный закон «О техническом регулировании» (в части ГОСТ Р 34.11-2012).
- Шнайер Б. «Прикладная криптография». 2-е издание. 1996.
- Menezes A., van Oorschot P., Vanstone S. «Handbook of Applied Cryptography». 1996.
- Rivest R. «The MD5 Message-Digest Algorithm». RFC 1321. 1992.
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →