Открыть главное меню

Атака на основе адаптивно подобранного открытого текста

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

Содержание

ПрименениеПравить

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

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

ИсторияПравить

Во время Второй мировой войны криптоаналитиками достаточно широко использовались атаки на основе (адаптивно) подобранного открытого текста, открытых текстов и их комбинации.

Так, криптоаналитики из Блетчли-Парка могли определить открытый текст сообщений в зависимости от того, когда эти сообщения были посланы. Например, ежедневный отчет о погоде посылался немецкими связистами в одно и то же время. По той причине, что военные доклады имеют определённую структуру, криптоаналитикам удавалось расшифровывать остальную информацию, пользуясь данными о погоде в той местности.[1]

Другим ярким примером являлись перехваченные сообщения офицера африканского корпуса, который постоянно отсылал «Нечего докладывать». Другие операторы тоже часто использовали стандартные ответы или приветствия.[1]

Также в Блетчли-Парк был придуман следующий способ заставить немцев отсылать определённые сообщения. По просьбе криптоаналитиков Королевские военно-воздушные силы Великобритании минировали определённые участки Северного моря, этот процесс был назван «Садоводством» (англ. «gardening»[2]). Практически сразу после этого немцами посылались зашифрованные сообщения с названиями мест, где были сброшены мины.[1]

После того, как немецкий военнопленный при допросе рассказал, что операторы Энигмы записывали цифры прописью, криптоаналитик Алан Тьюринг, анализируя присутствие в текстах наличие слова «eins» (нем. «один»), смог извлечь много информации о возможных положениях роторов и настройках клавиатуры Энигмы.[1]

Сравнение с другими видами атакПравить

Согласно Брюсу Шнайеру, предполагая, что криптоаналитик знает алгоритм шифрования, можно выделить 4 основных вида криптоанализа[3]:

  1. Атака на основе шифротекста
  2. Атака на основе открытых текстов и соответствующих шифртекстов
  3. Атака на основе подобранного открытого текста (возможность выбрать тексты для шифрования, но только один раз, перед атакой)
  4. Атака на основе адаптивно подобранного открытого текста

В случае атаки на основе открытых текстов и соответствующих шифртекстов криптоаналитик имеет доступ к некоторым парам текст — шифртекст.

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

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

Алгоритм атакиПравить

При атаке на основе адаптивно подобранного открытого текста часто используются методы дифференциального криптоанализа, которые описаны в работах Ади Шамира, и линейного криптоанализа. Общий метод таких атак заключаются в следующем:

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

  1. Выбирается пара открытых текстов с подобранной разностью
  2. Тексты подаются на шифрующее устройство
  3. Соответствующие шифртексты так же будут иметь некоторую разность
  4. Набирается статистика из пар вида открытый текст — шифртекст
  5. Сопоставляются разность между открытыми текстами с разностью между шифртекстами
  6. На основе собранных данных делается предположение о ключе системы

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

Основная задача криптоаналитика заключается в получении следующего однораундового соотношения:

 

где   — i-й бит открытого текста,

  — j-й бит зашифрованного текста,

  — k-й бит ключа.

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

Аппроксимация с заданным условием на вероятность может быть найдена довольно легко. Проблема возникает при экстраполировании метода на полнораундовое шифрование. Точное решение этой проблемы невозможно, так как при этом криптоаналитику придется проанализировать все возможные варианты открытых текстов и шифртекстов. Зато после ряда предположений появляется возможность использование леммы о набегании знаков (англ. «Piling-up lemma»). Таким образом линейная аппроксимация представляется в виде цепочки аппроксимаций, называемой линейной характеристикой. Вероятность такой характеристики находится по формуле:

 

Примеры атакПравить

Для систем с открытым ключом;Править

  • Обоснование

Во многих криптоаналитических системах применяется следующий режим работы:

  1. Принимается сообщение от отправителя
  2. Сообщение расшифровывается и далее обрабатывается
  3. Если сообщение признаются случайным набором цифр, то этот набор возвращается отправителю

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

  • Атака

При данной модели работы криптоаналитической системы, работающей на основе алгоритма RSA, рассмотрим следующий пример:

Пусть криптоаналитик перехватил некоторое сообщение  , которое он хочет расшифровать.

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

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

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

Атака с использованием методов дифференциального криптоанализаПравить

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

Рассмотрим для примера шифрование по алгоритму DES.

Допустим, что нам доступна некоторая программа, работающая по данному алгоритму, и известны все её параметры, кроме ключа.

Пусть   и   — подобранные открытые тексты с разностью  .

Им будут соответствовать шифртексты   и   с разностью —  .

Так как известны перестановки с расширением в  -блок, то известны   и  .

Значения   и   остаются неизвестными, зато можем найти их разность.

Так  .

Последнее выражение верно, так как совпадающие биты   и   сократятся, а различные дадут разницу, несмотря на  .

Процесс подбора ключа основан на том, что для заданного   различные   будут встречаться с разной вероятностью.

Таким образом, комбинации   и   позволяют с некоторой вероятностью предположить значения   и  . Что, при известных   и  , позволит найти ключ  .

Таким образом, заданные отличия открытых текстов с достаточной большой вероятностью вызовут определённые отличия полученных шифртекстов. Эти различия называются характеристиками. Характеристики находятся при помощи таблиц, построенных следующим образом: строкам соответствуют возможные  , столбцам —  . На пересечении данной строки и столбца записывается, сколько раз при данных   на входе, на выходе получили  . Так как каждая из итераций независима, то различные характеристики можно объединять, перемножая их вероятности. Зная распределение вероятности, можно с высокой степенью точности подобрать ключ.

Атака с использованием методов линейного криптоанализаПравить

Применение к DESПравить

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

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

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

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

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

См. такжеПравить

ПримечанияПравить

  1. 1 2 3 4 Tony Sale «The Enigma of Bletchley Park»
  2. 90 Squadron
  3. Шнайер Б. Криптоанализ // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 20. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  4. Mitsuru Matsui «Linear Cryptanalysis Method for DES Cipher»

ЛитератураПравить