RC4

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
(перенаправлено с «ARC4»)

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. Функция генерирует последовательность битов ([math]\displaystyle{ k_i }[/math]).
  2. Затем последовательность битов посредством операции «суммирование по модулю два» (xor) объединяется с открытым текстом ([math]\displaystyle{ m_i }[/math]). В результате получается шифрограмма ([math]\displaystyle{ c_i }[/math]):

[math]\displaystyle{ c_i = m_i \oplus k_i }[/math].

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

  1. Повторно создаётся (регенерируется) поток битов ключа (ключевой поток) ([math]\displaystyle{ k_i }[/math]).
  2. Поток битов ключа складывается с шифрограммой ([math]\displaystyle{ c_i }[/math]) операцией «xor». В силу свойств операции «xor» на выходе получается исходный (незашифрованный) текст ([math]\displaystyle{ m_i }[/math]):

[math]\displaystyle{ m_i = c_i \oplus k_i = (m_i \oplus k_i) \oplus k_i }[/math]

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].

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

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

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

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

RC4A

В 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

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

RC4+

В 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,0 1,1 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. ↑ Rivest FAQ (недоступная ссылка). Дата обращения: 15 октября 2009. Архивировано 15 июля 2017 года.
  3. ↑ Thank you Bob Anderson. Список рассылки Cypherpunks (9 сентября 1994). Дата обращения: 28 мая 2007.
  4. ↑ RSA Laboratories — 3.6.2 What is RC2?
  5. ↑ Bruce Schneier. Applied cryptography. Second edition. John Wiley & Sons. 1996
  6. ↑ http://www.networklife.net/images/wep-rc4/RC4.pdf
  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. ↑ 10,0 10,1 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.
  12. ↑ «RC4-drop(nbytes)». «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.
  14. ↑ RC4 NOMORE
  15. ↑ Хакеры показали практичный метод взлома RC4
  16. ↑ 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 
  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, 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 
  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, 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 
  19. ↑ RSA Laboratories — 3.6.3 What is RC4?
  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 года.

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=RC4&oldid=11342707