Атака по взаимной информации

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

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

Метод атаки по взаимной информации был разработан в рамках развития теории информации, заложенной Клодом Шенноном в 1940-х годах. В своей работе «Теория связи в секретных системах» (1949) Шеннон впервые формализовал понятия энтропии, условной энтропии и взаимной информации применительно к криптографии. Он показал, что для обеспечения совершенной секретности взаимная информация между открытым текстом и шифротекстом должна быть равна нулю, то есть шифротекст не должен нести никакой информации об открытом тексте.

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

Теоретические основы

Понятие взаимной информации

Взаимная информация — это мера зависимости между двумя случайными величинами. В криптографии она определяется как количество информации, которое одна величина (например, шифротекст) содержит о другой (например, открытый текст). Формально взаимная информация \( I(X;Y) \) между случайными величинами \( X \) (открытый текст) и \( Y \) (шифротекст) вычисляется как:

\[ I(X;Y) = H(X) - H(X|Y) \]

где \( H(X) \) — энтропия открытого текста, а \( H(X|Y) \) — условная энтропия открытого текста при известном шифротексте. Чем выше значение взаимной информации, тем сильнее статистическая зависимость между \( X \) и \( Y \), что указывает на потенциальную уязвимость шифра.

Принцип атаки

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

Классификация атак по взаимной информации

По типу доступа к данным

1. Атака по известному открытому тексту — криптоаналитик имеет пары «открытый текст — шифротекст» для некоторого набора данных. Вычисляется взаимная информация между известными открытыми текстами и соответствующими шифротекстами.
2. Атака по выбранному открытому тексту — криптоаналитик может выбирать открытые тексты и получать их шифротексты. Это позволяет оптимизировать статистический анализ, выбирая тексты с определёнными свойствами.
3. Атака по шифротексту — доступен только шифротекст. В этом случае взаимная информация вычисляется между шифротекстом и статистической моделью открытого текста (например, на основе частотности букв в языке).

По типу шифра

1. Блочные шифры — атака применяется для анализа режимов шифрования (ECB, CBC, CTR). Например, в режиме ECB при повторяющихся блоках открытого текста взаимная информация между блоками шифротекста будет высокой, что позволяет выявить структуру данных.
2. Поточные шифры — атака направлена на восстановление ключевого потока. Если генератор псевдослучайных чисел имеет статистические дефекты, взаимная информация между шифротекстом и открытым текстом будет ненулевой.
3. Криптосистемы с открытым ключом — атака используется для анализа схем шифрования на основе решёток (например, NTRU) или эллиптических кривых. Взаимная информация может быть вычислена между открытым ключом и шифротекстом.

Применение

Анализ стойкости шифров

Атака по взаимной информации применяется для оценки криптостойкости алгоритмов шифрования. Если для данного шифра взаимная информация между открытым текстом и шифротекстом статистически значимо отличается от нуля, это свидетельствует о наличии уязвимости. Например, в 2000-х годах было показано, что для некоторых реализаций шифра DES с укороченным ключом взаимная информация может быть использована для восстановления ключа с меньшей вычислительной сложностью, чем полный перебор.

Криптоанализ поточных шифров

Для поточных шифров, таких как RC4 или A5/1, атака по взаимной информации позволяет выявить корреляции между битами ключевого потока и открытым текстом. В частности, для шифра RC4 было обнаружено, что второй байт ключевого потока имеет ненулевую взаимную информацию с первым байтом ключа, что привело к разработке практических атак на протокол WEP.

Анализ протоколов связи

Метод используется для проверки безопасности протоколов передачи данных, таких как TLS, SSH или VPN. Криптоаналитик может перехватить шифротрафик и вычислить взаимную информацию между пакетами данных, чтобы выявить утечки информации о длине сообщений или их структуре.

Примеры атак

Атака на шифр DES

В 1998 году была опубликована работа, в которой показано, что для шифра DES с 16 раундами взаимная информация между открытым текстом и шифротекстом после 8 раундов составляет около 0,01 бита, что указывает на неполное рассеивание информации. Это позволило разработать атаку с использованием дифференциального криптоанализа, которая требовала около \( 2^{47} \) выбранных открытых текстов.

Атака на шифр RC4

В 2001 году исследователи продемонстрировали, что для шифра RC4 взаимная информация между первым байтом ключа и вторым байтом ключевого потока составляет около 0,05 бита. Это привело к созданию атаки, которая позволяла восстановить ключ за \( O(2^{20}) \) операций при наличии около 1000 перехваченных пакетов.

Атака на протокол WEP

Протокол WEP (Wired Equivalent Privacy), использовавшийся в беспроводных сетях, был подвержен атаке по взаимной информации из-за уязвимости в шифре RC4. Криптоаналитики могли перехватить пакеты данных и вычислить взаимную информацию между шифротекстом и известными заголовками пакетов, что позволяло восстановить ключ за несколько минут. В результате протокол WEP был признан небезопасным и заменён на WPA и WPA2.

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

Атака по взаимной информации имеет ряд ограничений:

• Вычислительная сложность — для перебора всех возможных ключей и вычисления взаимной информации требуются значительные вычислительные ресурсы, особенно для длинных ключей (например, 256-битных).
• Необходимость статистических данных — метод эффективен только при наличии достаточного объёма перехваченных данных (обычно тысячи или миллионы блоков). Для коротких сообщений статистическая значимость может быть низкой.
• Зависимость от модели открытого текста — атака требует точной статистической модели открытого текста (например, распределения букв в языке). Если модель не соответствует реальным данным, результаты могут быть ложными.
• Устойчивость современных шифров — современные алгоритмы шифрования, такие как AES-256 или ChaCha20, спроектированы таким образом, чтобы минимизировать взаимную информацию между открытым текстом и шифротекстом. Для них атака по взаимной информации обычно неэффективна при разумных вычислительных затратах.

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

• В 2010 году исследователи из Массачусетского технологического института (MIT) предложили модификацию атаки по взаимной информации, основанную на машинном обучении. Используя нейронные сети, они смогли выявить скрытые корреляции в шифротекстах, которые не обнаруживались традиционными статистическими методами.
• Атака по взаимной информации легла в основу метода «side-channel attack» (атака по побочным каналам), где взаимная информация вычисляется не между текстами, а между временем выполнения операций или потреблением энергии и ключом шифрования.
• В 2015 году российские криптографы из Академии криптографии РФ (организация, осуществляющая деятельность в области криптографии) опубликовали работу, в которой показали, что для российского стандарта шифрования ГОСТ 28147-89 атака по взаимной информации требует не менее \( 2^{64} \) операций, что делает её непрактичной при текущем уровне вычислительных мощностей.

Заключение

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

Источники

• Шеннон К. Теория связи в секретных системах. — 1949.
• Менезес А., ван Ооршот П., Ванстон С. Прикладная криптография. — 1996.
• Фергюсон Н., Шнайер Б. Практическая криптография. — 2003.
• Кнут Д. Искусство программирования. Том 2. — 1998.
• Работы Академии криптографии РФ (2015).