Атака на прообраз

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

Типы атак на прообраз

Различают два основных типа атак на прообраз, различающихся по постановке задачи и сложности выполнения.

Полная атака на прообраз (first-preimage attack)

При полной атаке на прообраз злоумышленник, зная значение хеш-функции \( h = H(m) \), должен найти любое сообщение \( m' \), такое что \( H(m') = h \). При этом \( m' \) может не совпадать с исходным сообщением \( m \). Успешное выполнение такой атаки означает, что хеш-функция не обладает свойством необратимости (однонаправленности). Для идеальной хеш-функции с длиной выхода \( n \) бит сложность полной атаки на прообраз составляет \( 2^n \) операций (полный перебор всех возможных сообщений).

Атака на второй прообраз (second-preimage attack)

При атаке на второй прообраз злоумышленник знает исходное сообщение \( m \) и его хеш \( h = H(m) \). Его задача — найти другое сообщение \( m' \neq m \), такое что \( H(m') = h \). Успешное выполнение такой атаки нарушает свойство коллизионной стойкости второго рода (слабой коллизионной стойкости). Для идеальной хеш-функции сложность атаки на второй прообраз также составляет \( 2^n \) операций, однако на практике она может быть несколько ниже, чем для полной атаки, из-за особенностей структуры некоторых хеш-функций.

Отличие от атаки на коллизию

Атаку на прообраз не следует путать с атакой на коллизию (collision attack). При атаке на коллизию злоумышленник ищет два произвольных различных сообщения \( m_1 \) и \( m_2 \), таких что \( H(m_1) = H(m_2) \). В этом случае злоумышленник не ограничен заданным значением хеша и может выбирать оба сообщения произвольно. Сложность атаки на коллизию для идеальной хеш-функции составляет \( 2^{n/2} \) операций (из-за парадокса дней рождения), что значительно меньше, чем для атаки на прообраз. Таким образом, атака на прообраз является более сложной задачей, чем атака на коллизию.

Методы реализации

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

Метод полного перебора (brute force)

Самый простой, но практически неосуществимый для больших \( n \) метод. Злоумышленник последовательно перебирает все возможные сообщения, вычисляет их хеш и сравнивает с заданным. Для хеш-функций с длиной выхода 128 бит и более такой перебор требует нереалистичных вычислительных ресурсов.

Атака «дней рождения» (birthday attack)

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

Криптоаналитические методы

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

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

Примеры уязвимых хеш-функций

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

MD5

Хеш-функция MD5 (128-битный выход) долгое время считалась стойкой, однако к 2008 году были найдены атаки на прообраз со сложностью \( 2^{123,4} \) операций, что лишь незначительно ниже полного перебора (\( 2^{128} \)). Практическая реализация таких атак остаётся крайне сложной, но теоретическая уязвимость существует.

SHA-1

Для SHA-1 (160-битный выход) в 2015 году была опубликована атака на прообраз со сложностью \( 2^{157} \) операций, что значительно ниже \( 2^{160} \). Однако и эта атака остаётся на грани практической реализуемости. В 2017 году Google и CWI Amsterdam продемонстрировали первую практическую коллизию для SHA-1, что подтвердило его нестойкость.

SHA-0 и SHA-1 (упрощённые версии)

Для усечённых версий SHA-0 и SHA-1 (например, с выходом 80 бит) были найдены практические атаки на прообраз, демонстрирующие возможность их взлома на современном оборудовании.

Защита от атак на прообраз

Для обеспечения стойкости к атакам на прообраз используются следующие подходы:

• Использование хеш-функций с достаточной длиной выхода (не менее 256 бит для современных приложений). Рекомендуется SHA-256, SHA-3, BLAKE2.
• Применение криптографических соли (случайных добавок к сообщению) — усложняет атаку, так как злоумышленник не может заранее вычислить хеш для известных сообщений.
• Использование итеративных схем (например, HMAC) — позволяет повысить стойкость даже при использовании уязвимых хеш-функций.
• Регулярное обновление криптографических стандартов — отказ от устаревших и уязвимых хеш-функций в пользу современных.

Значение в криптографии

Атаки на прообраз имеют критическое значение для оценки безопасности криптографических систем. Они применяются в следующих областях:

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

Источники

• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
• Wang, X., Yu, H. (2005). «How to Break MD5 and Other Hash Functions». Advances in Cryptology – EUROCRYPT 2005.
• Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y. (2017). «The first collision for full SHA-1». CRYPTO 2017.
• National Institute of Standards and Technology (NIST). (2015). SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions (FIPS PUB 202).