Простая реализация 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
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 15

    +3
    Хорошая работа. Два замечания/совета:
    1. Подобные вещи очень желательно наследовать от System.Security.Cryptography.SymmetricAlgorithm и System.Security.Cryptography.ICryptoTransform — тогда вашу реализацию можно будет подсунуть любому другому классу, который работает с симметрическим шифрованием.
    2. Выложить это все на GitHub или SourceForge — это полезно для вас, как разработчика, все таки собственный опенсорсный проект, пусть даже и такой маленький — это замечательный «плюс в карму» для любого разработчика.
    П.С. К сожалению ссылка на исходник у меня почему-то не работает, поэтому я не могу его посмотреть.
      0
      Спасибо за комментарий!

      1. Попробую посмотреть, как это сделать. Это действительно придаст завершенности и пригодности этому проекту.
      2. Начал разбираться с SourceForge.net — создал проект и вставил ссылку на исходник оттуда. Вроде бы теперь все нормально.
        +4
        гугл находит 100500 реализация rc4 на c#
          +1
          Не могу с Вами не согласиться. Но во-первых я постараюсь довести реализацию до должного уровня на основе совета mace (см. выше), дабы она приобрела ценность, а во-вторых всё же я попробовал объяснить на русском языке, почему создавался этот алгоритм, как помодульно он реализуется, и чем же эти блоки занимаются.
          Это моя первая публикация, и я буду очень рад улучшить и расширить статью.
      0
      Ждем собирательного анализа криптоалгоритмов на базе сетей Фейстеля. И про ChipherSaber не забудьте :)
        –2
        К сожалению, ничего не сказано о том, что всё-такие такое ключ. У настоящего RC4 ключи генерируются на основе LFSR.
          0
          *всё-таки
            0
            Кхм, это вы с чего такое решили? В статье же С# по белому написано как генерируется псевдослучайная последовательность из ключа. И никакого LFSR там и близко не валялось. И вот, кстати, пруф на педивикии где уже русским языком написано цитирую: «Поскольку шифр RC4 не использует LFSR и основан на байтовых операциях, его удобно реализовывать программно.»
              0
              Вы правы, в самом алгоритме LFSR нет. Я лишь хотел сказать, что автор алгоритма рекомендовал генерировать ключи на основе LFSR. Т.е. сгенерировали последовательность и отдали вместо ключа. А что там под капотом уже не интересно.
            0
            Удалось трафик игры расшифровать? Если да, то как в итоге ключ удалось достать?
              +4
              Удалось. Для трафика клиента и сервера используются разные ключи и базами для генерации ключей клиент и сервер обмениваются в начальных пакетах в открытом виде. Конечный ключ формируется так: объединяется базовый ключ с хэшем пароля (passHash+baseKey), а затем объединение пропускается через HMACMD5 c логином в качестве ключа.
              Мой минус в том, что алгоритм получения конечного ключа, который я описал, получить возможно только с помощью реверс-инжиниринга программы клиента. Этого я не делал положившись на работу «старшего» программиста.
              Так же думаю, что многим будет интересна реализация протокола компрессии данных MPPC, реализацию которого даже на C достать через гугл невозможно. Он уже посложнее RC4, но на него есть RFC, хотя он не помогает до конца написать реализацию для распаковки серверного траффика игры в связи с тем, что разработчики внесли в него некоторые изменения. Думаю будет интереснее и мне и хабрасообществу проследить весь путь восстановления алгоритма из дизасм-листинга.
              +3
              у mono есть прекрасная реализация rc4, наследуемая от ICryptoTransform

              github.com/mono/mono/blob/master/mcs/class/Mono.Security/Mono.Security.Cryptography/ARC4Managed.cs

              p.s. Perfect World? :)
                +2
                Жаль, что уже есть. Сделано весьма приятно. Но я думаю это не помешает изобрести мне велосипед. Это будет хороший опыт.
                  –1
                  да, безусловно, иногда велосипедить полезно.
                  сам люблю криптографию, даже ВКР про нее написал. :)
                +1
                Тут есть все. www.bouncycastle.org/csharp/

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое