Просмотр отдельных изменений

''''RC4''' ({{lang-en|'''Rivest Cipher 4'''}} или {{lang-en|'''Ron’s Code'''}}, также известен как '''ARCFOUR''' или '''ARC4''' ({{lang-en|'''Alleged RC4'''}})) — это [[потоковый шифр]], широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколах [[SSL]] и [[TLS]], алгоритме безопасности беспроводных сетей [[WEP]], для шифрования паролей в [[Windows NT]]). Шифр разработан компанией [[:en:RSA Security|RSA Security]] и для его использования требуется [[лицензия]]. Алгоритм RC4 строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов с равномерным распределением. Длина ключа может составлять от 40 до 256 бит<ref name="KLEIN_ATTACKS">{{cite journal |author=A. Klein |title=Attacks on the RC4 stream cipher |journal=Designs, Codes and Cryptography |year=2008 |volume=48 |issue=3 |pages=269—286 |doi=10.1007/s10623-008-9206-6 |url=http://www.networklife.net/images/wep-rc4/RC4.pdf}}</ref>. Основные преимущества шифра — высокая скорость работы и переменный размер ключа. RC4 довольно уязвим, если используются не случайные или связанные ключи, один ключевой поток используется дважды. Эти факторы, а также способ использования могут сделать [[Криптосистема|криптосистему]] небезопасной (например [[WEP]]). == История == [[Потоковый шифр]] RC4 был создан [[Ривест,_Рональд_Линн|Роном Ривестом]] из [[:en:RSA Security|RSA Security]] в [[1987 год]]у. Хотя официально сокращение обозначает ''Rivest Cipher 4'', его часто считают сокращением от ''Ron’s Code''<ref>[http://people.csail.mit.edu/rivest/faq.html#Ron Rivest FAQ]</ref>. Шифр являлся [[Коммерческая тайна|коммерческой тайной]], но в сентябре [[1994 год]]а его описание было анонимно отправлено в рассылку [[Cypherpunks]]<ref>{{cite mailing list |url=http://cypherpunks.venona.com/date/1994/09/msg00304.html |title=Thank you Bob Anderson |date=1994-09-09 |accessdate=2007-05-28 |mailinglist=[[Cypherpunks]]}}</ref>. Вскоре описание RC4 было опубликовано в ньюс-группе [http://groups.google.com/group/sci.crypt sci.crypt]. Именно оттуда исходный код попал на множество сайтов в сети [[Интернет]]. Опубликованный шифр давал те же [[шифротекст]]ы на выходе, какие давал подлинный RC4. По-видимому, данный текст был получен в результате анализа исполняемого кода. Опубликованный шифр совместим с имеющимися продуктами, использующими RC4, а некоторые участники телеконференции, имевшие, по их словам, доступ к исходному коду RC4, подтвердили идентичность алгоритмов при различиях в обозначениях и структуре программы. Поскольку данный [[алгоритм]] известен, он более не является [[Коммерческая тайна|коммерческой тайной]]. Однако, название «RC4» является [[Товарный знак|торговой маркой]] компании [[:en:RSA Security|RSA]]. Поэтому иногда шифр называют «ARCFOUR» или «ARC4» (имея ввиду '''A'''lleged '''RC4''' — предполагаемый RC4, поскольку [[:en:RSA Security|RSA]] официально не опубликовала алгоритм), чтобы избежать возможных претензий со стороны владельца [[Товарный знак|торговой марки]]. Шифр RC4 применяется в некоторых широко распространённых стандартах и протоколах шифрования таких, как [[WEP]], [[WPA]] и [[TLS]]. Главными факторами, способствовавшими широкому применению RC4, были простота его аппаратной и программной реализации, а также высокая скорость работы алгоритма в обоих случаях. В [[США]] длина ключа для использования внутри страны рекомендуется равной 128 битов, но соглашение, заключённое между Software Publishers Association (SPA) и правительством США даёт RC4 специальный статус, который означает, что разрешено экспортировать шифры длиной ключа до 40 бит. 56-битные ключи разрешено использовать заграничным отделениям американских компаний. == Описание алгоритма == [[Файл:RC4.png|right|thumbnail|320px|Генератор ключевого потока RC4]] Ядро алгоритма состоит из функции генерации ключевого потока. Эта функция генерирует последовательность битов (<math>k_i</math>), которая затем объединяется с открытым текстом (<math>m_i</math>) посредством [[Сложение по модулю 2|суммирования по модулю два]]. Так получается шифрограмма (<math>c_i</math>): <math>c_i = m_i \oplus k_i</math>. Расшифровка заключается в регенерации этого ключевого потока (<math>k_i</math>) и сложении его и шифрограммы (<math>c_i</math>) по модулю два. В силу свойств [[Сложение по модулю 2|суммирования по модулю два]] на выходе мы получим исходный незашифрованный текст(<math>m_i</math>): <math>m_i = c_i \oplus k_i = (m_i \oplus k_i) \oplus k_i</math> Другая главная часть алгоритма — функция инициализации, которая использует ключ переменной длины для создания начального состояния генератора ключевого потока. RC4 — фактически класс алгоритмов, определяемых размером его блока. Этот параметр ''n'' является размером слова для алгоритма. Обычно, ''n'' = 8, но в целях анализа можно уменьшить его. Однако для повышения безопасности необходимо увеличить эту величину. Внутреннее состояние RC4 представляется в виде массива слов размером 2^''n'' и двух счетчиков, каждый размером в одно слово. Массив известен как ''S-бокс'', и далее будет обозначаться как ''S''. Он всегда содержит перестановку 2^''n'' возможных значений слова. Два счетчика обозначены через ''i'' и ''j''. Алгоритм инициализации RC4 приведен ниже. Этот алгоритм также называется алгоритмом ключевого расписания ({{lang-en|'''Key-Scheduling Algorithm''' or '''KSA'''}}). Этот алгоритм использует ключ, сохраненный в ''Key'', и имеющий длину ''L'' байт. Инициализация начинается с заполнения массива ''S'', далее этот массив перемешивается путем перестановок, определяемых ключом. Так как только одно действие выполняется над ''S'', то должно выполняться утверждение, что ''S'' всегда содержит все значения кодового слова. Начальное заполнение массива: <!-- Кажется, лучше использовать <source> --> '''for''' i = 0 to 2ⁿ − 1 S[ i ] = i Скремблирование: j = 0 '''for''' i = 0 to 2ⁿ − 1 j = ( j + S[ i ] + Key[ i mod L ] ) mod 2ⁿ <br /> Перестановка( S[ i ], S[ j ] ) Генератор ключевого потока RC4 переставляет значения, хранящиеся в ''S'', и каждый раз выбирает различное значение из ''S'' в качестве результата. В одном цикле RC4 определяется одно ''n''-битное слово ''K'' из ключевого потока, которое в последующем суммируется с исходным текстом для получения зашифрованного текста. Эта часть алгоритма называется генератором псевдослучайной последовательности ({{lang-en|'''Pseudo-Random Generation Algorithm''' or '''PRGA'''}}). Инициализация: i = 0 j = 0 Цикл генерации: i = ( i + 1 ) mod 2ⁿ j = ( j + S[ i ] ) mod 2ⁿ Перестановка( S[ i ], S[ j ] ) Результат: K = S[ ( S[ i ] + S[ j ] ) mod 2ⁿ ] == Безопасность == В отличие от современных шифров (таких, как в [[:en:eSTREAM|eSTREAM]]), RC4 не использует отдельной оказии ({{lang-en|'''nonce'''}}) наряду с ключом. Это значит, что если один ключ должен использоваться в течение долгого времени для шифрования нескольких потоков, сама криптосистема, использующая RC4, должна комбинировать оказию и долгосрочный ключ для получения потокового ключа для RC4. Один из возможных выходов — генерировать '''новый''' ключ для RC4 с помощью хэш-функции от долгосрочного ключа и оказии. Однако, многие приложения, использующие RC4, просто конкатенируют ключ и оказию. Из-за этого и слабого расписания ключей, используемого в RC4, приложение может стать уязвимым. Здесь будут рассмотрены некоторые атаки на шифр и методы защиты от них. === Манипуляция битами === Шифр RC4 крайне уязвим к манипуляции битами, если он не реализован верным образом. И поэтому он был признан устаревшим многими софтверными компаниями, такими как [[Microsoft]]. Например, в [[.NET Framework]] от [[Microsoft]] отсутствует реализация RC4. === Исследования Руза и восстановление ключа из перестановки === В 1995 году Андрю Руз ({{lang-en|'''Andrew Roos'''}}) экспериментально пронаблюдал, что первый байт ключевого потока коррелирован с первыми тремя байтами ключа, а первые несколько байт перестановки после алгоритма расписания ключей ({{lang-en|'''KSA'''}}) коррелированы с некоторой линейной комбинацией байт ключа. Эти смещения не были доказаны до 2007 года, когда Пол, Рафи и Мэйтрэ доказали коррелированность ключа и ключевого потока. Также Пол и Мэйтрэ доказали коррелированность перестановки и ключа. Последняя работа также использует коррелированность ключа и перестановки для того, чтобы создать первый алгоритм полного восстановления ключа из последней перестановки после KSA, не делая предположений о ключе и векторе инициализации ({{lang-en|'''IV''' or '''Initial Vector'''}}). Этот алгоритм имеет постоянную вероятность успеха в зависимости от времени, которая соответствует квадратному корню из сложности полного перебора. Позднее было сделано много работ о восстановлении ключа из внутреннего состояния RC4. === Атака Флурера, Мантина и Шамира (ФМШ) === В 2001 году, Флурер, Мантин и Шамир опубликовали работу об уязвимости ключевого расписания RC4. Они показали, что среди всех возможных ключей, первые несколько байт ключевого потока являются совсем неслучайными. Из этих байт можно с высокой вероятностью получить информацию о используемом шифром ключе. И если долговременный ключ и оказия ({{lang-en|'''nonce'''}}) просто конкатенируются для создания ключа шифра RC4, то этот долговременный ключ может быть получен с помощью анализа достаточно большого количества сообщений, зашифрованных с использованием данного ключа<ref>{{cite journal |author=Scott R. Fluhrer, Itsik Mantin, Adi Shamir |title=Weaknesses in the Key Scheduling Algorithm of RC4 |journal=Lecture Notes in Computer Science |volume=2259 |year=2001 |pages=1—24 |doi=10.1007/3-540-45537-X_1 |url=http://www.math.psu.edu/mathnet/mdoc/md15/rc4_ksaproc-1.pdf}}</ref>. Эта уязвимость и некоторые связанные с ней эффекты были использованы при взломе шифрования [[WEP]] в беспроводных сетях стандарта IEEE 802.11. Это показало необходимость скорейшей замены [[WEP]], что повлекло за собой разработку нового стандарта безопасности беспроводных сетей [[WPA]]. Криптосистему можно сделать невосприимчивой к этой атаке, если отбрасывать начало ключевого потока. Таким образом модифицированный алгоритм называется «RC4-drop[n]», где n — количество байт из начала ключевого потока, которые следует отбросить. Рекомендовано использовать n = 768, консервативная оценка составляет n = 3072<ref>{{cite journal |author=I. Mironov |title=(Not so) random shuffles of RC4 |journal=Lecture Notes in Computer Science |year=2002 |volume=2442 |pages=304—319 |doi=10.1007/3-540-45708-9_20 |url=http://eprint.iacr.org/2002/067.pdf}}</ref><ref>[http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#RC4-drop «RC4-drop(nbytes)»]. ''«Standard Cryptographic Algorithm Naming»'' database.</ref>. === Атака Кляйна === В 2005 году Андреас Кляйн представил анализ шифра RC4, в котором он указал на сильную коррелированность ключа и ключевого потока RC4. Кляйн проанализировал атаки на первом раунде (подобные атаке ФМШ), на втором раунде и возможные их улучшения. Он также предложил некоторые изменения алгоритма для усиления стойкости шифра. В частности, он утверждает, что если поменять направление цикла на обратное в алгоритме ключевого расписания, то можно сделать шифр более стойким к атакам типа ФМШ<ref name="KLEIN_ATTACKS"/>. === Комбинаторная проблема === В 2001 году Ади Шамир и Ицхак Мантин первыми поставили комбинаторную проблему, связанную с количеством всевозможных входных и выходных данных шифра RC4. Если из всевозможных 256 элементов внутреннего состояния шифра известно ''x'' элементов из состояния (''x'' ≤ 256), то, если предположить, что остальные элементы нулевые, максимальное количество элементов, которые могут быть получены детерминированным алгоритмом за следующие 256 раундов также равно ''x''. В 2004 году это предположение было доказано Сорадюти Полом ({{lang-en|'''Souradyuti Paul'''}}) и Бартом Прэнилом ({{lang-en|'''Bart Preneel'''}}).<ref>{{cite journal |author=Souradyuti Paul, Bart Preneel |title=A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher |journal=Lecture Notes in Computer Science |volume=3017 |year=2004 |pages=245—259 |doi=10.1007/b98177 |url=http://www.cosic.esat.kuleuven.be/publications/article-40.pdf}}</ref> == Реализация == Работа многих [[Поточный шифр|поточных шифров]] основана на [[Линейный регистр сдвига с обратной связью|линейных регистрах сдвига с обратной связью]] (LFSR). Это позволяет достичь высокой эффективности реализаций шифра в виде [[Интегральная схема|ИС]]. Но затрудняет программную реализацию таких шифров. Поскольку шифр RC4 не использует LFSR и основан на байтовых операциях, его удобно реализовывать программно. Типичная реализация выполняет от 8 до 16 машинных команд на каждый [[Байт|байт]] текста, поэтому программная реализация шифра должна работать очень быстро<ref>[http://www.rsa.com/rsalabs/node.asp?id=2250# RSA Laboratories - 3.6.3 What is RC4?]</ref>. Пример реализации RC4 на языке [[C_(язык_программирования)|C]]: <source lang = "c"> unsigned char S[ 256 ]; unsigned int i, j; /* ключевое расписание */ void rc4_init( unsigned const char* key, unsigned int key_length ) { unsigned char temp; for( i = 0; i != 256; ++i ) S[ i ] = i; for( i = j = 0; i != 256; ++i ) { j = ( j + key[ i % key_length ] + S[ i ] ) % 256; temp = S[ i ]; S[ i ] = S[ j ]; S[ j ] = temp; } i = j = 0; } /* Вывод одного псевдослучайного байта */ unsigned char rc4_output() { unsigned char temp; i = ( i + 1 ) % 256; j = ( j + S[ i ] ) % 256; temp = S[ j ]; S[ j ] = S[ i ]; S[ i ] = temp; return S[ ( temp + S[ j ] ) % 256 ]; } </source> == Реализация алгоритма на языке [[C#_(язык_программирования)|C#]] == Пример реализации класса RC4: <source lang = "csharp"> using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace rc4 { public class RC4 { public byte[] text; //текст для шифрования/расшифрования private byte[] S = new byte[256]; private int i = 0; private int j = 0; //просто для удобства обмена private void swap(byte[] array, int ind1, int ind2) { byte temp = array[ind1]; array[ind1] = array[ind2]; array[ind2] = temp; } //инициализация, алгоритм ключевого расписания public void init(byte[] key) { for (int i = 0; i < 256; i++) { S[i] = (byte)i; } j = 0; for (int i = 0; i < 256; i++) { j = (j + S[i] + key[i % key.Length]) % 256; swap(S, i, j); } } //генератор псевдослучайной последовательности public byte kword () { i = (i + 1) % 256; j = (j + S[i]) % 256; swap(S, i, j); byte K = S[(S[i] + S[j]) % 256]; return K; } //функция шифрования/расшифрования public byte[] code() { byte[] data = text.Take(text.Length).ToArray(); byte[] res = new byte[data.Length]; for (int i = 0; i < data.Length; i++) { res[i] = (byte)(data[i] ^ kword()); } return res; } //бинарная запись в файл public void WriteByteArrayToFile (Byte[] buffer, string fileName) { try { FileStream fs = new FileStream(fileName, FileMode.Create, FileAccess.ReadWrite); BinaryWriter bw = new BinaryWriter(fs); for (int i = 0; i < buffer.Length; i++) bw.Write(buffer[i]); bw.Close(); fs.Close(); } catch (Exception ex) { Console.WriteLine(ex.Message); } } //бинарное чтение из файла public Byte[] ReadByteArrayFromFile (string fileName) { Byte[] buffer = null; try { FileStream fs = new FileStream(fileName, FileMode.Open, FileAccess.Read); BinaryReader br = new BinaryReader(fs); long numBytes = new FileInfo(fileName).Length; buffer = br.ReadBytes((int) numBytes); br.Close(); fs.Close(); } catch (Exception ex) { Console.WriteLine(ex.Message); } return buffer; } } } </source> И пример использования вышеизложенного класса: <source lang = "csharp"> using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace rc4 { class Program { static void Main (string[] args) { int key = 0; Console.Write("Введите ключ: "); string query = Console.ReadLine(); int.TryParse(query, out key); byte[] bytekey = BitConverter.GetBytes(key); Console.Write("Входной файл: "); string infile = Console.ReadLine(); Console.Write("Результирующий файл: "); string outfile = Console.ReadLine(); var ob = new RC4(); var test = new StatisticTests(); while (1 == 1) { switch (menu()) { case (1): ob.text = ob.ReadByteArrayFromFile(infile); ob.init(bytekey); ob.WriteByteArrayToFile(ob.code(), outfile); Console.WriteLine("Сообщение зашифровано!"); Console.Read(); break; case (2): ob.text = ob.ReadByteArrayFromFile(infile); ob.init(bytekey); ob.WriteByteArrayToFile(ob.code(), outfile); Console.WriteLine("Сообщение расшифровано!"); Console.Read(); break; case (3): key = 0; Console.Write("Введите ключ: "); query = Console.ReadLine(); int.TryParse(query, out key); bytekey = BitConverter.GetBytes(key); Console.Write("Входной файл: "); infile = Console.ReadLine(); Console.Write("Результирующий файл: "); outfile = Console.ReadLine(); break; case (4): Environment.Exit(0); break; default: Console.WriteLine("Такого действия нет!"); break; } } } private static int menu() { Console.Clear(); Console.WriteLine("Выберите действие:"); Console.WriteLine(" 1. Шифровать"); Console.WriteLine(" 2. Дешифровать"); Console.WriteLine(" 3. Ввести новые данные"); Console.WriteLine(" 4. Выход"); Console.Write(" \n\n>>> "); string action = Console.ReadLine(); int act = 0; int.TryParse(action, out act); Console.Clear(); return act; } } } </source> == Примечания == {{примечания|2}} == Ссылки == * [http://www.rsasecurity.com/rsalabs/node.asp?id=2009 RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4] * [http://cypherpunks.venona.com/archive/1994/09/msg00304.html Original posting of RC4 algorithm to Cypherpunks mailing list] * [http://cage.ugent.be/~klein/RC4/RC4-en.ps A. Klein, Attacks on the RC4 stream cipher, February 27, 2006(post-script формат)] == См. также == * [[VMPC]] * [[:en:CipherSaber|CipherSaber(en)]] {{симметричные криптоалгоритмы}} [[Категория:Шифры]] [[bg:RC4]] [[cs:RC4]] [[de:RC4]] [[en:RC4]] [[es:RC4]] [[fi:RC4]] [[fr:RC4]] [[he:RC4]] [[hr:RC4]] [[it:RC4]] [[ja:RC4]] [[ko:RC4]] [[nl:RC4 (encryptie)]] [[pl:RC4]] [[pt:RC4]] [[simple:RC4]] [[sl:RC4]] [[sv:RC4]]'