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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Принцип работы[править | править вики-текст]

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

Построение линейных уравнений[править | править вики-текст]

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

X_{i1} \oplus X_{i2} \oplus \dots \oplus X_{iu} \oplus Y_{j1} \oplus Y_{j2} \oplus \dots \oplus Y_{jv} = 0\ (1),

где X_i\ – i-й бит входного X = [X_1, X_2, \dots] и Y_j\ – j-й разряд выходного Y = [Y_1, Y_2, \dots]. Это уравнение представляет собой сумму u входных и v выходных бит по модулю 2.

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

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

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

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

Линейный криптоанализ имеет одно очень полезное свойство: при определённых условиях можно свести соотношение (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}.

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

Есть несколько видов атак линейного криптоанализа. Рассмотрим алгоритм Мацуи: исследуем построение линейной аппроксимации с участием битов открытого текста (представлены как X в (1)) и входом последнего шага алгоритма шифрования(представлены как Y в (1)). Открытый текст – случайные биты, следовательно, входные биты на последнем шаге алгоритма тоже случайны.

Как построить выражения, которые с большой вероятностью линейные, и, следовательно, могут быть использованы? Это делается с учетом свойств единственной нелинейной составляющей шифровальщика: S-блока. Можно разработать линейные аппроксимации между наборами входных и выходных битов в S-блоках. Следовательно, можно объединить линейные аппроксимации из S-блоков вместе, так что промежуточные вычисления могут быть заменены линейными аппроксимациями, тогда останется единое линейное уравнение, которое имеет большое смещение и содержит биты открытого текста и входные биты последнего шага алгоритма.[3][4]

Лемма о набегании знаков (Piling-up lemma)[править | править вики-текст]

Перед рассмотрением построения линейного выражения для примера шифровальщика, потребуются несколько базовых понятий. Рассмотрим две случайных двоичных переменных X_1 и X_2. Прежде всего, отметим простые отношения: X_1\oplus X_2 = 0 – линейное выражение, эквивалентно X_1 = X_2; X_1\oplus X_2 = 1 – аффинный и эквивалент X_1 \neq X_2.

Теперь предположим, что распределения вероятностей представленно в виде


P(X_1 = i) = \begin{cases}
  p_1,  &  i = 0\\
  1 - p_1, & i = 1
\end{cases}

и


P(X_2 = i) = \begin{cases}
  p_2,  &  i = 0\\
  1 - p_2, & i = 1
\end{cases}

Если две случайные величины независимы, тогда


P(X_1 = i, X_2 = j) = \begin{cases}
p_1p_2,  &  i = 0, j = 0\\
p_1(1-p_2), & i = 0, j = 1\\
(1-p_1)p_2, & i = 1, j = 0\\
(1-p_1)(1-p_2), & i = 1, j = 1\\
\end{cases}

Можно показать, что

P(X_1 \oplus X_2 = 0) =P(X_1=0)P(X_2=0)+P(X_1=1)P(X_2=1)\
=p_1p_2 + (1-p_1)(1-p_2)\
=p_1p_2 + (1-p_1-p_2+p_1p_2)\
=2p_1p_2-p_1-p_2+1\

С другой стороны, положим

 p_1 = 1/2 + \varepsilon_1\ и p_2 = 1/2 + \varepsilon_2\ , где \varepsilon_1\ и \varepsilon_2\ – вероятности смещения, и -1/2 \leq \varepsilon_1 , \varepsilon_2 \leq 1/2 .

Следовательно

 P(X_1\oplus X_2 = 0) = 1/2 + \varepsilon_1\varepsilon_2,

и смещение  \varepsilon_{1,2}\ для X_1\oplus X_2 = 0 \ будет равно

 \varepsilon_{1,2} = 2 \varepsilon_1\varepsilon_2.

Это выражение можно обобщить на две и более случайных двоичных переменных, X_1, X_n, с вероятностями  p_1 = 1/2 + \varepsilon_1 \dots p_n = 1/2 + \varepsilon_n .

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

P(X_1\oplus X_2\oplus\cdots\oplus X_n=0)=1/2+2^{n-1}\prod_{i=1}^n \epsilon_i,

где  \varepsilon_{1,2,...,n}\ представляет собой смещение для X_1 \oplus \dots \oplus X_n = 0. [5]

Анализ компонент шифровальщика[править | править вики-текст]

S-Блок

Перед детальным рассмотрением атаки на шифровальщик, потребуются знания о линейных уязвимостях S-блоков. Рассмотрим S-блок, представленный на рисунке с вводом X = [X_1 X_2 X_3 X_4] и соответствующим выходом Y = [Y_1 Y_2 Y_3 Y_4]. Все линейные приближения могут быть изучены, чтобы определить их полезность, путем вычисления смещения вероятности для каждого. Следовательно, рассматриваются все выражения вида уравнения (1), где X и Y входы и выходы S-блока соответственно.

Например, для S-блока, который используется в шифровальщике, рассмотрим линейное приближение  X_1 \oplus X_3 \oplus Y_1 \oplus Y_3 \oplus Y_4 = 0\ или, что эквивалентно,

 X_1 \oplus X_3 \oplus X_3 \oplus = Y_1 \oplus Y_3 \oplus Y_4.

Подставляя 16 возможных значений входных данных для X и изучая соответствующие выходы для Y, можно заметить, что ровно в 12 из 16 случаев приведенное выше выражение справедливо. Таким образом, смещение вероятности: 12/16 - 1/2 = 1/4. Результат представлен в Таблице "Пример линейной аппроксимации S-блока".

Пример линейной аппроксимации S-блока
X_1 X_2 X_3 X_4 Y_1 Y_2 Y_3 Y_4 X_2 \oplus X_3 Y_1 \oplus Y_3 \oplus X_4 X_1 \oplus X_4 Y_2 X_3 \oplus X_4 Y_1 \oplus Y_4
0 0 0 0 1 1 1 0 0 0 0 1 0 1
0 0 0 1 0 1 0 0 0 0 1 1 1 0
0 0 1 0 1 1 0 1 1 0 0 1 1 0
0 0 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 0 1 0 1 1 0 0 0 0
0 1 0 1 1 1 1 1 1 1 1 1 1 0
0 1 1 0 1 0 1 1 0 1 0 0 1 0
0 1 1 1 1 0 0 0 0 1 1 0 0 1
1 0 0 0 0 0 1 1 0 0 1 0 0 1
1 0 0 1 1 0 1 0 0 0 0 0 1 1
1 0 1 0 0 1 1 0 1 1 1 1 1 0
1 0 1 1 1 1 0 0 1 1 0 1 0 1
1 1 0 0 0 1 0 1 1 1 1 1 0 1
1 1 0 1 1 0 0 1 1 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1 0 1 0
1 1 1 1 0 1 1 1 0 0 0 1 0 1

Аналогичным образом для уравнения

X_1 \oplus X_4 = Y_2

Видно, что вероятность смещения равна нулю, и для уравнения

X_3 \oplus X_4 = Y_1 \oplus Y_4

вероятность смещения 2/16-1/2 = -3/8. В последнем случае наилучшим приближением является аффинная аппроксимация, как показано знаком "-". Однако, успех атаки зависит от величины смещения, и аффинные аппроксимации могут быть использованы в равной степени и для линейной аппроксимации.[6]

Получение битов ключа[править | править вики-текст]

Получение одного бита информации о ключе[править | править вики-текст]

Линейное приближение алгоритма.

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

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

Получение бит первого и последнего подключей[править | править вики-текст]

После того, как найден R-1 раунд линейных приближений для алгоритма с R раундами, с достаточно большой вероятностью смещения, возможно атаковать алгоритм для восстановления бит последнего подключа. Нашей целью являются биты, которые можно извлечь из последнего вспомогательного подключа. В частности, целевые биты – биты из последнего подключа, связанного с S-блоком, участвующим в линейном приближении.

Назовем биты, извлеченные из последнего подключа "частичным целевым подключом". Процесс извлечения битов ключа включает в себя частичную дешифровку последнего раунда алгоритма. В частности, для всех возможных значений частичного целевого подключа, биты, соответствующие шифртексту складываются с битами частичнного целевого подключа, и результат проходит обратно через всю цепочку S-блоков. Это выполняется для всех известных пар открытый текст/шифртекст, и для каждого значения частичного целевого ключа создается свой счетчик. Счетчик для конкретного частичного целевого подключа увеличивается, когда линейное выражение справедливо для битов в S-блоках в последнем цикле. Предполагается, что частичный целевой подключ, значение счетчика которого имеет наибольшее отклонение от половины числа пар открытый текст/шифртекст, является верным значением частичного целевого подключа.

Это работает, так как подразумевается, что значение верного частичного целевого подключа будет результатом линейной аппроксимации, которая выполняется с вероятностью, значительно отличающейся от 1/2. При использовании неверного подключа в результате будут относительно случайные биты, поступающие в S-блок в последнем цикле, и, как следствие, линейное выражение будет выполняться с вероятностью 1/2.[7]

Применение[править | править вики-текст]

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

Применение к DES[править | править вики-текст]

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

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

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

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

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

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

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

Применение к другим методам шифрования[править | править вики-текст]

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

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

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

Защита от линейного криптоанализа[править | править вики-текст]

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

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

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

Примечания[править | править вики-текст]

  1. Mitsuru Matsui Linear cryptanalysis method of DES cipher // Springer-Verlang. — 1998.
  2. Howard M. Heys A Tutorial on Linear and Differential Cryptanalysis. — С. 6,7.
  3. Mitsuru Matsui Linear cryptanalysis method of DES cipher // Springer-Verlang. — 1998.
  4. Howard M. Heys Tutorial on Linear and Differential Cryptanalysis.
  5. C. Harpes, G. Kramer, and J.L. Massey. A generalization of linear cryptanalysis and the applicability of Matsui’s piling-up lemma // Springer-Verlag. — 1995.
  6. Howard M. Heys A Tutorial on Linear and Differential Cryptanalysis.
  7. E. Biham and A. Shamir. Differential Cryptanalysis of the Data En- cryption Standard // Springer-Verlag. — 1993.
  8. Mitsuru Matsui "Linear Cryptanalysis Method for DES Cipher"
  9. Andrea Rock and Kaisa Nyberg Exploiting Linear Hull in Matsui’s Algorithm 1. — Aalto University School of Science, Department of Information and Computer Science P.O. Box 15400, FI-00076 Aalto, Finland, 2011.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

  • ETH Zurich: Linear Cryptanalysis of DES (англ.). — Дипломная работа Паскаля Жюно (Pascal Junod), Научный руководитель – Серж Вауденай (Serge Vaudenay).