Стойкость ко второму прообразу¶

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

¶Определение и формальное описание

Формально, для хеш-функции \( H: \{0,1\}^* \to \{0,1\}^n \), стойкость ко второму прообразу означает, что для любого фиксированного входного сообщения \( x \) вычислительно невозможно найти другое сообщение \( x' \neq x \), такое что \( H(x) = H(x') \). Иными словами, зная хеш-значение \( h = H(x) \), злоумышленник не может найти \( x' \), отличное от \( x \), которое даёт тот же хеш.

Это свойство отличается от стойкости к коллизиям, где требуется найти любую пару различных сообщений \( (x, x') \) с одинаковым хешем, без ограничения на одно из них. Стойкость ко второму прообразу считается более слабым требованием: если функция стойка к коллизиям, она автоматически стойка и ко второму прообразу, но обратное неверно.

¶Связь с другими свойствами

¶Стойкость к прообразу

Стойкость к прообразу (preimage resistance) требует, чтобы по заданному хеш-значению \( h \) было невозможно найти ни одного сообщения \( x \), такого что \( H(x) = h \). Стойкость ко второму прообразу является более сильным свойством: если функция не стойка к прообразу, это не означает автоматически уязвимость ко второму прообразу, но на практике уязвимости часто коррелируют.

¶Стойкость к коллизиям

Стойкость к коллизиям (collision resistance) — наиболее строгое требование. Если функция стойка к коллизиям, то она стойка и ко второму прообразу, и к прообразу. Однако обратное неверно: существуют функции, стойкие ко второму прообразу, но уязвимые к коллизиям (например, усечённые хеши).

¶Практическое значение

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

• Цифровые подписи: при подписании сообщения \( x \) подписывается его хеш \( H(x) \). Если злоумышленник сможет найти другое сообщение \( x' \) с тем же хешем, он сможет выдать подпись за подпись под \( x' \), что нарушает аутентичность.
• Хеширование паролей: при хранении паролей в виде хешей стойкость ко второму прообразу предотвращает подбор другого пароля, дающего тот же хеш, что и известный пароль.
• Системы контроля версий: в системах вроде Git, где каждый коммит идентифицируется хешем, стойкость ко второму прообразу гарантирует, что нельзя подменить содержимое коммита без изменения его идентификатора.

¶Атаки на стойкость ко второму прообразу

¶Атака «дня рождения»

Классическая атака «дня рождения» нацелена на поиск коллизий, а не вторых прообразов. Для поиска второго прообраза требуется перебор в среднем \( 2^n \) попыток, где \( n \) — длина хеша в битах. Это значительно больше, чем \( 2^{n/2} \) для коллизий.

¶Атаки на основе структуры хеш-функции

Некоторые хеш-функции, такие как MD5 и SHA-1, имеют уязвимости, позволяющие находить вторые прообразы быстрее, чем полным перебором. Например, для SHA-1 (длина хеша 160 бит) теоретическая стойкость ко второму прообразу составляет \( 2^{160} \) операций, но практические атаки на коллизии снижают этот показатель до \( 2^{63} \) для коллизий, что косвенно влияет на стойкость ко второму прообразу.

¶Атаки с использованием длинных сообщений

Для хеш-функций, построенных по схеме Меркла-Дамгора (например, MD5, SHA-1, SHA-2), существует атака, позволяющая находить вторые прообразы для длинных сообщений быстрее, чем \( 2^n \). В 2005 году Джон Келси и Брюс Шнайер показали, что для сообщения длиной \( 2^k \) блоков сложность атаки составляет \( k \cdot 2^{n/2+1} + 2^{n-k+1} \). Для SHA-1 с сообщением в \( 2^{55} \) блоков сложность падает до \( 2^{106} \) операций, что всё ещё выше практического порога, но демонстрирует теоретическую уязвимость.

¶Примеры хеш-функций и их стойкость

¶Критика и ограничения

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

Кроме того, стойкость ко второму прообразу не защищает от атак, основанных на социальной инженерии или ошибках реализации. Например, если злоумышленник может заставить жертву подписать сообщение \( x \), а затем подменить его на \( x' \) с тем же хешем, это нарушает безопасность, даже если функция формально стойка.

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

• Термин «стойкость ко второму прообразу» часто путают с «стойкостью к коллизиям», хотя это разные свойства. В российских стандартах (ГОСТ Р 34.11-2012) используется термин «стойкость к нахождению второго прообраза».
• В 2004 году группа китайских криптографов под руководством Сяоюня Ванга опубликовала атаки на MD5, SHA-0 и SHA-1, которые существенно снизили их стойкость ко второму прообразу.
• Современные хеш-функции, такие как SHA-3 и BLAKE2, спроектированы с учётом этих атак и обеспечивают высокую стойкость ко второму прообразу.

¶Источники

• Криптографические хеш-функции: теория и практика. — М.: Наука, 2010.
• Kelsey J., Schneier B. Second Preimages on n-bit Hash Functions for Much Less than 2^n Work. — 2005.
• Wang X. et al. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. — 2004.
• ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хеширования.
• Menezes A. et al. Handbook of Applied Cryptography. — CRC Press, 1996.