Войти
В криптографии атака расширенной разреженной линеаризацией (XSL) является методом криптоанализ для блочных шифров. Впервые атака была опубликована в 2002 году исследователями Николя Куртуа и Йозефом Пиепшиком. Это вызвало некоторые споры, поскольку было заявлено, что оно потенциально может взломать Advanced Encryption Standard (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).
Courtois and Pieprzyk (2002) заметили, что AES (Rijndael) и частично также Serpent могут быть выражены как система квадратных уравнений. Переменные представляют не только открытый текст, зашифрованный текст и биты ключей, но также различные промежуточные значения в алгоритме. S-блок AES оказывается особенно уязвимым для этого типа анализа, поскольку он основан на алгебраически простой обратной функции. Впоследствии были изучены другие шифры, чтобы увидеть, какие системы уравнений могут быть получены (Бирюков и Де Канньер, 2003), включая Camellia, KHAZAD, MISTY1 и КАСУМИ. В отличие от других форм криптоанализа, таких как дифференциальный и линейный криптоанализ, требуется только один или два известных открытых текстов.
Алгоритм XSL адаптирован для решения создаваемых систем уравнений. По оценке Куртуа и Пиепшика, «оптимистическая оценка показывает, что атака XSL могла бы взломать Rijndael [с] 256 битами и Serpent с длиной ключа [] 192 и 256 бит». Однако их анализ не является общепринятым. Например:
Я считаю, что работа Куртуа – Пепшика ошибочна. Они преувеличивают количество линейно независимых уравнений. В результате у них фактически нет достаточного количества линейных уравнений для решения системы, и этот метод не нарушает Rijndael… Метод имеет некоторые достоинства и заслуживает изучения, но он не нарушает Rijndael в его нынешнем виде.
— Дон Копперсмит, Crypto-Gram 15 октября 2002 г.: Комментарии читателейНа конференции AES 4, Бонн, 2004, один из изобретателей Rijndael, Винсент Раймен, прокомментировал: " Атака XSL - это не атака. Это мечта ». Куртуа тут же ответил: «XSL может быть сном. Это также может быть очень плохой сон и превратиться в кошмар». Однако ни какие-либо более поздние документы или какие-либо действия NSA или NIST не подтверждают это замечание Куртуа.
В 2003 году Мерфи и Робшоу обнаружили альтернативное описание AES, встроив его в более крупный шифр под названием «BES», который можно описать с помощью очень простых операций. над одним полем, GF (2). XSL-атака, установленная на этой системе, дает более простой набор уравнений, который нарушит AES со сложностью около 2, если анализ Куртуа и Пепшика верен. В 2005 году Сид и Леурент показали, что в предлагаемой форме алгоритм XSL не обеспечивает эффективного метода решения системы уравнений AES; однако Куртуа оспорил их выводы. На FSE 2007 Чу-Ви Лим и Хунгминг Кху показали, что это не может работать так, как представлено.
Даже если XSL работает против некоторых современных алгоритмов, атака в настоящее время представляет небольшую опасность с точки зрения практической безопасности. Как и многие современные результаты криптоанализа, это будет так называемая «слабая сторона сертификации»: хотя и быстрее, чем атака грубой силой, требуемые ресурсы по-прежнему огромны, и очень маловероятно, что реальные системы могут быть скомпрометированным, используя его. Однако будущие улучшения могут повысить практичность атаки. Поскольку этот тип атаки является новым и неожиданным, некоторые криптографы выразили беспокойство по поводу алгебраической простоты шифров, таких как Rijndael. Брюс Шнайер и Нильс Фергюсон пишут: «У нас есть одна критика AES: мы не совсем доверяем безопасности... Что нас больше всего беспокоит в AES, так это его простая алгебраическая структура... Нет другой известный нам блочный шифр имеет такое простое алгебраическое представление. Мы не знаем, приводит ли это к атаке или нет, но незнание является достаточной причиной, чтобы скептически относиться к использованию AES ». (Практическая криптография, 2003 г., стр. 56–57)
