XSL атака - XSL attack

В криптография, то Расширенная разреженная линеаризация (XSL) атака это метод криптоанализ для блочные шифры. Атака была впервые опубликована в 2002 году исследователями. Николя Куртуа и Йозеф Пиепшик. Это вызвало некоторые споры, поскольку было заявлено, что оно может нарушить Расширенный стандарт шифрования (AES) шифр, также известен как Rijndael, быстрее, чем исчерпывающий поиск. Поскольку AES уже широко используется в торговле и правительстве для передачи секретной информации, поиск метода, который может сократить время, необходимое для извлечения секретного сообщения без ключа, может иметь серьезные последствия.

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

В общем, XSL-атака основана на первом анализе внутренней структуры шифра и получении системы квадратичный одновременные уравнения. Эти системы уравнений обычно очень большие, например 8000 уравнений с 1600 переменные для 128-битного AES. Известно несколько методов решения таких систем. В атаке XSL специальный алгоритм, названный Расширенная разреженная линеаризация, затем применяется для решения этих уравнений и восстановления ключ.

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

Решение многомерных квадратных уравнений

Решение многомерный квадратные уравнения (MQ) над конечным набором чисел - это NP-жесткий проблема (в общем случае) с несколькими приложениями в криптографии. Атака XSL требует эффективного алгоритма борьбы с MQ. В 1999 году Кипнис и Шамир показал, что конкретный алгоритм открытого ключа, известный как Уравнения скрытого поля схему (HFE), можно было бы свести к сверхдетерминированная система квадратных уравнений (больше уравнений, чем неизвестных). Одним из методов решения таких систем является линеаризация, который включает замену каждого квадратичного члена независимой переменной и решение полученной линейной системы с использованием такого алгоритма, как Гауссово исключение. Чтобы добиться успеха, линеаризация требует достаточно линейно независимый уравнения (примерно столько же, сколько членов). Однако для криптоанализа HFE было слишком мало уравнений, поэтому Кипнис и Шамир предложили повторная линеаризация, метод, при котором дополнительные нелинейные уравнения добавляются после линеаризации, а результирующая система решается с помощью второго применения линеаризации. Релинеаризация оказалась достаточно общей, чтобы быть применимой к другим схемам.

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

Исследования эффективности XL и производных от него алгоритмов продолжаются (Yang and Chen, 2004).

Приложение для блокирования шифров

Куртуа и Пиепшик (2002) отметили, что AES (Rijndael) и частично также Змея можно было бы выразить в виде системы квадратных уравнений. Переменные представляют не только простой текст, зашифрованный текст и ключевые биты, а также различные промежуточные значения в алгоритме. В S-коробка AES оказывается особенно уязвимым для этого типа анализа, поскольку он основан на алгебраически простом обратная функция. Впоследствии были изучены другие шифры, чтобы увидеть, какие системы уравнений могут быть получены (Бирюков и De Cannière, 2003), в том числе Камелия, ХАЗАД, MISTY1 и КАСУМИ. В отличие от других форм криптоанализа, таких как дифференциал и линейный криптоанализ, всего один или два известные открытые тексты являются обязательными.

Алгоритм XSL адаптирован для решения типа создаваемых систем уравнений. По оценке Куртуа и Пиепшика, «оптимистическая оценка показывает, что атака XSL могла бы взломать Rijndael [с] 256 битами и Serpent с длиной ключа [] 192 и 256 бит». Однако их анализ не является общепринятым. Например:

Я считаю, что работа Куртуа-Пепшика ошибочна. Они преувеличивают количество линейно независимых уравнений. В результате у них фактически нет достаточного количества линейных уравнений для решения системы, и этот метод не нарушает Rijndael ... Метод имеет некоторые достоинства и заслуживает изучения, но он не нарушает Rijndael в его нынешнем виде.

— Дон Копперсмит, Crypto-Gram 15 октября 2002 г .: комментарии читателей

На конференции AES 4, Бонн, 2004 г., один из изобретателей Rijndael, Винсент Реймен, прокомментировал: «Атака XSL - это не атака. Это мечта». Куртуа тут же ответил: «XSL может быть сном. Это также может быть очень плохой сон и превратиться в кошмар».[1] Однако ни более поздние документы, ни действия со стороны АНБ или NIST поддержать это замечание Куртуа.

В 2003 г. Мерфи и Робшоу открыл альтернативное описание AES, встроив его в более крупный шифр под названием «BES», который можно описать с помощью очень простых операций над одним поле, GF (28). XSL-атака, установленная на этой системе, дает более простой набор уравнений, который сломает AES со сложностью около 2100, если анализ Куртуа и Пепшика верен. В 2005 году Сид и Леурент показали, что в предлагаемой форме XSL-алгоритм не обеспечивает эффективного метода решения системы уравнений AES; однако Куртуа оспорил их выводы.[нужна цитата ] На FSE 2007 Чу-Ви Лим и Хунгминг Ху показали, что[требуется разъяснение ] не может работать как представлено.[нужна цитата ]

Даже если XSL работает против некоторых современных алгоритмов, эта атака в настоящее время представляет небольшую опасность с точки зрения практической безопасности. Как и многие современные результаты криптоанализа, это будет так называемая «слабая сторона сертификации»: хотя она быстрее, чем атака грубой силой, требуемые ресурсы по-прежнему огромны, и очень маловероятно, что реальные системы могут быть скомпрометированы с его использованием. Однако будущие улучшения могут повысить практичность атаки. Поскольку этот тип атаки является новым и неожиданным, некоторые криптографы выразили беспокойство по поводу алгебраической простоты шифров, таких как Rijndael. Брюс Шнайер и Нильс Фергюсон напишите: «У нас есть одна критика AES: мы не совсем доверяем безопасности… Что нас больше всего беспокоит в AES, так это его простая алгебраическая структура… Ни один другой блочный шифр, о котором мы знаем, не имеет такого простого алгебраического представления. Мы понятия не имеем. приводит ли это к атаке или нет, но незнание является достаточной причиной, чтобы скептически относиться к использованию AES ". (Практическая криптография, 2003, с. 56–57).

использованная литература

  1. ^ Винсент Реймен (2002-12-18). "Re: Rijndael и другие блочные шифры". Архивировано из оригинал на 2004-08-03. Получено 2015-03-16.

внешние ссылки