Дифференциально-линейный криптоанализ

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

История

Дифференциальный криптоанализ был впервые предложен Эли Бихамом и Ади Шамиром в конце 1980-х годов, а линейный криптоанализ — Мицуру Мацуи в 1993 году. Оба метода стали основными инструментами для анализа стойкости блочных шифров. Однако вскоре выяснилось, что многие шифры, такие как DES, могут быть защищены от одного из этих методов за счёт выбора S-блоков и числа раундов, но остаются уязвимыми для комбинированных атак.

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

Основные принципы

Дифференциальный криптоанализ

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

Линейный криптоанализ

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

Комбинированный подход

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

Формально дифференциально-линейная характеристика задаётся парой: входная разность (для дифференциальной части) и выходная маска (для линейной части). Аналитик оценивает вероятность того, что при заданной входной разности выходная маска будет коррелировать с определённым значением. Если эта вероятность существенно отличается от 1/2, то атака может быть успешной.

Применение

Атаки на DES

Одним из первых успешных применений дифференциально-линейного криптоанализа стала атака на шифр DES. В 1995 году Бихам и Шамир показали, что комбинированный метод позволяет сократить количество необходимых пар открытый текст — шифртекст по сравнению с чистым дифференциальным или линейным криптоанализом. Для DES с 16 раундами атака требовала около 2^47 пар, что было значительно меньше, чем 2^47 для дифференциального и 2^43 для линейного методов (хотя последний был более эффективен в некоторых случаях). Однако комбинированный подход позволил атаковать варианты DES с уменьшенным числом раундов, где другие методы были менее эффективны.

Атаки на другие шифры

Дифференциально-линейный криптоанализ применялся к ряду других блочных шифров, включая FEAL, IDEA и некоторые варианты AES. В частности, для шифра FEAL-8 (8 раундов) атака требовала около 2^32 пар, что было лучше, чем чисто дифференциальный метод. Для шифра IDEA, несмотря на его сложную структуру, были найдены дифференциально-линейные характеристики, позволяющие атаковать до 4 раундов.

Современные исследования

В 2000-х и 2010-х годах дифференциально-линейный криптоанализ был расширен на многомерный случай, где используются несколько линейных аппроксимаций одновременно. Это позволило повысить эффективность атак на шифры с большим числом раундов. Также были разработаны методы автоматического поиска дифференциально-линейных характеристик с помощью алгоритмов, таких как MILP (Mixed-Integer Linear Programming) и SAT-решатели.

Классификация методов

Усечённый дифференциально-линейный криптоанализ

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

Многомерный дифференциально-линейный криптоанализ

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

Дифференциально-линейный криптоанализ с использованием отбрасывания

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

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

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

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

• Дифференциально-линейный криптоанализ был впервые применён к шифру DES, который в то время считался одним из самых стойких.
• Метод активно используется в академических исследованиях для оценки новых шифров, таких как Serpent, Twofish и другие участники конкурса AES.
• В 2010-х годах были разработаны автоматизированные инструменты для поиска дифференциально-линейных характеристик, что значительно ускорило анализ шифров.

Источники

• Biham, E., & Shamir, A. (1995). Differential Cryptanalysis of the Data Encryption Standard. Springer.
• Matsui, M. (1993). Linear Cryptanalysis Method for DES Cipher. Advances in Cryptology — EUROCRYPT ’93.
• Handschuh, H., & Heys, H. (1994). A Differential-Linear Attack on DES. Proceedings of the 2nd ACM Conference on Computer and Communications Security.
• Knudsen, L. R. (1998). Contemporary Block Ciphers. Springer.
• Bogdanov, A., & Rijmen, V. (2014). Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers. Designs, Codes and Cryptography.