RC4

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

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

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

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

История

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

В течение семи лет шифр являлся коммерческой тайной , и точное описание алгоритма предоставлялось только после подписания соглашения о неразглашении , но в сентябре 1994 года его описание было анонимно отправлено в рассылку Cypherpunks^[3]. Вскоре описание 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-битные ключи разрешено использовать заграничным отделениям американских компаний.^[4]

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

Ядро алгоритма поточных шифров состоит из генератора гаммы , который выдаёт ключевой поток (гамму). Функция генерирует последовательность битов ($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 — фактически класс алгоритмов, определяемых размером блока (в дальнейшем S-блока). Параметр n является размером слова для алгоритма и определяет длину S-блока. Обычно, n = 8, но в целях анализа можно уменьшить его. Однако для повышения безопасности необходимо увеличить эту величину. В алгоритме нет противоречий на увеличение размера S-блока . При увеличении n, допустим, до 16 бит , элементов в S-блоке становится 65536 и соответственно время начальной итерации будет увеличено. Однако, скорость шифрования возрастет. ^[5]

Внутреннее состояние 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

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

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

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

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

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

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

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

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

Атака Кляйна

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

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

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

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

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

RC4A

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

Для 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+).^[16]

Алгоритм :

 Все арифметические операции выполняются по 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 машинных команд на каждый байт текста, поэтому программная реализация шифра должна работать очень быстро^[17].

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

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

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

См. также

• VMPC
• CipherSaber(en)

Примечания

1. ↑ ^{1 2} A. Klein (2008). «Attacks on the RC4 stream cipher». Designs, Codes and Cryptography 48 (3): 269—286. DOI:10.1007/s10623-008-9206-6.
2. ↑ Rivest FAQ
3. ↑ Thank you Bob Anderson. Список рассылки Cypherpunks (9 сентября 1994). Проверено 28 мая 2007.
4. ↑ http://www.rsa.com/rsalabs/node.asp?id=2249
5. ↑ Bruce Schneier. Applied Cryptography. Second Edition, John Wiley & Sons, 1996
6. ↑ http://www.networklife.net/images/wep-rc4/RC4.pdf
7. ↑ http://aboba.drizzlehosting.com/IEEE/rc4_ksaproc.pdf
8. ↑ https://uwspace.uwaterloo.ca/bitstream/10012/1141/1/memckagu2005.pdf
9. ↑ Weak Keys in RC4
10. ↑ ^{1 2} Scott R. Fluhrer, Itsik Mantin, Adi Shamir (2001). «Weaknesses in the Key Scheduling Algorithm of RC4». Lecture Notes in Computer Science 2259: 1—24. DOI:10.1007/3-540-45537-X_1.
11. ↑ I. Mironov (2002). «(Not so) random shuffles of RC4». Lecture Notes in Computer Science 2442: 304—319. DOI:10.1007/3-540-45708-9_20.
12. ↑ «RC4-drop(nbytes)». «Standard Cryptographic Algorithm Naming» database.
13. ↑ Souradyuti Paul, Bart Preneel (2004). «A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher». Lecture Notes in Computer Science 3017: 245—259. DOI:10.1007/b98177.
14. ↑ Ilya Mironov (2002-06-01), "(Not So) Random Shuffles of RC4", «Advances in Cryptology – CRYPTO 2002», vol. 2442, Lecture Notes in Computer Science, Springer-Verlag, сс. 304–319, Cryptology ePrint Archive: Report 2002/067, ISBN 3-540-44050-X, doi:10.1007/3-540-45708-9_20 
15. ↑ Souradyuti Paul & Bart Preneel (2004), "A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher", «Fast Software Encryption, FSE 2004», vol. 3017, Lecture Notes in Computer Science, Springer-Verlag, сс. 245–259, ISBN 3-540-22171-9, doi:10.1007/978-3-540-25937-4_16 
16. ↑ Subhamoy Maitra & Goutam Paul (2008-09-19), "Analysis of RC4 and Proposal of Additional Layers for Better Security Margin", «Progress in Cryptology – INDOCRYPT 2008», vol. 5365, Lecture Notes in Computer Science, Springer-Verlag, сс. 27–39, Cryptology ePrint Archive: Report 2008/396, ISBN 3-540-89753-4, doi:10.1007/978-3-540-89754-5_3 
17. ↑ RSA Laboratories — 3.6.3 What is RC4?
18. ↑ Opera Mini FAQ
19. ↑ RFC 4757 - The RC4-HMAC Kerberos Encryption Types Used by Microsoft Windows
20. ↑ http://www.pdf-tools.com/public/downloads/pdf-reference/pdfreference12.pdf
21. ↑ Skype's encryption procedure partly exposed. www.h-online.com. Архивировано из первоисточника 7 ноября 2012. Проверено 8 июля 2010.

Ссылки

• 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 формат)

Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.