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

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

Классификация атак

Криптоаналитические атаки классифицируются по нескольким основаниям: по объёму доступной информации, по типу используемого метода, по цели и по характеру воздействия.

По доступной информации

Наиболее распространённая классификация основана на том, какими исходными данными располагает атакующий.

• Атака только по шифротексту (Ciphertext-only attack, COA). Атакующий имеет только перехваченные зашифрованные сообщения. Это наиболее сложный тип атаки, так как отсутствует какая-либо дополнительная информация. Успех зависит от статистических свойств языка открытого текста и слабостей алгоритма. Пример — частотный анализ для классических шифров (например, шифра Цезаря).
• Атака с известным открытым текстом (Known-plaintext attack, KPA). Атакующий знает пары «открытый текст — соответствующий шифротекст». Это позволяет искать закономерности в алгоритме шифрования. Например, при атаке на шифр Вернама (одноразовый блокнот) при повторном использовании ключа.
• Атака с выбранным открытым текстом (Chosen-plaintext attack, CPA). Атакующий может временно получить доступ к шифрующему устройству и зашифровать произвольные сообщения по своему выбору. Это мощный тип атаки, часто используемый в дифференциальном криптоанализе. Если атакующий может выбирать открытые тексты до шифрования, атака называется адаптивной.
• Атака с выбранным шифротекстом (Chosen-ciphertext attack, CCA). Атакующий может расшифровывать произвольные шифротексты, получая соответствующие открытые тексты. Этот тип атаки особенно опасен для асимметричных криптосистем (например, RSA). Различают атаки CCA1 (неадаптивные, до получения целевого шифротекста) и CCA2 (адаптивные, после получения целевого шифротекста). Современные стандарты шифрования, такие как RSA-OAEP, специально проектируются для защиты от CCA2.
• Атака по времени (Timing attack). Атакующий измеряет время выполнения криптографических операций (шифрования, дешифрования, генерации ключа) и по временным вариациям восстанавливает секретные данные (например, секретный ключ). Впервые продемонстрирована Полом Кохером в 1996 году на RSA.
• Атака по энергопотреблению (Power analysis attack). Атакующий анализирует график потребления энергии устройством (например, смарт-картой) во время выполнения криптоопераций. Различают простой (SPA) и дифференциальный (DPA) анализ мощности.
• Атака по побочным каналам (Side-channel attack). Обобщающее название для атак, использующих физическую реализацию криптосистемы: электромагнитное излучение, акустические шумы, тепловые следы, вибрации и т.д.

По методу

• Статистический криптоанализ. Основан на анализе частотных характеристик символов, биграмм, триграмм и т.д. Эффективен против классических шифров (подстановочных, перестановочных) и слабых современных шифров.
• Дифференциальный криптоанализ. Метод, предложенный Эли Бихамом и Ади Шамиром в 1990 году. Анализирует влияние разностей (XOR) между парами открытых текстов на разности соответствующих шифротекстов. Позволяет восстанавливать ключ для симметричных блочных шифров (например, DES). Для DES требовалось около \(2^{47}\) пар открытых текстов.
• Линейный криптоанализ. Метод, предложенный Мицуру Мацуи в 1993 году. Строит линейные аппроксимации (XOR-комбинации битов открытого текста, шифротекста и ключа) и находит ключ по статистическим отклонениям. Для DES требовалось около \(2^{43}\) пар открытых текстов.
• Атака на основе связанных ключей (Related-key attack). Атакующий знает или может задавать соотношения между несколькими неизвестными ключами (например, различие в одном бите). Используется для анализа стойкости алгоритмов (например, AES-256).
• Атака методом «встречи посередине» (Meet-in-the-middle attack). Применяется к каскадным шифрам (двойное или тройное шифрование). Атакующий строит таблицы для всех возможных значений первого ключа и сравнивает их с результатами для второго ключа. Снижает эффективную длину ключа с \(2^{2n}\) до \(2^{n+1}\).
• Квантовый криптоанализ. Использует квантовые алгоритмы (например, алгоритм Шора для факторизации и дискретного логарифмирования, алгоритм Гровера для поиска). Угрожает асимметричным криптосистемам (RSA, ECDSA) и вдвое снижает стойкость симметричных шифров (например, AES-128 до \(2^{64}\)).

По цели

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

История развития

Криптоаналитические атаки развивались параллельно с криптографией. Первые известные атаки — частотный анализ, описанный арабским учёным аль-Кинди в IX веке в трактате «О расшифровке криптографических сообщений». В Средние века и эпоху Возрождения атаки совершенствовались для вскрытия шифров простой замены и перестановки (например, шифр Виженера был взломан в XIX веке Чарльзом Бэббиджем и Фридрихом Касиски).

В XX веке с появлением электромеханических шифровальных машин (например, «Энигма») криптоанализ стал систематическим. Польские и британские криптоаналитики (Мариан Реевский, Алан Тьюринг) разработали атаки, основанные на известных открытых текстах (например, «женские» сообщения) и повторяющихся ключах. Взлом «Энигмы» считается одним из крупнейших достижений криптоанализа.

В 1970-х годах с публикацией стандарта DES началась эра математического криптоанализа. В 1990-х годах дифференциальный и линейный криптоанализ стали стандартными инструментами оценки стойкости. В 2000-х годах внимание сместилось к атакам по побочным каналам и квантовому криптоанализу.

Примеры известных атак

Атака на «Энигму» (1932–1945)

Польские криптоаналитики (Бюро шифров) использовали атаку с известным открытым текстом, основанную на повторяющихся сообщениях (например, «WETTER»). Алан Тьюринг и его команда в Блетчли-парке разработали электромеханические «бомбы» для автоматизации поиска ключей. Атака требовала знания части открытого текста и структуры машины.

Атака на DES (1990–1993)

Эли Бихам и Ади Шамир показали, что DES можно взломать дифференциальным криптоанализом за \(2^{47}\) операций, что значительно быстрее полного перебора (\(2^{55}\)). Мицуру Мацуи продемонстрировал линейный криптоанализ DES, требующий \(2^{43}\) пар. Эти атаки стимулировали разработку новых стандартов (AES).

Атака на RSA с выбранным шифротекстом (1998)

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

Атака на Wi-Fi WPA2 (KRACK, 2017)

Мати Ванхоф и Франк Писсенс продемонстрировали атаку на протокол WPA2, основанную на повторном использовании nonce (одноразового числа) в процессе четырёхстороннего рукопожатия. Атака позволяла расшифровывать трафик в сетях Wi-Fi. Уязвимость была устранена в обновлениях протокола.

Методы защиты

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

• Использование доказательно стойких схем. Например, шифр Вернама (одноразовый блокнот) является абсолютно стойким при условии истинной случайности ключа и его одноразового использования. Однако на практике это редко достижимо.
• Увеличение длины ключа. Для симметричных шифров рекомендуется длина ключа не менее 128 бит (AES-128), для асимметричных — не менее 2048 бит (RSA) или 256 бит (эллиптические кривые).
• Применение современных алгоритмов. AES, ChaCha20, SHA-3, Ed25519 прошли многолетний криптоанализ и считаются стойкими.
• Защита от побочных каналов. Использование константного времени выполнения (constant-time), маскирования (masking), скремблирования данных, экранирования и фильтрации сигналов.
• Квантово-устойчивая криптография. Разработка алгоритмов, стойких к квантовым атакам (например, на решётках, кодах, хэшах). В 2024 году NIST (Национальный институт стандартов и технологий США) стандартизировал алгоритмы CRYSTALS-Kyber (для шифрования) и CRYSTALS-Dilithium (для подписей).
• Регулярное обновление протоколов. Устранение уязвимостей в криптографических протоколах (TLS, SSH, IPsec) путём внедрения новых версий (TLS 1.3, SSH-2).

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

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

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

Источники

• Шнайер Б. «Прикладная криптография». — М.: Триумф, 2002.
• Мао В. «Современная криптография: теория и практика». — М.: Вильямс, 2005.
• Biham E., Shamir A. «Differential Cryptanalysis of the Data Encryption Standard». — Springer, 1993.
• Matsui M. «Linear Cryptanalysis Method for DES Cipher» // Advances in Cryptology — EUROCRYPT’93, 1994.
• Kocher P. «Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems» // Advances in Cryptology — CRYPTO’96, 1996.
• Vanhoef M., Piessens F. «Key Reinstallation Attacks: Forcing Nonce Reuse in WPA2» // CCS’17, 2017.
• NIST. «Post-Quantum Cryptography: Selected Algorithms 2022». — Gaithersburg, 2022.