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

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

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

Стойкость доказуемо стойких криптоалгоритмов определяется сложностью решения хорошо известной математической задачи, которую пытались решить многие математики и которая является общепризнанно сложной. В качестве примера можно привести системы DH (Диффи-Хеллмана) и RSA (Ривеста-Шамира-Адельмана), основанные на сложностях дискретного логарифмирования и разложения целого числа на множители соответственно. Достоинством доказуемо стойких алгоритмов является хорошая изученность задач, положенных в их основу, а недостатком - невозможность в случае необходимости оперативной доработки криптоалгоритмов, т.е. отсутствие гибкости. Повышение стойкости достигается увеличением размера математической задачи или ее заменой, что, как правило, влечет цепь изменений в аппаратуре, используемой для шифрования.

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

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

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

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

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

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

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

Предположим, злоумышленнику известна одна или несколько  пар (x, y). Пусть для простоты для любой пары (x, y) существует единственный ключ k, удовлетворяющий соотношению E_k(x)=y . Упорядочим множество возможных ключей (пространство ключей) и будем последовательно проверять ключи из K на выполнения равенства E_k(x)=y . Если считать проверку одного варианта ключа k ∈ K за одну операцию, то полный перебор ключей потребует |K| - число элементов в множестве. Пусть ключ в схеме шифрования выбирается случайно и равновероятно из множества K. Тогда с вероятностью ключ будет угадан и трудоемкость метода полного перебора будет равна 1. Поэтому естественно в качестве оценки трудоемкости метода взять математическое ожидание случайной величины α, где α - число опробований до момента обнаружения использованного ключа. Поскольку α – равномерно распределенная случайная величина, то .

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

Во-первых, построение конвейера. Пусть алгоритм соотношения E_k(x)=y представим в виде детерминированной цепочки простейших действий (операций): O₁,O₂,…,O_N.

Возьмем N процессоров A₁, A₂,…,A_N, зададим их порядок и положим, что i-ый процессор выполняет три одинаковые по времени операции:

1. прием данных от (i -1)-го процессора;
2. выполнение операции O_i;
3. передача данных следующему (i +1)-му процессору.

Тогда конвейер из N последовательно соединенных, параллельно и синхронно работающих процессоров работает со скоростью , где v -скорость выполнения одной операции процессором. Второе направление распараллеливания состоит в том, что множество K разбивается на непересекающиеся подмножества K₁,K₂,…,K_Q. Система из Q машин перебирает ключи так, что i-ая машина осуществляет перебор ключей из множества K_i, 1≤i≤Q . Система прекращает работу, если одна из машин нашла ключ. Самой большой сложностью в изложенном подходе является организация деления ключевого множества. Однако если организовать поиск ключа таким образом, что при каждом очередном опробовании каждый из N процессоров стартует со случайной точки, то время опробования увеличится, но схема значительно упростится. Как показано в работе, среднее число шагов опробования N процессорами (машинами) ключей из множества K в этом случае составляет .

Реализация  такого параллелизма предполагает различные  решения. Самое очевидное решение – создание компьютерного вируса для распространения программы-взломщика в глобальной сети. Вирус должен использовать периоды простоя компьютера (по данным исследований, компьютер простаивает 70-90% времени) для осуществления перебора по множеству ключей. Рано или поздно один из зараженных компьютеров обнаружит искомый ключ (необходимо предусмотреть механизм оповещения злоумышленника); с ростом производительности компьютеров и скорости распространения вирусов угроза успешного исхода такой атаки растет.

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

Тем не менее, возможно, что несколько  вариантов пройдут критерий на открытый текст. К. Шеннон привел следующий пример. Криптограмму WNAJW, полученную при использовании сдвигового шифра для шифрования текста на английском языке, порождают два открытых текста RIVER и ARENA, отвечающим ключам F (=5) и W (=22). При этом один из ключей является истинным, а другой – ложным. Для сдвигового шифра одинаковые криптограммы порождают и более длинные слова SULPHUR (сера) и PRIMERO (запал, учебник). Аналогичные примеры имеются и для русского языка: АГАТА – ОСОБО, КОНОПЛЕЮ – ОТСТУПИВ и т.д. Среднее число ложных ключей θ_L относительно всех возможных шифротекстов длины L определяется формулой 1:

       (1)

где V_L - множество криптограмм длины L, p(v) - вероятность появления криптограммы v, θ_L(v) - число ложных ключей, соответствующих данной криптограмме.

Противник заинтересован в получении некоторой  вероятностной информации об исходном тексте сообщения. Например, известный факт написания текста на английском языке предоставляет криптоаналитику некоторую априорную информацию об этом сообщении даже до анализа шифровки. В этом случае он заранее знает, что слово «HELLO» является более вероятным началом сообщения, чем набор букв «FGHKM». Поэтому одной из целей криптоанализа может являться увеличение информации, относящейся к каждому возможному сообщению. Предположим, противник перехватил шифровку «ABCCD» и знает (или предполагает), что использованный шифр – это шифр простой замены. Анализ шифровки позволяет сделать вывод, что исходное сообщение состоит из пяти букв, причем на третьей и четвертой позициях стоит одна и та же буква, а остальные отличны от нее и различны между собой. Противник не может считать, что это сообщение «HELLO», потому что имеются и другие возможные сообщения, например, «TEDDY». Однако апостериорные вероятности таких открытых текстов возрастают относительно их априорных вероятностей. В то же время апостериорная вероятность таких открытых текстов, как «PEACE» или «GATES», снижается до нуля вне зависимости от их априорных вероятностей. По Шеннону, криптосистема является совершенной, если после анализа закрытых текстов апостериорные вероятности возможных открытых текстов остаются такими же, какими были их априорные вероятности.

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

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

Генераторы  случайных чисел – ещё одно уязвимое место криптографических систем. Это означает, что, если для генерации ключей используется криптографический слабый алгоритм, независимо от используемого шифра вся система будет нестойкой. Качественный ключ, предназначенный для использования в рамках симметричной криптосистемы, представляет собой случайный двоичный набор. Если требуется ключ разрядностью n, в процессе его генерации с одинаковой вероятностью должен получаться любой из 2ⁿ возможных вариантов. Генерация ключей для асимметричных криптосистем – процедура более сложная, т.к. ключи, применяемые в таких системах, должны обладать определенными математическими свойствами. Например, в случае системы RSA модуль шифрования представляет собой произведение двух больших простых чисел.

Рассмотрим  понятие криптографически стойкого генератора псевдослучайных кодов, или, для краткости, псевдослучайного генератора, которое было введено Блюмом и Микали. Пусть g: {0, 1}ⁿ →{0, 1}^q(n) -функция, вычислимая за полиномиальное от n время, q(n) - некоторый полином. Такая функция называется генератором. Генератор g является псевдослучайным, если порождаемые им последовательности неотличимы никаким полиномиальным вероятностным алгоритмом от случайных последовательностей той же длины q(n). В 1989-1990 гг. Импальянцо, Левин, Луби и Хостад доказали, что псевдослучайные генераторы существуют тогда и только тогда, когда существуют односторонние функции.

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

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