RC4

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

Потоковый шифр RC4 был создан Рональдом Ривестом, сотрудником компании RSA Security[англ.], в 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[англ.]. Чтобы избежать возможных претензий со стороны владельца торговой марки, шифр иногда называют «ARCFOUR» или «ARC4», имея в виду англ. alleged RC4 — «предполагаемый» RC4 (поскольку «RSA Security» официально не опубликовала алгоритм).

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

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

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

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

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

[править | править код]

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

Режим гаммирования для поточных шифров

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

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

.

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

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

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

Внутреннее состояние RC4 представляется в виде массива размером 2n и двух счётчиков. Массив известен как S-блок, и далее будет обозначаться как S. Он всегда содержит перестановку 2n возможных значений слова. Два счётчика обозначены через 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, 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.

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

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

[править | править код]

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

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

[править | править код]

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

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

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

Атака NOMORE (2015)

[править | править код]

Летом 2015 года Мэти Ванхоф (Mathy Vanhoef) и Франк Писсенс (Frank Piessens) из университета Левена в Бельгии продемонстрировали реальную атаку на протоколы TLS и TKIP, использующие RC4 для шифрования передаваемых данных, получившую название «Numerous Occurrence MOnitoring & Recovery Exploit» (NOMORE)[14]. Идея взлома базируется на принципе MITM. Встроившись в канал передачи данных, атакующая сторона генерирует серверу большое количество запросов, вынуждая его в ответ возвращать куки, зашифрованные одним и тем же ключом. Имея в распоряжении около 9x227 ~ 230 пар {открытый текст, шифротекст}, злоумышленник получает возможность на основе статистических методов Флюрер-Макгрю и ABSAB с вероятностью 94 % восстановить ключ и, следовательно, зашифрованные куки. Практические временные затраты составили около 52 часов, верхняя же оценка потребного времени на момент демонстрации составила около 72 часов[15].

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

[править | править код]

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

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

Для 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

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

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

Алгоритм:

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

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

[править | править код]

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

Примечания

[править | править код]
  1. 1 2 Klein A. Attacks on the RC4 stream cipher (неопр.) // Designs, codes and cryptography. — 2008. — Т. 48, № 3. — С. 269—286. — doi:10.1007/s10623-008-9206-6. Архивировано 2 апреля 2015 года.
  2. Rivest FAQ. Дата обращения: 15 октября 2009. Архивировано из оригинала 15 июля 2017 года.
  3. "Thank you Bob Anderson". Cypherpunks (Mailing list). 1994-09-09. Архивировано 4 апреля 2008. Дата обращения: 28 мая 2007.
  4. RSA Laboratories — 3.6.2 What is RC2? Дата обращения: 7 ноября 2012. Архивировано из оригинала 29 июля 2012 года.
  5. Bruce Schneier. Applied cryptography. Second edition. John Wiley & Sons. 1996
  6. Источник. Дата обращения: 18 июня 2010. Архивировано 2 апреля 2015 года.
  7. Архивированная копия. Дата обращения: 16 октября 2013. Архивировано из оригинала 16 ноября 2012 года.
  8. https://uwspace.uwaterloo.ca/bitstream/10012/1141/1/memckagu2005.pdf
  9. Weak keys in RC4. Дата обращения: 7 ноября 2012. Архивировано из оригинала 18 июня 2012 года.
  10. 1 2 Scott R. Fluhrer, Itsik Mantin, Adi Shamir. Weaknesses in the key scheduling algorithm of RC4 (неопр.) // Lecture notes in computer science. — 2001. — Т. 2259. — С. 1—24. — doi:10.1007/3-540-45537-X_1. Архивировано 7 сентября 2008 года.
  11. I. Mironov. (Not so) random shuffles of RC4 (неопр.) // Lecture Notes in Computer Science. — 2002. — Т. 2442. — С. 304—319. — doi:10.1007/3-540-45708-9_20. Архивировано 19 января 2010 года.
  12. «RC4-drop(nbytes)» Архивная копия от 25 января 2012 на Wayback Machine. «Standard cryptographic algorithm naming» database.
  13. Souradyuti Paul, Bart Preneel. A New Weakness in the RC4 Keystream generator and an approach to improve the security of the cipher (англ.) // Lecture notes in computer science : journal. — 2004. — Vol. 3017. — P. 245—259. — doi:10.1007/b98177. Архивировано 6 марта 2009 года.
  14. RC4 NOMORE. Дата обращения: 17 апреля 2016. Архивировано 18 августа 2020 года.
  15. Хакеры показали практичный метод взлома RC4. Дата обращения: 17 апреля 2016. Архивировано 25 апреля 2016 года.
  16. Ilya Mironov (2002-06-01), "(Not So) Random shuffles of RC4", Advances in cryptology – CRYPTO 2002, Lecture notes in computer science, vol. 2442, Springer-Verlag, pp. 304—319, doi:10.1007/3-540-45708-9_20, ISBN 3-540-44050-X, Cryptology ePrint archive: Report 2002/067, Архивировано 6 сентября 2011, Дата обращения: 4 ноября 2011
  17. 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, Lecture Notes in Computer Science, vol. 3017, Springer-Verlag, pp. 245—259, doi:10.1007/978-3-540-25937-4_16, ISBN 3-540-22171-9, Архивировано из оригинала 11 июня 2011, Дата обращения: 4 ноября 2011
  18. Subhamoy Maitra; Goutam Paul (2008-09-19), "Analysis of RC4 and Proposal of Additional Layers for Better Security Margin", Progress in Cryptology – INDOCRYPT 2008, Lecture Notes in Computer science, vol. 5365, Springer-Verlag, pp. 27—39, doi:10.1007/978-3-540-89754-5_3, ISBN 3-540-89753-4, Cryptology ePrint Archive: Report 2008/396, Архивировано 30 января 2012, Дата обращения: 4 ноября 2011
  19. RSA Laboratories — 3.6.3 What is RC4? Дата обращения: 18 октября 2009. Архивировано из оригинала 26 февраля 2009 года.
  20. Ответы Архивная копия от 24 марта 2010 на Wayback Machine на вопровы пользователей браузера Opera mini.
  21. RFC 4757. The RC4-HMAC kerberos encryption types used by Microsoft Windows.
  22. PDF & PDF/A software | PDF Tools AG | Premium PDF technology Архивировано 3 ноября 2005 года.
  23. Skype's encryption procedure partly exposed. www.h-online.com. Дата обращения: 8 июля 2010. Архивировано 6 ноября 2012 года.