Хеширование данных¶

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

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

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

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

¶Основные алгоритмы

¶MD5

Алгоритм MD5 (Message Digest 5) разработан Рональдом Ривестом в 1991 году. Генерирует 128-битный хеш. В настоящее время считается криптографически небезопасным из-за найденных атак на коллизии, но продолжает использоваться для проверки целостности файлов в не криптографических сценариях.

¶SHA-семейство

Семейство алгоритмов SHA (Secure Hash Algorithm) разработано Агентством национальной безопасности США (NSA). Ключевые версии:

SHA-1 был взломан в 2017 году исследователями из Google и Института Курта Лоренца (SHAttered-атака). После этого крупнейшие технологические компании отказались от него в пользу SHA-256 и более новых алгоритмов.

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

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

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

В системах аутентификации пароли не хранятся в открытом виде — вместо них сохраняется хеш. При входе пользователя вводимый пароль хешируется и результат сравнивается с сохранённым значением.

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

• Соль (salt) — уникальная случайная последовательность, добавляемая к паролю перед хешированием. Исключает совпадение хешей для одинаковых паролей и делает невозможным использование предвычисленных таблиц (радужных таблиц).
• Медленные хеш-функции — алгоритмы с высокой вычислительной стоимостью: PBKDF2, bcrypt, scrypt, Argon2. Argon2 стал победителем конкурса Password Hashing Competition в 2015 году.

¶Применение

¶Проверка целостности

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

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

В сертификатах X.509 и цифровых подписях используются хеш-функции для сжатия подписываемых данных. Алгоритмы RSA, ECDSA и EdDSA работают с хешем сообщения, а не с исходным текстом.

¶Блокчейн

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

¶Хеш-таблицы

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

¶Контрольные суммы и дедупликация

Хеширование применяется в системах резервного копирования, облаках хранения и файловых системах (например, Btrfs, ZFS) для обнаружения дубликатов и повреждённых блоков.

¶Ограничения

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

Источники:

• Нист Р., ФИПС 180-4: Secure Hash Standard (SHS)
• Ривест Р. The MD5 Message-Digest Algorithm, RFC 1321
• Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходный код на языке C
• Мензок С., Хенкок Дж. Криптография для начинающих: алгоритмы, протоколы, защита паролей