Русская Википедия:XSL-атака
XSL-атака (Шаблон:Lang-en, алгебраическая атака) — это метод криптографического анализа, основанный на алгебраических свойствах шифра. Метод предполагает решение особой системы уравнений.
Данный метод был предложен в 2001 году Николя Куртуа (Nicolas T. Courtois) и Юзефом Пепшиком (Josef Pieprzyk).
XSL-атаки ранее считались невозможными, однако 26 мая 2006 года Куртуа продемонстрировал возможность XSL-атаки против модели одного шифра, сходного по своей структуре с шифром AESШаблон:Sfn.
Как говорил один из создателей шифра Rijndael в частной переписке: «XSL — это не атака, это всего лишь мечтательный сон». «Этот сон может превратиться в кошмар», — отвечал Николя Куртуа[1].
Шаблон:Начало цитаты Если XSL атаки действительно работают, они взломают все существующие на данный момент шифры. Спасти шифр от взлома может лишь чистая случайность. С другой стороны вполне возможно (а с нашей точки зрения и наиболее вероятно), что XSL атаки не применимы на практике или же применимы только к небольшому числу высокоструктурированных шифров Шаблон:Конец цитаты
История создания
В 2001 году Нильс Фергюсон, Ричард Шроппель (R. Schroeppel) и Даг Вайтинг (D. Whiting) опубликовали статьюШаблон:Sfn, в которой смогли представить запись шифра Rijndael в виде алгебраической формулы, используя представления линейных частей шифра и нелинейных S-блоков в виде уравнений высокого порядка . Они пришли к выводу, что все симметричные блочные шифры могут быть приведены к многомерному уравнению над некоторым конечным полем. Они же задались вопросом, поможет ли знание об алгебраической форме помочь взломать шифр. Если в функции, выражающей S-блоки, не учитывать аргументы в степени -1, тогда шифр становится аффинным и легко взламывается другими способами, не требующими линеаризации. Если же приравнять эти аргументы <math>1/x</math> к <math>x^{254}</math>, то уравнение получается полиномиально сложным.
В те годы появлялось множество атак на открытые ключи: атака на систему Мацумото-Имаи[2], атака на HFE[3]. Эти атаки завершались успехом сразу после раскрытия факта (теоретического или экспериментального) существования дополнительных уравнений многих переменных, которые не очевидны и не были предусмотрены разработчиками оригинального шифраШаблон:Sfn.
Ади Шамир в 1998 показал, что квадратные уравнения многих переменных (MQ) — NP-полная задача[4]. Её сложность заметно снижается, когда уравнения становятся переопределеныШаблон:Sfn. В первом исследовании Николя Куртуа и Юзеф Пепшик показывают, что получаемые MQ — разрежены и имеют регулярную структуруШаблон:Sfn.
2 декабря 2002 года на ASIACRYPT-2002 Николя Куртуа и Юзеф Пепшик выступили со статьёй "Cryptanalysis of block ciphers with overdefined systems of equations", где впервые представили две вариации метода XSL-атакиШаблон:Sfn. Выводом из этой работы служит то, что стойкость AES опирается только на невозможность на данный момент решить систему уравнений, описывающую алгебраическую структуру шифра.
XSL-шифр
Обобщая класс SP-шифров, которые состоят из S-блоков и функций перемешивания бит (permutation of bits), Куртуа и Пепчик обозначили новый класс SA-шифров, который состоит из S-блоков и аффинных функцийШаблон:Sfn. Согласно исследованию Ади Шамира и Алекса Бирюкова атаки на SA-шифры не зависят от свойств определенного S-блока[5]. После в статье был введён XSL-шифр класса SA, который описывает структуру типового блочного шифра, для которого метод может быть применён.
Структура шифрования состоит из <math>N</math>раундов:
- <math>X:</math> в раунде <math>i = 1</math> проводится операция <math>XOR</math> открытого текста с сессионым ключом <math>K_{i-1}</math>
- <math>S:</math> Результат разделяется на блоки по <math>s</math> бит. Каждый такой блок параллельно поступает на вход некоторого числа B биективных S-блоков.
- <math>L:</math> потом применяем линейный рассеивающий слой.
- <math>X:</math> применяем операцию <math>XOR</math> к следующему сессионному ключу <math>K_i</math>
- если <math>i = N</math> прерываем цикл, в противном случае переходим к следующей итерации по <math>i</math> и возвращаемся к шагу <math>S</math>.
Математические основы
S-блоки шифров Rijndael и Serpent могут быть представлены в виде некоторой функции многих переменных высоких степенейШаблон:Sfn, метод Куртуа понижает степень функции до некоторого числа <math>d</math>, где <math>d</math> обычно выбирается равным 2, с помощью расширения пространства аргументов. Особый интерес имеет количество таких функций <math>r</math>. Если <math>r = s</math>, такие уравнения достаточно описывают S-блок. Если же <math>r >> s</math>, тогда говорим, что система переопределена.
Существует два типа XSL-атак. Первый (общий) оперирует с XSL-шифрами, независимо от алгоритма расписания ключей (см. key schedule). Тогда алгоритм требует такое число шифротекстов, сколько внутри шифра существует S-блоков. Второй вариант XSL-атаки учитывает, что известен алгоритм расписания ключей, поэтому требует всего один шифротекстШаблон:Sfn.
Алгоритм первого варианта XSL-атаки
Каждый раунд работы S-блока записывается в виде уравнения:
<math>{\displaystyle \sum _{i,j}\alpha _{ijk}*X_{ij}*Y_{jk}+\sum _{i,j}\beta _{ij}*X_{ij}+\sum _{i,j}\gamma _{ij}*Y_{ij}+\delta =0} </math>
где <math>X_{ij}</math>- биты на входе <math>i</math>- ого S-блока, <math>Y_{ik}</math>- биты на выходе <math>i</math>- ого S-блока.
Далее выбирается критический параметр атаки <math>P\in\natnums</math>. Во время атаки уравнение каждого S-блока будет умножаться на все возможные одночлены подмножества <math>(P - 1)</math> оставшихся S-блоков. Причем при изменении числа раундов шифра параметр <math>P</math> должен возрастать не сильно, как показали эксперименты Куртуа и ПепшикаШаблон:Sfn.
Далее для нахождения системы, для которой существует единственное решение, записывается новое уравнение:
<math>X_{i,j} \bigoplus \sum \alpha_{j}Y_{i-1,j} = X'_{i,j} \bigoplus \sum \alpha_jY'{i-1,j} = X_{i,j}\sum\alpha_jY_{i-1,j} = ...</math>
Цель всех этих преобразований — привести систему уравнений к линейной переопределенной системе, в которой нет очевидных линейно зависимых уравнений.
Мнение научного сообщества
Метод алгебраических атак показался многообещающим для криптоанализа, так как не требовал большого числа шифротекстов в теории и предлагал взлом наиболее используемого стандарта шифрования (AES). В течение пяти лет вышло много исследований на тему работоспособности XSL-атак.
Так, в работе Карлоса Сида (Carlos Cid) и Г. Лорен (Ga¨etan Leurent) был разобран второй вариант XSL-атаки из оригинальной статьи — compact XSL — на AES-128[6]. В статье были разобраны примеры, при которых данный алгоритм рушится в так называемом T-блоке, который используется для расширения пространства переменных. Однако учёные сделали вывод, что XSL подход — первая попытка найти уязвимость в структурной части AES-шифра.
Например, в работе Chu-Wee Lim и Khoongming Khoo Шаблон:Sfn исследуется попытка взлома приложения BES (Big Encryption System) к AES. Это расширение переводит все вычисления в поле <math>{GF_{256}}</math>, что, соответственно, должно уменьшать количество операций. Однако теоретические расчёты показали, что сложность алгоритма для BES-шифра повышается. Сложность для вариантов BES:
- BES-128: <math>\approx 2^{401}</math>
- BES-192: <math>\approx 2^{622}</math>
- BES-256: <math>\approx 2^{691}</math>
Было установлено, что XSL-атака не эффективна против BES-шифров.
Примечания
Литература
