Линейный криптоанализ
- Автор метода
- Mitsuru Matsui
- Год
- 1993
- Тип
- linear approximation attack
- Семейство
- Cryptanalytic technique
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Линейный криптоанализ — это атака по известному открытому тексту, которая использует линейные аппроксимации нелинейных преобразований шифра для восстановления битов секретного ключа.
Представленный Мицуру Мацуи в 1993 году, линейный криптоанализ позволяет проводить практические атаки на такие шифры, как DES, с вычислительной сложностью меньшей, чем полный перебор. Метод анализирует статистические смещения в том, как линейные комбинации битов открытого и зашифрованного текста связаны с битами ключа, что позволяет восстанавливать ключ с меньшими требованиями к данным.
Интуиция метода
Линейный криптоанализ находит линейные уравнения, связывающие биты открытого текста, биты зашифрованного текста и биты ключа. Из-за неидеального перемешивания в раундах шифра эти линейные уравнения выполняются с вероятностью немного лучшей, чем случайная. Собирая множество пар открытый текст — зашифрованный текст и наблюдая, какие значения ключа заставляют эти уравнения выполняться чаще, злоумышленник может сузить круг возможных ключей.
История
Линейный криптоанализ был представлен Мацуи в 1993 году как атака по известному открытому тексту на DES. В 1994 году Мацуи продемонстрировал первый экспериментальный криптоанализ стандарта DES с использованием линейного криптоанализа, восстановив ключ с 2^43 известными открытыми текстами. Этот прорыв продемонстрировал практические атаки на используемый стандарт и повлиял на разработку AES с доказанными границами стойкости.
Когда применять
Линейный криптоанализ используется в криптоаналитических исследованиях и оценке дизайна шифров. Он помогает разработчикам шифров выбирать S-блоки и преобразования, устойчивые к линейным аппроксимациям. Современные шифры разрабатываются с доказанными границами стойкости к линейным аппроксимациям.
Ограничения и замечания
- Современные шифры (AES) тщательно разработаны для сопротивления линейному криптоанализу с доказуемыми границами
- Требует известных пар открытый текст — зашифрованный текст, которые могут быть недоступны во всех сценариях
- Вычислительные требования и требования к данным могут превышать практическую осуществимость для хорошо разработанных шифров
- Обнаружение сильных линейных аппроксимаций для современных шифров чрезвычайно затруднительно
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Практическая атака на DES, требующая 2^43 пар открытый текст — зашифрованный текст и 2^39 операций
- Хорошо формализованная математическая основа (лемма о накоплении) для анализа смещений аппроксимаций
- Дополняет дифференциальный криптоанализ, выявляя слабые места, которые дифференциальный анализ может пропустить
- Формирует требования к дизайну шифра для выбора S-блоков и раундовых преобразований
Применение
- Криптоанализ блочных шифров, оценивающий свойства безопасности в исследованиях и стандартизации
- Разработка шифров и выбор S-блоков для обеспечения адекватных границ линейной аппроксимации
- Валидация криптографических стандартов (NIST, ETSI), требующая анализа линейной стойкости
- Оценка устаревших шифров для принятия решений о выводе из эксплуатации и замене
Как это работает
Как это работает
Шаг 1 — Найти линейные аппроксимации: линейные соотношения между битами открытого текста, битами зашифрованного текста и битами ключа, которые выполняются с вероятностью, значительно отличающейся от 0.5.
Шаг 2 — Оценить смещение (отклонение от 0.5) каждой линейной аппроксимации, используя статистический анализ раундовых преобразований.
Шаг 3 — Для значений ключей-кандидатов подсчитать, как часто линейная аппроксимация выполняется в известных парах открытый текст — зашифрованный текст. При правильном ключе аппроксимация выполняется наиболее часто.
Шаг 4 — Проверить восстановленные биты ключа путем расшифровки зашифрованного текста и проверки корректности.
Частые ошибки
- Предположение, что все линейные аппроксимации пригодны для эксплуатации; слабые аппроксимации дают минимальное преимущество
- Недооценка практической сложности атаки, когда теоретические требования к данным кажутся разумными
- Пренебрежение взаимодействием между линейными и дифференциальными свойствами в анализе шифра
Часто задаваемые вопросы
Что такое лемма о накоплении?
Лемма о накоплении предоставляет метод для вычисления смещения линейных аппроксимаций на протяжении нескольких раундов путем объединения смещений отдельных раундовых аппроксимаций. Она является основополагающей для линейного криптоанализа.
Как AES сопротивляется линейному криптоанализу?
AES использует S-блоки, выбранные для минимизации максимальной вероятности линейной аппроксимации, и слой диффузии, обеспечивающий быструю диффузию линейных смещений по раундам. Доказанные границы гарантируют отсутствие практических линейных аппроксимаций.
В чем разница между линейным и дифференциальным криптоанализом?
Дифференциальный анализ изучает разности вход-выход, тогда как линейный анализ изучает линейные аппроксимации (XOR битов открытого и зашифрованного текста). Оба метода используют структурные слабости в шифрах.
Может ли линейный криптоанализ взломать современные шифры?
Практически нет. Современные шифры, такие как AES, имеют доказуемые границы на линейные аппроксимации, что делает атаки вычислительно неосуществимыми.
Как мне оценить линейную стойкость в моем дизайне шифра?
Проанализируйте таблицы линейных аппроксимаций S-блоков и вычислите максимальное смещение по раундам, используя лемму о накоплении. Убедитесь, что максимальное смещение незначительно для всех возможных линейных аппроксимаций.
Похожие методы
Источники
Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.
Открыть ссылку DOIСкопировано.Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.
Открыть ссылку DOIСкопировано.