XSL (eXtended Sparse Linearization) attack

XSL-атака (алгебраическая атака) — это атака на криптографический шифр, основанная на алгебраических свойствах шифра. Она предполагает решение особой системы нелинейных уравнений. Данная атака применима как к блочным, так и поточным шифрам. Цель данной атаки – минимизировать нелинейность нелинейных блоков преобразований. В общем виде, если степень используемых нелинейных преобразований равна n, то алгебраические атаки позволяют свести эту степень к floor(n/2). К настоящему времени с помощью данного метода взломан ряд поточных шифров, а также блочный шифр AES (несколько раундов). Единственный действенный метод, позволяющий противостоять атакам данного вида – использовать нелинейные преобразования, порядок нелинейности которых стремится к n – 1.&

XL метод

XL (eXtended Linearization) метод предложили Николя Куртуа, Александр Климов и Ади Шамир в 2000 году.

Алгоритм реализации XL метода

1. Multiply: составление всех произведений вида , где k≤D-2;
2. Linearize: рассмотрение каждого одночлена хi в степени ≤ D как новой переменной и применение Гауссовского исключения к уравнениям, полученным в пункте 1.
3. Solve: повторение пункта 2 до тех пор, пока в результате не будет получено по крайней мере одно уравнение с единственной переменной.
4. Repeat: упростить уравнения и повторить процесс для нахождения значений других переменных.

XSL метод

В 2002 году вместо техники XL был создан алгоритм, использующий преимущества особой структуры уравнений и их разреженность. Эта атака была названа XSL-атака, что расшифровывается как «eXtended Sparse Linearization» или «multiply(X) by Selected monomials and Linearize». Алгоритм XSL предложен для работы только со специальными типами шифров, для который выполняются условия:

• S-блоки должны быть такими, чтобы их можно было описать с помощью сверхопределенной системы квадратных уравнений.
• Алгоритм получения ключей должен иметь схожую структуру с алгоритмом зашифрования.

Алгоритм реализации XSL метода

1. Обработка имеющейся системы уравнений путем выбора конкретного набора одночленов и уравнений, которые будут использоваться в дальнейших этапах алгоритма
2. Выбор значения параметра Р и умножение выбранных на предыдущем этапе уравнений на результаты произведений (Р-1) выбранных одночленов
3. При недостаточном числе уравнений применение Т’ метода, в котором некоторые выбранные уравнения умножаются на одиночные переменные. Цель данного метода – создание новых уравнений без получения каких-либо новых одночленов.
4. Применение линеаризации, путем представления каждого одночлена в виде новой переменной и выполнения Гауссовского исключения.

См. также

1. Nicolas Courtois and Josef Pieprzyk
2. XL 1 ссылка
3. XL 2 ссылка