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

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

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

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

1. Устойчивость к коллизиям (Collision Resistance): вычислительно невозможно найти два различных входных сообщения, которые дают одинаковое хеш-значение. Коллизия — это ситуация, когда H(x) = H(y) при x ≠ y.

1. Устойчивость к прообразу (Preimage Resistance): по заданному хеш-значению h вычислительно невозможно найти какое-либо входное сообщение x, такое что H(x) = h. Это свойство также называют однонаправленностью.

1. Устойчивость ко второму прообразу (Second Preimage Resistance): для заданного входного сообщения x вычислительно невозможно найти другое сообщение y ≠ x, такое что H(y) = H(x). Это более слабое свойство, чем устойчивость к коллизиям.

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

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

История

Ранние разработки

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

Эра SHA

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

В 2001 году NIST выпустил семейство SHA-2, включающее функции SHA-224, SHA-256, SHA-384 и SHA-512. Они используют 64-битные слова и более сложную структуру, чем SHA-1.

Современный этап

В 2012 году после открытого конкурса NIST выбрал SHA-3 (Keccak), разработанную Гвидо Бертони, Джоан Даймен и Жилем ван Ассше. SHA-3 использует конструкцию «губка» (sponge construction), отличную от Меркла-Дамгора.

Параллельно развивались другие функции: BLAKE2 (2012) — оптимизированная версия финалиста конкурса SHA-3, Skein, Whirlpool. В России стандартизирован алгоритм ГОСТ Р 34.11-2012 («Стрибог»), выпускающий хеш длиной 256 или 512 бит.

Классификация

По длине хеш-значения

• Короткие (128-160 бит): MD5, SHA-1 (считаются небезопасными)
• Стандартные (256-512 бит): SHA-256, SHA-512, SHA-3-256
• Переменной длины: SHA-3 (поддерживает 224, 256, 384, 512 бит)

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

• На основе конструкции Меркла-Дамгора: MD5, SHA-1, SHA-2
• На основе конструкции «губка»: SHA-3, Keccak
• На основе блочных шифров: Whirlpool (использует модифицированный AES)

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

• Универсальные: SHA-2, SHA-3
• Специализированные: BLAKE2 (оптимизирован для программной реализации)
• Стандартизированные: ГОСТ Р 34.11-2012 (Россия), SM3 (Китай)

Устройство и принцип работы

Конструкция Меркла-Дамгора

Большинство классических хеш-функций (MD5, SHA-1, SHA-2) используют эту конструкцию:

1. Входное сообщение дополняется до длины, кратной размеру блока.
2. Сообщение разбивается на блоки фиксированного размера.
3. Каждый блок обрабатывается сжатием вместе с текущим состоянием (инициализируется начальным вектором).
4. После обработки всех блоков получается финальный хеш.

Уязвимость этой конструкции — атаки удлинения сообщения (length extension attack), когда зная H(M), можно вычислить H(M || pad || extra) без знания M.

Конструкция «губка»

Используется в SHA-3:

1. Состояние представляется в виде трёхмерного массива битов.
2. Операция «впитывания»: блоки сообщения XOR-ятся с состоянием, затем применяется перестановка Keccak-f.
3. Операция «выжимания»: из состояния извлекаются блоки хеша.
4. Длина выходного хеша может варьироваться.

Эта конструкция устойчива к атакам удлинения сообщения.

Применение

Цифровые подписи

Хеш-функции используются для создания дайджеста сообщения, который затем подписывается асимметричным алгоритмом (RSA, ECDSA). Это ускоряет подпись и уменьшает размер подписи.

Хранение паролей

Вместо хранения паролей в открытом виде системы хранят их хеши. При аутентификации введённый пароль хешируется и сравнивается с хранимым значением. Для защиты от атак по словарю используются соль (random salt) и медленные хеш-функции (bcrypt, scrypt, Argon2).

Проверка целостности данных

Контрольные суммы (например, SHA-256) позволяют проверить, не были ли изменены файлы при передаче или хранении. Используется в протоколах загрузки, системах контроля версий (Git использует SHA-1).

Блокчейн и криптовалюты

В биткоине и других криптовалютах хеш-функции (SHA-256, Keccak-256) используются для:

• Создания адресов кошельков
• Формирования цепочки блоков (каждый блок содержит хеш предыдущего)
• Доказательства работы (Proof-of-Work)

Протоколы аутентификации

HMAC (Hash-based Message Authentication Code) — механизм аутентификации сообщений, основанный на хеш-функции. Используется в протоколах TLS, SSH, IPsec.

Критика и уязвимости

Атаки на коллизии

• MD5: в 2004 году китайские исследователи (Сяоюнь Ван и др.) продемонстрировали практическую атаку на коллизии. В 2008 году были созданы коллизии за секунды.
• SHA-1: в 2017 году Google и CWI Amsterdam опубликовали коллизию (SHAttered) стоимостью около 110 000 долларов.
• SHA-2: на 2024 год не обнаружено практических атак на коллизии.

Атаки на прообраз

Для современных функций (SHA-256, SHA-3) атаки на прообраз требуют 2^256 операций, что вычислительно невозможно. Однако для MD5 и SHA-1 существуют теоретические уязвимости.

Атаки удлинения сообщения

Уязвимы MD5, SHA-1, SHA-2. Позволяют злоумышленнику, зная H(M), подделать аутентифицированное сообщение. SHA-3 и BLAKE2 не подвержены этой атаке.

Квантовая угроза

Квантовые компьютеры с помощью алгоритма Гровера могут найти прообраз за O(2^(n/2)) операций, что вдвое сокращает эффективную длину хеша. Для SHA-256 это 2^128 операций, что всё ещё считается безопасным.

Интересные факты

• Хеш-функция SHA-1 использовалась в системе контроля версий Git до 2023 года, когда начался переход на SHA-256.
• Алгоритм SHA-3 (Keccak) был выбран NIST в 2012 году после четырёхлетнего конкурса, в котором участвовали 64 кандидата.
• В России стандарт ГОСТ Р 34.11-2012 («Стрибог») был разработан в 2012 году и обязателен для использования в государственных информационных системах.
• Хеш-функции могут использоваться для генерации псевдослучайных чисел (например, в протоколах аутентификации).
• Самая длинная известная коллизия SHA-1 была найдена в 2020 году с использованием 6500 лет процессорного времени на GPU.

Источники

• Брюс Шнайер. «Прикладная криптография» (1996)
• NIST FIPS PUB 180-4: Secure Hash Standard (SHS)
• NIST FIPS PUB 202: SHA-3 Standard
• Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche. «The Keccak reference» (2011)
• Xiaoyun Wang, Hongbo Yu. «How to Break MD5 and Other Hash Functions» (2005)
• Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. «The first collision for full SHA-1» (2017)
• ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хэширования»