Сравнительный анализ криптографических систем

c_i =p_i ^ k_i

При дешифрировании операция XOR выполняется над битами шифротекста и тем же самым потоком ключей для восстановления битов открытого текста.

p_i = c_i ^ k_i

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

 

Рис. 2. Потоковый шифр.

 

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

Генератор потока ключей состоит из трех основных частей. Внутреннее состояние описывает текущее состояние генератора потока ключей. Два генератора потока ключей, с одинаковым ключом и одинаковым внутренним состоянием, выдают одинаковые потоки ключей. Функция выхода по внутреннему состоянию генерирует бит потока ключей. Функция следующего состояния по внутреннему состоянию генерирует новое внутреннее состояние.

Рис. 3. Устройство генератора потока ключей

 

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

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

Рис. 4. Самосинхронизирующийся генератор потока ключей

 

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

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

 

1.3 Алгоритм RC4 и его криптоанализ

Существенное повышение производительности микропроцессоров в 1980-е годы вызвало в криптографии усиление интереса к программным методам реализации криптоалгоритмов как возможной альтернативе аппаратным схемам на регистрах сдвига. Одним из самых первых подобных криптоалгоритмов, получившим широкое распространение, стал RC4. Алгоритм RC4 - это потоковый шифр с переменной длиной ключа, разработанный в 1987 году Рональдом Райвистом для компании RSA Data Security. Он обладает следующими свойствами:

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

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

* адаптивностью на процессоры различных длин слова.

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

* низким требованием к памяти, что позволяет реализовывать алгоритм на устройствах с ограниченной памятью;

* использованием циклических сдвигов, зависимых от данных, с "переменным" числом.

* простотой и легкостью выполнения.

В течение семи лет этот алгоритм был фирменным секретом и детали о его конструкции предоставлялись только после подписания договора о неразглашении, но в сентябре 1994 года кто-то анонимно распространил исходный код алгоритма через Internet. Пользователи Сети, имеющие легальные криптосредства фирмы RSA, реализующие RC4, подтвердили совместимость кода с криптопрограммой. В настоящее время алгоритм RC4 реализован в десятках коммерческих криптографических продуктов, включая Lotus Notes, Apple Computer's AOCE, Oracle Secure SQL, а также является частью спецификации стандарта сотовой связи CDPD.

Криптогенератор функционирует независимо от открытого текста. Генератор имеет подстановочную таблицу (S-бокс 8 х 8): S₀, S₁, . . ., S₂₅₅. Входами генератора являются замененные по подстановке числа от 0 до 255, и эта подстановка является функцией от ключа изменяемой длины. Генератор имеет два счетчика i и j, инициализируемых нулевым значением.

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

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 последовательных векторов входа) со сравнительно большими коэффициентами корреляции. Метод АЛПС состоит в задании и решении линейной последовательной схемы (ЛПС), которая аппроксимирует комбинирующий узел с памятью. Эта ЛПС имеет добавочные несбалансированные входы и основана на линейных аппроксимациях функции выхода и всех компонент функции следующего состояния. Линейная аппроксимация булевой функции - это любая линейная функция, с которой заданная булева функция скоррелирована. Описанный метод применим к произвольным комбинирующим узлам с памятью без ограничений на функции выхода и следующего состояния.

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

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

S_t+1 = AS_t + BX_t + D(X_t, S_t), t≥0,

y_t = CS_t + DX_t + e(X_t, S_t), t ≥0,

где векторы рассматриваются как матрицы-столбцы; A, B, C, D - двоичные матрицы; а e и каждый компонент в D = (d₁, . . . , d_M) - несбалансированные булевы функции, именуемые функциями шума. Основная идея состоит в том, чтобы рассматривать {e(X_t ,S_t)}_t=0^Ґ и {d(X_t ,S_t)}_t=0^Ґ , 1≤i≤M, в качестве входных последовательностей, так что последние уравнения оказываются задающими неавтономную линейную машину с конечным числом состояний или ЛПС, именуемую АЛПС комбинирующего узла с памятью. Тогда можно решать эту ЛПС с использованием техники производящих функций (D-преобразований). В частности, пусть S, X, D, e, y обозначают производящие функции от переменной z для последовательностей {S_t}, {X_t}, D(X_t, S_t)}, e (X_t, S_t)}, y_t}, соответст венно. Тогда уравнения сводятся к виду

Решение имеет вид

где I - единичная матрица, det(zA - I) = f(z), f(0) = 1, - многочлен, обратный к характеристическому многочлену матрицы переходов A степени, не превышающей ранг A (≤M); а элементы (присоединенной) матрицы adj(zA - I) - это полиномы от z степени не более M-1. Вычислительная сложность для отыскания такого решения составляет O(M³(N+1)). В другом виде решение можно переписать как

где x_i и d_j обозначают производящие функции для {x_it} и {d_j(X_t, S_t)}, а степени полиномов g_i(z) и h_j(z) самое большее равны M и M-1, 1≤i≤N, 1≤j≤M, соответственно. Полагая

решение можно преобразовать к виду: