Силовые атаки К этому классу относятся атаки, осуществляющие полный перебор всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Этот класс атак применим ко всем видам систем поточного шифрования. При разработке систем шифрования разработчики стремятся сделать так, чтобы этот вид атак был наиболее эффективным по сравнению с другими существующими методами взлома.
Статистические атаки Статистические атаки делятся на два подкласса:
метод криптоанализа статистических свойств шифрующей гаммы: направлен на изучение выходной последовательности криптосистемы; криптоаналитик пытается установить значение следующего бита последовательности с вероятностью выше вероятности случайного выбора с помощью различных статистических тестов.
метод криптоанализа сложности последовательности: криптоаналитик пытается найти способ генерировать последовательность, аналогичную гамме, но более просто реализуемым способом.
Оба метода используют принцип линейной сложности.
Аналитические атаки Этот вид атак рассматривается в предположении, что криптоаналитику известны описание генератора, открытый и соответствующий закрытый тексты. Задача криптоаналитика определить использованный ключ. Виды аналитических атак, применяемые к синхронным поточным шифрам:
корреляционные
компромисс “время-память”
инверсионная
“предполагай и определяй”
на ключевую загрузку и реинициализацию
XSL-атака
Корреляционные атаки Являются наиболее распространёнными атаками для взлома поточных шифров.
Известно, что работа по вскрытию криптосистемы может быть значительно сокращена, если нелинейная функция пропускает на выход информацию о внутренних компонентах генератора. Поэтому для восстановления начального заполнения регистров корреляционные атаки исследуют корреляцию выходной последовательности шифросистемы с выходной последовательностью регистров.
Существуют следующие подклассы корреляционных атак:
Атаки, основанные на восстановлении линейных полиномов
Быстрые корреляционные атаки.
Базовые корреляционные атаки
Схема базовой корреляционной атаки
Рассмотрим на примере базовой корреляционной атаки Зигенталера, которая основана на понятии расстояния Хэмминга между двумя двоичными последовательностями одинаковой длины. Применима к комбинирующим генераторам.
Для выявления влияния j-го линейного регистра сдвига. Алгоритм атаки состоит из двух этапов:
вычисления корреляционной вероятности исходя из комбинирующей функции и второго этапа.
перебор начальных заполнений регистра. На этом этапе определяется наличие корреляции данного фрагмента гаммы с соответствующим фрагментом из , путём вычисления функции кросс-корреляции и сравнения этого значения с некоторым числом .
В случае успеха при сравнении, фаза называется верной и происходит переход к следующему регистру . Иначе, фаза называется неверной и переходят к . Выходными значениями этого алгоритма являются состояния , вносящие информацию в гамму.
Теперь немного о подборе порогового значения и необходимого для успешного криптоанализа количество бит гаммы : Задаём нужные нам вероятности «ложной тревоги» и пропуска истинного начального заполнения .
Например, выбрали , где - длина регистра. А затем из этих условий находим и .
Атаки, основанные на низко-весовых проверках четности
Примером этого покласса атак может служить быстрая корреляционная атака Майера и Штаффельбаха. Применима она как к фильтр-генераторам, так и комбинирующим генераторам и является базовой для всех остальных быстрых корреляционных атак данного типа. Идея атаки основывается на использовании уравнений проверки четности для полинома обратной связи линейного регистра.
Быстрые корреляционные атаки
Под быстрыми корреляционными атаками подразумеваются атаки, вычислительная сложность которых значительно меньше вычислительной сложности силовых атак.
Этот вид атак сводит проблему декодирования в двоичном симметричном канале к проблеме криптоанализа и моделируется как декодирование случайного линейного кода. Аналогично базовым корреляционным атакам, этот подкласс использует понятие расстояния Хэмминга.
