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

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

Лучший  способ генерации множества случайных  битов – извлечение их из естественно  случайных событий реального  мира. Часто такой метод требует  наличия специальной аппаратуры, но можно реализовать его и  на компьютерах. Дж. Б. Эгнью предложил генератор случайных битов, который можно встроить в СБИС. Это конденсатор металл-изолятор-полупроводник. Два таких конденсатора помещаются рядом друг с другом, а случайный бит определяется разностью зарядов этих конденсаторов. Другой генератор случайных битов генерирует поток случайных битов, используя нестабильность частоты свободно колеблющегося осциллятора. Коммерческая микросхема фирмы AT&T генерирует случайные числа, опираясь именно на это явление, а генератор М. Гьюда собирает случайные числа из физических явлений (например, радиоактивного распада). В качестве случайных величин можно также рассматривать интервалы между нажатиями клавиш клавиатуры. Главный недостаток подобных систем – возможные закономерности в генерируемой последовательности. Используемые физические процессы могут быть случайны, однако использование измерительных инструментов может привести к появлению проблем: смещения, отклонения или корреляции между битами. Обойти эти недостатки можно, используя не один, а несколько случайных источников. В качестве случайных событий Брюс Шнайер предлагает рассматривать, например:

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

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

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

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

В таблице 1 приведены частоты появления  русских букв.

Таблица 1.

Частота появления пробела или знака  препинания в русском языке составляет 17,4%. Кроме того, порядок букв в словах и фразах естественного языка подчиняется определенным статистическим закономерностям. Частотный анализ также учитывает частоту появления различных буквосочетаний: например, пара стоящих рядом букв «ся» в русском языке более вероятна, чем «цы», а «оь» не встречается никогда. Для большинства естественных языков такая статистика документирована.

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

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

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

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

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

Блочный шифр представляет собой отображение  векторных пространств над полем  из двух элементов вида , где ключ , а блоки открытого и зашифрованного текста . Идея, лежащая в основе большинства итерационных блочных шифров, состоит в построении криптографически стойкой системы путем последовательного применения относительно простых криптографических преобразований. Принцип многоразового шифрования с помощью простых криптографических преобразований был впервые предложен Шенноном: он использовал с этой целью преобразования перестановки и подстановки. Первое из этих преобразований переставляет отдельные символы преобразуемого информационного блока, а второе – заменяет каждый символ (или группу символов) из преобразуемого информационного блока другим символом из того же алфавита (соответственно группой символов того же размера и из того же алфавита). Узлы, реализующие эти преобразования, называются, соответственно, P-блоками (P-box, permutation box) и S-блоками (S-box, substitution box).

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

1. Статистический  метод

Задачей статистического метода криптоанализа является разработка алгоритмов определения неизвестного ключа (или части ключа) . Рассмотрим базовые принципы и понятия статистического метода для блочных шифров. Реализации статистического метода криптоанализа для ряда блочных шифров позволяют получать оценки эффективности алгоритмов определения секретного ключа лучше, чем оценки метода полного перебора ключей. Входом алгоритма является некоторое число пар (), 1≤i≤N открытого и шифрованного текста, полученных в результате применения отображения F с ключом k. Такие пары будем называть материалом и обозначим буквой M. Объем материала соответствует числу пар ():|M|=N. Предполагается, что открытые тексты X_i, 1≤i≤N выбраны случайно, равновероятно и независимо из всего пространства .

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

Доступными  случайными наблюдениями в нашем  случае является материал M , а неизвестным параметром - часть ключа или некоторые линейные комбинации битов ключа. Обозначим множество, в котором принимает значения неизвестный параметр, через Г, |Г| = s ≤ 2ⁿ.

Каждая  ПСК определяет разбиение всего  пространства наблюдений на T>1, непересекающихся областей: , при i≠j, 1≤i,j≤T. Области M_i , 1≤i≤T, называют областями принятия решений, причем для заданного наблюдения m∈M сложность алгоритма определения номера i(m), такого, что m∈M_i(m), считается малой. Для каждой области M_i ПСК также определяет упорядоченный список объема s′, 1≤s′≤s элементов множества Г: γ_i,1,γ_i,2,…,γ_i,s′, при этом γ_{i, j1} ≠ γ_{i, j2} при j₁ ≠ j₂.

Для определения неизвестного параметра  из Г выполняются следующие действия. Сначала по полученному наблюдению m∈M нужно определить номер области принятия решений i(m). Затем последовательно перебирают параметры из Г: γ_i(m),1,γ_i(m),2 ,…,γ_i(m),s′ и проверяют, является ли значение j −го параметра, 1≤j≤s′ искомым или нет. Алгоритм проверки включает два этапа:

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

В этом случае Г = . Как правило, для доопределения оставшейся части ключа используется полный перебор все оставшихся неизвестными битов ключа. Если параметром является часть ключа или невырожденная линейная комбинация битов ключа Г = , 1≤ n*≤ n , потребуется перебрать 2^n−n* вариантов.

Проверка  того, правильно ли доопределен весь ключ, осуществляется следующим образом: для пар ()∈M, ∈, 1≤i≤N открытого и шифрованного текста из доступного материала M проверяют, выполнены или нет равенства: F(X_i,k*)=Y, где∈опробуемый вариант всего ключа. Ложный ключ, как правило, отсеивается уже на первых шагах проверки. На самом деле проверку достаточно осуществить для d первых пар открытого и зашифрованного текста, где число d таково, что для любого набора из d различных открытых текстов X_i, 1≤i≤d и для любых двух различных ключей k₁≠k₂∈ найдется такой номер j∈{1,…,d}, что F(X_i,k₁)≠F(X_i,k₂) (минимальное d₀ , удовлетворяющее этому условию, называют расстоянием единственности шифра F).

Алгоритмы определения ключа сравнивают по трем параметрам: N – объем используемого материала, Q₀ - средняя трудоемкость работы алгоритма и π₀ - надежность алгоритма. Q₀ и π₀ зависят от того, какие открытые тексты были случайно выбраны, и от искомого ключа. Трудоемкость соответствует математическому ожиданию числа шагов алгоритма при случайном выборе открытых текстов и случайном, равновероятном и независимом от выбора открытых текстов выборе ключа. Надежность алгоритма равна математическому ожиданию вероятности того, что процедура выдаст правильный результат в предположении, что ключ выбран в пространстве случайно, равновероятно и независимо от выбора открытых текстов. Между параметрами Q₀ и π₀ существует прямая зависимость: чем выше надежность, тем больше трудоемкость, и наоборот.

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

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