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

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

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

Основные преимущества шифра:

• высокая скорость работы;
• переменный размер ключа.

RC4 довольно уязвим, если:

• используются не случайные или связанные ключи;
• один ключевой поток используется дважды.

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

История

Потоковый шифр RC4 был создан Рональдом Ривестом , сотрудником компании , в 1987 году . Сокращение «RC4» официально обозначает «Rivest cipher 4» или «шифр Ривеста » («4» — номер версии; см. RC2 , RC5 , RC6 ; RC1 никогда не публиковался; RC3 разрабатывался, но в нём была найдена уязвимость ), но его часто считают сокращением от « Ron’s code » («код Рона ») .

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

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

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

RC4 стал популярен благодаря:

• простоте его аппаратной и программной реализации;
• высокой скорости работы алгоритма в обоих случаях.

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

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

Ядро алгоритма поточных шифров состоит из функции — генератора псевдослучайных битов ( гаммы ), который выдаёт поток битов ключа (ключевой поток, гамму, последовательность псевдослучайных битов).

Алгоритм шифрования.

1. Функция генерирует последовательность битов ( ${\displaystyle k_{i}}$ ).
2. Затем последовательность битов посредством операции « суммирование по модулю два » (xor) объединяется с открытым текстом ( ${\displaystyle m_{i}}$ ). В результате получается шифрограмма ( ${\displaystyle c_{i}}$ ):

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

Алгоритм расшифровки.

1. Повторно создаётся (регенерируется) поток битов ключа (ключевой поток) ( ${\displaystyle k_{i}}$ ).
2. Поток битов ключа складывается с шифрограммой ( ${\displaystyle c_{i}}$ ) операцией « xor ». В силу свойств операции « xor » на выходе получается исходный (незашифрованный) текст ( ${\displaystyle m_{i}}$ ):

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

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

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

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

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

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

Алгоритм также известен как «key-scheduling algorithm» или «KSA». Этот алгоритм использует ключ, подаваемый на вход пользователем, сохранённый в Key , и имеющий длину L байт. Инициализация начинается с заполнения массива S , далее этот массив перемешивается путём перестановок, определяемых ключом. Так как только одно действие выполняется над S , то должно выполняться утверждение, что S всегда содержит один набор значений, который был дан при первоначальной инициализации ( S[i] := i ).

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

Эта часть алгоритма называется генератором псевдослучайной последовательности ( англ. p seudo- r andom g eneration a lgorithm , 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 (от англ. nonce — «number that can only be used once» — число, которое может быть использовано один раз) наряду с ключом. Это значит, что если один ключ должен использоваться в течение долгого времени для шифрования нескольких потоков, сама криптосистема, использующая RC4, должна комбинировать оказию и долгосрочный ключ для получения потокового ключа для RC4. Один из возможных выходов — генерировать новый ключ для RC4 с помощью хеш -функции от долгосрочного ключа и nonce . Однако многие приложения, использующие RC4, просто конкатенируют ключ и nonce . Из-за этого и слабого расписания ключей, используемого в RC4, приложение может стать уязвимым . Поэтому он был признан устаревшим многими софтверными компаниями, такими как Microsoft . Например, в .NET Framework от Microsoft отсутствует реализация RC4.

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

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

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

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

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

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

Атака базируется на слабости . Зная первое псевдослучайное слово 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 ) .

Атака Ванхофа и Писсенса (2015)

Летом 2015 года Мэти Ванхоф (Mathy Vanhoef) и Франк Писсенс (Frank Piessens) из университета Левена в Бельгии продемонстрировали реальную атаку на протокол TLS , использующий RC4 для шифрования передаваемых данных . Идея взлома базируется на принципе MITM . Встроившись в канал передачи данных, атакующая сторона генерирует серверу большое количество запросов, вынуждая его в ответ возвращать куки , зашифрованные одним и тем же ключом. Имея в распоряжении около 9x2 ²⁷ ~ 2 ³⁰ пар {открытый текст, шифротекст}, атакующая сторона получила возможность на основе статистических методов и с вероятностью 94 % восстановить ключ и, следовательно, зашифрованные куки. Практические временные затраты составили около 52 часов, верхняя же оценка потребного времени на момент демонстрации составила около 72 часов .

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

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

RC4A

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

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

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

Алгоритм :

i := 0
j₁ := 0
j₂ := 0
while Цикл генерации:
    i := i + 1
    j₁ := ( j₁ + S₁[i] ) mod 256
    поменять местами S₁[i] и S₁[j₁]
    I₂ := ( S₁[i] + S₁[j₁] ) mod 256
    output := S₂[I₂]
    j₂ = ( j₂ + S₂[i] ) mod 256
    поменять местами S₂[i] и S₂[j₂]
    I₁ = ( S₂[i] + S₂[j₂] ) mod 256
    output := S₁[I₁]
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

• WEP ;
• ;
• MPPE ;
• браузер Opera Mini ;
• протокол SSL (вариативно);
• протокол SSH (вариативно);
• протокол RDP ;
• Kerberos (вариативно);
• SASL mechanism digest- MD5 (вариативно);
• формат PDF
• Skype (вариативно) .

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

См. также

• VMPC

Примечания

Ссылки

• .
• , содержащее описание алгоритма RC4, в списке рассылки « ».
• Klein A. « ». 27 февраля 2006 года (формат PostScript ).