Криптографическое хеширование¶

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

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

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

Детерминированность: Один и тот же вход всегда даёт один и тот же выход.
Высокая скорость вычисления: Для любого входного сообщения хеш-сумма должна вычисляться быстро.
Необратимость (свойство односторонности): По заданному значению хеша (h) должно быть невозможно вычислительно эффективно найти исходное сообщение (m), такое что h = H(m). Иными словами, восстановить исходные данные по хешу практически невозможно.
Устойчивость к коллизиям первого рода (слабая коллизионная стойкость): Для заданного сообщения m1 должно быть вычислительно невозможно найти другое сообщение m2, такое что H(m1) = H(m2).
Устойчивость к коллизиям второго рода (сильная коллизионная стойкость): Должно быть вычислительно невозможно найти любую пару различных сообщений (m1, m2), для которых H(m1) = H(m2). Это свойство является более строгим.
Лавинный эффект: Незначительное изменение входных данных (например, изменение одного бита) должно приводить к кардинальному и непредсказуемому изменению выходного хеша (примерно половина битов хеша должна измениться).

¶Отличие от не-криптографического хеширования

Существуют хеш-функции, не предназначенные для криптографии (например, CRC32, MurmurHash, CityHash). Они оптимизированы на скорость и равномерность распределения, но не обладают свойствами необратимости и коллизионной стойкости. Их использование в криптографических целях (например, для хранения паролей) недопустимо, так как коллизии для них могут быть найдены намеренно или случайно.

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

¶Ранние алгоритмы

Первые криптографические хеш-функции появились в конце 1980-х — начале 1990-х годов. Одним из первых широко распространённых алгоритмов был MD4 (Message Digest 4), разработанный Рональдом Ривестом в 1990 году. Вскоре после его публикации были найдены серьёзные уязвимости, и на его основе был создан MD5 (1991 год). MD5 долгое время был стандартом де-факто, но в 2004 году китайские исследователи (Ван Сяоюнь и др.) продемонстрировали практические атаки на коллизии для MD5. После этого MD5 считается полностью скомпрометированным и не рекомендуется к использованию в криптографии.

¶Семейство SHA

Наиболее известным и широко используемым семейством является SHA (Secure Hash Algorithm — Безопасный алгоритм хеширования), разработанное Агентством национальной безопасности США (АНБ) и опубликованное Национальным институтом стандартов и технологий США (NIST).

SHA-0 и SHA-1: SHA-0 был опубликован в 1993 году, но вскоре отозван из-за необъявленной уязвимости. SHA-1 (1995 год) долгое время считался стандартом. Однако с 2005 года начали появляться теоретические атаки, а в 2017 году компания Google и Центр математики и информатики (CWI) в Нидерландах продемонстрировали первую практическую атаку на коллизию для SHA-1 (атака SHAttered). С этого момента SHA-1 считается небезопасным и не рекомендуется к использованию.
SHA-2: Семейство, включающее алгоритмы SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256. SHA-256 и SHA-512 являются наиболее распространёнными. На сегодняшний день (2024 год) SHA-2 считается криптостойким и широко применяется в протоколах TLS/SSL, блокчейне (Биткойн использует SHA-256 дважды), цифровых подписях и системах контроля версий (Git).
SHA-3: Победитель конкурса NIST (2012 год), основанный на алгоритме Keccak (разработан Гвидо Бертони, Жоаном Дайменом, Микаэлем Питерсом и Жилем ван Ассхе). SHA-3 имеет принципиально иную внутреннюю структуру (губка) по сравнению с SHA-2 (конструкция Меркла-Дамгарда) и предназначен для обеспечения резервной криптостойкости на случай, если в SHA-2 будут найдены уязвимости.

¶Другие алгоритмы

RIPEMD-160: Разработан в Европе как альтернатива SHA-1. Используется в криптовалюте Bitcoin для генерации адресов кошельков (в комбинации с SHA-256).
BLAKE2: Высокоскоростной алгоритм, созданный как улучшенная версия BLAKE (финалист конкурса SHA-3). BLAKE2b и BLAKE2s оптимизированы для 64-битных и 8-32-битных платформ соответственно. Широко используется в современных криптографических библиотеках.
SM3: Китайский национальный стандарт криптографического хеширования (GB/T 32905-2016), используемый в китайских криптографических протоколах.

¶Применение

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

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

¶Цифровые подписи и сертификаты

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

¶Контроль целостности данных

Хеш-суммы используются для проверки того, что файл или сообщение не были изменены в процессе передачи или хранения. Например, при скачивании больших файлов (образы ISO, дистрибутивы программ) сайты часто публикуют контрольные суммы (SHA-256, MD5). Пользователь может вычислить хеш скачанного файла и сравнить его с эталонным.

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

В технологии блокчейн (например, Bitcoin, Ethereum) криптографическое хеширование играет ключевую роль:

Связывание блоков: Каждый блок содержит хеш предыдущего блока, образуя неизменяемую цепочку.
Доказательство работы (Proof of Work): Майнеры ищут значение nonce (случайное число), такое чтобы хеш блока начинался с определённого количества нулей. Это требует огромных вычислительных затрат и обеспечивает безопасность сети.
Адреса кошельков: Адреса генерируются из публичных ключей с помощью последовательного применения хеш-функций (SHA-256 и RIPEMD-160).

¶Сети и протоколы

Хеш-функции используются в протоколах TLS/SSL для обеспечения целостности рукопожатия и сессионных ключей, в протоколах аутентификации (например, HMAC — Hash-based Message Authentication Code), в системах контроля версий (Git использует SHA-1 для идентификации коммитов, хотя это считается уязвимостью), а также в распределённых хеш-таблицах (DHT) в пиринговых сетях.

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

Основная критика в области криптографического хеширования связана с устареванием алгоритмов. По мере роста вычислительной мощности и развития криптоанализа, алгоритмы, которые когда-то считались безопасными, становятся уязвимыми. Наиболее яркие примеры — MD5 и SHA-1, коллизии для которых были найдены.

Другая проблема — атаки на расширение длины (length extension attack), которым подвержены хеш-функции, построенные на конструкции Меркла-Дамгарда (SHA-1, SHA-2). Зная H(m) и длину m, можно вычислить H(m || padding || extra) без знания m. Это делает такие функции непригодными для некоторых протоколов без дополнительных модификаций (например, HMAC). SHA-3 и BLAKE2 не подвержены этой атаке.

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

¶Источники

Национальный институт стандартов и технологий (NIST). FIPS PUB 180-4: Secure Hash Standard (SHS). 2015.
Национальный институт стандартов и технологий (NIST). FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. 2015.
Бертони, Г., Даймен, Дж., Питерс, М., ван Ассхе, Ж. Keccak sponge function family. 2011.
Ривест, Р. The MD5 Message-Digest Algorithm. RFC 1321. 1992.
Стивенс, М., Бурштейн, Э., Карпман, П., Альбертини, А., Марков, Ю. The first collision for full SHA-1. 2017.
Ван, С., Ю, Х. How to break MD5 and other hash functions. EUROCRYPT 2005.
Аарс, Й., и др. BLAKE2: simpler, smaller, fast as MD5. 2013.
Персиваль, К. Stronger Key Derivation via Sequential Memory-Hard Functions. 2009.
Гровер, Л. К. A fast quantum mechanical algorithm for database search. 1996.