1 Теоретические основы криптографии 9. КолСодержание Теоретические основы криптографии 9

• Название: КолСодержание Теоретические основы криптографии 9
• Дата: 01.12.2019
• Размер: 0.52 Mb.
• Имя файла: 1 Теоретические основы криптографии 9.doc
• Тип: Реферат; #97986
• страница: 15 из 16

6.2. Виды атак на криптоалгоритмы

В современном криптоанализе рассматриваются атаки на засекреченные системы на основе следующих известных данных:

• 
  Шифртекста;
  
• 
  Открытого текста и соответствующего ему шифртекста;
  
• 
  Выбранного открытого текста;
  
• 
  Выбранного шифртекста;
  
• 
  Адаптированного открытого текста;
  
• 
  Адаптированного шифртекста.
  

Кроме того, рассматриваются следующие методы инженерного (технического) криптоанализа с использованием перечисленных выше известных данных:

• 
  Преднамеренно генерируемых аппаратных ошибок;
  
• 
  Замеров потребляемой мощности;
  
• 
  Замеров времени вычислений.
  

Рассмотрим перечисленные типы атак подробнее.

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

В настоящее время к наиболее мощным видам атак на основе выбранных или адаптированных текстов относятся дифференциальный (разностный) криптоанализ (ДКА) и линейный криптоанализ (ЛКА), которые будут рассмотрены ниже, а также производные от них методы.

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

1. 
   полное раскрытие;
   
2. 
   нахождение эквивалентного алгоритма;
   
3. 
   нахождение открытого сообщения;
   
4. 
   частичное раскрытие.
   

Любая из этих операций может привести в конечном итоге к полному или частичному раскрытию криптосистемы.

6.3. Методы современного криптоанализа

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

6.3.1. Нетехнические методы взлома (Social Hacking)

Этот метод не имеет никакого отношения к математике, но, тем не менее, является очень распространенным. Состоит он в следующем:

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

6.3.2. Метод частотного анализа

Этот метод считается классическим еще со времен появления т.н. шифра Цезаря. Основан он на том, что в каждом языке существует определенная исторически сложившаяся статистическая структура, т.е. существуют определенные символы или комбинации символов, наиболее часто встречающиеся в естественной речи. При перехвате зашифрованного сообщения можно подсчитать частоту появления определенных символов¹² и сопоставить их с вероятностями появления определенных символов или их комбинаций (биграммы, триграммы и т.д.), что в некоторых случаях может привести к однозначному дешифрованию отдельных участков зашифрованного сообщения.

Также этот метод основан на наличии вероятных слов. Речь идет о словах или выражениях, появление которых можно ожидать в сообщении с большой вероятностью. Так, в деловой переписке присутствуют шаблонные слова; в английском языке наиболее часто встречаются слова "and", "the", "are" и т.д.

В качестве классического примера использования частотного анализа может служить рассказ Э. По "Золотой жук".

6.3.3. Атака методом "грубой силы" (Brute Force Attack)

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

Скорость вскрытия методом грубой силы определяется двумя параметрами: количеством проверяемых ключей и скоростью проверки одного ключа. Большинство симметричных алгоритмов в качестве ключа могут использовать любую битовую последовательность фиксированной длины. Длина ключа, например, алгоритма DES составляет 56 бит, значит, всего может быть 2⁵⁶ возможных ключей. Длина ключей некоторых других алгоритмов равна 64 и 128 битам.

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

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

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

6.3.4. Метод встречи посередине

Этот метод основан на следующем факте:

Если множество ключей криптоалгоритма замкнуто относительно композиции, то есть для любых ключей z_i и z_j найдется ключ z_k такой, что результат шифрования любого текста последовательно на z_i и z_j равен шифрограмме этого же числа на z_k, то есть то можно воспользоваться этим свойством. Пусть нам нужно найти ключ z_k. Тогда для нахождения ключа z_k, необходимо найти эквивалентную ему пару ключей z_i, z_j. Данный метод криптоанализа основан на "парадоксе дней рождения". Известно, что если считать, что дни рождения распределены равномерно, то в группе из 24 человек с вероятностью 0,5 у двух человек дни рождения совпадут. В общем виде этот парадокс формулируется так: если a√n предметов выбираются с возвращением из некоторой совокупности размером n, то вероятность того что два из них совпадут, равна 1-exp(-a² / 2) .

Пусть известен открытый текст x и его шифрограмма y. Для текста x строим базу данных, содержащую случайное множество ключей z^| и соответствующих шифрограмм w=F(z^| , x), и упорядочиваем ее по шифрограммам w. Объем базы данных выбираем . Затем подбираем случайным образом ключи z^{| |} для расшифровки текстов y и результат расшифрования v = F(z^{| |} , y) сравниваем с базой данных. Если текст v окажется равным одной из шифрограмм w, то ключ z^| z^{| |} эквивалентен искомому ключу z. Временная сложность метода составляет О(√#{z}log#{z}). Множитель log#{z} учитывает сложность сортировки. Требуемая память равна О(√#{z}log#{z}) бит или О(√#{z}) блоков (предполагается, что длина блока и длина ключа различаются на ограниченную константу).

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

Другое применение этого метода для множества, не являющегося полугруппой, можно продемонстрировать на хэш-функциях. Например, для подделки подписи надо найти два текста, обладающих одним хэш-образом. После этого можно подписанное сообщение заменить на другое, обладающее таким же хэш-образом. Поиск двух таких сообщений можно выполнить с использованием метода "встречи посередине". Сложность поиска равна О(√#{h}), где #{h} - число всевозможных хэш-образов.

6.3.5. Метод Полларда

Для нахождения ключа, например в криптоалгоритме, основанном на задаче логарифма на некоторой группе, достаточно решить задачу о встрече на графе случайного отображения. Для этого из двух разных стартовых точек x₀^|, x₀^{| |} строится траектория до входа в цикл. Затем одна из двух конечных точек, лежащих в цикле, фиксируется, а траектория другой продолжается до встречи с фиксированной точкой. Для функции f и точки входа x₀ длина траектории составляет О(√#М ) шагов. Типичный вид этой траектории содержит предельный цикл длины О(√#М ) и отрезок до входа в цикл примерно такой же длины. В качестве индикатора замыкания траектории Поллард предложил использовать равенство x_i = x_2i , где x_i - i-я точка траектории для входа x₀. Это равенство будет выполняться всегда. Значение индекса i не превышает суммы длины пути до входа в цикл.

В среднем сложность нахождения равенства x_i = x_2i равна 3√()#М. Сложность встречи, когда обе точки лежат в цикле, равна 0,5√()#М. Таким образом, итоговая сложность равна 3,5 ()#М.

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

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

Успех таких попыток вскрытия r-циклического шифра зависит от существования дифференциалов (r-1)-го цикла, которые имеют большую вероятность. Дифференциал i-го цикла определяется как пара (a, b)_iтакая, что пара различных открытых текстов x, x* c разностью a может привести к паре выходных текстов y, y* после i-ого цикла, имеющих разность b (для соответствующего понятия разности). Вероятность i-циклового дифференциала (a, b)_i- это условная вероятность P(D y(i)=b | Dx=a ) того, что разность D y(i) пары шифротекстов (y, y*) после i-ого цикла равна b при условии, что пара текстов (x, x*) имеет разность Dx=a; открытый текст x и подключи циклов к⁽¹⁾ , к⁽²⁾ ,...., к⁽ⁱ⁾независимыми и равновероятными.

Основная процедура ДКА r-циклического шифра с использованием выбранных открытых текстов может быть следующей:

1. На этапе предвычислений ищем множество (r-1)-цикловых дифференциалов . Упорядочиваем это множество дифференциалов по величине их вероятности.

2. Выбираем открытый текст x произвольным образом и вычисляем x* так, чтобы разность между x и x* была равна a₁. Тексты x и x* шифруются на подлинном ключе и после r циклов получаем пару шифртекстов y(r) , y*(r). Предполагаем, что на выходе предпоследнего (r-1)-ого цикла разность шифртекстов равна наиболее вероятной: Dy(r-1)=b₁. Для тройки (D y(r-1), y(r), y*(r)) находим каждое возможное (если их несколько) значение подключа последнего цикла к^(r). Добавляем его к количеству появлений каждого такого значения подключа к^(r).

3. Повторяем п.2 до тех пор, пока одно или несколько значений подключа к^(r) не станет появляться чаще других. Берем этот подключ или множество таких подключей в качестве криптографического решения для подключа к^(r).

4. Повторяем пп.1-3 для предпоследнего цикла, при этом значения y(r-1) вычисляются расшифрованием шифртекстов на найденном подключе последнего цикла к^(r). Далее действуем аналогично, пока не будут раскрыты ключи всех циклов шифрования.

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

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

Обычно при шифровании используется сложение по модулю 2 текста с ключом и операции рассеивания и перемешивания. Задача криптоаналитика - найти наилучшую линейную аппроксимацию (после всех циклов шифрования) выражения



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

Требуемое для раскрытия ключа количество N пар открытых и зашифрованных текстов (блоков) оценивается выражением:

N|P_L-1/2| ^-2 .

Для раскрытия ключа шифра DES этим методом необходимо 2⁴⁷ пар известных открытых и зашифрованных текстов.

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

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