Атака на основе связанных ключей

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

История возникновения и развития

Концепция атаки на основе связанных ключей была впервые формально предложена в 1992 году израильскими криптографами Эли Бихамом и Ади Шамиром в контексте анализа алгоритма DES. В своей работе они показали, что если злоумышленник может получить шифротексты для нескольких ключей, различающихся на известную величину, то сложность полного перебора может быть существенно снижена. Однако широкое признание и систематическое изучение этот класс атак получил в 1990-х — начале 2000-х годов, когда были найдены эффективные атаки на ряд популярных шифров, включая AES (в некоторых конфигурациях), IDEA, Blowfish и другие.

Развитие атак на связанных ключах стимулировало разработку более устойчивых алгоритмов. В частности, конкурс AES (1997—2000) учитывал устойчивость к этому типу атак как один из критериев отбора. Тем не менее, для многих шифров, особенно с простым расписанием ключей, атаки остаются актуальными. В 2009 году группа исследователей (Алекс Бирюков, Дмитрий Ховратович, Иво Николич) представила атаку на основе связанных ключей на полный AES-256, что вызвало дискуссии о достаточности его ключевого расписания.

Механизм атаки

Основные предположения

Атака на основе связанных ключей предполагает, что злоумышленник обладает следующими возможностями:

• Доступ к оракулу шифрования: может получать шифротексты для произвольных открытых текстов на нескольких неизвестных ключах.
• Контроль над связями: может выбирать разности (или другие соотношения) между ключами. Например, если исходный ключ \( K \), то злоумышленник может запросить шифрование на ключах \( K \oplus \Delta_1 \), \( K \oplus \Delta_2 \) и т. д., где \( \Delta_i \) — известные константы.
• Неизвестность ключей: сами ключи \( K \) остаются неизвестными, но их взаимосвязь известна.

Типы связей

Наиболее распространённые виды связей между ключами:

• Разностная связь: ключи различаются на фиксированную разность (XOR или вычитание по модулю).
• Циклическая связь: один ключ является циклическим сдвигом другого.
• Аффинная связь: ключи связаны линейным преобразованием (например, \( K_2 = a \cdot K_1 + b \)).

Общий сценарий

Атака обычно реализуется в два этапа:

1. Сбор данных: злоумышленник получает пары (открытый текст, шифротекст) для нескольких связанных ключей.
2. Анализ: используя известные соотношения между ключами, криптоаналитик пытается вывести информацию о самих ключах или о внутреннем состоянии шифра. Часто применяются методы дифференциального криптоанализа, когда разности открытых текстов и шифротекстов сопоставляются с разностями ключей.

Классификация атак на основе связанных ключей

По цели воздействия

• Атаки на восстановление ключа: нацелены на полное или частичное определение секретного ключа.
• Атаки на различение: позволяют отличить шифр от случайной перестановки при использовании связанных ключей.
• Атаки на предсказание: позволяют предсказывать поведение шифра при определённых изменениях ключа.

По методу анализа

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

По объёму данных

• Атаки с малым числом связанных ключей (2–4 ключа): часто применяются к шифрам с коротким расписанием.
• Атаки с большим числом связанных ключей (десятки и сотни): требуются для сложных шифров, например, AES-256.

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

На AES-256

В 2009 году была опубликована атака на полный AES-256 (10 раундов) с использованием двух связанных ключей. Сложность атаки составила около \( 2^{119} \) операций, что значительно ниже полного перебора (\( 2^{256} \)). Атака основана на построении дифференциальных характеристик, проходящих через несколько раундов, и использовании коллизий в расписании ключей. Для AES-128 и AES-192 подобные атаки не найдены или имеют сложность, близкую к полному перебору.

На IDEA

Шифр IDEA (International Data Encryption Algorithm) был подвержен атаке на основе связанных ключей, требующей всего \( 2^{64} \) операций при использовании четырёх связанных ключей. Уязвимость связана с линейным преобразованием в расписании ключей.

На Blowfish

Для Blowfish (16 раундов) была показана атака на основе связанных ключей со сложностью \( 2^{48} \) операций, что обусловлено слабой зависимостью раундовых ключей от основного.

На хеш-функции

Атаки на основе связанных ключей применяются к хеш-функциям, построенным на блочных шифрах (например, MDC-2, MDC-4). В 2005 году была найдена атака на хеш-функцию на основе AES-256, позволяющая находить коллизии с практической сложностью.

Уязвимые алгоритмы и устойчивость

Шифры, подверженные атаке

• AES-256: атака на полный шифр (10 раундов) со сложностью \( 2^{119} \).
• IDEA: атака на 4 из 8 раундов.
• Blowfish: атака на 16 раундов.
• GOST 28147-89: атака на основе связанных ключей на 8 из 32 раундов со сложностью \( 2^{56} \).
• KASUMI: атака на 6 из 8 раундов.

Шифры, устойчивые к атаке

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

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

Реалистичность модели

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

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

Значение для проектирования

Несмотря на ограниченную практическую применимость, атаки на основе связанных ключей важны для оценки запаса прочности шифров. Они выявляют скрытые слабости в расписании ключей и структуре раундовых преобразований. Современные стандарты (например, AES-128, ChaCha20) и конкурсы (CAESAR, NIST Lightweight Cryptography) учитывают устойчивость к этому классу атак как один из критериев.

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

Атаки на основе связанных ключей часто комбинируются с другими методами:

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

Критика и перспективы

Некоторые криптографы (например, Брюс Шнайер) критикуют атаки на основе связанных ключей за их искусственность, утверждая, что они редко встречаются на практике. Однако другие (в частности, Эли Бихам) отмечают, что такие атаки являются важным инструментом для понимания внутренней структуры шифров. В 2010-х годах интерес к этому классу атак снизился из-за перехода к шифрам с более сложным расписанием ключей и использованию режимов, устойчивых к связанным ключам (например, режим CTR с независимыми ключами).

Современные исследования сосредоточены на поиске атак на лёгковесные шифры (например, PRESENT, SPECK, SIMON), используемые в интернете вещей (IoT), где расписание ключей часто упрощено для экономии ресурсов.

Источники

• Biham E., Shamir A. Differential Cryptanalysis of the Data Encryption Standard. — Springer, 1993.
• Biryukov A., Khovratovich D., Nikolic I. Distinguisher and Related-Key Attack on the Full AES-256 // CRYPTO 2009.
• Kelsey J., Schneier B., Wagner D. Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA // ICICS 1997.
• National Institute of Standards and Technology (NIST). Advanced Encryption Standard (AES) — FIPS 197, 2001.
• Шнайер Б. Прикладная криптография. — 2-е изд. — Вильямс, 2002.