Атака XSL - XSL attack

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

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

В общем, 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) и частично также Serpent могут быть выражены как система квадратных уравнений. Переменные представляют не только открытый текст , зашифрованный текст и биты ключа, но также различные промежуточные значения в алгоритме. S-ящик ПЯ , как представляется, особенно уязвимы для такого рода анализа, поскольку он основан на алгебраически простой обратной функции . Впоследствии были изучены другие шифры, чтобы увидеть, какие системы уравнений могут быть получены ( Biryukov and De Cannière, 2003), включая Camellia , KHAZAD , MISTY1 и KASUMI . В отличие от других форм криптоанализа, таких как дифференциальный и линейный криптоанализ, требуется только один или два известных открытых текста .

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

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

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

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

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

Рекомендации

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