Алгоритм хэширования

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

История

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

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

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

Алгоритмы хэширования делятся на два основных типа: криптографические и некриптографические.

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

Эти функции обладают дополнительными свойствами безопасности:

• Устойчивость к коллизиям: невозможно найти два разных входных сообщения, дающих одинаковый хеш.
• Необратимость: по хешу нельзя восстановить исходные данные.
• Лавинный эффект: малейшее изменение входных данных приводит к кардинальному изменению хеша.

Примеры:

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

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

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

Примеры:

• CRC32 (Cyclic Redundancy Check) — 32-битная контрольная сумма. Используется для обнаружения случайных ошибок в сетях и архивах.
• MurmurHash — быстрый некриптографический хеш, разработанный Остином Эпплби. Применяется в базах данных (Cassandra, Hadoop).
• CityHash — разработан Google, оптимизирован для процессоров Intel.
• xxHash — один из самых быстрых современных некриптографических хешей, используется в архиваторах и файловых системах.

Принцип работы

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

1. Дополнение (padding): входное сообщение дополняется до длины, кратной блоку (обычно 512 или 1024 бита). В конец добавляется бит «1», затем нули и длина сообщения.
2. Разбиение на блоки: сообщение делится на блоки фиксированного размера.
3. Инициализация: задаётся начальное значение хеша (IV — initial vector).
4. Циклическое сжатие: каждый блок обрабатывается с помощью сжимающей функции, которая принимает текущее состояние хеша и блок данных, выдавая новое состояние. В конструкции Меркла — Дамгорда это последовательное применение.
5. Вывод: после обработки всех блоков получается окончательная хеш-сумма.

В губчатой конструкции (SHA-3) данные сначала впитываются в состояние (absorbing), а затем выжимаются (squeezing) для получения хеша.

Применение

Криптография и безопасность

• Цифровые подписи: хеш сообщения подписывается асимметричным ключом.
• Аутентификация сообщений (HMAC): хеш с секретным ключом.
• Хранение паролей: вместо пароля хранится его хеш (с солью). Примеры: bcrypt, scrypt, Argon2 (специализированные функции для паролей).
• Проверка целостности: контрольные суммы файлов (SHA-256).

Информационные технологии

• Хеш-таблицы: структуры данных для быстрого поиска (словари, кэши).
• Дедупликация данных: в системах хранения (ZFS, btrfs).
• Контроль версий: Git использует SHA-1 для идентификации коммитов.
• Блокчейн и криптовалюты: Bitcoin (SHA-256), Ethereum (Keccak-256).

Базы данных

• Индексирование: хеш-индексы для ускорения запросов (например, в PostgreSQL).
• Шардирование: распределение данных по узлам на основе хеша ключа.

Уязвимости и критика

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

• Коллизии: для MD5 и SHA-1 найдены практические атаки. Для SHA-2 теоретически возможны атаки на уменьшенное число раундов, но на полную версию — нет.
• Атаки на растяжение времени: для паролей требуется медленный хеш (bcrypt, scrypt), чтобы затруднить перебор.
• Квантовая угроза: квантовые компьютеры с алгоритмом Гровера могут ускорить поиск коллизий, но не делают хеш-функции полностью бесполезными — требуется удвоение длины хеша.

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

• Алгоритм SHA-256 используется в майнинге Bitcoin: майнеры перебирают nonce, чтобы получить хеш блока, начинающийся с определённого количества нулей.
• В 2017 году Google опубликовала коллизию для SHA-1, затратив 110 GPU-лет вычислений.
• Для хранения паролей в современных системах рекомендуется использовать Argon2, bcrypt или PBKDF2, а не простые хеш-функции.
• Существуют хеш-функции с доказательством работы (Proof of Work), такие как Hashcash, лёгшие в основу Bitcoin.

Источники

• NIST. Secure Hash Standard (SHS). FIPS PUB 180-4, 2015.
• Rivest, R. The MD5 Message-Digest Algorithm. RFC 1321, 1992.
• Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. The Keccak Reference, 2011.
• Menezes, A., van Oorschot, P., Vanstone, S. Handbook of Applied Cryptography. CRC Press, 1996.
• Stallings, W. Cryptography and Network Security: Principles and Practice. Pearson, 2017.