XSL-атака ( англ. eXtended Sparse Linearization , алгебраическая атака) — это метод криптографического анализа , основанный на алгебраических свойствах шифра . Метод предполагает решение особой системы уравнений .

Данный метод был предложен в 2001 году Николя Куртуа (Nicolas T. Courtois) и Юзефом Пепшиком (Josef Pieprzyk).

XSL-атаки ранее считались невозможными, однако 26 мая 2006 года Куртуа продемонстрировал возможность XSL-атаки против модели одного шифра, сходного по своей структуре с шифром AES .

Как говорил один из создателей шифра Rijndael в частной переписке: «XSL — это не атака, это всего лишь мечтательный сон». «Этот сон может превратиться в кошмар», — отвечал Николя Куртуа .

Если XSL атаки действительно работают, они взломают все существующие на данный момент шифры. Спасти шифр от взлома может лишь чистая случайность. С другой стороны вполне возможно (а с нашей точки зрения и наиболее вероятно), что XSL атаки не применимы на практике или же применимы только к небольшому числу высокоструктурированных шифров

— Нильс Фергюсон , Брюс Шнайер Практическая криптография

История создания

В 2001 году Нильс Фергюсон , Ричард Шроппель (R. Schroeppel) и Даг Вайтинг (D. Whiting) опубликовали статью , в которой смогли представить запись шифра Rijndael в виде алгебраической формулы, используя представления линейных частей шифра и нелинейных S-блоков в виде уравнений высокого порядка . Они пришли к выводу, что все симметричные блочные шифры могут быть приведены к многомерному уравнению над некоторым конечным полем . Они же задались вопросом, поможет ли знание об алгебраической форме помочь взломать шифр . Если в функции, выражающей S-блоки, не учитывать аргументы в степени -1, тогда шифр становится аффинным и легко взламывается другими способами, не требующими линеаризации . Если же приравнять эти аргументы ${\displaystyle 1/x}$ к ${\displaystyle x^{254}}$ , то уравнение получается полиномиально сложным.

В те годы появлялось множество атак на открытые ключи: атака на систему Мацумото-Имаи , атака на HFE . Эти атаки завершались успехом сразу после раскрытия факта (теоретического или экспериментального) существования дополнительных уравнений многих переменных, которые не очевидны и не были предусмотрены разработчиками оригинального шифра .

Ади Шамир в 1998 показал, что квадратные уравнения многих переменных (MQ) — NP-полная задача . Её сложность заметно снижается, когда уравнения становятся переопределены . В первом исследовании Николя Куртуа и Юзеф Пепшик показывают, что получаемые MQ — разрежены и имеют регулярную структуру .

2 декабря 2002 года на ASIACRYPT-2002 Николя Куртуа и Юзеф Пепшик выступили со статьёй "Cryptanalysis of block ciphers with overdefined systems of equations", где впервые представили две вариации метода XSL-атаки . Выводом из этой работы служит то, что стойкость AES опирается только на невозможность на данный момент решить систему уравнений, описывающую алгебраическую структуру шифра.

XSL-шифр

Обобщая класс SP-шифров, которые состоят из S-блоков и функций перемешивания бит (permutation of bits), Куртуа и Пепчик обозначили новый класс SA-шифров, который состоит из S-блоков и аффинных функций . Согласно исследованию Ади Шамира и Алекса Бирюкова атаки на SA-шифры не зависят от свойств определенного S-блока . После в статье был введён XSL-шифр класса SA, который описывает структуру типового блочного шифра, для которого метод может быть применён.

Структура шифрования состоит из ${\displaystyle N}$ раундов:

1. ${\displaystyle X:}$ в раунде ${\displaystyle i=1}$ проводится операция ${\displaystyle XOR}$ открытого текста с сессионым ключом ${\displaystyle K_{i-1}}$
2. ${\displaystyle S:}$ Результат разделяется на блоки по ${\displaystyle s}$ бит. Каждый такой блок параллельно поступает на вход некоторого числа B биективных S-блоков.
3. ${\displaystyle L:}$ потом применяем линейный слой.
4. ${\displaystyle X:}$ применяем операцию ${\displaystyle XOR}$ к следующему сессионному ключу ${\displaystyle K_{i}}$
5. если ${\displaystyle i=N}$ прерываем цикл, в противном случае переходим к следующей итерации по ${\displaystyle i}$ и возвращаемся к шагу ${\displaystyle S}$ .

Математические основы

S-блоки шифров Rijndael и Serpent могут быть представлены в виде некоторой функции многих переменных высоких степеней , метод Куртуа понижает степень функции до некоторого числа ${\displaystyle d}$ , где ${\displaystyle d}$ обычно выбирается равным 2, с помощью расширения пространства аргументов. Особый интерес имеет количество таких функций ${\displaystyle r}$ . Если ${\displaystyle r=s}$ , такие уравнения достаточно описывают S-блок. Если же ${\displaystyle r>>s}$ , тогда говорим, что система переопределена.

Существует два типа XSL-атак. Первый (общий) оперирует с XSL-шифрами, независимо от алгоритма расписания ключей (см. ). Тогда алгоритм требует такое число шифротекстов, сколько внутри шифра существует S-блоков. Второй вариант XSL-атаки учитывает, что известен алгоритм расписания ключей, поэтому требует всего один шифротекст .

Алгоритм первого варианта XSL-атаки

Каждый раунд работы S-блока записывается в виде уравнения:

${\displaystyle {\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}}$

где ${\displaystyle X_{ij}}$ - биты на входе ${\displaystyle i}$ - ого S-блока, ${\displaystyle Y_{ik}}$ - биты на выходе ${\displaystyle i}$ - ого S-блока.

Далее выбирается критический параметр атаки ${\displaystyle P\in \mathbb {N} }$ . Во время атаки уравнение каждого S-блока будет умножаться на все возможные одночлены подмножества ${\displaystyle (P-1)}$ оставшихся S-блоков. Причем при изменении числа раундов шифра параметр ${\displaystyle P}$ должен возрастать не сильно, как показали эксперименты Куртуа и Пепшика .

Далее для нахождения системы, для которой существует единственное решение, записывается новое уравнение:

${\displaystyle X_{i,j}\bigoplus \sum \alpha _{j}Y_{i-1,j}=X'_{i,j}\bigoplus \sum \alpha _{j}Y'{i-1,j}=X''_{i,j}\sum \alpha _{j}Y''_{i-1,j}=...}$

Цель всех этих преобразований — привести систему уравнений к линейной переопределенной системе, в которой нет очевидных линейно зависимых уравнений.

Мнение научного сообщества

Метод алгебраических атак показался многообещающим для криптоанализа, так как не требовал большого числа шифротекстов в теории и предлагал взлом наиболее используемого стандарта шифрования (AES). В течение пяти лет вышло много исследований на тему работоспособности XSL-атак.

Так, в работе Карлоса Сида (Carlos Cid) и Г. Лорен (Ga¨etan Leurent) был разобран второй вариант XSL-атаки из оригинальной статьи — compact XSL — на AES-128 . В статье были разобраны примеры, при которых данный алгоритм рушится в так называемом T-блоке, который используется для расширения пространства переменных. Однако учёные сделали вывод, что XSL подход — первая попытка найти уязвимость в структурной части AES-шифра.

Например, в работе Chu-Wee Lim и Khoongming Khoo исследуется попытка взлома приложения (Big Encryption System) к AES. Это расширение переводит все вычисления в поле ${\displaystyle {GF_{256}}}$ , что, соответственно, должно уменьшать количество операций. Однако теоретические расчёты показали, что сложность алгоритма для BES-шифра повышается. Сложность для вариантов BES:

• BES-128: ${\displaystyle \approx 2^{401}}$
• BES-192: ${\displaystyle \approx 2^{622}}$
• BES-256: ${\displaystyle \approx 2^{691}}$

Было установлено, что XSL-атака не эффективна против BES-шифров.

Примечания

Литература

• Nicolas T. Courtois, Gregory V. Bard. // Cryptography and Coding. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. — ISBN 9783540772712 .
• Фергюсон Н., Шнайер Б. Практическая криптография. — 2005. — 424 с.
• Nicolas T. Courtois and Josef Pieprzyk. . — Berlin, Heidelberg: Springer Berlin, 2002. — С. 1-35 .
• Chu-Wee Lim, Khoongming Khoo. // Fast Software Encryption. — 2007. — С. 13 . 3 марта 2016 года.
• Niels Ferguson, Richard Schroeppel, Doug Whiting. // Selected Areas in Cryptography. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. — С. 103–111 . — ISBN 9783540430667 , 9783540455370 .