Хеш-функция

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

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

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

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

История

Первые идеи использования хеш-функций для организации данных появились в 1950-х годах. В 1953 году американский учёный Ганс Питер Лун разработал алгоритм хеширования для поиска в больших массивах данных. Однако современное понимание криптографических хеш-функций начало формироваться в 1970-х годах с развитием криптографии с открытым ключом.

В 1979 году Ральф Меркле предложил концепцию дерева хешей (дерево Меркле), которая стала основой для многих блокчейн-технологий. В 1990 году Рональд Ривест разработал алгоритм MD4, а затем MD5, которые широко использовались, но позже были признаны уязвимыми. В 1993 году Национальный институт стандартов и технологий США (NIST) опубликовал SHA-0, а затем, в 1995 году, SHA-1. После обнаружения уязвимостей в SHA-1 в 2000-х годах NIST в 2001 году представил семейство SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), которое остаётся стандартом де-факто. В 2012 году NIST объявил победителем конкурса на новый стандарт — SHA-3 (алгоритм Keccak).

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

Хеш-функции делятся на два основных класса:

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

Предназначены для обеспечения безопасности и обладают всеми перечисленными выше свойствами. Используются в цифровых подписях, аутентификации сообщений, хранении паролей и криптовалютах. Примеры: SHA-256, SHA-3, BLAKE2.

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

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

Применение

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

Хеш-суммы используются для контроля неизменности файлов при передаче или хранении. Пользователь может вычислить хеш скачанного файла и сравнить его с эталонным значением, опубликованным разработчиком. При несовпадении данных файл считается повреждённым или подменённым.

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

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

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

Хеш-функции являются ключевым компонентом асимметричной криптографии. Вместо подписания всего сообщения подписывается его хеш, что значительно ускоряет процесс. Сертификаты X.509, используемые в протоколах HTTPS, также содержат хеши для проверки подлинности.

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

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

Хеш-таблицы

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

Известные алгоритмы

• MD5 (Message Digest 5) — 128-битный алгоритм, разработанный в 1991 году. С 2004 года считается криптографически сломанным: найдены практические методы нахождения коллизий. Не рекомендуется к использованию в системах безопасности.
• SHA-1 (Secure Hash Algorithm 1) — 160-битный алгоритм. В 2017 году группа исследователей (включая Google) продемонстрировала успешную атаку на коллизию (SHAttered). С 2017 года NIST рекомендовал отказаться от SHA-1.
• SHA-2 — семейство алгоритмов с длиной хеша 224, 256, 384 и 512 бит. Наиболее распространённый стандарт. SHA-256 используется в Биткоине и многих протоколах TLS/SSL.
• SHA-3 — стандарт, принятый в 2015 году, основанный на алгоритме Keccak. Отличается от SHA-2 внутренней структурой (использует губчатую конструкцию вместо конструкции Меркла — Дамгора).
• BLAKE2 — высокопроизводительный алгоритм, разработанный в 2012 году. Считается более быстрым, чем SHA-2, и рекомендован для использования в программных реализациях.

Критика и ограничения

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

Некриптографические хеш-функции могут страдать от чрезмерного количества коллизий при неправильном выборе алгоритма для конкретного набора данных, что приводит к деградации производительности хеш-таблиц.

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

• Алгоритм SHA-256, используемый в Биткоине, требует огромных вычислительных затрат: по оценкам, на конец 2023 года мощность сети Биткоин превышала 400 экзахешей в секунду (400 × 10^18 операций хеширования в секунду).
• Первая успешная атака на коллизию для MD5 была проведена китайским криптографом Ван Сяоюнь в 2004 году.
• В 2022 году NIST объявил о начале стандартизации новых алгоритмов хеширования, устойчивых к квантовым атакам.

Источники

• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
• Schneier, B. (2015). Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons.
• NIST FIPS PUB 180-4: Secure Hash Standard (SHS).
• NIST FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions.
• RFC 1321: The MD5 Message-Digest Algorithm.
• RFC 4634: US Secure Hash Algorithms (SHA and HMAC-SHA).