Перейти к содержанию

XSL-атака

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

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

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

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


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

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

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

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

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

XSL-шифр

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

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

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

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

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

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

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

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

[math]\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} }[/math]

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

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

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

[math]\displaystyle{ 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[15]. В статье были разобраны примеры, при которых данный алгоритм рушится в так называемом T-блоке, который используется для расширения пространства переменных. Однако учёные сделали вывод, что XSL подход — первая попытка найти уязвимость в структурной части AES-шифра.

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

  • BES-128: [math]\displaystyle{ \approx 2^{401} }[/math]
  • BES-192: [math]\displaystyle{ \approx 2^{622} }[/math]
  • BES-256: [math]\displaystyle{ \approx 2^{691} }[/math]

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

Примечания

  1. ↑ Algebraic Cryptanalysis of the Data Encryption Standard, 2007, pp. 152-169.
  2. ↑ Vincent Rijmen. Rijndael and other block ciphers. NESSIE forum (12-18-02 18:51).
  3. ↑ Нильс Фергюсон, Брюс Шнайер. Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М. : Диалектика, 2004. — 432 с. — 3000 экз. — ISBN 5-8459-0733-0, ISBN 0-4712-2357-3.
  4. ↑ A Simple Algebraic Representation of Rijndael, 2001, pp. 1-9.
  5. ↑ Jacques Patarin. Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88 // Advances in Cryptology — CRYPT0’ 95. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. — С. 248–261. — ISBN 9783540602217, 9783540447504.
  6. ↑ Cryptographers' Track at RSA Conference (2001 : San Francisco, Calif.). Topics in cryptology, CT-RSA 2001 : the Cryptographers' Track at RSA Conference 2001, San Francisco, CA, USA, April 2001 : proceedings. — ISBN 3540418989, 9783540418986, 2001020877.
  7. ↑ 7,0 7,1 7,2 Cryptanalysis of Block Ciphers with Overdefined Systems of Equations, 2002, pp. 2.
  8. ↑ Aviad Kipnis, Adi Shamir. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization // Advances in Cryptology — CRYPTO’ 99. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. — С. 19–30. — ISBN 9783540663478, 9783540484059.
  9. ↑ Cryptanalysis of Block Ciphers with Overdefined Systems of Equations, 2002, pp. 1-35.
  10. ↑ Cryptanalysis of Block Ciphers with Overdefined Systems of Equations, 2002, pp. 3.
  11. ↑ Alex Biryukov, Adi Shamir. Structural Cryptanalysis of SASAS // Journal of Cryptology. — 2010-06-08. — Т. 23, вып. 4. — С. 505–518. — ISSN 1432-1378 0933-2790, 1432-1378. — doi:10.1007/s00145-010-9062-1.
  12. ↑ A Simple Algebraic Representation of Rijndael, 2001, pp. 1-4.
  13. ↑ Cryptanalysis of Block Ciphers with Overdefined Systems of Equations, 2002, pp. 6-8.
  14. ↑ Cryptanalysis of Block Ciphers with Overdefined Systems of Equations, 2002, pp. 12.
  15. ↑ International Conference on the Theory and Application of Cryptology and Information Security (11th : 2005 : Madras, India). Advances in cryptology : ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4-8, 2005 : proceedings. — Springer, 2005. — ISBN 9783540322672, 3540322671, 3540306846, 9783540306849.
  16. ↑ An Analysis of XSL Applied to BES, 2007, pp. 7-13.

Литература

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=XSL-атака&oldid=5855804