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, тогда шифр становится аффинным и легко взламывается другими способами, не требующими линеаризации. Если же приравнять эти аргументы ${\displaystyle 1/x}$ к ${\displaystyle x^{254}}$, то уравнение получается полиномиально сложным.

В те годы появлялось множество атак на открытые ключи: атака на систему Мацумото-Имаи^[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, который описывает структуру типового блочного шифра, для которого метод может быть применён.

Структура шифрования состоит из ${\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 могут быть представлены в виде некоторой функции многих переменных высоких степеней^[12], метод Куртуа понижает степень функции до некоторого числа ${\displaystyle d}$, где ${\displaystyle d}$ обычно выбирается равным 2, с помощью расширения пространства аргументов. Особый интерес имеет количество таких функций ${\displaystyle r}$. Если ${\displaystyle r=s}$, такие уравнения достаточно описывают S-блок. Если же ${\displaystyle r>>s}$, тогда говорим, что система переопределена.

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

Алгоритм первого варианта 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}$ должен возрастать не сильно, как показали эксперименты Куртуа и Пепшика^[14].

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

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

Например, в работе Chu-Wee Lim и Khoongming Khoo ^[16] исследуется попытка взлома приложения BES (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-шифров.

Примечания

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). Дата обращения: 20 декабря 2018. Архивировано из оригинала 3 августа 2004 года.
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. 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.

Литература

• Nicolas T. Courtois, Gregory V. Bard. Algebraic Cryptanalysis of the Data Encryption Standard // Cryptography and Coding. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. — ISBN 9783540772712.
• Фергюсон Н., Шнайер Б. Практическая криптография. — 2005. — 424 с.
• Nicolas T. Courtois and Josef Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. — Berlin, Heidelberg: Springer Berlin, 2002. — С. 1-35.
• Chu-Wee Lim, Khoongming Khoo. An Analysis of XSL Applied to BES // Fast Software Encryption. — 2007. — С. 13. Архивировано 3 марта 2016 года.
• Niels Ferguson, Richard Schroeppel, Doug Whiting. A Simple Algebraic Representation of Rijndael // Selected Areas in Cryptography. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. — С. 103–111. — ISBN 9783540430667, 9783540455370.