Лекция 4. Методы криптоанализа

Лекция 4. Методы криптоанализа

Цель лекции

·  рассмотреть возможные исходы криптоанализа;

·  изучить методы криптоанализа и их влияние на развитие криптографии;

·  оценить предельные возможности по взлому шифров методом полного перебора ключей;

·  проанализировать применимость различных типов криптоатак к симметричным и асимметричным криптосистемам и хеш-функциям;

·  ознакомиться с перспективными технологиями криптоанализа.

Понятие криптоанализа

Криптоанализом (от греческого krypts – «скрытый» и analein – «ослаблять» или «избавлять») называют науку восстановления (дешифрования) открытого текста без доступа к ключу. Хотя история криптоанализа насчитывает многие века, особенно интенсивно эта область знаний начала развиваться с наступлением компьютерной эры. Какие методы криптоанализа считаются наиболее эффективными сегодня, и что нас ждет в будущем? Существует ли предельно стойкий шифр, взлом которого является непосильной задачей при любом уровне развития криптоанализа и средств вычислительной техники? В чем отличие научного и практического криптоанализа? На эти и другие вопросы мы постараемся ответить в этой лекции.

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

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

·  полный взлом - криптоаналитик извлекает секретный ключ;

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

·  частичная дедукция - криптоаналитику удается расшифровать или зашифровать некоторые сообщения;

·  информационная дедукция - криптоаналитик получает некоторую информацию об открытом тексте или ключе.

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

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

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

На рис. 5 методы криптоанализа систематизированы по хронологии их появления и применимости для взлома различных категорий криптосистем. Горизонтальная ось разделена на временные промежутки: в область «вчера» попали атаки, которые успешно применялись для взлома шифров в прошлом; «сегодня» – методы криптоанализа, представляющие угрозу для широко используемых в настоящее время криптосистем; «завтра» - эффективно применяемые уже сегодня методы, значение которых в будущем может возрасти, а также методы, которые пока не оказали серьезного влияния на криптологию, однако со временем могут привести прорывам во взломе шифров. На вертикальной оси обозначены области применения методов криптоанализа: для взлома криптосистем с секретным ключом, открытым ключом или хеш-функций.

Рисунок 5 - Методы криптоанализа

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

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

На протяжении веков дешифрованию криптограмм помогает частотный анализ появления отдельных символов и их сочетаний. Идея этого метода хорошо известна любителям детективов по рассказу А. Конан Дойля «Пляшущие человечки». Вероятности появления отдельных букв, а также их порядок в словах и фразах естественного языка подчиняются задокументированным статистическим закономерностям: например, пара стоящих рядом букв «ся» в русском языке более вероятна, чем «цы», а «оь» не встречается никогда. Анализируя достаточно длинный текст, зашифрованный методом замены, можно по частотам появления символов произвести обратную замену и восстановить исходный текст.

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

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

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

При осуществлении попытки атаки на основе только шифртекста криптоаналитику требуется анализировать выходные данные алгоритма и проверять их «осмысленность». В случае, когда в качестве объекта шифрования выступает графический файл или программа, задача определения «осмысленности» выходных данных становится очень трудной. Если известно, что открытый текст представляет собой предложение на естественном языке, проанализировать результат и опознать успешный исход дешифрования сравнительно несложно, тем более что криптоаналитик зачастую располагает некоторой априорной информацией о содержании сообщения. Задачу выделения осмысленного текста, т.е. определения факта правильной дешифрации, решают при помощи ЭВМ с использованием теоретических положений, разработанных в конце XIX века петербургским математиком Марковым А.А., - цепей Маркова.

Атаки с использованием известного или подобранного открытого текста встречаются чаще, чем можно подумать. В среде криптоаналитиков нельзя назвать неслыханными факты добычи открытого текста шифрованного сообщения или подкупа лица, которое должно будет зашифровать избранное сообщение. Предположим, злоумышленнику известна одна или несколько пар . Пусть для простоты для любой пары  существует единственный ключ , удовлетворяющий соотношению . Примем проверку одного варианта ключа k \in K за одну операцию. Тогда полный перебор ключей потребует  операций, где  - число элементов в множестве. Если в качестве оценки трудоемкости метода взять математическое ожидание случайной величины, соответствующей числу опробований до момента обнаружения использованного ключа, то мы получим  операций. Кроме того, алгоритм полного перебора допускает распараллеливание, что позволяет значительно ускорить нахождение ключа.

Оценка предельных мощностей взлома

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

Два фундаментальных ограничения:

1.          Предел, основанный на выделяемой Солнцем энергии. Все вычисления потребляют энергию. Согласно принципам классической термодинамики и статистической механики, потребление энергии при осуществлении необратимого преобразования (вычисления) имеет порядок , где  - температура окружающей среды (по абсолютной шкале Кельвина), а  - постоянная Больцмана (равная ). Мощность излучения Солнца составляет приблизительно ; таким образом, за весь свой предполагаемый период существования - 10 млрд. лет, или  секунд - Солнце выделит около  Дж). Предположим, температура окружающей среды  градусов, тогда энергозатраты на одну операцию составляют . Значит, количество вычислительных операций, которые можно осуществить с использованием всей выделяемой солнцем энергии, равно выделяемой мощности, поделенной на количество энергии, необходимой для осуществления одной операции, т.е. всего  операций. Такое количество операций потребовалось бы на взлом ключа из 73 десятичных цифр (или около 250 бит) методом прямого перебора при грубом предположении, что для проверки одного значения ключа необходима всего одна операция (на самом деле - сотни операций). Для справки, количество атомов солнечной системы – около .

2.          Предел, основанный на массе Земли. Масса Земли составляет порядка  кг. Масса протона - , т.е. Земля содержит приблизительно  протонов. Сопоставим каждому протону отдельный компьютер и примем за скорость выполнения операции на таком компьютере время, за которое луч света проходит расстояние, равное диаметру этого протона (). Таким образом, каждый компьютер может выполнять  операций в секунду. Если все эти компьютеры будут работать параллельно, их суммарное быстродействие составит  операций в секунду, т.е. . Возраст Вселенной приблизительно 10 млрд. лет, т.е.  секунд. За весь период существования Вселенной такие гипотетические компьютеры размером с протон смогли бы выполнить  операций. При описанных в п. 1 предположений относительно количества операций, необходимых на проверку значения ключа, такое количество операций позволит взломать ключ длиной 95 десятичных цифр, или 320 бит.

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

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

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

Генераторы случайных чисел - еще один источник угрозы для стойкости криптосистемы. Если для генерации ключей используется криптографический слабый алгоритм, независимо от используемого шифра вся система будет нестойкой. Качественный ключ, предназначенный для использования в рамках симметричной криптосистемы, представляет собой случайный двоичный набор. Если требуется ключ разрядностью , в процессе его генерации с одинаковой вероятностью должен получаться любой из  возможных вариантов. Исследования компании Counterpane, президентом которой является известный криптограф Брюс Шнайер, показали, что определённые генераторы случайных чисел могут быть надёжными при использовании с одной целью, но ненадёжными для другой; обобщение анализа надёжности опасно.

Метод «встречи посередине»

Известно, что если считать, что дни рождения распределены равномерно, то в группе из 23 человек с вероятностью 0,5 у двух человек дни рождения совпадут. В общем виде парадокс дней рождения формулируется так: если  предметов выбираются с возвращением из некоторой совокупности размером , то вероятность того, что два из них совпадут, равна  (в описанном частном случае  - количество дней в году, , т.е. ).

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

Алгоритм является вероятностным. Существуют детерминированный аналог этого алгоритма «giant step – baby step» с такой же сложностью, предложенный американским математиком Д. Шенксом.

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

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

Метод разностного анализа сочетает в себе обобщение идеи общей линейной структуры с применением вероятностно-статистических методов исследования. Этот метод относится к атакам по выбранному открытому тексту. Хотя Д. Копперсмит утверждает, что разностный криптоанализ был известен команде разработчиков DES алгоритма еще в начале 70-х годов, официальной датой появления этого метода считается 1990 г., а первенство в разработке признано за израильскими математиками Э. Бихамом и А. Шамиром. Разностный анализ основан на использовании неравновероятности в распределении значений разности двух шифртекстов, полученных из пары открытых текстов, имеющих некоторую фиксированную разность. Отметим, что разностный анализ применим и для взлома хеш-функций.

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

На сегодняшний день метод линейного криптоанализа позволил получить наиболее сильные результаты по раскрытию ряда итерационных систем блочного шифрования, в том числе и системы DES. Метод линейного криптоанализа в неявном виде появился еще в работе С. Мёрфи в 1990 г., где он успешно применялся при анализе системы блочного шифрования FEAL. В 1992 г. М. Мацуи формализовал этот подход, а позже успешно применил его к анализу криптоалгоритма DES. В 2001 г. в США на смену DES и Triple DES пришел новые стандарт AES, действующий и по сей день.

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

Практически все используемые алгоритмы асимметричной криптографии основаны на задачах факторизации (например, известная криптосистема RSA) и дискретного логарифмирования в различных алгебраических структурах (схема электронно-цифровой подписи Эль-Гамаля). Несмотря на то, что принадлежность этих задач к классу NP-полных задач не доказана, на сегодняшний день не найден полиномиальный алгоритм их решения. Для криптоанализа асимметричных криптосистем можно применять универсальные методы - например, метод «встречи посередине». Другой подход заключается в решении математической задачи, положенной в основу асимметричного шифра. С того момента, как У. Диффи и М. Хеллман в 1976 г. предложили концепцию криптографии с открытым ключом, проблемы факторизации целых чисел и дискретного логарифмирования стали объектом пристального изучения математиков всего мира. За последние годы в этой области наблюдался значительный прогресс. Подтверждением тому может служить следующий казус: в 1977 г. Р. Ривест заявил, что разложение на множители 125-разрядного числа потребует 40 квадриллионов лет, однако уже в 1994 г. было факторизовано число, состоящее из 129 двоичных разрядов!

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

Последние достижения теории вычислительной сложности показали, что общая проблема логарифмирования в конечных полях уже не является достаточно прочным фундаментом. Наиболее эффективные на сегодняшний день алгоритмы дискретного логарифмирования имеют уже не экспоненциальную, а субэкспоненциальную временную сложность. Это алгоритмы «index-calculus», использующие факторную базу. Первый такой алгоритм для вычисления дискретного логарифма в простом поле  был предложен Л. Адлеманом. На практике алгоритм Адлемана оказался недостаточно эффективным; Д. Копперсмит, А. Одлыжко и Р. Шреппель предложили свою версию субэкспоненциального алгоритма дискретного логарифмирования – «COS». Алгоритм решета числового поля, предложенный О. Широкауэром, при  работает эффективнее различных модификаций метода COS.

Ряд успешных атак на системы, основанные на сложности дискретного логарифмирования в конечных полях, привел к тому, что стандарты ЭЦП России и США, которые были приняты в 1994 г. и базировались на схеме Эль-Гамаля, в 2001 году были обновлены: переведены на эллиптические кривые. Схемы ЭЦП при этом остались прежними, но в качестве чисел, которыми они оперируют, теперь используются не элементы конечного поля  или , а эллиптические числа - решения уравнения эллиптических кривых над указанными конечными полями. Алгоритмов, выполняющих дискретной логарифмирование на эллиптических кривых в общем случае хотя бы с субэкспоненциальной сложностью, на сегодняшний день не существует, хотя работы в этом направлении ведутся. Так, для эллиптических кривых специального вида наш соотечественник И. Семаев указал способ сведения задачи логарифмирования в группе точек эллиптической кривой к задаче логарифмирования в некотором расширении простого поля.

Криптоанализ хеш-функций

Основная атака на хеш - это метод коллизий. Пусть  и  - сообщения,  - хеш-функция, а ЭЦП представляет собой некоторую функцию  от хеша сообщения: . Законный обладатель пары «открытый ключ – секретный ключ» готов подписать сообщение , но злоумышленник заинтересован в получении подписи под сообщением . Если  выбрано так, что , то злоумышленник может предъявить пару : тогда атака удалась. Реализовать подбор такого сообщения можно методом, который основан на упомянутом выше «парадоксе дней рождения». Варьируя интервалы, шрифты, формат и т.п., злоумышленник получает  пар вариантов  и  без изменения их смысла. Сообщения  отличаются слабо, а их хеш-функции - значительно, т.е. можно считать, что значения хеш-функций выбираются случайно, равновероятно и независимо друг от друга. Тогда при  ( - некоторая константа,  - мощность множества всевозможных хеш-функций) вероятность того, что имеется пара сообщений  и , для которых , вычисляется по формуле .

Этот метод криптоанализа породил требования устойчивости к коллизиям для хеш-функций.

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

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

В последние годы количество криптографических атак, использующих слабости в реализации и размещении механизмов криптоалгоритма, резко возросло. Противник может замерять время, затрачиваемое на выполнение криптографической операции, или анализировать поведение криптографического устройства при возникновении определённых ошибок вычисления. Другой подход предполагает отслеживание энергии, потребляемой смарт-картой в процессе выполнения операций с секретным ключом (например, расшифрования или генерации подписи). Побочную информацию собрать порой несложно - на сегодняшний день выделено более десяти побочных каналов, в т.ч. электромагнитное излучение, ошибки в канале связи, кэш-память и световое излучение. Более подробное описание перечисленных типов атак можно найти в материалах доклада А.Е.Жукова на конференции РусКрипто2006, использованных при подготовке данного раздела.

Нанотехнологии в криптоанализе

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

Важно отметить, что алгоритм Шора чрезвычайно прост и довольствуется гораздо более скромным аппаратным обеспечением, чем то, которое понадобилось бы для универсального квантового компьютера. Поэтому вероятно, что квантовое устройство для разложения на множители будет построено задолго до того, как весь диапазон квантовых вычислений станет технологически осуществимым. На сегодняшний день есть конкретные результаты. Так, IBM продемонстрировала использование созданного в лабораториях компании семикубитового квантового компьютера для факторизации чисел по алгоритму Шора. Хотя решённая им задача вряд ли способна поразить воображение (компьютер верно определил, что делителями числа 15 являются числа 5 и 3), это самое сложное вычисление в области теории чисел за всю историю квантовых компьютеров.

Краткие итоги

В лекции рассмотрены основные исторические этапы и новые тенденции развития методов криптоанализа. Подчеркнута важная роль взаимодействия криптоанализа и криптографии в развитии науки криптологии.

Скачано с www.znanio.ru