RC4 – потоковый шифр c переменным размером ключа

     RC4 (от англ. Rivest cipher 4 или Ron’s code) – потоковый шифр c переменным размером ключа. Потоковый шифр означает, что каждый символ незашифрованного, точнее открытого текста будет зашифрован в зависимости от таких параметров, как: положения символа в открытом тексте и ключа. 
     История
     Алгоритм RC4 был создан профессором Массачусетского технологического института Рональдом Ривестом для компании RSA Data Security в 1987. Также Рональд Ривест создал такие алгоритмы, как RC2, RC5, RC6, и линейку криптографических хэш-функций MD2, MD3, MD4, MD5, MD6. 
      Алгоритм находился в частной собственности в течении семи лет, поэтому подробное описание RC4 представлялось только после подписания соглашения о неразглашения.
     В сентябре 1994 года кто-то анонимно отправил описание исходного кода алгоритма в список рассылки «Cypherpunks». Он быстро распространился в телеконференции Usenet sci.crypt и через интернет по различным ftp-серверам во всем мире. Те, кто обладали легальными копиями RC4, подтвердили достоверность этого кода. После, компания RSA Data Security пыталась «вернуть» алгоритм обратно, утверждая, что несмотря на опубликование RC4, он остается торговым секретом, но было поздно. Алгоритм распространился по всему миру.
     В настоящее время алгоритм RC4 реализован в десятках коммерческих криптопродуктов, включая Lotus Notes, Apple Computer’s AOCE, Oracle Secure SQL; он также является частью спецификации стандарта сотовой связи CDPD.
     Безопасность 
     В отличие от современных шифров (таких, как eSTREAM), RC4 не использует nonce (оказию) наряду с ключом. Это значит, что если один ключ должен использоваться в течение долгого времени для шифрования нескольких потоков, сама криптосистема, использующая RC4, должна комбинировать оказию и долгосрочный ключ для получения потокового ключа для RC4. Один из возможных выходов — генерировать новый ключ для RC4 с помощью хэш-функции от долгосрочного ключа и nonce. Однако многие приложения, использующие RC4, просто конкатенируют ключ и nonce. Из-за этого и слабого расписания ключей, используемого в RC4, приложение может стать уязвимым. Поэтому он был признан устаревшим многими софтверными компаниями, такими как Microsoft. Например, в .NET Framework от Microsoft отсутствует реализация RC4.
     Здесь будут рассмотрены некоторые атаки на шифр и методы защиты от них.
     Исследования Руза и восстановление ключа из перестановки
     В 1995 году Андрю Руз (англ. Andrew Roos) экспериментально пронаблюдал, что первый байт ключевого потока коррелирован с первыми тремя байтами ключа, а первые несколько байт перестановки после алгоритма расписания ключей (англ. KSA) коррелированы с некоторой линейной комбинацией байт ключа. Эти смещения не были доказаны до 2007 года, когда Пол, Рафи и Мэйтрэ доказали коррелированность ключа и ключевого потока. Также Пол и Мэйтрэ доказали коррелированность перестановки и ключа. Последняя работа также использует коррелированность ключа и перестановки для того, чтобы создать первый алгоритм полного восстановления ключа из последней перестановки после KSA, не делая предположений о ключе и векторе инициализации (англ. IV, initial vector). Этот алгоритм имеет постоянную вероятность успеха в зависимости от времени, которая соответствует квадратному корню из сложности полного перебора. Позднее было сделано много работ о восстановлении ключа из внутреннего состояния RC4.
     Атака Флурера, Мантина и Шамира (ФМШ)
     В 2001 году, Флурер, Мантин и Шамир опубликовали работу об уязвимости ключевого расписания RC4. Они показали, что среди всех возможных ключей, первые несколько байт ключевого потока являются совсем неслучайными. Из этих байт можно с высокой вероятностью получить информацию об используемом шифром ключе. И если долговременный ключ и nonce просто конкатенируются для создания ключа шифра RC4, то этот долговременный ключ может быть получен с помощью анализа достаточно большого количества сообщений, зашифрованных с использованием данного ключа. Эта уязвимость и некоторые связанные с ней эффекты были использованы при взломе шифрования WEP в беспроводных сетях стандарта IEEE 802.11. Это показало необходимость скорейшей замены WEP, что повлекло за собой разработку нового стандарта безопасности беспроводных сетей WPA.
     Криптосистему можно сделать невосприимчивой к этой атаке, если отбрасывать начало ключевого потока. Таким образом, модифицированный алгоритм называется «RC4-drop[n]», где n — количество байт из начала ключевого потока, которые следует отбросить. Рекомендовано использовать n = 768, консервативная оценка составляет n = 3072.
     Атака базируется на слабости инициализационного вектора. Зная первое псевдо-случайное слово K и m байтов входного ключа Key, используя слабость в алгоритме генерации псевдо-случайного слова K , можно получить m + 1 байт входного ключа. Повторяя шаги добывается полный ключ. При атаке на WEP, для n = 8 IV имеет вид (B; 255; N), где B — от 3 до 8, а N любое число . Для определения около 60 вариантов N потребуется перехватить примерно 4 миллиона пакетов.
     Атака Кляйна
     В 2005 году Андреас Кляйн представил анализ шифра RC4, в котором он указал на сильную коррелированность ключа и ключевого потока RC4. Кляйн проанализировал атаки на первом раунде (подобные атаке ФМШ), на втором раунде и возможные их улучшения. Он также предложил некоторые изменения алгоритма для усиления стойкости шифра. В частности, он утверждает, что если поменять направление цикла на обратное в алгоритме ключевого расписания, то можно сделать шифр более стойким к атакам типа ФМШ.
     Комбинаторная проблема
     В 2001 году Ади Шамир и Ицхак Мантин первыми поставили комбинаторную проблему, связанную с количеством всевозможных входных и выходных данных шифра RC4. Если из всевозможных 256 элементов внутреннего состояния шифра известно x элементов из состояния (x ? 256), то, если предположить, что остальные элементы нулевые, максимальное количество элементов, которые могут быть получены детерминированным алгоритмом за следующие 256 раундов, также равно x. В 2004 году это предположение было доказано Сорадюти Полом (англ. Souradyuti Paul) и Бартом Пренелем (англ. Bart Preneel).
     Атака Ванхофа и Писсенса (2015)
     Летом 2015 года Мэти Ванхоф (Mathy Vanhoef) и Франк Писсенс (Frank Piessens) из университета Левена в Бельгии продемонстрировали реальную атаку на протокол TLS, использующий RC4 для шифрования передаваемых данных. Идея взлома базируется на принципе MITM. Встроившись в канал передачи данных, атакующая сторона генерирует серверу большое количество запросов, вынуждая его в ответ возвращать куки, зашифрованные одним и тем же ключом. Имея в распоряжении около 9x227 ~ 230 пар {открытый текст, шифротекст}, атакующая сторона получила возможность на основе статистических методов Флюрер-Макгрю и ABSAB с вероятностью 94 % восстановить ключ и, следовательно, зашифрованные куки. Практические временные затраты составили около 52 часов, верхняя же оценка потребного времени на момент демонстрации составила около 72 часов.
     Модификации RC4
     Ранее рассматривались атаки, основанные на коррелируемости первых байт шифрованного текста и ключа. Подобные слабости алгоритма могут быть решены отбрасыванием начальной части шифрованного текста. Надёжным считается отбрасывание первых 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, используется в единственном числе для всего алгоритма. Принцип выполнения алгоритма остается прежним, но имеется ряд отличий:
     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
     Скорость шифрования данного алгоритма может быть увеличена за счёт распараллеливания.
     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
     Weak Keys in RC4
     Это архив авторских постов Эндрю Руса, сделанных в 1995 году, чтобы объявить о своем открытии слабостей ключей в RC4. Хотя большинство точек доступа беспроводной сети избегают эти ключи, спустя много лет это открытые привело к отказу от RC4 для использования в WEP (Проводной Эквивалент Конфиденциальности) для Wi-Fi сетей, поскольку конфиденциальность более не была гарантирована. Вторая часть его исследования находится в следующем посте.
     INTRODUCTION
     Эта статья обсуждает класс слабых ключей в потоковом шифре RSA’s RC4. Это показывает, что для менее 1 из всех 256 возможных ключей начальный байт псевдо-случайного потока, генерируемого RC4 является сильно коррелируемым с только несколькими байтами ключа, который эффективно уменьшает необходимую работу для полного исследования пространства ключей RC4.
     2. STATE TABLE INITIALIZATION IN RC4
     Хотя алгоритм RC4 не был опубликован RSA Data Security, источник кода реализации алгоритма был анонимно опубликован в списке рассылок Cypherpunks несколько месяцев назад. Успех атаки грубой силы Cypherpunks на SSL с 40-битным ключом указывает на то, что опубликованный исходный код точно реализовал RC4
     RC4 использует переменную длину ключа от 1 до 256 байтов для инициализации 256 байтовой таблицы состояний, которая используется для последующей генерации псевдо-рандомных байтов. Таблица состояний сначала инициализируется таблицей {0,1,2,…,255}. Затем:
     1    index1 = 0;
     2    index2 = 0;
     3
     4    for(counter = 0; counter < 256; counter++)
     5    {
     6        index2 = (key_data_ptr[index1] + state[counter] + index2) % 256;
     7        swap_byte(&state[counter], &state[index2]);
     8        index1 = (index1 + 1) % key_data_len;
     9    }
     Обратите внимание, что единственная строка, которая непосредственно влияет на таблицу состояний – это 7 строка, в которой меняются 2 байта таблицы состояний. Первый байт обозначается как „counter“, который увеличивается с каждой итерацией цикла. Второй байт обозначается „index2“, который является функцией ключа. Следовательно, каждый элемент таблицы состояний будет меняться хотя бы 1 раз (хотя возможно и с собой), когда он индексируется как „counter“. Если мы предположим, что „index2“ – это равномерно распределенное псевдо-случайное число, то вероятность, что конкретный элемент таблицы состояний будет индексироваться как „index2“ на некоторое время во время обычной инициализации является:
          P = 1 - (255/256) ^ 255
            = 0.631
      (Показатель 255, потому-что мы можем игнорировать случай, когда „index2“ и „counter“ индексируют один и тот же элемент, поскольку это не повлияет на его значение )
     И наоборот, существует 37% вероятность того, что определенный элемент не будет индексироваться во время инициализации, поэтому его конечное значение в таблице инициализации будет зависеть от одного перемещения, когда он обозначается за „counter“. Поскольку ключевые байты используются последовательно (начиная с самого начала, когда ключ исчерпан) это подразумевает:
     A.   Given a key length of K bytes, and E < K, there is a 37% probability that
          element E of the state table depends only on elements 0..E (inclusive) of
          the key.
     (Это приблизительно, поскольку „index2“ вряд ли будет равномерно распределенным)
     Чтобы использовать это, нам нужно определить наиболее вероятные значения элементов таблицы состояний. Поскольку каждый элемент меняется хотя бы 1 раз (где он индексируется как „counter“), это необходимо брать в расчет вероятный эффект этого перемещения. Перемещение – это нелинейный процесс, который труден для анализа. Однако, при работе с первыми несколькими элементами таблицы состояний, существует вероятность того, что байт, с которым элемент переставлен, не был вовлечен в ранние обмены, и поэтому сохраняет начальные значения {0,1,2,…,255}. Аналогично, когда имеется дела с первыми несколькими элементами таблицы состояний, существует также значительная вероятность того, что ни один элемент таблицы состояния, добавленных к index2 в 6 строке алгоритма был заменен другим.
     Это означает, что более вероятно элемент в таблице состояний мог быть в предположении, приблизительно state[x] == x в алгоритме выше. В этом случае,
     1    index1 = 0;
     2    index2 = 0;
     3
     4    for(counter = 0; counter < 256; counter++)
     5    {
     6        index2 = (key_data_ptr[index1] + counter + index2) % 256;
     7        state[counter] = index2;
     8        index1 = (index1 + 1) % key_data_len;
     9    }
     Что может быть сокращенно до:
     B.   The most likely value for element E of the state table is:
          S[E] = X(E) + E(E+1)/2
          where X(E) is the sum of bytes 0..E (inclusive) of the key.
     (где подсчитана сумма элементов ключа, ключ считается «повернутым вокруг» себя).
     Учитывая этот анализ, мы можем посчитать вероятность для каждого элемента в таблице состояний, что его значение является «наиболее вероятным значением» в B выше. Простейший путь до этого – это оценивать произведенную таблицу состояний числом псевдо-случайной генерации ключей RC4. Следующая таблица показывает результат для первых 47 элементов из пробы 100 000 восьмидесяти-битных ключей RC4.
               Probability (%)
     0-7       37.0  36.8  36.2  35.8  34.9  34.0  33.0  32.2
     8-15      30.9  29.8  28.5  27.5  26.0  24.5  22.9  21.6
     16-23     20.3  18.9  17.3  16.1  14.7  13.5  12.4  11.2
     24-31     10.1   9.0   8.2   7.4   6.4   5.7   5.1   4.4
     32-39      3.9   3.5   3.0   2.6   2.3   2.0   1.7   1.4
     40-47      1.3   1.2   1.0   0.9   0.8   0.7   0.6   0.6
     Таблица подтверждает, что существует значительная корреляция м/у первыми несколькими значениями таблицы состояний и «вероятными значениями» предсказанными в B.
      WEAK KEYS
     Таблица состояний RC4 используется для генерации псевдо-случайного потока, с использованием операции XOR к открытому тексту для получения шифрованного текста. Для генерации потока используется следующий алгоритм:
          x and y are initialized to 0.
          To generate each byte:
     1    x = (x + 1) % 256;
     2    y = (state[x] + y) % 256;
     3    swap_byte(&state[x], &state[y]);
     4    xorIndex = (state[x] + state[y]) % 256;
     5    GeneratedByte = state[xorIndex];
     Один из способов использования нашего анализа таблицы состояний – это найти обстоятельства, при которых 1 или более сгенерированных байтов сильно коррелирует с небольшим подмножеством байтов ключа.
     Рассмотрим, что происходит при генерации первого байта, если state[1] == 1
     1    x = (0 + 1) % 256;                  /* x == 1 */
     2    y = (state[1] + 0) % 256;           /* y == 1 */
     3    swap_byte(&state[1], &state[1]);    /* no effect */
     4    xorIndex = (state[1] + state[1]);   /* xorIndex = 2 */
     5    GeneratedByte = state[2]
     И мы знаем, что state[2] имеет высокую вероятность быть
          S[2] = K[0] + K[1] + K[2] + 2 (2+1) / 2
     Аналогично,
          S[1] = K[0] + K[1] + 1 (1+1) / 2
     Таким образом, чтобы сделать вероятным, что S[1] == 1, мы имеем
          K[0] + K[1] == 0 (mod 256)
     В этом случае, большая вероятность значения для S[2] является:
          S[2] = K[2] + 3
     Это позволяет определить класс слабых ключей:
     C.   Given an RC4 key K[0]..K[N] with K[0] + K[1] == 0 (mod 256), there is a
          significant probability that the first byte generated by RC4 will be
          K[2] + 3 (mod 256).
     Обратите внимание, что существует 2 специальных случая, вызванных «внезапной» перестановкой во время генерации ключа. Это когда K[0]==1, «ожидаемый» выходной байт будет K[2] + 2 и когда K[0]==2, ожидаемым значением получается K[2] + 1.
     Существует несколько подобных классов "слабых ключей", которые только влияют на несколько ключей из любых 65536. Однако, конкретно симметрия в этом классе означает, что их влияние 1 ключа из 256, что делает их более интересным экземпляром.
     Еще раз я взял легкий выход и использовал моделирование для определения аппроксимации вероятности, которая в результате C выполняется для любого полученного ключа. Вероятность колеблется м/у 12% и 16% в зависимости от значений K[0] и K[1], в среднем около 13.8%. Все эти значения значительно больше, чем 0.39%, которые должны быть ожидаемы для некоррелированной генерации. Длина ключа снова была 80 бит. Это работает и наоборот: заданный первый байт B[0] генерируется слабым ключом, вероятность, что K[2]==B[0]-3 (mod 256) является 13.8%.
     4. EXPLOITING WEAK KEYS IN RC4
     Найдя класс слабых ключей, мы имеем практический способ для атаки криптосистем, основанных на RC4. Самый очевидный способ, должен быть, поиском потенциально слабых ключей первыми во время исчерпывающей атаки. Однако, поскольку только 1 из всех 256 ключей является слабым, эффективное сокращение в пространстве поиска будет не особо значимым.
     Полезность слабых ключей увеличивается, только если оппонент удовлетворен восстановлением процента ключей, подвергнутых анализу. Полученные знания генерации, которые включают первую генерацию байт, должны предполагать, что ключ был слабым и исследовать только слабые ключи, которые генерируют известный начальный байт. Поскольку 1 из 256 ключей – слабый, и существует 13.8% шанс, что предполагаемое значение K[2] было корректно, существует только a 0.054% вер-ть нахождения ключа этим способом. Однако, мы имеем уменьшенное количество исследований значений K[2], так фактор работы в взятый ключ уменьшен фактором 35, которое соответствующее уменьшая эффективную длину ключа 5,1 битами.
     Однако, в особых случаях, знание зависимости м/у слабыми ключами может обеспечить гораздо более значительное сокращение в рабочей нагрузке. Остаток этой секции описывает атаку, которая, хотя требует очень специфических условий, показывает потенциальную опасность.
     В качестве потокового шифра, конкретный ключ RC4 может использоваться только 1 раз. Если требуется несколько сеансов связи, необходимо предусмотреть определенный механизм для создания нового ключа сеанса каждый раз. Давайте предположим, что реализация шанса простого метода увеличение ключа предыдущей сессии, чтобы получить ключ новой сессии, и что сессионный ключ считается как „little endian“ (наименее значимый байт первый) включительно для этой цели.
     Мы теперь имеем интересную ситуацию, что сессионные ключи будут «циклом до конца» слабых ключей в шаблоне, которые повторяется каждые 2^16 ключей:
     00 00 00 ...    Weak
     (510 non-weak keys)
     FF 01 00 ...    Weak
     (254 non-weak keys)
     FE 02 00 ...    Weak
     (254 non-weak keys)
     FD 03 00 ...    Weak
     ...
     01 FF 00 ...    Weak
     (254 non-weak keys)
     00 00 01 ...    Weak
     (510 non-weak keys)
     FF 01 01 ...    Weak
     FC C1 11 8 = 1ДД 
     (Наименьший значащий байт слева)
     Теперь, пока изолированный слабый ключ не может быть идентифицирован просто знанием выходной генерации, этот цикл слабых ключей с известными интервалами м.б. идентифицирован с использованием статических технологий, поскольку каждый из слабых ключей имеет высшую, чем ожидаемую вер-ть генерации того же начального байта. Это означает, что оппонент, который знает начальную генерацию байтов об 2^16 сессионных ключей, может идентифицировать слабые ключи и м.б. также умело определить 510-ключевой разрыв м/у последующими циклами слабых ключей (хотя не точно).
     Поскольку 510-ключевой разрыв происходит сразу следующим ключом, который начинается с 00 00, оппонент не только знает, что ключи являются слабыми, но также знает первые 2 байта каждого ключа. Третий байт каждого ключа может быть угадан от первого выходного сгенерированного байта ключа с 13.8% шансом правильной догадки. Предполагая, что“ 510-key gap " сужается до 1 из 8 слабых ключей, злоумышленник может искать пространство ключей, которое на 24 бита меньше размера сеансовых ключей, с вероятностью успеха 13,8% / 8, эффективно уменьшая пространство ключей примерно на 18 бит
     Хотя такая практическая атака зависит от многих специфических факторов, это является вероятным, что другие криптосистемы на RC4, в которых существует линейная зависимость м/у последующими сессионными ключами д.б. уязвимой для подобной атаки
     5. RECOMMENDATIONS
     Атаки, описанные в этом алгоритме, являются результатом неадекватного "смешивания" ключевых байтов во время генерации таблицы состояний RC4. Для укрепления криптосистем на основе алгоритма RC4 могут быть приняты следующие меры 
      (a) После инициализации алгоритма и генерации, отбрасывайте несколько байт. Поскольку алгоритм использует для генерации байтов также внедряет дополнительные нелинейные зависимости в таблице состояний, это бы сделало анализ более трудным
     (б) В системах, где требуется несколько сеансовых ключей, убедитесь, что сеансовые ключи не связаны друг с другом линейно
     (с) Избегайте использования описанных слабых клавиш
     6. CONCLUSION
     Предварительный анализ RC4 показывает, что алгоритм уязвим к аналитическим атакам на основе статистического анализа его таблицы состояний. Вполне вероятно, что более детальный анализ алгоритма позволит выявить более эффективные способы использования описанных недостатков.
      
.......................