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

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

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

Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (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)

где Pn, Cn, Kn — n-ые биты текста, шифротекста и ключа.

Данные соотношения называются линейными аппроксимациями. Для произвольно выбранных бит открытого текста, шифротекста и ключа вероятность справедливости такого соотношения 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}.

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

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 взламывается с помощью 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).

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

Примечания

См. также

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Линейный криптоанализ" в других словарях:

  • линейный криптоанализ — Атака по известному открытому тексту, при которой используются линейные аппроксимации для описания блокового шифрования. [Криптографический словарь Карэна Исагулиева www.racal.ru] [http://www.morepc.ru/dict/] Тематики информационные технологии в… …   Справочник технического переводчика

  • Линейный конгруэнтный метод — один из алгоритмов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов. Содержание 1 Описание 2 Свойства …   Википедия

  • Дифференциальный криптоанализ — Дифференциальный криптоанализ  метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хэш функций). Предложен в 1990 году израильскими специалистами Эли Бихамом и Ади Шамиром. Дифференциальный… …   Википедия

  • Криптографическая атака — Криптоанализ (от греч. κρυπτός скрытый и анализ) наука о методах получения исходного значения зашифрованной информации, не имея доступа к секретной информации (ключу), необходимой для этого. В большинстве случаев под этим подразумевается… …   Википедия

  • Блочный шифр — Общая схема работы блочного шифра Блочный шифр  разновидность симметричного шифра …   Википедия

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

  • NUSH — Создатель: Анатолий Лебедев, Алексей Волчков Создан: 1999 г. Опубликован: 2000 г. Размер ключа: 128, 192, 256 бит Размер блока: 64, 128, 256 бит Число раундов: 36, 68, 132 NUSH («Наш»)  блочный …   Википедия

  • DES — У этого термина существуют и другие значения, см. DES (значения). DES, Data Encryption Standard Создатель: IBM Создан: 1977 г. Опубликован: 1977 г. Размер ключа: 56 бит Размер блока: 64 бит …   Википедия

  • Бирюков, Алекс — Алекс Бирюков (англ. Alex Biryukov)  криптограф, в настоящее время доцент университета Люксембурга[1]. К его значимым достижениям относится дизайн поточного шифра LEX, а также криптоанализ многочисленных криптографических примитивов. В 1998… …   Википедия

  • MAGENTA — MAGENTA  блочный шифр, разработанный Майклом Якобсоном и Клаусом Хубером для немецкой телекоммуникационной компании Deutsche Telekom AG. MAGENTA является сокращением от Multifunctional Algorithm for General purpose Encryption and Network… …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»