XSL (eXtended Sparse Linearization) attack
Последнее изменение этой страницы: 02:50, 12 июня 2016.
XSL-атака (алгебраическая атака) — это атака на криптографический шифр, основанная на алгебраических свойствах шифра. Она предполагает решение особой системы нелинейных уравнений. Данная атака применима как к блочным, так и поточным шифрам. Цель данной атаки – минимизировать нелинейность нелинейных блоков преобразований. В общем виде, если степень используемых нелинейных преобразований равна n, то алгебраические атаки позволяют свести эту степень к floor(n/2). К настоящему времени с помощью данного метода взломан ряд поточных шифров, а также блочный шифр AES (несколько раундов). Единственный действенный метод, позволяющий противостоять атакам данного вида – использовать нелинейные преобразования, порядок нелинейности которых стремится к n – 1.&
Содержание
XL метод
XL (eXtended Linearization) метод предложили Николя Куртуа, Александр Климов и Ади Шамир в 2000 году.
Алгоритм реализации XL метода
- Multiply: составление всех произведений вида , где k≤D-2;
- Linearize: рассмотрение каждого одночлена хi в степени ≤ D как новой переменной и применение Гауссовского исключения к уравнениям, полученным в пункте 1.
- Solve: повторение пункта 2 до тех пор, пока в результате не будет получено по крайней мере одно уравнение с единственной переменной.
- Repeat: упростить уравнения и повторить процесс для нахождения значений других переменных.
XSL метод
В 2002 году вместо техники XL был создан алгоритм, использующий преимущества особой структуры уравнений и их разреженность. Эта атака была названа XSL-атака, что расшифровывается как «eXtended Sparse Linearization» или «multiply(X) by Selected monomials and Linearize». Алгоритм XSL предложен для работы только со специальными типами шифров, для который выполняются условия:
- S-блоки должны быть такими, чтобы их можно было описать с помощью сверхопределенной системы квадратных уравнений.
- Алгоритм получения ключей должен иметь схожую структуру с алгоритмом зашифрования.
Алгоритм реализации XSL метода
- Обработка имеющейся системы уравнений путем выбора конкретного набора одночленов и уравнений, которые будут использоваться в дальнейших этапах алгоритма
- Выбор значения параметра Р и умножение выбранных на предыдущем этапе уравнений на результаты произведений (Р-1) выбранных одночленов
- При недостаточном числе уравнений применение Т’ метода, в котором некоторые выбранные уравнения умножаются на одиночные переменные. Цель данного метода – создание новых уравнений без получения каких-либо новых одночленов.
- Применение линеаризации, путем представления каждого одночлена в виде новой переменной и выполнения Гауссовского исключения.
ISSN 2542-0356
Следуй за Полисом
Оставайся в курсе последних событий
Лицензия
Если не указано иное, содержание этой страницы доступно по лицензии Creative Commons «Attribution-NonCommercial-NoDerivatives» 4.0, а примеры кода – по лицензии Apache 2.0. Подробнее см. Условия использования.