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].
Ядро алгоритма поточных шифров состоит из функции — генератора псевдослучайных битов (гаммы), который выдаёт поток битов ключа (ключевой поток, гамму, последовательность псевдослучайных битов).
Алгоритм шифрования.
.
Алгоритм расшифровки.
RC4 — фактически класс алгоритмов, определяемых размером блока (в дальнейшем S-блока). Параметр n является размером слова для алгоритма и определяет длину S-блока. Обычно, n = 8, но в целях анализа можно уменьшить его. Однако для повышения безопасности необходимо увеличить эту величину. В алгоритме нет противоречий на увеличение размера S-блока . При увеличении n, допустим, до 16 бит, элементов в S-блоке становится 65 536 и соответственно время начальной итерации будет увеличено. Однако, скорость шифрования возрастёт[5].
Внутреннее состояние RC4 представляется в виде массива размером 2n и двух счётчиков. Массив известен как S-блок, и далее будет обозначаться как S
. Он всегда содержит перестановку 2n возможных значений слова. Два счётчика обозначены через i
и j
.
Инициализация RC4 состоит из двух частей:
K
.Алгоритм также известен как «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
Эта часть алгоритма называется генератором псевдослучайной последовательности (англ. 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 года Мэти Ванхоф (Mathy Vanhoef) и Франк Писсенс (Frank Piessens) из университета Левена в Бельгии продемонстрировали реальную атаку на протокол TLS, использующий RC4 для шифрования передаваемых данных[14]. Идея взлома базируется на принципе MITM. Встроившись в канал передачи данных, атакующая сторона генерирует серверу большое количество запросов, вынуждая его в ответ возвращать куки, зашифрованные одним и тем же ключом. Имея в распоряжении около 9x227 ~ 230 пар {открытый текст, шифротекст}, атакующая сторона получила возможность на основе статистических методов Флюрер-Макгрю и ABSAB с вероятностью 94 % восстановить ключ и, следовательно, зашифрованные куки. Практические временные затраты составили около 52 часов, верхняя же оценка потребного времени на момент демонстрации составила около 72 часов[15].
Ранее рассматривались атаки, основанные на коррелируемости первых байт шифрованного текста и ключа. Подобные слабости алгоритма могут быть решены отбрасыванием начальной части шифрованного текста[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, используется в единственном числе для всего алгоритма.
Принцип выполнения алгоритма остается прежним, но имеется ряд отличий:
S₁
является параметром для S₂
.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 является одним из нескольких алгоритмов шифрования, которые могут использоваться системой.
Потоковые шифры | |
---|---|
Сеть Фейстеля | |
SP-сеть | |
Другие |