Хэширование

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

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

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

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

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

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

История

Первые хэш-функции появились в 1950-х годах в связи с развитием методов сортировки и поиска данных. В 1953 году Ганс Петер Лун предложил использовать хэш-таблицы для быстрого доступа к записям. В 1956 году Арнольд Думи и Джордж Коллинз описали метод «открытой адресации» для разрешения коллизий.

В 1970-х годах началось применение хэш-функций в криптографии. В 1979 году Ральф Меркл и Иван Дамгорд независимо друг от друга разработали конструкцию (конструкция Меркла — Дамгорда), на которой основаны многие современные хэш-функции, включая MD5, SHA-1 и SHA-2.

В 1990-х годах Национальный институт стандартов и технологий США (NIST) опубликовал стандарт SHA-1 (1995 год), который стал широко использоваться в протоколах SSL/TLS, PGP и SSH. Однако к 2005 году в SHA-1 были обнаружены серьёзные уязвимости, и NIST объявил конкурс на новый стандарт. В 2012 году победителем стал алгоритм Keccak, который был стандартизирован как SHA-3.

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

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

По назначению

• Криптографические хэш-функции: используются для обеспечения безопасности (SHA-2, SHA-3, BLAKE2). Обладают всеми свойствами односторонности и устойчивости к коллизиям.
• Некриптографические (контрольные суммы): предназначены для обнаружения случайных ошибок передачи данных, но не защищены от целенаправленных атак (CRC32, Adler-32).
• Хэш-функции для хэш-таблиц: оптимизированы на скорость и равномерное распределение по корзинам (MurmurHash, CityHash, xxHash).

По структуре

• На основе блочных шифров: например, хэш-функции, построенные по схеме Дэвиса — Мейера.
• На основе конструкции Меркла — Дамгорда: MD5, SHA-1, SHA-2.
• На основе губчатой конструкции (sponge construction): SHA-3 (Keccak).
• На основе алгебраических структур: например, хэш-функции на основе эллиптических кривых.

Применение

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

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

Целостность данных

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

Хэш-таблицы

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

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

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

Цифровые подписи

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

Криптографические алгоритмы

MD5 (Message Digest 5)

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

SHA-1 (Secure Hash Algorithm 1)

Разработан АНБ США в 1995 году. Выдаёт 160-битный хэш. В 2017 году группа Google и CWI Amsterdam продемонстрировала атаку SHAttered, показавшую возможность создания коллизий. С 2017 года NIST рекомендует отказаться от SHA-1.

SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)

Семейство хэш-функций, разработанное АНБ в 2001 году. Наиболее распространён SHA-256 (256-битный хэш). На 2024 год считается криптостойким и широко используется в TLS, SSH, PGP, блокчейне.

SHA-3 (Keccak)

Победитель конкурса NIST (2012). Основан на губчатой конструкции, отличается от SHA-2 внутренним устройством. Поддерживает размеры хэша 224, 256, 384 и 512 бит. Используется в криптовалютах (например, Ethereum) и протоколах.

BLAKE2

Высокоскоростная хэш-функция, созданная как альтернатива SHA-3. Оптимизирована для программной реализации. Используется в протоколах Zcash, WireGuard, Argon2.

Атаки на хэш-функции

• Атака на коллизию: нахождение двух различных сообщений с одинаковым хэшем. Для SHA-1 такая атака была продемонстрирована в 2017 году.
• Атака на прообраз: нахождение сообщения по его хэшу. Для современных криптографических хэш-функций считается вычислительно невозможной.
• Атака «день рождения»: основана на парадоксе дней рождения, позволяет найти коллизию для n-битного хэша примерно за 2^(n/2) операций.
• Радужные таблицы: предвычисленные таблицы для обратного поиска хэшей паролей. Защита — использование соли.
• Атака удлинения сообщения (length extension attack): уязвимость для хэш-функций на основе конструкции Меркла — Дамгорда (MD5, SHA-1, SHA-2). SHA-3 и BLAKE2 не подвержены этой атаке.

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

• Хэш-функция SHA-1 была взломана группой исследователей, которые потратили на вычисление коллизии около 110 лет процессорного времени (в пересчёте на один процессор).
• Алгоритм MD5 до сих пор используется в некоторых системах для хранения паролей, несмотря на то, что коллизии для него можно найти за несколько секунд на обычном компьютере.
• В криптовалюте биткойн майнеры перебирают триллионы хэшей в секунду, чтобы найти блок с хэшем, начинающимся с определённого количества нулей.
• Хэш-функции используются в системах контроля версий (например, Git) для идентификации коммитов и файлов.
• В 2020 году NIST объявил конкурс на новый стандарт лёгкой криптографии, включая лёгкие хэш-функции для устройств IoT.

Источники

• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996.
• Schneier B. Applied Cryptography. — John Wiley & Sons, 1996.
• 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.
• Wang X., Yu H. How to Break MD5 and Other Hash Functions. — EUROCRYPT, 2005.
• Stevens M., Bursztein E., Karpman P., Albertini A., Markov Y. The First Collision for Full SHA-1. — CRYPTO, 2017.