Реферат: Анализ криптостойкости методов защиты информации в операционных системах Microsoft Window 9x

Для генерации случайного байта гаммы выполняются следующие операции:

i = (i+1) mod 256

j = (j+S_i) mod 256

swap (S_i, S_j)

t = (S_i+S_j) mod 256

K = S_t

Байт K складывается операцией XOR с открытым текстом для выработки шифротекста, либо с шифротекстом для получения байта открытого текста. Шифрование происходит весьма быстро - примерно в 10 раз быстрее DES-алгоритма. Инициализация S-бокса столь же проста. На первом шаге он заполняется линейно:

S₀ = 0, S₁ = 1, . . ., S₂₅₅ = 255.

Затем еще один 256-байтный массив полностью заполняется ключом, для чего ключ повторяется соответствующее число раз в зависимости от длины: K₀, K₁, . . ., K₂₅₅. Индекс j обнуляется. Затем:

for i=0 to 255

j = (j+S_i+K_i) mod 256

swap (S_i , S_j)

Схема показывает, что RC4 может принимать примерно 2¹⁷⁰⁰ (256! * 256²) возможных состояний. S-бох медленно изменяется в процессе работы: параметр i обеспечивает изменение каждого элемента, а j отвечает за то, чтобы эти элементы изменялись случайным образом. Фактически, RC4 представляет собой семейство алгоритмов, задаваемых параметром n, который является положительным целым с рекомендованным типичным значением n = 8.

Внутреннее состояние генератора RC4 в момент времени t состоит из таблицы S_t =(S_t(L))_t=0^{n2 -1}, содержащей 2ⁿ n-битных слов и из двух n-битных слов-указателей i_t и j_t. Таким образом, размер внутренней памяти составляет M = n2ⁿ + 2n бит. Пусть выходное n-битное слово генератора в момент t обозначается как Z_t.

Пусть начальные значения i₀ = j₀ = 0. Тогда функция следующего состояния и функция выхода RC4 для каждого t ≥ 1 задается следующими соотношениями:

i_t = i_t-1 + 1

j_t = j_t-1 + S_t-1(i_t)

S_t(i_t) = S_t-1(j_t)

S_t(j_t) = S_t-1(i_t)

Z_t = S_t(S_t(i_t) + S_t(j_t)),

где все сложения выполняются по модулю 2ⁿ. Подразумевается, что все слова, кроме подвергаемых перестановке, остаются теми же самыми. Выходная последовательность n-битных слов обозначается как Z_t =(Z_t )_t=1^ .Начальная таблица S₀ задается в терминах ключевой последовательности

K = (K_L)_t=0^{2n -1}

с использованием той же самой функции следующего состояния, начиная от таблицы единичной подстановки (L)²ⁿ _L=0^{2n -1}. Более строго, пусть j₀ = 0 и для каждого 1 ≤ t ≤ 2ⁿ вычисляется j_t = (j_t - 1 + S_t-1(t-1) + K_t-1) mod 2 n, а затем переставляются местами S_t-1(t-1) и S_t-1(j_t).

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

До последнего времени в открытой литературе практически не было публикаций по криптоанализу алгоритма RC4. Компания RSA Data Security объявила, что шифр обладает иммунитетом к методам линейного и дифференциального криптоанализа, высоко не линеен и не похоже, чтобы у него были короткие циклы. Обычно цитируется заключение закрытой работы криптографа RSA Labs Мэтта Робшоу: "Не имеется известных слабых ключей и, хотя нет доказательства для нижней границы периодов последовательностей RC4, проведенный теоретический анализ показывает, что период в подавляющем большинстве случаев превышает 10¹⁰⁰. Тщательный и всеобъемлющий анализ стойкости RC4 не выявил никаких оснований подвергать сомнению стойкость, обеспечиваемую генератором RC4".

Первой открытой публикацией можно считать работу Йована Голича, представленную на конференции Eurocrypt '96. В ней отмечается, что для последовательностей, генерируемых RC4, не подходят методы статистического анализа. Но, с другой стороны, как показано в работах, для блоков, размер которых превышает M (размер внутренней памяти генератора), всегда существует линейная статистическая слабость или так называемая "линейная модель". Такую модель можно эффективно определять с помощью метода аппроксимации линейной последовательной схемой. Линейная статистическая слабость - это линейное соотношение между битами гаммы, которое выполняется с вероятностью, отличающейся от 1/2.

Главная цель работы Голича - с помощью метода АЛПС вывести линейные модели для RC4. Метод АЛПС заключается в нахождении и решении последовательной линейной схемы, которая аппроксимирует генератор гаммы и приводит к линейным моделям с относительно большим корреляционным коэффициентом c, где вероятность соответствующего линейного соотношения между битами гаммы составляет (1+ c)/2. При анализе использовалась техника двоичных производных. Пусть Z = (Z_t)_t=1^ обозначает последовательность самых младших бит слов выхода RC4, и пусть Z^/=( Z^/_t = Z_t+ Z_t+1) _t=1^ и Z^//=( Z^//_t = Z_t+ Z_t+2) _t=1^ обозначают ее первую и вторую двоичные производные, соответственно. Показано, что Z^/ не коррелирует ни с 1, ни с 0, но Z^// коррелирует с 1 с корреляционным коэффициентом, близким к 15*2^-3n при больших 2n, где n – длина ключа. Поскольку длина выходной последовательности, требуемая для выявления статистической слабости с корреляционным коэффициентом c, составляет O(c^-2), то эта длина равна примерно 64ⁿ /225. Например, если n = 8, как рекомендуется в большинстве приложений, то требуемая длина близка к 2⁴⁰.

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

В 1997 году опубликована большая работа Йована Голича, посвященная криптоанализу обобщенной схемы комбинирующего узла с произвольным размером памяти. Исследованы корреляционные свойства таких узлов, обоснованы новые конструктивные критерии, предъявляемые к схемам подобного типа. Разработан эффективный метод аппроксимации линейной последовательной схемой для построения линейных функций от входа и выхода со сравнительно большим коэффициентом взаимной корреляции. Это практичная процедура, позволяющая с высокой вероятностью находить пары взаимно коррелированных линейных функций (от самое большее M + 1 последовательных выходных бит и самое большее M + 1 последовательных векторов входа) со сравнительно большими коэффициентами корреляции. Метод АЛПС состоит в задании и решении линейной последовательной схемы (ЛПС), которая аппроксимирует комбинирующий узел с памятью. Эта ЛПС имеет добавочные несбалансированные входы и основана на линейных аппроксимациях функции выхода и всех компонент функции следующего состояния. Линейная аппроксимация булевой функции - это любая линейная функция, с которой заданная булева функция скоррелирована. Описанный метод применим к произвольным комбинирующим узлам с памятью без ограничений на функции выхода и следующего состояния.