Криптографическая хэш-функция

Криптографическая хэш-функция — это детерминированная математическая функция, которая преобразует входные данные произвольной длины (сообщение) в выходную строку фиксированной длины (хэш-значение, или дайджест), обладающую рядом специфических свойств, делающих её пригодной для использования в криптографии. В отличие от обычных хэш-функций, применяемых, например, для построения хэш-таблиц, криптографические версии должны быть устойчивы к целенаправленным атакам злоумышленника.

Основные свойства

Криптографическая хэш-функция должна удовлетворять трём фундаментальным требованиям безопасности:

• Стойкость к коллизиям (Collision Resistance): Вычислительно невозможно найти два различных входных сообщения \( x \) и \( y \), для которых \( H(x) = H(y) \). Это свойство гарантирует, что хэш-значение однозначно идентифицирует сообщение.
• Необратимость (Preimage Resistance, или свойство «односторонности»): По заданному хэш-значению \( h \) вычислительно невозможно найти какое-либо сообщение \( x \), такое что \( H(x) = h \). Это означает, что восстановить исходные данные по их дайджесту практически невозможно.
• Стойкость к поиску второго прообраза (Second Preimage Resistance): При заданном сообщении \( x \) вычислительно невозможно найти другое сообщение \( y \neq x \), такое что \( H(y) = H(x) \). Это свойство защищает от подмены одного сообщения другим с тем же хэшем.

Дополнительными важными характеристиками являются:

• Лавинный эффект (Avalanche Effect): Незначительное изменение входных данных (например, изменение одного бита) должно приводить к кардинальному и непредсказуемому изменению выходного хэш-значения (в среднем меняется около половины битов).
• Детерминированность: Одно и то же входное сообщение всегда даёт один и тот же хэш-код.
• Высокая скорость вычислений: Для практического применения функция должна вычисляться достаточно быстро на современных процессорах.

История развития

Первые криптографические хэш-функции появились в 1970-х годах. Одной из ранних разработок стала функция MD2, созданная Рональдом Ривестом в 1989 году. В 1992 году была опубликована функция MD5, которая на протяжении многих лет была стандартом де-факто, однако к 2004 году в ней были найдены серьёзные уязвимости, связанные с коллизиями.

В 1993 году Национальный институт стандартов и технологий США (NIST) опубликовал стандарт SHA-0, который вскоре был заменён на SHA-1 из-за обнаруженной уязвимости. SHA-1 использовался до 2010-х годов, пока не были продемонстрированы практические атаки на его коллизионную стойкость.

В ответ на уязвимости SHA-1 NIST провёл конкурс, результатом которого стало семейство SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), опубликованное в 2001 году. Эти функции на сегодняшний день считаются безопасными и широко применяются.

В 2007 году NIST объявил новый конкурс на разработку стандарта SHA-3. Победителем в 2012 году стала функция Keccak, основанная на принципиально иной конструкции — губчатой функции (sponge function). SHA-3 был стандартизирован в 2015 году и обеспечивает запас прочности на случай уязвимостей в SHA-2.

Классификация и типы

Криптографические хэш-функции можно классифицировать по нескольким признакам:

По длине выходного значения

• Короткие: 128 бит (MD5 — устарел), 160 бит (SHA-1 — устарел).
• Средние: 224, 256 бит (SHA-224, SHA-256).
• Длинные: 384, 512 бит (SHA-384, SHA-512).

По конструкции

• На основе конструкции Меркла — Дамгора (Merkle–Damgård): Сообщение разбивается на блоки фиксированной длины, которые последовательно обрабатываются через сжимающую функцию. К этому типу относятся MD5, SHA-1, SHA-2.
• Губчатая функция (Sponge Construction): Использует чередование фаз «впитывания» (absorbing) и «выжимания» (squeezing). Keccak (SHA-3) является представителем этого типа.

По назначению

• Универсальные (стандартные): SHA-256, SHA-3.
• Специализированные: для хэширования паролей (bcrypt, scrypt, Argon2), которые намеренно замедлены для защиты от атак перебором.

Применение

Криптографические хэш-функции являются фундаментальным строительным блоком для множества систем информационной безопасности:

• Проверка целостности данных: При скачивании файлов из интернета часто публикуется их хэш-сумма (например, SHA-256). Пользователь может вычислить хэш скачанного файла и сравнить его с эталонным, чтобы убедиться, что файл не был повреждён или модифицирован.
• Хранение паролей: Вместо хранения паролей в открытом виде системы хранят их хэши. При аутентификации хэш введённого пароля сравнивается с хранящимся. Для защиты от атак по словарю применяется «соль» (salt) — случайная строка, добавляемая к паролю перед хэшированием.
• Цифровые подписи: Хэш-функция используется для создания «дайджеста» сообщения, который затем подписывается асимметричным алгоритмом (например, RSA или ECDSA). Это значительно эффективнее, чем подписывать всё сообщение целиком.
• Блокчейн и криптовалюты: В технологии блокчейн (например, в сети Биткойн) хэш-функция SHA-256 используется для связывания блоков в цепочку и для майнинга (Proof-of-Work).
• Контроль версий (Git): Система Git использует хэш-функцию SHA-1 для идентификации каждого коммита, файла и дерева.
• Генерация псевдослучайных чисел: Хэш-функции могут быть использованы как компонент генераторов псевдослучайных чисел.

Атаки и уязвимости

Основные типы атак на криптографические хэш-функции направлены на нарушение их свойств:

• Атака на коллизии: Нахождение двух разных сообщений с одинаковым хэшем. Для MD5 и SHA-1 такие атаки реализованы на практике. В 2017 году Google продемонстрировал коллизию для SHA-1 (атака SHAttered).
• Атака на прообраз: Восстановление исходного сообщения по хэшу. Для современных функций (SHA-2, SHA-3) считается вычислительно невозможной при правильном использовании.
• Атака удлинения сообщения (Length Extension Attack): Уязвимость, характерная для функций на основе конструкции Меркла — Дамгора (MD5, SHA-1, SHA-2). Злоумышленник, зная \( H(M) \) и длину \( M \), может вычислить \( H(M \parallel X) \) для некоторого \( X \), не зная \( M \). SHA-3 и BLAKE2 не подвержены этой атаке.

Стандартизация в России

В Российской Федерации действует национальный стандарт на криптографические хэш-функции — ГОСТ Р 34.11-2012 (также известный как Стрибог). Он был введён в действие в 2013 году и заменил устаревший ГОСТ Р 34.11-94. Функция Стрибог может выдавать хэш-код длиной 256 или 512 бит. Она основана на итеративной конструкции, отличной от Меркла — Дамгора, и является обязательной для использования в государственных информационных системах и при создании электронной подписи по ГОСТ.

Источники

1. Шнайер Б. «Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си». — М.: Триумф, 2002.
2. Фергюсон Н., Шнайер Б., Кохун Т. «Практическая криптография». — М.: Вильямс, 2005.
3. Menezes A., van Oorschot P., Vanstone S. «Handbook of Applied Cryptography». — CRC Press, 1996.
4. Национальный институт стандартов и технологий США (NIST). FIPS PUB 180-4: Secure Hash Standard (SHS). — 2015.
5. Национальный институт стандартов и технологий США (NIST). FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. — 2015.
6. Федеральное агентство по техническому регулированию и метрологии. ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хэширования». — 2012.