Поточное шифрование

     Расшифровка заключается в регенерации этого  ключевого потока (ki) и сложении его  и шифрограммы (ci) по модулю два. В  силу свойств суммирования по модулю два на выходе мы получим исходный незашифрованный текст (mi):

     Другая  главная часть алгоритма —  функция инициализации, которая  использует ключ переменной длины для  создания начального состояния генератора ключевого потока.

     RC4 — фактически класс алгоритмов, определяемых размером его блока.  Этот параметр n является размером  слова для алгоритма. Обычно, n = 8, но в целях анализа можно  уменьшить его. Однако для повышения  безопасности необходимо увеличить  эту величину. Внутреннее состояние  RC4 представляется в виде массива  слов размером 2n и двух счетчиков,  каждый размером в одно слово.  Массив известен как S-бокс, и  далее будет обозначаться как  S. Он всегда содержит перестановку 2n возможных значений слова. Два  счетчика обозначены через i и  j.

     Алгоритм  инициализации RC4 приведен ниже. Этот алгоритм также называется алгоритмом ключевого  расписания ( Key-Scheduling Algorithm or KSA). Этот алгоритм использует ключ, сохраненный в Key, и имеющий длину l байт. Инициализация начинается с заполнения массива S, далее этот массив перемешивается путем перестановок определяемых ключом. Так как только одно действие выполняется над S, то должно выполняться утверждение, что S всегда содержит все значения кодового слова. 
 
 

     Начальное заполнение массива:

       for i = 0 to 2n − 1

         S[i] = i

     Скремблирование:

         j = 0

       for i = 0 to 2n − 1

         j = (j + S[i] + Key[i mod l]) mod 2n

     Перестановка (S[i], S[j]) 

     Генератор ключевого потока RC4 переставляет значения, хранящиеся в S, и каждый раз выбирает различное значение из S в качестве результата. В одном цикле RC4 определяется одно n-битное слово K из ключевого потока, которое в последующем суммируется  с исходным текстом для получения  зашифрованного текста. Эта часть  алгоритма называется генератором  псевдослучайной последовательности (Pseudo-Random Generation Algorithm or PRGA). 

     Инициализация:

       i = 0

       j = 0

     Цикл  генерации:

       i = (i + 1) mod 2n

       j = (j + S[i]) mod 2n

        Перестановка (S[i], S[j])

        Результат: K = S[(S[i] + S[j]) mod 2n] 
 
 
 
 

Безопасность

     В отличие от современных шифров (таких, как в eSTREAM), RC4 не использует отдельной  оказии (nonce) наряду с ключом. Это  значит, что если один ключ должен использоваться в течение долгого времени  для шифрования нескольких потоков, сама криптосистема, использующая RC4, должна комбинировать оказию и долгосрочный ключ для получения потокового ключа  для RC4. Один из возможных выходов  — генерировать новый ключ для RC4 с помощью хэш-функции от долгосрочного  ключа и оказии. Однако, многие приложения, использующие RC4, просто конкатенируют  ключ и оказию. Из-за этого и слабого  расписания ключей, используемого в RC4, приложение может стать уязвимым.

     Здесь будут рассмотрены некоторые  атаки на шифр и методы защиты от них.

Манипуляция битами

     Шифр RC4 крайне уязвим к манипуляции битами, если он не реализован верным образом. И поэтому он был признан устаревшим многими софтверными компаниями, такими как Microsoft. Например, в .NET Framework от Microsoft отсутствует реализация RC4.

Исследования  Руза и восстановление ключа из перестановки

     В 1995 году Андрю Руз (Andrew Roos) экспериментально пронаблюдал, что первый байт ключевого  потока коррелирован с первыми тремя  байтами ключа, а первые несколько  байт перестановки после алгоритма  расписания ключей (KSA) коррелированны с некоторой линейной комбинацией  байт ключа. Эти смещения не были доказаны до 2007 года, когда Пол, Рафи и Мэйтрэ доказали коррелированность ключа  и ключевого потока. Также Пол  и Мэйтрэ доказали коррелированность  перестановки и ключа. Последняя  работа также использует коррелированность  ключа и перестановки для того, чтобы создать первый алгоритм полного  восстановления ключа из последней  перестановки после KSA, не делая предположений  о ключе и векторе инициализации(V or Initial Vector). Этот алгоритм имеет постоянную вероятность успеха в зависимости  от времени, которая соответствует  квадратному корню из сложности  полного перебора. Позднее было сделано  много работ о восстановлении ключа из внутреннего состояния RC4. 
 

Атака Флурера, Мантина  и Шамира (ФМШ)

     В 2001 году, Флурер, Мантин и Шамир опубликовали работу об уязвимости ключевого расписания RC4. Они показали, что среди всех возможных ключей, первые несколько  байт ключевого потока являются совсем неслучайными. Из этих байт можно с  высокой вероятностью получить информацию о используемом шифром ключе. И если долговременный ключ и оказия (nonce) просто конкатенируются для создания ключа шифра RC4, то этот долговременный ключ может быть получен с помощью анализа достаточно большого количества сообщений, зашифрованных с использованием данного ключа. Эта уязвимость и некоторые связанные с ней эффекты были использованы при взломе шифрования WEP в беспроводных сетях стандарта IEEE 802.11. Это показало необходимость скорейшей замены WEP, что повлекло за собой разработку нового стандарта безопасности беспроводных сетей WPA.

     Криптосистему можно сделать невосприимчивой  к этой атаке, если отбрасывать начало ключевого потока. Таким образом, модифицированный алгоритм называется «RC4-drop[n]», где n — количество байт из начала ключевого потока, которые  следует отбросить. Рекомендовано  использовать n = 768, консервативная оценка составляет n = 3072.

Атака Кляйна

     В 2005 году Андреас Кляйн представил анализ шифра RC4, в котором он указал на сильную коррелированность ключа  и ключевого потока RC4. Кляйн проанализировал  атаки на первом раунде (подобные атаке  ФМШ), на втором раунде и возможные  их улучшения. Он также предложил  некоторые изменения алгоритма  для усиления стойкости шифра. В  частности, он утверждает, что если поменять направление цикла на обратное в алгоритме ключевого расписания, то можно сделать шифр более стойким  к атакам типа ФМШ.

Комбинаторная проблема

     В 2001 году Ади Шамир и Ицхак Мантин первыми поставили комбинаторную проблему, связанную с количеством всевозможных входных и выходных данных шифра RC4. Если из всевозможных 256 элементов внутреннего состояния шифра известно x элементов из состояния (x ≤ 256), то, если предположить, что остальные элементы нулевые, максимальное количество элементов, которые могут быть получены детерминированным алгоритмом за следующие 256 раундов также равно x. В 2004 году это предположение было доказано Сорадюти Полом (Souradyuti Paul) и Бартом Прэнилом (Bart Preneel).