Хеширование

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

История

Идея использования хеш-функций для организации данных восходит к 1950-м годам. Одним из первых применений стало создание так называемых «рассеянных таблиц» (scatter tables) для ускорения поиска в больших массивах информации. Термин «хеширование» ввёл в обиход, по разным данным, либо Ханс Петер Лун (1953), либо Арнольд Думи (1956). В 1962 году американский программист Джон Моррис опубликовал одну из первых работ, описывающих хеш-таблицы как структуру данных.

В криптографии хеширование начало активно развиваться с 1970-х годов. Первой широко известной криптографической хеш-функцией стала MD5 (Message Digest 5), разработанная Рональдом Ривестом в 1991 году. Впоследствии были созданы более стойкие алгоритмы: SHA-1 (1995), семейство SHA-2 (2001) и SHA-3 (2015). В России стандартизирована собственная криптографическая хеш-функция «Стрибог», описанная в ГОСТ Р 34.11-2012.

Основные свойства хеш-функций

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

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

Классификация хеш-функций

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

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

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

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

Предназначены для обеспечения безопасности. Они должны быть устойчивы к атакам, направленным на нахождение коллизий или восстановление исходных данных. Примеры: MD5 (считается устаревшим и небезопасным), SHA-1 (считается устаревшим), SHA-256, SHA-3, ГОСТ Р 34.11-2012 («Стрибог»), BLAKE2.

Применение хеширования

Хеширование используется в самых разных областях информационных технологий.

Хеш-таблицы

Это структура данных, где ключ элемента преобразуется в индекс массива с помощью хеш-функции. Это позволяет выполнять операции вставки, поиска и удаления элемента в среднем за время O(1) (константное время), что значительно быстрее, чем в списках или деревьях. Хеш-таблицы лежат в основе многих языков программирования (например, словари в Python, HashMap в Java, объекты в JavaScript).

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

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

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

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

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

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

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

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

Поиск дубликатов

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

Критика и проблемы

Основной проблемой хеширования являются коллизии — ситуации, когда два разных входных набора данных дают одинаковый хеш. Для криптографических функций коллизии являются серьёзной уязвимостью. Так, в 2004 году китайские исследователи продемонстрировали практическую атаку на MD5, а в 2017 году Google объявила о нахождении коллизии для SHA-1. Эти алгоритмы были признаны устаревшими и не рекомендованы к использованию.

Другая проблема — «атака по времени» (timing attack), когда злоумышленник может определить значение хеша, измеряя время ответа системы на различные запросы. Для защиты от таких атак используются алгоритмы сравнения, выполняющиеся за константное время.

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

• Самая короткая хеш-функция (например, CRC32) может давать коллизию на очень небольших объёмах данных, в то время как криптографические функции (SHA-256) имеют такое большое пространство выходных значений (2^256), что вероятность случайной коллизии ничтожно мала.
• В русском языке термин «хеширование» часто заменяют словом «хэширование», однако первый вариант является более распространённым в технической литературе.
• Алгоритм «Стрибог» (ГОСТ Р 34.11-2012) был разработан для использования в российских государственных информационных системах и является обязательным для применения в ряде ведомств.

Источники

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
2. Шнайер Б. Прикладная криптография. — 2-е изд. — М.: Триумф, 2002.
3. ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хэширования.
4. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996.
5. Ferguson N., Schneier B., Kohno T. Cryptography Engineering: Design Principles and Practical Applications. — Wiley, 2010.