Поточный шифр - Криптоанализ. Атаки на поточные шифры

Интернет магазин китайских планшетных компьютеров

Компьютеры - Поточный шифр - Криптоанализ. Атаки на поточные шифры

22 января 2011

Оглавление:
1. Поточный шифр
2. Режим гаммирования для поточных шифров
3. Классификация поточных шифров
4. Поточные шифры на регистрах сдвига с линейной обратной связью
5. Потоковые шифры основанные на РСЛОС. Усложнение
6. Основные отличия поточных шифров от блочных
7. Проектирование поточных шифров
8. Криптоанализ. Атаки на поточные шифры

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

Силовые атаки

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

Статистические атаки

Статистические атаки делятся на два подкласса:

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

Оба метода используют принцип линейной сложности.

Аналитические атаки

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

корреляционные
компромисс “время-память”
инверсионная
“предполагай и определяй”
на ключевую загрузку и реинициализацию
XSL-атака

Корреляционные атаки

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

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

Существуют следующие подклассы корреляционных атак:

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

Базовые корреляционные атаки

Схема базовой корреляционной атаки

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

Для выявления влияния j-го линейного регистра сдвига. Алгоритм атаки состоит из двух этапов:

вычисления корреляционной вероятности $~p_j = P}})$ исходя из комбинирующей функции $~f$ и второго этапа.
перебор начальных заполнений регистра. На этом этапе определяется наличие корреляции данного фрагмента гаммы $~g$ с соответствующим фрагментом из $~x_d^{}$ , путём вычисления функции кросс-корреляции $~C_{{x^{j},{g}}}=\frac{1}{n}*\sum_{i=1}^n^{g_i}*^{x_{i+d}^{}}$ и сравнения этого значения с некоторым числом $~T$ .

В случае успеха при сравнении, фаза называется верной и происходит переход к следующему регистру $~j+1$ . Иначе, фаза называется неверной и переходят к $~d=d+1, d=1,2,\dots,2^{L_j}$ . Выходными значениями этого алгоритма являются состояния $~{x_0^j}$ , вносящие информацию в гамму.

Теперь немного о подборе порогового значения $~T$ и необходимого для успешного криптоанализа количество бит гаммы $~n$ : Задаём нужные нам вероятности «ложной тревоги» $~P_f=P \ge T|WrongPhase)$ и пропуска истинного начального заполнения $~P_m=P < T|RightPhase)$ .

Например, выбрали $~P_m=0.01, P_f=2^{-L}$ , где $~L$ - длина регистра. А затем из этих условий находим $~T$ и $~n$ .

Атаки, основанные на низко-весовых проверках четности

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

Быстрые корреляционные атаки

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

Компромисс «время-память»

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

Состоит из двух этапов:

построение большого словаря, в котором записаны всевозможные пары «состояние-выход»;
предположение о начальном заполнении регистра сдвига, генерация выхода, просмотр перехваченной выходной последовательности и поиск соответствия со сгенерированным выходом. Если произошло совпадение, то данное предположительное заполнение с большой вероятностью является начальным.

Примерами этого класса атак являются атака Стива Беббиджа и атака Бирюкова-Шамира.

«Предполагай и определяй»

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

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

Сложность алгоритма зависит от устройства генератора и от количества предположений.

<<< Поросячья латынь

Простая литорея >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие