XSL-атака

В криптографии атака расширенной разреженной линеаризации (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 (от eXtended Linearization ), который увеличивает количество уравнений за счет их умножения на все мономы определенной степени . Оценки сложности показали, что атака XL не сработает против уравнений, полученных на основе блочных шифров, таких как AES. Однако полученные системы уравнений имели особую структуру, и алгоритм XSL был разработан как усовершенствованная версия XL, которая могла использовать преимущества этой структуры. В XSL уравнения умножаются только на тщательно выбранные мономы, и было предложено несколько вариантов.

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

Приложение для блокировки шифров [ править ]

Куртуа и Пипшик (2002) заметили, что AES (Rijndael) и частично также Serpent можно выразить в виде системы квадратных уравнений. Переменные представляют собой не только открытый текст , зашифрованный текст и ключевые биты, но также различные промежуточные значения в алгоритме. S -блок AES оказывается особенно уязвимым для такого типа анализа, поскольку он основан на алгебраически простой обратной функции . Впоследствии были изучены и другие шифры, чтобы увидеть, какие системы уравнений можно получить ( Бирюков и Де Каньер, 2003), включая Camellia , KHAZAD , MISTY1 и KASUMI . В отличие от других форм криптоанализа, таких как дифференциальный и линейный только один или два (в случае размера блока 128 бит и размера ключа 256 бит) известных открытых текстов криптоанализ, требуется .

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

Я считаю, что работа Куртуа-Пепшика ошибочна. Они пересчитывают количество линейно независимых уравнений. В результате у них на самом деле недостаточно линейных уравнений для решения системы, и метод не нарушает Рейндала… Метод имеет некоторые достоинства и заслуживает изучения, но он не нарушает Рейндала в его нынешнем виде.
— Дон Копперсмит , Crypto-Gram, 15 октября 2002 г.: комментарии читателей.

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

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

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

Ссылки [ править ]

^ Винсент Реймен (18 декабря 2002 г.). «Re: Rijndael и другие блочные шифры» . Архивировано из оригинала 3 августа 2004 г. Проверено 16 марта 2015 г.

Бирюков, Алекс; Каньер, Кристоф Де (2003). «Блочные шифры и системы квадратных уравнений». В Йоханссоне, Томас (ред.). Быстрое программное шифрование, 10-й международный семинар, FSE 2003, Лунд, Швеция, 24-26 февраля 2003 г., Пересмотренные статьи . Конспекты лекций по информатике. Том. 2887. Спрингер. стр. 274–289. дои : 10.1007/978-3-540-39887-5_21 .
Куртуа, Николя Т.; Климов, Александр; Патарен, Жак; Шамир, Ади (2000). «Эффективные алгоритмы решения переопределенных систем многомерных полиномиальных уравнений» (PDF) . В Прениле, Барт (ред.). Достижения в криптологии - EUROCRYPT 2000, Международная конференция по теории и применению криптографических методов, Брюгге, Бельгия, 14-18 мая 2000 г., Тезисы . Конспекты лекций по информатике. Том. 1807. Спрингер. стр. 392–407. дои : 10.1007/3-540-45539-6_27 .
Куртуа, Николя Т.; Пепшик, Йозеф (2002). «Криптоанализ блочных шифров с переопределенными системами уравнений» . Ин Чжэн, Юлян (ред.). Достижения в криптологии - ASIACRYPT 2002, 8-я Международная конференция по теории и применению криптологии и информационной безопасности, Квинстаун, Новая Зеландия, 1-5 декабря 2002 г., Материалы . Конспекты лекций по информатике. Том. 2501. Спрингер. стр. 267–287. дои : 10.1007/3-540-36178-2_17 .
Кипнис, Авиад; Шамир, Ади (1999). «Криптоанализ криптосистемы с открытым ключом HFE путем релинеаризации». В Винере, Майкл Дж. (ред.). Достижения в криптологии - CRYPTO '99, 19-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 15-19 августа 1999 г., Материалы . Конспекты лекций по информатике. Том. 1666. Спрингер. стр. 19–30. дои : 10.1007/3-540-48405-1_2 .
Лим, Чу-Ви; Ху, Кхунгминг (2007). «Анализ XSL применительно к BES». В Бирюков, Алексей (ред.). Быстрое программное шифрование, 14-й международный семинар, FSE 2007, Люксембург, Люксембург, 26-28 марта 2007 г., Пересмотренные избранные статьи . Конспекты лекций по информатике. Том. 4593. Спрингер. стр. 242–253. дои : 10.1007/978-3-540-74619-5_16 .
Дана Маккензи (2003). «Азартная игра». Новый учёный . 178 (2398): 36.
Мерфи, Шон; Робшоу, Мэтью Дж. Б. (2002). «Основная алгебраическая структура в AES». В Юнге, Моти (ред.). Достижения в криптологии - CRYPTO 2002, 22-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 18-22 августа 2002 г., Материалы . Конспекты лекций по информатике. Том. 2442. Спрингер. стр. 1–16. дои : 10.1007/3-540-45708-9_1 .
Комментарии С. Мерфи, М. Робшоу о безопасности AES и технологии XSL .
Ян, Бо-Инь; Чен, Цзюнь{-}Мин (2004). «Теоретический анализ XL в малых полях». Ин Ван, Хуасюн; Пепшик, Йозеф; Варадхараджан, Виджай (ред.). Информационная безопасность и конфиденциальность: 9-я Австралазийская конференция, ACISP 2004, Сидней, Австралия, 13-15 июля 2004 г. Материалы . Конспекты лекций по информатике. Том. 3108. Спрингер. стр. 277–288. дои : 10.1007/978-3-540-27800-9_24 .
Сид, Карлос; Леран, Гаэтан (2005). «Анализ алгоритма XSL». В Рое, Бимал К. (ред.). Достижения в криптологии - ASIACRYPT 2005, 11-я Международная конференция по теории и применению криптологии и информационной безопасности, Ченнаи, Индия, 4-8 декабря 2005 г., Материалы . Конспекты лекций по информатике. Том. 3788. Спрингер. стр. 333–352. дои : 10.1007/11593447_18 .
Дим, Клаус (2004). «XL-алгоритм и гипотеза коммутативной алгебры». В Ли, Пиль Джун (ред.). Достижения в криптологии - ASIACRYPT 2004, 10-я Международная конференция по теории и применению криптологии и информационной безопасности, остров Чеджу, Корея, 5-9 декабря 2004 г., Материалы . Конспекты лекций по информатике. Том. 3329. Спрингер. стр. 323–337. дои : 10.1007/978-3-540-30539-2_23 .

Внешние ссылки [ править ]

Страница Куртуа на AES
«Квадратический криптоанализ», объяснение атаки XSL Дж. Дж. Савара.
«AES НЕ сломан» Т. Мох
Статья Куртуа и Пепшика на ePrint
Комментарий в информационном бюллетене Crypto-gram : [1] , [2] , [3] .
Обзор AES и XSL

[1] Винсент Реймен (18 декабря 2002 г.). «Re: Rijndael и другие блочные шифры» . Архивировано из оригинала 3 августа 2004 г. Проверено 16 марта 2015 г.

[1]