Способы криптоанализа симметричных шифров

ФЕДЕРАЛЬНОЕ АГЕНТСТВО  ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

 

Федеральное государственное  бюджетное образовательное учреждение

высшего профессионального  образования

«ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»

(ФГБОУ ВПО ИРГУПС)

 

Факультет управления транспортом  и информационных технологий

Кафедра «Информационная безопасность»

 

К защите допускаю

Доцент кафедры «ИБ»

Бутин А. А.

____________________

«__»__________ 2012 г.

 

СПОСОБЫ КРИПТОАНАЛИЗА СИММЕТРИЧНЫХ ШИФРОВ

КР.460300.090105.65.ПЗ

 

Выполнил	Руководитель
студент гр. ЗИ-09-1 Макеев  М. В.	доцент кафедры ИБ Бутин А. А.
______________________	______________________
«    »                        2012 г.	«   »                         2012 г.

 

 

 

 

 

Иркутск, 2012 г.

 

Аннотация

Курсовая работа 48 с., 7 рисунков, 1 таблица, 5 формул, 8 источников.

КРИПТОАНАЛИЗ, КРИПТОАТАКИ, АЛГОРИТМЫ, ВЗЛОМ, БЛОЧНЫЕ ШИФРЫ, ПОТОЧНЫЕ ШИФРЫ.

Объектом  исследования является криптоанализ симметричных шифров.

Цель  работы – изучить различные методы криптоанализа.

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

 

Содержание

Введение 6

1 Теоретическая часть 7

1.1 Классификация криптоатак 7

1.2 Универсальные методы криптоанализа 14

1.2.1  Метод полного перебора 14

1.2.2  Атака по ключам 17

1.2.3  Частотный анализ 21

1.3 Методы криптоанализа блочных шифров 22

1.3.1  Статистический метод 23

1.3.2  Метод разностного (дифференциального) анализа 25

1.3.3  Метод линейного анализа 28

1.4 Методы криптоанализа поточных шифров 30

1.5 Криптоанализ по побочным каналам 36

1.5.1  Атака по времени 38

1.5.2  Атаки по мощности 39

1.5.3  Атаки по ошибкам вычислений 40

1.5.4  Атаки по электромагнитному излучению 41

2 Практическая часть 42

Заключение 47

Список использованных источников 48

 

 

 

Нормативные ссылки

ГОСТ 28147-89. Системы  обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. 

Обозначения и сокращения

БШ – блочный шифр;

ПСК – процедура статистической классификации;

ПШ – поточный шифр;

СБИС – сверхбольшая интегральная схема;

ЭВМ – электронно-вычислительная машина;

 

Введение

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

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

1. Теоретическая часть

1. Классификация криптоатак

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

Современная криптография — соревнование методов  шифрования и криптоанализа. Криптоанализом (от греческого kryptos – «скрытый» и analyein –«ослаблять» или «избавлять») называют науку восстановления (дешифрования) открытого текста без доступа к ключу. Фундаментальное допущение криптоанализа, впервые сформулированное Кирхгоффом, состоит в том, что секретность сообщения всецело зависит от ключа, т.е. весь механизм шифрования, кроме значения ключа, известен противнику. Как бы то ни было, секретность алгоритма не является большим препятствием: например, для определения типа программно реализованного криптографического алгоритма требуется лишь несколько дней инженерного анализа исполняемого кода.

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

• Полный взлом – криптоаналитик извлекает секретный ключ.
• Глобальная дедукция – криптоаналитик разрабатывает функциональный эквивалент исследуемого алгоритма, позволяющий зашифровывать и расшифровывать информацию без знания ключа.
• Частичная дедукция – криптоаналитику удается расшифровать или зашифровать некоторые сообщения.
• Информационная дедукция – криптоаналитик получает некоторую информацию об открытом тексте или ключе.

Однако  взлом шифра совсем не обязательно  подразумевает обнаружение способа, применимого на практике для восстановления открытого текста по перехваченному зашифрованному сообщению. В научной криптологии другие правила. Шифр считается взломанным, если в системе обнаружено слабое место, которое может быть использовано для более эффективного взлома, чем метод полного перебора ключей («brute-force approach»). Под взломом понимается лишь подтверждение наличия уязвимости криптоалгоритма, свидетельствующее о том, что свойства надежности шифра не соответствуют заявленным характеристикам. Как правило, криптоанализ начинается с попыток взлома упрощенной модификации алгоритма, после чего результаты распространяются на полноценную версию: прежде чем браться за взлом, например, 16-раундовой версии DES, естественно для начала попытаться взломать шифр с меньшим количеством раундов, чем указано в его спецификации (например, 8-раундовую версию шифра).

Попытка криптоанализа называется атакой. Прежде чем классифицировать атаки, необходимо ввести ряд обозначений: открытый текст будем обозначать буквой x, шифротекст - буквой y (в качестве x может выступать любая последовательность битов: текстовый файл, оцифрованный звук, точечный рисунок и т.д.). Пусть для зашифровывания и расшифровывания, используются ключи k и k′ соответственно (в симметричной криптографии k=k′); обозначим функцию зашифровывания E_k, расшифрования – D_k’ . Тогда выполняются E_k(x)=y, соотношения D_k’(y)=x. Известны четыре основных типа криптоаналитических атак. В каждом случае предполагается (согласно фундаментальному допущению Кирхгоффа), что криптоаналитик знает используемый алгоритм шифрования:

• Атака на основе только шифротекста. Криптоаналитик располагает шифротекстами y₁,…,y_m, полученными из неизвестных открытых текстов x₁,…,x_m различных сообщений. Требуется найти хотя бы один из x_i , 1≤i≤m (или соответствующий ключ k_i), исходя из достаточного числа m криптограмм, или убедиться в своей неспособности сделать это. В качестве частных случаев возможно совпадение ключей: k₁=…=k_m или совпадение открытых текстов: x₁=…=x_m.
• Атака на основе открытого текста. Криптоаналитик располагает парами (x₁,y₁),…,(x_m,y_m) открытых и соответствующим им зашифрованных текстов. Требуется определить ключ k_i для хотя бы одной из пар. В частном случае, когда k₁=…=k_m=k , требуется определить ключ k или, убедившись в своей неспособности сделать это, определить открытый текст x_m+1 еще одной криптограммы y_m+1, зашифрованной на том же ключе.
• Атака на основе подобранного открытого текста отличается от предыдущей лишь тем, что криптоаналитик имеет возможность выбора открытых текстов x₁,…,x_m. Цель атаки та же, что и предыдущей. Подобная атака возможна, например, в случае, когда криптоаналитик имеет доступ к шифратору передающей стороны.
• Атака на основе адаптивно подобранного открытого текста. Это частный случай вышеописанной атаки с использованием подобранного открытого текста. Криптоаналитик может не только выбирать используемых шифруемый текст, но также уточнять свой последующий выбор на основе полученных ранее результатов шифрования.

Атаки с использованием известного или  подобранного открытого текста встречаются  чаще, чем можно подумать. Необходимым требованием к хорошему криптоалгоритму является способность противостоять таким атакам. Это означает, что рассекречивание некоторой информации, передававшейся по каналу связи в зашифрованном виде, не должно приводить к рассекречиванию другой информации, зашифрованной на этом ключе. Кроме того, указанное требование учитывает особенности эксплуатации аппаратуры и допускает некоторые вольности со стороны оператора или лиц, имеющих доступ к формированию засекреченной информации. В среде криптоаналитиков нельзя назвать неслыханными факты добычи открытого текста шифрованного сообщения или подкупа лица, которое должно будет зашифровать избранное сообщение. Применяются и «косвенные» методы осуществления атаки на основе подобранного шифротекста. Злоумышленник может убедить обладателя секретного ключа переслать некое сообщение, но в зашифрованной форме. Например, использованный командованием военно-морского флота США во время Второй Мировой Войны перед битвой на Мидвее. Чтобы убедиться в правильности результатов работы по взлому японского военного шифра, криптоаналитики США попросили американский гарнизон, дислоцированный на Мидвее, сообщить по открытому незащищенному каналу о нехватке пресной воды. Спустя два дня было перехвачено секретное сообщение, в котором японцы, осуществлявшие мониторинг использованного канала, сообщали о проблемах с водой в некоем «AF». Благодаря этому американцы узнали, «AF» – кодовое обозначение Мидвея в шифрограммах противника. Атаки на основе подобранных текстов считаются наиболее опасными.

Указанные криптоатаки относятся к классу пассивных. Так классифицируются действия противника, который «пассивно изучает» шифрованные сообщения, может их перехватить и подвергнуть криптоанализу с целью получения информации об открытом тексте или ключе. Однако современные технические средства позволяют потенциальному противнику «активно» вмешиваться в процесс передачи сообщения. Обычно различают два типа активных атак, которые носят названия имитации и подмены сообщения. Атака имитации состоит в том, что противник «вставляет» в канал связи сфабрикованное им «шифрованное сообщение», которое на самом деле не передавалось от законного отправителя к получателю. При этом противник рассчитывает на то, что получатель воспримет это сообщение как подлинное (аутентичное). Атака подмены состоит в том, что противник, наблюдая передаваемое по каналу связи подлинное сообщение от отправителя, «изымает» его и заменяет поддельным. Различные шифры могут быть более или менее уязвимыми к активным атакам. Способность самого шифра (без использования дополнительных средств) противостоять активным атакам обычно называют имитостойкостью шифра. Количественной мерой имитостойкости шифра служат вероятности успеха имитации и подмены соответственно. Эти вероятности определяют шансы противника на успех при навязывании получателю ложного сообщения.

Атаки можно также классифицировать по объему ресурсов, необходимых для  их осуществления:

• Память – объем памяти, требуемый для реализации атаки;
• Время – количество элементарных операций, которые необходимо выполнить;
• Данные – необходимый объём открытых и соответствующим им зашифрованных текстов. В некоторых случаях эти параметры являются взаимозависимыми: например, за счет увеличения памяти можно сократить время атаки.

Способность криптосистемы противостоять атакам криптоаналитика называется стойкостью. Количественно стойкость измеряется как сложность наилучшего алгоритма, приводящего криптоаналитика к успеху с приемлемой вероятностью. Универсальный метод прямого перебора множества всех возможных ключей позволяет получить оценку сверху для стойкости алгоритма шифрования. Проблема всей современной криптографии – это отсутствие нижней границы стойкости; длина ключа задаёт лишь общий объём пространства ключей, но всегда есть вероятность, ткнув пальцем в небо, угадать решение. Относительное ожидаемое безопасное время определяется как полупроизведение числа открытых ключей и времени, необходимого криптоаналитику для того, чтобы испытывать каждый ключ. В зависимости от целей и возможностей криптоаналитика меняется и стойкость. Различают стойкость ключа (сложность раскрытия ключа наилучшим известным алгоритмом), стойкость бесключевого чтения, имитостойкость (сложность навязывания ложной информации наилучшим известным алгоритмом) и вероятность навязывания ложной информации. Аналогично можно различать стойкость собственно криптоалгоритма, стойкость протокола, стойкость алгоритма генерации и распространения ключей.