Криптография
9 января 2011

Простая реализация RC4 на C#

Из песочницы
RC4

Введение


Одно время я играл в одну довольно известную в рунете MMORPG. Потратил на нее довольно много времени, но вскоре игровой процесс мне наскучил. Однако появилось желание узнать как работает игра и попытаться сделать к ней различные прибамбасы. Первым результатом стал кривой бот, написанный на C# и умеющий бить мобов, но он тоже быстро стал неинтересен. К тому времени я наткнулся на форум, связанный со взломом игр и, в частности, тему одного талантливого программиста, который на досуге решил разобрать трафик игры. Это меня сильно заинтересовало и я решил повторить его достижение.

Вооружившись Wireshark'ом я получил несколько дампов и был, честно говоря, ошарашен содержимым. К шестнадцатеричным значениям было уже не привыкать, но вот структуры никакой вычленить было невозможно. Так как опыт в системном программировании у меня совсем небольшой, я решил воспользоваться советами профессионала (автора темы) и попросить у него наводку: в какую сторону копать. Кроме общих рекомендаций, я узнал, что трафик игры зашифрован при помощи алгоритма RC4, а данные сервера к тому же сжимаются (об этом в другой раз). Направление было задано и я начал изучать алгоритм, чтобы реализовать его на C#.



Общие сведения о RC4


Итак, RC4 является потоковым шифром (stream cipher), что означает, что каждый символ открытого (незашифрованного) текста будет зашифрован в зависимости от двух параметров: ключа и положения символа в открытом тексте. В следующем разделе я поясню, как это работает.

Создал данный алгоритм шифрования профессор Массачусетского технологического института, Рональд Ривест, которому мы также обязаны такими алгоритмами, как RC2, RC5, RC6, RSA и линейкой хэшей MD2-MD6.

Несмотря на то, что вряд ли кто-то будет применять RC4 в новых ответственных проектах в связи с известными уязвимостями, существует целый ряд технологий которые его используют. Примерами таких технологий являются WEP, SSL, TLS. Также, в моем примере, его решили использовать и разработчики одной из MMORPG.

Алгоритм


Хочу, чтобы каждый мог понять, как работает RC4, потому буду объяснять на пальцах.

Итак, входными данными у нас будет выступать массив байт. Это может быть любая информация: голос, изображение, текст. Конечно, информация может поступать в виде потока, но что такое поток, если не длинный массив?
Какое же шифрование без ключа!? Ключ тоже выступает в качестве входных данных. Для алгоритма RC4 он может быть от 8 до 2048 бит, но обычно используется диапазон 40 — 256 бит.
Но данные для шифрования у нас — массив байт, а ключ почему-то в битах. Дело в том, что существует такое понятие как размер блока n. Для примера мы будем использовать n=8, но алгоритм будет даже более криптостоек, если взять n=16. Тогда за один шаг будут шифроваться сразу 2 байта.

Идеальным вариантом с точки зрения стойкости для потокового шифра, является размер ключа, сопоставимый с размером шифруемых данных. Тогда каждый бит открытого текста объединяется с соответствующим битом ключа посредством суммирования по модулю 2 (XOR), образуя зашифрованную последовательность. Для расшифровки требуется проделать ту же операцию еще раз на принимающей стороне.
Принцип шифрования
При условии, что последовательность битов ключа выбирается произвольно и не имеет периодов, взломать шифр невозможно, но возникает проблема передачи длинного ключа. Поэтому на практике для генерации ключевого потока используется генератор псевдослучайных чисел на основе заданного ключа. То есть мы расширяем наш ключ до любого размера (динамически, во время обработки входных данных) и XOR'ом объединяем его с входными данными.

Конкретно будем разбираться с алгоритмом на примере С#. Создадим класс «RC4» и объявим следующие члены:
byte[] S = new byte[256];
int x = 0;
int y = 0;


Для генерации ключевого потока шифр использует скрытое внутреннее состояние, состоящее из двух частей:
Перестановки, содержащей все возможные байты от 0x00 до 0xFF (массив S).
— Переменных-счетчиков x и y.

Для начальной инициализация вектора-перестановки ключём, используется алгоритм ключевого расписания (Key-Scheduling Algorithm):
    private void init(byte[] key)
    {
      int keyLength = key.Length;

      for (int i = 0; i < 256; i++)
      {
        S[i] = (byte)i;
      }

      int j = 0;
      for (int i = 0; i < 256; i++)
      {
        j = (j + S[i] + key[i % keyLength]) % 256;
        S.Swap(i, j);      
      }
    }

С точки зрения кода, ничего сложного. Хочу только отметить, что метод Swap (поменять два элемента массива местами) расширяет стандартный список методов класса Array:
  static class SwapExt
  {
    public static void Swap(this T[] array, int index1, int index2)
    {
      T temp = array[index1];
      array[index1] = array[index2];
      array[index2] = temp;
    }
  }


Метод init нужно вызвать перед шифровкой/расшифровкой, когда известен ключ. Можно сделать это в конструкторе:
    public RC4(byte[] key)
    {
      init(key);
    }


Дальше нужно реализовать генератор псевдослучайной последовательности (Pseudo-Random Generation Algorithm). При каждом вызове метод будет выплевывать последующий байт ключевого потока, который мы и будем объединять xor'ом c байтом исходных данных.
    private byte keyItem()
    {
      x = (x + 1) % 256;
      y = (y + S[x]) % 256;

      S.Swap(x, y);

      return S[(S[x] + S[y]) % 256];
    } 


Теперь осталось самое простое! Для каждого байта массива/потока входных незашифрованных данных запрашиваем байт ключа и объединяем их при помощи xor (^):
    public byte[] Encode(byte[] dataB, int size)
    {   
      byte[] data = dataB.Take(size).ToArray();       

      byte[] cipher = new byte[data.Length];

      for (int m = 0; m < data.Length; m++)
      {       
        cipher[m] = (byte)(data[m] ^ keyItem());
      }

      return cipher;
    }


Для расшифровки можно использовать этот же метод. Завернем его в отдельный метод для наглядности:
    public byte[] Decode(byte[] dataB, int size)
    {
      return Encode(dataB, size);
    }


Пример, как можно использовать этот класс:
byte[] key = ASCIIEncoding.ASCII.GetBytes("Key");

RC4 encoder = new RC4(key);
string testString = "Plaintext";
byte[] testBytes = ASCIIEncoding.ASCII.GetBytes(testString);
byte[] result = encoder.Encode(testBytes, testBytes.Length);

RC4 decoder = new RC4(key);
byte[] decryptedBytes = decoder.Decode(result, result.Length);
string decryptedString = ASCIIEncoding.ASCII.GetString(decryptedBytes);


И вот результат, чтобы убедиться, что все правильно работает:
Результат работы RC4

Реализацией класса, дешифрующего трафик, мы на шаг приблизились к разбору пакетов.

В заключение скажу, что данная реализация наиболее простая и очевидная. Ее можно усложнить, чтобы повысить стойкость ко взлому.

Большое Спасибо моему знакомому Vort за советы и рекомендации.

Ссылка на исходник целиком:
SourceForge — RC4.cs

+29
50,4k 51
Комментарии 15