Семантическая стойкость

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

История и происхождение понятия

Понятие семантической стойкости было введено в 1984 году Шафи Гольдвассером и Сильвио Микали в их работе «Probabilistic Encryption». До этого основным критерием безопасности шифров считалась стойкость к атаке на основе только шифротекста (COA — Ciphertext-Only Attack), которая, однако, не гарантировала защиты от утечки частичной информации. Например, классический шифр Вернама (одноразовый блокнот) стоек в смысле COA, но если два сообщения зашифрованы одним и тем же ключом, противник может вычислить разность открытых текстов.

Гольдвассер и Микали предложили более строгое определение: шифр называется семантически стойким, если для любого вероятностного полиномиального противника, который знает распределение открытых текстов, вероятность угадать любой бит открытого текста по шифротексту отличается от 1/2 на пренебрежимо малую величину. Это определение было формализовано в рамках теории сложности вычислений и стало основой для построения доказуемо стойких криптосистем.

Формальное определение

Пусть \( \Pi = (\text{Gen}, \text{Enc}, \text{Dec}) \) — схема шифрования с секретным ключом, где Gen — алгоритм генерации ключа, Enc — алгоритм шифрования, Dec — алгоритм расшифрования. Схема называется семантически стойкой (или IND-CPA — Indistinguishability under Chosen Plaintext Attack), если для любого вероятностного полиномиального противника \( \mathcal{A} \) выполняется следующее условие:

1. Противник выбирает два сообщения \( m_0 \) и \( m_1 \) одинаковой длины.
2. Система выбирает случайный бит \( b \in \{0,1\} \) и шифрует сообщение \( m_b \), получая шифротекст \( c \).
3. Противник получает \( c \) и должен угадать \( b \).

Вероятность успеха противника не должна превышать \( \frac{1}{2} + \text{negl}(n) \), где \( \text{negl}(n) \) — пренебрежимо малая функция от параметра безопасности \( n \).

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

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

IND-CPA (Indistinguishability under Chosen Plaintext Attack)

Семантическая стойкость в модели с выбором открытого текста (CPA) является стандартным минимальным требованием для современных шифров. В этой модели противник может запрашивать шифрование любых сообщений по своему выбору, но не может расшифровывать. Если шифр стоек в смысле IND-CPA, он автоматически является семантически стойким. Обратное также верно: семантическая стойкость влечёт IND-CPA. Это эквивалентные понятия в рамках симметричной криптографии.

IND-CCA (Indistinguishability under Chosen Ciphertext Attack)

Более сильное свойство — стойкость к атаке с выбором шифротекста (CCA). В этой модели противник может запрашивать расшифрование произвольных шифротекстов (кроме целевого). Семантическая стойкость не гарантирует защиты от CCA-атак. Например, схема шифрования Эль-Гамаля является семантически стойкой (IND-CPA), но не стойкой к CCA-атакам, так как противник может модифицировать шифротекст и получить информацию о расшифрованном сообщении. Для достижения IND-CCA требуется использование дополнительных механизмов, таких как проверка целостности (например, схема OAEP для RSA).

Стойкость к атаке на основе только шифротекста (COA)

Семантическая стойкость является более сильным свойством, чем COA. В классической криптографии (например, шифр Цезаря или Виженера) шифры не являются семантически стойкими, так как противник может получить статистическую информацию о частоте символов. Современные блочные шифры (AES, ГОСТ 28147-89) в режимах, обеспечивающих вероятностное шифрование (например, CBC с случайным вектором инициализации), могут быть семантически стойкими, если они удовлетворяют определённым предположениям (например, что AES является псевдослучайной перестановкой).

Примеры семантически стойких схем

Симметричные шифры

• AES в режиме CBC (Cipher Block Chaining) с случайным вектором инициализации (IV) обеспечивает семантическую стойкость, если AES является псевдослучайной перестановкой. Однако CBC не является стойким к CCA-атакам, так как противник может манипулировать IV.
• AES в режиме CTR (Counter) с случайным начальным значением счётчика также является семантически стойким, так как каждый блок шифруется с уникальным значением счётчика, что делает шифротекст неотличимым от случайного.
• Режим GCM (Galois/Counter Mode) сочетает шифрование в режиме CTR с аутентификацией, что обеспечивает как семантическую стойкость, так и стойкость к CCA-атакам (при условии корректной реализации).

Асимметричные шифры

• Схема Эль-Гамаля является семантически стойкой в предположении сложности задачи Диффи-Хеллмана (CDH) или задачи принятия решения Диффи-Хеллмана (DDH). Однако она не стойка к CCA-атакам без дополнительных модификаций.
• RSA-OAEP (Optimal Asymmetric Encryption Padding) — это схема, основанная на RSA, которая доказуемо является семантически стойкой в модели случайного оракула (Random Oracle Model) и стойкой к CCA-атакам. OAEP добавляет случайное заполнение и проверку целостности.
• Схема Cramer-Shoup — это асимметричный шифр, который доказуемо является семантически стойким и стойким к CCA-атакам без использования модели случайного оракула, на основе предположения DDH.

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

Семантическая стойкость, хотя и является важным теоретическим критерием, не охватывает все возможные угрозы. Например:

• Атаки по побочным каналам (side-channel attacks): семантическая стойкость не гарантирует защиты от атак, основанных на времени выполнения, потребляемой мощности или электромагнитном излучении. Даже если шифр семантически стоек в теоретическом смысле, практическая реализация может быть уязвима.
• Атаки на основе длины сообщения: семантическая стойкость не скрывает длину открытого текста. Противник может получить информацию о длине сообщения, что в некоторых приложениях (например, в системах анонимности или базах данных) может быть критичным.
• Квантовые атаки: с развитием квантовых компьютеров многие классические схемы, считающиеся семантически стойкими (например, RSA-OAEP, Эль-Гамаля), могут быть взломаны с помощью алгоритма Шора. Для защиты от квантовых атак требуются постквантовые криптосистемы, такие как схемы на основе решёток (например, CRYSTALS-Kyber, признанный стандартом NIST в 2024 году).
• Практическая реализация: семантическая стойкость часто требует вероятностного шифрования, что может увеличивать размер шифротекста и снижать производительность. Например, в режиме CBC каждый шифротекст содержит случайный IV, что добавляет 16 байт к каждому сообщению.

Применение

Семантическая стойкость является обязательным требованием для большинства современных криптографических протоколов и стандартов. В России требования к стойкости шифров регламентируются ГОСТ Р 34.10-2012 (для электронной подписи) и ГОСТ Р 34.12-2015 (для блочных шифров «Кузнечик» и «Магма»). Оба стандарта поддерживают режимы, обеспечивающие семантическую стойкость (например, режим CTR для «Кузнечика»). В международных стандартах, таких как TLS 1.3, используются только шифры, удовлетворяющие IND-CCA (например, AES-GCM или ChaCha20-Poly1305), что гарантирует семантическую стойкость и защиту от атак с выбором шифротекста.

Источники

1. Goldwasser S., Micali S. Probabilistic Encryption // Journal of Computer and System Sciences, 1984.
2. Katz J., Lindell Y. Introduction to Modern Cryptography, 3rd edition, CRC Press, 2020.
3. Шнайер Б. Прикладная криптография, 2-е издание, Вильямс, 2002.
4. ГОСТ Р 34.12-2015. Информационная технология. Криптографическая защита информации. Блочные шифры.
5. NIST SP 800-38A. Recommendation for Block Cipher Modes of Operation, 2001.