RC4

RC4 (англ. Rivest Cipher 4 или англ. Ron’s Code, также известен как ARCFOUR или ARC4 (англ. Alleged RC4)) — потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколах SSL и TLS, алгоритме безопасности беспроводных сетей WEP, для шифрования паролей в Windows NT).

Шифр разработан компанией RSA Security и для его использования требуется лицензия.

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

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

История

Потоковый шифр RC4 был создан Роном Ривестом из RSA Security в 1987 году. Хотя официально сокращение обозначает Rivest Cipher 4, его часто считают сокращением от Ron’s Code.

В течении семи лет шифр являлся коммерческой тайной , и точное описание алгоритма предоставлялось только после подписания соглашения о неразглашении , но в сентябре 1994 года его описание было анонимно отправлено в рассылку Cypherpunks. Вскоре описание RC4 было опубликовано в ньюс-группе sci.crypt. Именно оттуда исходный код попал на множество сайтов в сети Интернет. Опубликованный шифр давал те же шифротексты на выходе, какие давал подлинный RC4. Опубликованный шифр совместим с имеющимися продуктами, использующими RC4, обладатели легальных копий RC4 подтвердили идентичность алгоритмов при различиях в обозначениях и структуре программы.

Поскольку данный алгоритм известен, он более не является коммерческой тайной. Однако, название «RC4» является торговой маркой компании RSA. Поэтому иногда шифр называют «ARCFOUR» или «ARC4» (имея в виду Alleged RC4 — предполагаемый RC4, поскольку RSA официально не опубликовала алгоритм), чтобы избежать возможных претензий со стороны владельца торговой марки.

Шифр RC4 применяется в некоторых широко распространённых стандартах и протоколах шифрования таких, как WEP, WPA и TLS.

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

В США длина ключа для использования внутри страны рекомендуется равной 128 битам, но соглашение, заключённое между Software Publishers Association (SPA) и правительством США даёт RC4 специальный статус, который означает, что разрешено экспортировать шифры длиной ключа до 40 бит. 56-битные ключи разрешено использовать заграничным отделениям американских компаний.

Описание алгоритма

Ядро алгоритма поточных шифров состоит из функции генерации ключевого потока. Функция генерирует последовательность битов ($k_{i}$), которая затем объединяется с открытым текстом ($m_{i}$) посредством суммирования по модулю два. Так получается шифрограмма ($c_{i}$):

$c_{i}=m_{i}\oplus k_{i}$.

Расшифровка заключается в регенерации ключевого потока ($k_{i}$) и сложении с шифрограммой ($c_{i}$) по модулю два. В силу свойств суммирования по модулю два на выходе мы получим исходный незашифрованный текст($m_{i}$):

$m_{i}=c_{i}\oplus k_{i}=(m_{i}\oplus k_{i})\oplus k_{i}$

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

Внутреннее состояние RC4 представляется в виде массива размером 2ⁿ и двух счётчиков. Массив известен как S-блок, и далее будет обозначаться как S. Он всегда содержит перестановку 2ⁿ возможных значений слова. Два счётчика обозначены через i и j.

Инициализация RC4 состоит из двух частей :

1. Инициализация S-блока
2. Генерация псевдо-случайного слова K

Инициализация S-блока

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

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + Key[i mod L]) mod 256 // n = 8 ; 28 = 256
    поменять местами S[i] и S[j]
endfor

Генерация псевдо-случайного слова K

Генератор ключевого потока RC4

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

i := 0
j := 0
while Цикл генерации:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    поменять местами S[i] и S[j]
    t := (S[i] + S[j]) mod 256
    K := S[t]
    сгенерирован псевдо-случайное слово K (для n = 8 будет сгенерирован один байт)
endwhile

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

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

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

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

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

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

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

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

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

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

Атака базируется на слабости инициализационного вектора (initialization vectors (IVs)). Зная первое псевдо-случайное слово K и m байтов входного ключа Key , используя слабость в алгоритме генерации псевдо-случайного слова K , можно получить m + 1 байт входного ключа. Повторяя шаги добывается полный ключ. При атаке на WEP , для n = 8 IV имеет вид (B; 255;N) где B от 3 до 8 , а N любое число . Для определения около 60 вариантов N потребуется перехватить примерно 4 миллионов пакетов.

Атака Кляйна

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

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

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

Модификации RC4

Ранее рассматривались атаки основанные на кореллируемости первых байт шифрованного текста и ключа. Подобные слабости алгоритма могут быть решены отбрасыванием начальной части шифрованного текста. Надежным считается отбрасывание первых 256 , 512 , 768 и 1024 байт. Были предложены несколько модификаций RC4 выполняющие поставленную задачу усиления безопасности при использовании алгоритма : RC4A, VMPC,RC4+.

RC4A

В 2004 году свет увидела работа Souradyuti Paul и Bart Preneel , в которой предлогалась модификация RC4A.

Для RC4A используется два S-блока вместо одного как в RC4, обозначим S1 и S2. Для них соответствующе используются два счетчика j1 , j2. Счетчик i , как и для RC4 , используется в единственном числе для всего алгоритма. Принцип выполнения алгоритма остается прежним , но имеется ряд отличий:

1. S1 является параметром для S2.
2. За одну итерацию , то есть за одно увеличение индекса i , генерируется два байта шифротекста.

Алгоритм :

i := 0
j1 := 0
j2 := 0
while Цикл генерации:
    i := i + 1
    j1 := (j1 + S1[i]) mod 256
    поменять местами S1[i] и S1[j1]
    I2 := (S1[i] + S1[j1]) mod 256
    output := S2[I2]
    j2 = (j2 + S2[i]) mod 256
    поменять местами S2[i] и S2[j2]
    I1 = (S2[i] + S2[j2]) mod 256
    output := S1[I1]
endwhile

Скорость шифрования данного алгоритма может быть увеличена за счет распараллеливания.

RC4+

В 2008 году была разработана и предложена модификация RC4+ . Авторы Subhamoy Maitra и Goutam Paul модифицировали инициализацию S-блока(KSA+) использовав 3-уровневое скремблирование. Так же модификации был подвергнут алгоритм генерация псевдо-случайного слова (PRGA+).

Алгоритм :

 Все арифметические операции выполняются по mod 256.  << и >> побитовый сдвиг влево и вправо соответственно, ⊕ исключающее ИЛИ
while Цикл генерации:
    i := i + 1
    a := S[i]
    j := j + a
    b := S[j]
    S[i] := b     (поменяли местами S[i] и S[j])
    S[j] := a
    c := S[i<<5 ⊕ j>>3] + S[j<<5 ⊕ i>>3]
    output (S[a+b] + S[c⊕0xAA]) ⊕ S[j+b]
endwhile

Реализация

Работа многих поточных шифров основана на линейных регистрах сдвига с обратной связью (LFSR). Это позволяет достичь высокой эффективности реализаций шифра в виде ИС, но затрудняет программную реализацию таких шифров. Поскольку шифр RC4 не использует LFSR и основан на байтовых операциях, его удобно реализовывать программно. Типичная реализация выполняет от 8 до 16 машинных команд на каждый байт текста, поэтому программная реализация шифра должна работать очень быстро.

RC4-based cryptosystems

• WEP
• BitTorrent protocol encryption
• Microsoft Point-to-Point Encryption
• Opera Mini
• Secure Sockets Layer (вариативно)
• Secure shell (вариативно)
• Remote Desktop Protocol
• Kerberos (вариативно)
• SASL Mechanism Digest-MD5 (вариативно)
• PDF
• Skype (in modified form)

"(вариативно)" означает , что RC4 один из нескольких алгоритмов шифрования , которые могут быть использованы системой.

См. также

• VMPC
• CipherSaber(en)

Ссылки

• RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4
• Original posting of RC4 algorithm to Cypherpunks mailing list
• A. Klein, Attacks on the RC4 stream cipher, February 27, 2006(post-script формат)