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

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

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

Открытие линейного криптоанализа послужило толчком к построению новых криптографических схемШаблон:Source-ref.

Принцип работы

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

Построение линейных уравнений

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

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

где [math]\displaystyle{ P_n, C_n, K_n }[/math] — n-ые биты текста, шифртекста и ключа соответственно.

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

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

Есть несколько видов атак линейного криптоанализаШаблон:Source-refШаблон:Source-ref. Рассматривается алгоритм Мацуи: изначально для каждого раунда шифра находится линейная аппроксимация с наибольшей вероятностью смещения. Полученные выражения объединяются в общую для всех раундов линейную аппроксимацию, вероятность смещения которой позволяет найти лемма о набегании знаков.

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

Линейный криптоанализ имеет одно очень полезное свойство: при определённых условиях (например, когда об открытом тексте известно, что он состоит из символов в кодировке ASCII) можно свести соотношение (1) к уравнению видаШаблон:Source-ref:

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

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

Лемма о набегании знаков

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

[math]\displaystyle{ P = \frac{1}{2} + 2^{n-1}\prod_{i=1}^{n} (p_i - \frac{1}{2}). }[/math]

Получение битов ключа

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

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

Применение

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

Применение к DES

Эксперименты Мицуру Мацуи по атакам по открытому тексту (вычисления проводились на HP9750 66 МГц) дали следующие результатыШаблон:Source-ref:

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

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

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

В отличие от дифференциального криптоанализа, которому требуются выбранные открытые тексты, метод довольствуется известными открытыми текстами, что существенно увеличивает его область применения. Однако и в линейном криптоанализе иногда бывает полезно использовать выбранные открытые тексты вместо известных. Например, для DES существует методика, значительно уменьшающая количество требуемых данных и вычислений, используя выбранные открытые текстыШаблон:Source-ref.

Применение к другим методам шифрования

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

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

Защита от линейного криптоанализа

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

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

Значительную роль в построении стойких S-блоков сыграло применение бент-функций. В 1982 году было обнаружено, что последовательности максимальной длины, построенные на основе бент-функций, имеют предельно низкие значения как взаимной корреляции, так и автокорреляцииШаблон:Source-refШаблон:Source-ref. Впоследствии ряд криптографов работал над применением бент-функций и их векторных аналогов для предельного повышения криптографической стойкости блочных шифров к линейному и дифференциальному анализуШаблон:Source-refШаблон:Source-refШаблон:Source-ref.

См. также

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

Литература

• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Нильс Фергюсон, Брюс Шнайер. Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: Диалектика, 2004. — 432 с. — 3000 экз. — ISBN 5-8459-0733-0, ISBN 0-4712-2357-3.