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

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

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

Стойкость к прообразу (англ. preimage resistance) означает, что для заданного хеш-значения \( h \) вычислительно невозможно найти какое-либо входное сообщение \( m \), такое что \( \text{Hash}(m) = h \). Формально, для любого вероятностного полиномиального алгоритма \( A \) вероятность успеха \( \Pr[A(h) = m] \) пренебрежимо мала, где \( h \) — случайно выбранное значение из области значений хеш-функции.

Различают два основных типа стойкости:

• Стойкость к прообразу первого рода (preimage resistance): для фиксированного хеш-значения \( h \) сложно найти любой прообраз \( m \).
• Стойкость к прообразу второго рода (second-preimage resistance): для заданного сообщения \( m_1 \) сложно найти другое сообщение \( m_2 \neq m_1 \), такое что \( \text{Hash}(m_1) = \text{Hash}(m_2) \). Это свойство также называют стойкостью к коллизиям второго рода.

¶Математическая основа

Стойкость к прообразу базируется на односторонности хеш-функции. Функция \( f: \{0,1\}^* \to \{0,1\}^n \) считается односторонней, если:

1. Существует полиномиальный алгоритм вычисления \( f(x) \) для любого \( x \).
2. Для любого вероятностного полиномиального алгоритма \( A \) вероятность найти прообраз \( x \) по заданному \( y = f(x) \) пренебрежимо мала.

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

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

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

• MD5 (Message Digest 5, 1991): длина хеша 128 бит. В 2004 году китайские криптографы Ван Сяоюнь и Ю Хунбо продемонстрировали практическую атаку на коллизии, а в 2009 году — атаку на прообраз с трудоёмкостью \( 2^{123.4} \) операций, что лишь незначительно ниже полного перебора \( 2^{128} \). Однако для практических целей MD5 считается небезопасным.
• SHA-1 (Secure Hash Algorithm 1, 1995): длина хеша 160 бит. В 2017 году компания Google и CWI Amsterdam объявили о первой практической коллизии (атака SHAttered). Стойкость к прообразу теоретически составляет \( 2^{160} \), но из-за структурных уязвимостей фактическая стойкость ниже.
• SHA-2 (SHA-256, SHA-512, 2001): длина хеша 256/512 бит. На 2025 год не известно практических атак на прообраз или коллизии. Считается безопасным для большинства применений.
• SHA-3 (Keccak, 2015): разработан после конкурса NIST, имеет принципиально иную структуру (губка). Обеспечивает заявленную стойкость.

¶Современные стандарты

В России действует национальный стандарт ГОСТ Р 34.11-2012 («Стрибог»), утверждённый Федеральным агентством по техническому регулированию и метрологии. Функция имеет длину хеша 256 или 512 бит. Стойкость к прообразу для варианта с 256 битами составляет \( 2^{256} \) операций, для 512 бит — \( 2^{512} \). На 2025 год не опубликовано атак, снижающих заявленную стойкость.

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

¶Методы атак

• Полный перебор (brute force): универсальный метод, требующий в среднем \( 2^{n-1} \) попыток для нахождения прообраза. Для n=256 это практически нереализуемо.
• Атака «дней рождения»: применима для поиска коллизий второго рода, снижая сложность до \( 2^{n/2} \).
• Криптоаналитические атаки: используют структурные особенности алгоритма. Например, атака на MD5 (2009) снизила сложность до \( 2^{123.4} \).
• Атаки на основе квантовых вычислений: алгоритм Гровера теоретически позволяет найти прообраз за \( 2^{n/2} \) операций, что вдвое снижает эффективную стойкость. Для SHA-256 это означает \( 2^{128} \) операций, что всё ещё считается вычислительно невозможным.

¶Практические примеры

• Атака на MD5 (2009): группа исследователей под руководством Тао Се и Фэн Дэн-Го опубликовала метод нахождения прообраза для MD5 с трудоёмкостью \( 2^{123.4} \). Хотя это не является практической атакой (требует огромных вычислительных ресурсов), она демонстрирует, что теоретическая стойкость MD5 ниже заявленной.
• Атака на SHA-1 (2020): группа Gaëtan Leurent и Thomas Peyrin продемонстрировала атаку на прообраз для SHA-1 с трудоёмкостью \( 2^{159.3} \), что лишь незначительно ниже полного перебора \( 2^{160} \).

¶Применение стойкости к прообразу

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

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

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

В схемах цифровой подписи (например, RSA, DSA, ГОСТ Р 34.10-2012) хеш-функция используется для сжатия подписываемого сообщения. Стойкость к прообразу предотвращает подделку подписи: злоумышленник не может подобрать сообщение, хеш которого совпадает с хешем подписанного документа.

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

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

¶Системы контроля целостности

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

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

¶Квантовая угроза

Развитие квантовых компьютеров представляет потенциальную угрозу для стойкости к прообразу. Алгоритм Гровера теоретически снижает сложность поиска прообраза с \( 2^n \) до \( 2^{n/2} \). Для SHA-256 это означает \( 2^{128} \) операций, что всё ещё считается вычислительно невозможным, но для SHA-128 (если бы он использовался) это было бы \( 2^{64} \) — уже потенциально достижимо. Для защиты от квантовых атак рекомендуется использовать хеш-функции с длиной выхода не менее 256 бит.

¶Ограничения практической реализации

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

¶Сравнение с другими свойствами

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

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

• В 2019 году исследователи из Google и ETH Zurich продемонстрировали атаку на SHA-1 с использованием облачных вычислений, затратив около 110 000 долларов на вычислительные ресурсы. Это показало, что теоретическая стойкость может быть преодолена при достаточных ресурсах.
• Алгоритм MD5, несмотря на доказанную уязвимость, всё ещё используется в некоторых устаревших системах, что создаёт риски для безопасности.
• В России разработка хеш-функции «Стрибог» (ГОСТ Р 34.11-2012) велась с учётом требований стойкости к квантовым атакам, что делает её перспективной для будущих применений.

¶Источники

• Книга: «Криптография: теория и практика» (Дуглас Стинсон, 3-е издание, 2005)
• Статья: «Preimage Attack on MD5» (Тао Се, Фэн Дэн-Го, 2009)
• Стандарт: ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хеширования»
• Документ NIST: «Secure Hash Standard (SHS)» (FIPS PUB 180-4, 2015)
• Статья: «Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms» (Мартин Рёттелер и др., 2017)