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

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

Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (Mitsuru Matsui). Предложенный им в 1993 г. (на Еврокрипте-93) алгоритм был изначально направлен на вскрытие DES и FEAL. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров. Разработаны атаки на блочные и потоковые шифры.

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

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

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

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

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

$P_{i_1} \oplus P_{i_2} \oplus ... \oplus P_{i_a} \oplus C_{j_1} \oplus C_{j_2} \oplus ... \oplus C_{j_b} = K_{k_1} \oplus K_{k_2} \oplus ... \oplus K_{k_c}, (1)$

где P_n, C_n, K_n — n-ые биты текста, шифротекста и ключа.

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

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

В блочных шифрах анализ преимущественно концентрируется на S-боксах, так как они являются нелинейной частью шифра. Наиболее эффективное однораундовое соотношение для алгоритма DES использует свойство таблицы S5. Второй входной бит таблицы равен результату операции XOR над всеми выходными битами с вероятностью 3/16 (смещение в 5/16 относительно 1/2). А для полнораундового DES известно соотношение, выполняющееся с вероятностью 1/2 + 2⁻²⁴.

Линейный криптоанализ имеет одно очень полезное свойство — при определённых условиях можно свести соотношение (1) к уравнению вида:

$C_{j_1} \oplus C_{j_2} \oplus ... \oplus C_{j_b} = K_{k_1} \oplus K_{k_2} \oplus ... \oplus K_{k_c}.$

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

Piling-up lemma

Хотя аппроксимацию с наибольшим отклонением от 1/2 найти не сложно, возникает ряд проблем при экстраполировании метода на полнораундовый шифр. Первая затрагивает вычисление вероятности линейной аппроксимации. В принципе, это потребовало бы от криптоаналитика просмотреть все возможные комбинации открытых текстов и ключей, что невыполнимо. Решение этой проблемы — сделать ряд предположений и приблизить вероятность, используя лемму о набегании знаков (piling-up lemma). При использовании этой леммы линейная аппроксимация представляется в виде цепочки аппроксимаций, причём каждая из них охватывает лишь небольшую часть шифра. Такая цепочка называется линейной характеристикой. Вероятность нахождения комбинации:

$P = \frac{kg}{am} * jjot + 2^{n-1}\prod_{i=1}^{n} (p_i - \frac{1}{2}).$

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

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

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

Применение

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

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

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

• 8-ми раундовый DES взламывается с помощью 2²¹ известных открытых текстов. Это заняло у Мацуи 40 секунд.
• 12-ти раундовый DES взламывается с помощью 2³³ известных открытых текстов. На это потребовалось 50 часов.
• На 16-ти раундовый DES требуется 2⁴⁷ известных открытых текстов. Данная атака обычно не практична. Однако, метод работает быстрее, чем исчерпывающий поиск 56-ти битного ключа.

Современная вычислительная техника способна выполнять взлом быстрее.

Весьма часто линейный криптоанализ используется вместе с методом «грубой силы» — после того, как определённые биты ключа найдены с помощью линейного криптоанализа, проводится исчерпывающий поиск по возможным значениям остальных бит. Для взлома DES подобным образом требуется 2⁴³ открытых текстов.

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

Что касается атак по шифротексту, Мацуи были получены следующие результаты:

• Если открытый текст состоит из английских предложений в кодировке ASCII, то 8-ми раундовый DES можно взломать, используя только 2²⁹ шифротекстов.
• Если открытый текст состоит из любых символов ASCII, то 8-ми раундовый DES взламывается с помощью 2³⁷ шифротекстов.

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

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

1. Линейный криптоанализ действует против алгоритма RC5 в случае, если искомый ключ шифрования попадает в класс слабых ключей.
2. Алгоритмы NUSH и Noekeon также вскрываются методом линейного криптоанализа.
3. Некоторые варианты алгоритма DES (DESX, DES с независимыми подключами и Biham-DES) вскрываются линейным криптоанализом.

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

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

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

Данный подход обеспечивает хорошее обоснование стойкости шифра, но чтобы строго доказать защищённость от линейного криптоанализа, разработчикам шифров необходимо учитывать более сложное явление — эффект линейных оболочек (linear hull effect).

Несколько более общая теория доказательства защищённости от класса атак, основанных на линейном криптоанализе, базируется на понятии декорреляции. Теория предполагает, чтобы устройство являлось так называемым декорреляционным модулем, эффективно блокирующим распространение традиционных линейных и дифференциальных характеристик. Следует заметить, что шифры, которые оптимальны против некоторого узкого класса атак, обычно слабы против других типов атак.

Примечания

1. ↑ Mitsuru Matsui "Linear Cryptanalysis Method for DES Cipher"

См. также

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

Ссылки

• Matsui, M. "Linear cryptanalysis method for DES cipher" (PDF). Advances in Cryptology - EUROCRYPT 1993. 
• Biryukov,A and De Canniere, C. "Linear cryptanalysis" (PDF).. 
• Панасенко, С. "Современные методы вскрытия алгоритмов шифрования, часть 4". Chief Information Officer - 2006.