Хеш-функция: требования к криптографической стойкости

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

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

Формально хеш-функция - это отображение $H: \{0,1\}^* \to \{0,1\}^n$, переводящее битовую строку произвольной длины в строку фиксированной длины $n$ (для SHA-256 это $n = 256$ бит). Результат $h = H(m)$ называют хешем, дайджестом или образом сообщения $m$.

Поскольку область определения бесконечна, а множество значений конечно ($2^n$ вариантов), функция заведомо не инъективна: разные сообщения неизбежно дают одинаковый хеш. Совпадение $H(m_1) = H(m_2)$ при $m_1 \neq m_2$ называют коллизией. Коллизии существуют всегда - вопрос лишь в том, можно ли их найти за разумное время. Именно вокруг этого строятся ключевые требования.

Рассчитать для своей задачи

Требование 1: детерминированность и эффективность

Базовое и очевидное: одно и то же сообщение всегда даёт один и тот же хеш. $H(m)$ не зависит от времени, машины или случайности - иначе проверка целостности была бы невозможна. Если вы скачали файл и сравнили его SHA-256 с эталонным, совпадение хешей должно гарантировать, что байты не изменились.

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

Требование 2: сжатие и фиксированная длина

Выход всегда фиксированной длины $n$ независимо от входа: и однобайтовое сообщение, и гигабайтный файл дают ровно $n$ бит. Это свойство называют сжатием (compression). Оно обеспечивает однородность: хеши можно складывать в таблицы, сравнивать, использовать как ключи и индексы.

Фиксированная длина задаёт и потолок безопасности. Всего возможно $2^n$ различных хешей, поэтому никакая стойкость не может превышать барьер, диктуемый этим числом. Чем больше $n$, тем выше потолок - но и тем дороже вычисление и хранение.

Требование 3: лавинный эффект

Изменение даже одного бита входа должно менять примерно половину битов выхода, причём непредсказуемым образом. Это лавинный эффект (avalanche effect) - строгая форма требования: хеш не должен «коррелировать» с сообщением.

$$m_1 = \text{«привет»}, \quad m_2 = \text{«Привет»} \implies H(m_1) \text{ и } H(m_2) \text{ различаются в} \approx 50\% \text{ битов}$$

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

Рассчитать для своей задачи

Требование 4: односторонность (стойкость к прообразу)

Главное криптографическое требование - односторонность (one-wayness), или стойкость к нахождению прообраза (preimage resistance). По известному хешу $h$ вычислительно невозможно найти такое сообщение $m$, что $H(m) = h$.

Функцию легко посчитать в прямую сторону, но практически нельзя обратить. Именно поэтому хеши паролей хранят вместо самих паролей: даже получив базу хешей, атакующий не может восстановить исходные пароли напрямую - только перебором. Для стойкой $n$-битной функции прямой перебор прообраза требует около $2^n$ операций.

Связанное свойство - стойкость ко второму прообразу (second preimage resistance): по известному сообщению $m_1$ нельзя найти другое $m_2 \neq m_1$ с тем же хешем $H(m_2) = H(m_1)$. Это защищает от подмены конкретного известного документа на поддельный с тем же дайджестом.

Требование 5: стойкость к коллизиям и парадокс дней рождения

Самое сильное требование - стойкость к коллизиям (collision resistance): вычислительно невозможно найти любую пару $m_1 \neq m_2$ такую, что $H(m_1) = H(m_2)$. Здесь атакующий свободен в выборе обоих сообщений, и это резко облегчает задачу по сравнению с поиском прообраза.

Причина - парадокс дней рождения. Чтобы с вероятностью около 50% найти коллизию, нужно перебрать не $2^n$, а лишь порядка $2^{n/2}$ значений:

$$N_{\text{коллизия}} \approx 2^{n/2} \quad \text{против} \quad N_{\text{прообраз}} \approx 2^n$$

Поэтому для 256-битной функции стойкость к прообразу - около $2^{256}$, а к коллизиям - лишь $2^{128}$. Именно из-за квадратичного разрыва длину хеша берут с запасом: чтобы получить 128 бит реальной защиты от коллизий, нужен 256-битный выход.

Три уровня - прообраз, второй прообраз, коллизия - образуют иерархию: стойкость к коллизиям сильнее всего, и её нарушение первым же сигнализирует о «смерти» функции. Так в своё время пали MD5 и SHA-1: для них нашли практические коллизии, хотя полный обратный прообраз так и не научились вычислять.

Рассчитать для своей задачи

Где требования ломаются: история MD5 и SHA-1

Теория хороша, но требования регулярно нарушаются на практике, и это отправляет функции на свалку:

• MD5 (128 бит). В 2004 году китайская группа Ван Сяоюнь нашла метод построения коллизий за минуты. Сегодня для MD5 можно сгенерировать два разных файла с одинаковым хешем на ноутбуке - стойкость к коллизиям полностью разрушена. MD5 нельзя использовать ни для подписей, ни для сертификатов.
• SHA-1 (160 бит). В 2017 году Google и CWI продемонстрировали атаку SHACAL/SHAttered - две разные PDF с одинаковым SHA-1. Это потребовало огромных вычислений, но доказало непригодность SHA-1 для подписи. Браузеры и центры сертификации отказались от него.
• Контрольные суммы (CRC32, Adler). Их вообще нельзя называть криптографическими: они защищают от случайных ошибок передачи, но подделать сообщение под нужную контрольную сумму тривиально - нет ни односторонности, ни стойкости к коллизиям.

Современный стандарт - семейство SHA-2 (SHA-256, SHA-512) и SHA-3 (Keccak), построенный на принципиально иной губчатой конструкции. Для систем, готовящихся к квантовой угрозе, важна также квантово-устойчивая криптография, где требования к длине хеша пересматриваются с учётом алгоритма Гровера.

Зачем все эти требования: применения

Каждое свойство оправдано конкретной задачей:

• Целостность данных. Детерминированность плюс лавинный эффект позволяют по хешу обнаружить любое изменение файла или сообщения.
• Хранение паролей. Односторонность не даёт восстановить пароль из базы хешей (на практике добавляют соль и медленные функции вроде bcrypt/Argon2).
• Цифровая подпись. Подписывают не само сообщение, а его хеш - поэтому стойкость к коллизиям критична. Если её нет, можно подменить подписанный документ. Это лежит в основе цифровой подписи ECDSA.
• Блокчейн и Proof-of-Work. Майнинг - это поиск входа, дающего хеш с нужным числом нулей, что опирается на односторонность и равномерность выхода.
• Структуры данных. Деревья Меркла, хеш-таблицы, дедупликация - везде нужна фиксированная длина и низкая вероятность коллизий.

Частые ошибки

• «Хеш можно расшифровать». Нет. Хеширование - не шифрование, у него нет ключа и обратной операции. Можно лишь перебирать прообразы, и для стойкой функции это вычислительно невозможно.
• «MD5 годится для паролей, если добавить соль». Соль защищает от радужных таблиц, но не лечит сломанную стойкость к коллизиям. MD5 непригоден в принципе; нужны SHA-256 поверх медленной KDF.
• «Длиннее хеш - всегда лучше». Лишняя длина повышает стоимость без выигрыша, если конструкция уязвима. SHA-1 (160 бит) сломан, а SHA-256 надёжен - дело в алгоритме, а не только в числе бит.
• «Стойкость к прообразу и к коллизиям - одно и то же». Нет. Из-за парадокса дней рождения коллизию найти на порядки легче ($2^{n/2}$ против $2^n$). Функция может потерять стойкость к коллизиям, сохраняя односторонность.
• «Контрольная сумма защищает от подделки». CRC защищает только от случайных искажений. Подделать данные под заданный CRC элементарно - это не криптографическая функция.

FAQ

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

Почему длину хеша берут вдвое больше нужной стойкости? Из-за парадокса дней рождения коллизию находят за $2^{n/2}$ операций, а не за $2^n$. Чтобы гарантировать 128 бит защиты от коллизий, нужен 256-битный выход. Это требование напрямую следует из вероятностной оценки совпадений.

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

Коротко

Криптографическая хеш-функция обязана удовлетворять связке требований: детерминированность и быстрое вычисление, сжатие до фиксированной длины $n$, лавинный эффект (один бит входа меняет половину выхода), односторонность (по хешу нельзя найти прообраз, около $2^n$ операций) и три уровня стойкости - к прообразу, второму прообразу и коллизиям. Из-за парадокса дней рождения коллизия находится за $2^{n/2}$, поэтому длину берут с двойным запасом. Нарушение стойкости к коллизиям убивает функцию первым - так пали MD5 и SHA-1. Контрольные суммы вроде CRC не криптографичны: они ловят случайные ошибки, но не защищают от подделки. Современный выбор - SHA-256 и SHA-3.