WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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 и соответственно время начальной итерации будет увеличено. Однако, скорость шифрования возрастёт^[5].

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

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

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

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

Эта часть алгоритма называется генератором псевдослучайной последовательности (англ. pseudo-random generation algorithm, 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, приложение может стать уязвимым^[6][7][8]. Поэтому он был признан устаревшим многими софтверными компаниями, такими как Microsoft. Например, в .NET Framework от Microsoft отсутствует реализация RC4.

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

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

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

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

 Все арифметические операции выполняются по 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

Реализация

Имеется викиучебник по теме
«Программные реализации RC4»

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

Криптосистемы и протоколы, использующие RC4

• WEP;
• BitTorrent protocol encryption^[en];
• MPPE;
• браузер Opera Mini^[20];
• протокол SSL (вариативно);
• протокол SSH (вариативно);
• протокол RDP;
• Kerberos^[21] (вариативно);
• SASL mechanism digest-MD5 (вариативно);
• формат PDF^[22]
• Skype (вариативно)^[23].

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

См. также

• VMPC
• CipherSaber^[en]

Примечания

Ссылки

• RSA security response to weaknesses in key scheduling algorithm of RC4.
• Письмо, содержащее описание алгоритма RC4, в списке рассылки «Cypherpunks».
• Klein A. «Attacks on the RC4 stream cipher». 27 февраля 2006 года (формат PostScript).