Линейный криптоанализ

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

Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (яп. 松井 充 Мацуи Мицуру). Предложенный им в 1993 году (на конференции Eurocrypt '93) алгоритм был изначально направлен на вскрытие DES и FEAL^[1]. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров^[2]. Также пригоден для атак на потоковые шифры.

Открытие линейного криптоанализа послужило толчком к построению новых криптографических схем^[3].

Криптоанализ происходит в два шага. Первый — построение соотношений между открытым текстом, шифртекстом и ключом, которые справедливы с высокой вероятностью. Второй — использование этих соотношений вместе с известными парами «открытый текст — шифртекст» для получения битов ключа.

Смысл алгоритма состоит в получении соотношений следующего вида:

${\displaystyle P_{i_{1}}\oplus P_{i_{2}}\oplus \dots \oplus P_{i_{a}}\oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \dots \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \dots \oplus K_{k_{c}},\qquad (1)}$

где ${\displaystyle P_{n},C_{n},K_{n}}$ — n-ые биты текста, шифртекста и ключа соответственно.

Данные соотношения называются линейными аппроксимациями. Вероятность P справедливости такого соотношения для произвольно выбранных битов открытого текста, шифртекста и ключа примерно равна 1/2. Такими соотношениями, вероятность которых заметно отличается от 1/2, можно пользоваться для вскрытия алгоритма.

Идея линейного криптоанализа — определить выражения вида (1), которые имеют высокую или низкую вероятность возникновения. Если алгоритм шифрования имеет высокую частоту выполнения уравнения (1), или напротив, уравнение выполняется с низкой частотой, то это свидетельствует о бедной способности рандомизации шифра. Если вероятность выполнения уравнения (1) равна p, то вероятность смещения p − 1/2. Чем больше величина вероятности смещения |p − 1/2|, тем лучше применимость линейного криптоанализа с меньшим количеством открытых текстов, необходимых для атаки^[1][4].

Есть несколько видов атак линейного криптоанализа^[5][6][7]. Рассматривается алгоритм Мацуи: изначально для каждого раунда шифра находится линейная аппроксимация с наибольшей вероятностью смещения. Полученные выражения объединяются в общую для всех раундов линейную аппроксимацию, вероятность смещения которой позволяет найти лемма о набегании знаков.

Далее рассматривается алгоритм нахождения наилучшей линейной аппроксимации для одного раунда. В блочных шифрах анализ преимущественно концентрируется на S-блоки, так как они являются нелинейной частью шифра. Так как S-блок принимает на входе m битов и возвращает n битов, от криптоаналитика требуется построить 2^m+n аппроксимаций. Чтобы найти вероятность для одной аппроксимации, на вход S-блоку даются все 2^m возможных входных значений и идёт подсчёт, сколько раз данная аппроксимация верна для входных и выходных битов. Полученное количество совпадений делится на 2^m. В алгоритме DES наибольшую вероятность смещения имеет линейная аппроксимация для таблицы S₅, в которой четвёртый из шести входных битов равен XOR над всеми четырьмя выходными битами с вероятностью 12/64^[8][4]. Для полнораундового DES получено соотношение с вероятностью выполнения 1/2 + 2^−24[9].

Линейный криптоанализ имеет одно очень полезное свойство: при определённых условиях (например, когда об открытом тексте известно, что он состоит из символов в кодировке ASCII) можно свести соотношение (1) к уравнению вида^[10][11]:

${\displaystyle C_{j_{1}}\oplus C_{j_{2}}\oplus \dots \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \ldots \oplus K_{k_{c}}.}$

Здесь отсутствуют биты открытого текста, то есть можно построить атаку на основе только шифртекста. Такая атака может применяться к перехваченному шифртексту и является более практичной.

Хотя аппроксимацию с наибольшим отклонением от 1/2 не сложно найти для одного раунда, возникает проблема с вычислением вероятности смещения при экстраполировании метода на полнораундовый шифр. В принципе, это потребовало бы от криптоаналитика просмотреть все возможные комбинации открытых текстов и ключей, что невыполнимо. Решение этой проблемы — сделать ряд предположений и приблизить вероятность, используя лемму о набегании знаков^[англ.]. Пусть мы получили линейные аппроксимации ${\displaystyle F_{i}\,(1\leq i\leq n)}$ для различных раундов, которые равны 0 с вероятностью ${\displaystyle p_{i}}$. Тогда вероятность того, что общая линейная аппроксимация ${\displaystyle F_{1}\oplus F_{2}\oplus \dots \oplus F_{n}}$ равняется нулю, равна^[1][4]

${\displaystyle P={\frac {1}{2}}+2^{n-1}\prod _{i=1}^{n}(p_{i}-{\frac {1}{2}}).}$

Как только получена линейная аппроксимация, можно применить прямой алгоритм и, используя пары открытый текст-шифртекст, предположить значения битов ключа. При этом логично использовать максимально эффективное соотношение, то есть такое, для которого отклонение вероятности P от 1/2 максимально.

Для каждого набора значений битов ключа в правой части уравнения (1) вычисляется количество пар открытый текст-шифртекст T, для которых справедливо равенство (1). Тот кандидат, для которого отклонение T от половины количества пар открытый текст-шифртекст — наибольшее по абсолютному значению, полагается наиболее вероятным набором значений битов ключа^[1][4].

Линейный криптоанализ изначально разрабатывался для атак на блочные шифры, но применим и к потоковым. Самим разработчиком было подробно изучено его применение к DES.

Эксперименты Мицуру Мацуи по атакам по открытому тексту (вычисления проводились на HP9750 66 МГц) дали следующие результаты^[12][13]:

• На 8-раундовый DES понадобилось 2²¹ известных открытых текстов. Атака заняла 40 секунд.
• На 12-раундовый DES понадобилось 2³³ известных открытых текстов и 50 часов.
• На 16-раундовый DES потребовалось 2⁴³ известных открытых текстов и 50 дней.

В 2001 году Паскаль Жюно (фр. Pascal Junod) провёл ряд экспериментов, чтобы определить сложность атаки. В результате оказалось, что в действительности атака на 16-раундовый DES может успешно применяться при наличии 2³⁹—2⁴¹ известных текстов^[13].

При большом количестве раундов шифра линейный криптоанализ, как правило, используется вместе с методом «грубой силы» — после того, как определённые биты ключа найдены с помощью линейного криптоанализа, проводится исчерпывающий поиск по возможным значениям остальных битов. У такого подхода есть несколько оснований: во-первых, наилучшие линейные аппроксимации позволяют найти значения лишь некоторых битов ключа, во-вторых, количество требуемых открытых текстов в таком случае меньше, а перебор оставшихся битов ключа занимает меньше времени^[5][13].

В отличие от дифференциального криптоанализа, которому требуются выбранные открытые тексты, метод довольствуется известными открытыми текстами, что существенно увеличивает его область применения. Однако и в линейном криптоанализе иногда бывает полезно использовать выбранные открытые тексты вместо известных. Например, для DES существует методика, значительно уменьшающая количество требуемых данных и вычислений, используя выбранные открытые тексты^[7].

Помимо DES и FEAL, известны и другие алгоритмы, подверженные линейному криптоанализу, например:

1. Линейный криптоанализ действует против алгоритма RC5 в случае, если искомый ключ шифрования попадает в класс слабых ключей^[14].
2. Алгоритмы NUSH и NOEKEON также вскрываются методом линейного криптоанализа^[15][16][17].
3. Расширение линейного криптоанализа, основанное на некоррелирующих между собой линейных аппроксимациях, применимо для вскрытия 6-раундовых AES-192 и AES-256, а также 13-раундового CLEFIA-256^[6].

Для атаки на блочный шифр с помощью линейного криптоанализа достаточно, как было описано выше, получить линейное соотношение, существенно смещённое по вероятности от 1/2. Соответственно, первая цель при проектировании шифра, стойкого к атаке, — минимизировать вероятностные смещения, убедиться, что подобное соотношение не будет существовать. Другими словами, необходимо сделать так, чтобы блочный шифр удовлетворял строгому лавинному критерию (СЛК). Говорят, что блочный шифр удовлетворяет СЛК, если при любом изменении текста или ключа в получающемся шифртексте ровно половина битов меняет своё значение на противоположное, причём каждый бит изменяется с вероятностью 1/2. Обычно это достигается путём выбора высоко нелинейных S-блоков и усилением диффузии.

Данный подход обеспечивает хорошее обоснование стойкости шифра, но, чтобы строго доказать защищённость от линейного криптоанализа, разработчикам шифров необходимо учитывать более сложное явление — эффект линейных оболочек (англ. linear hull effect)^[6][18]. Следует заметить, что шифры, которые оптимальны против некоторого узкого класса атак, обычно слабы против других типов атак. К примеру, известно расположение S-блоков в DES, при котором существенно увеличивается стойкость к линейному криптоанализу, но ухудшается стойкость к дифференциальному криптоанализу^[19].

Значительную роль в построении стойких S-блоков сыграло применение бент-функций. В 1982 году было обнаружено, что последовательности максимальной длины, построенные на основе бент-функций, имеют предельно низкие значения как взаимной корреляции, так и автокорреляции^[20][21]. Впоследствии ряд криптографов работал над применением бент-функций и их векторных аналогов для предельного повышения криптографической стойкости блочных шифров к линейному и дифференциальному анализу^[22][23][24].

• Дифференциальный криптоанализ

• Matsui M. Linear Cryptanalysis Method for DES Cipher (англ.) // Advances in Cryptology — EUROCRYPT ’93: Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23–27, 1993 Proceedings / T. Helleseth — 1 — Berlin: Springer Berlin Heidelberg, 1993. — P. 386—397. — 465 p. — ISBN 978-3-540-57600-6 — doi:10.1007/3-540-48285-7_33
• Matsui M. The First Experimental Cryptanalysis of the Data Encryption Standard (англ.) // Advances in Cryptology — CRYPTO’94: 14th Annual International Cryptology Conference Santa Barbara, California, USA August 21–25, 1994 Proceedings / Y. G. Desmedt — Berlin: Springer Berlin Heidelberg, 1994. — P. 1—11. — (Lecture Notes in Computer Science; Vol. 839) — ISBN 978-3-540-58333-2 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-48658-5_1
• Heys H. M. A Tutorial on Linear and Differential Cryptanalysis (англ.) // Cryptologia — United States of America: Taylor & Francis, 2002. — Vol. 26, Iss. 3. — P. 189—221. — ISSN 0161-1194; 1558-1586 — doi:10.1080/0161-110291890885
• Нильс Фергюсон, Брюс Шнайер. Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: Диалектика, 2004. — 432 с. — 3000 экз. — ISBN 5-8459-0733-0, ISBN 0-4712-2357-3.

Эта статья входит в число добротных статей русскоязычного раздела Википедии.