Алгоритм шифрования RC4

Размещено на http://www.allbest.ru

Реферат

по информационной безопасности и защите информации

На тему: «Алгоритм шифрования RC4»

2011г.

Содержание

Введение

1. Алгоритм RC4

2. Описание алгоритма

3. Генератор ключевого потока RC4

4. Алгоритм инициализации RC4

5. Безопасность

6. Манипуляция битами

7. Исследования Руза и восстановление ключа из перестановки

8. Атака Флурера, Мантина и Шамира (ФМШ)

9. Атака Кляйна

10. Комбинаторная проблема

Список литературы

Введение

Один из широко распространенных алгоритмов потокового шифрования - RC4 - был разработан в 1987г. Рональдом Линном Ривестом, известным американским специалистом в области криптографии, который также является соавтором алгоритма RSA, автором хэш-функции MD5 и целого ряда других активно используемых в криптографии хэш-функций и шифров. В течение нескольких лет алгоритм считался коммерческой тайной компании RSA Security, пока не был анонимно опубликован в 1994г. Начиная с этого времени, он нашел широкое применение в целом ряде криптографических приложений, включая такие известные, как SSL и TLS - для шифрования данных, передаваемых по сетям ЭВМ, не предусматривающим защиты пользовательских данных, WPA и WEP - для защиты беспроводных соединений.

Таким широким распространением алгоритм обязан ряду свойств, не утративших актуальности за двадцать лет его существования. Одно из них - высокое быстродействие. Хотя прогресс в развитии вычислительной техники в настоящее время существенно увеличил возможности применения более ресурсоемких методик шифрования, одновременно с этим значительно выросли и объемы данных, что до известной степени нивелирует указанное преимущество. Помимо этого, возник целый класс мобильных и встраиваемых устройств, для которых ключевой характеристикой является низкое энергопотребление, а, следовательно, к ним предъявляются повышенные требования экономности алгоритмов в плане вычислений. Среди таких устройств можно выделить смарт-карты, в которых может быть необходима функция шифрования данных, и мобильные устройства, подключающиеся к беспроводным сетям. Оба этих класса устройств переживают в настоящее время расцвет, что привлекает внимание к таким алгоритмам, как RC4.

1. Алгоритм RC4

алгоритм шифрование rc4 манипуляция бит

Алгоритм RC4 строится, как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов с равномерным распределением. Длина ключа может составлять от 40 до 256 бит.

Поскольку данный алгоритм известен, он более не является коммерческой тайной. Однако, название «RC4» является торговой маркой компании RSA. Поэтому иногда шифр называют «ARCFOUR» или «ARC4» (имея в виду Alleged RC4 -- предполагаемый RC4, поскольку RSA официально не опубликовала алгоритм), чтобы избежать возможных претензий со стороны владельца торговой марки.

Главными факторами, способствовавшими широкому применению RC4, были простота его аппаратной и программной реализации, а также высокая скорость работы алгоритма в обоих случаях.

В США длина ключа для использования внутри страны рекомендуется равной 128 битов, но соглашение, заключённое между Software Publishers Association (SPA) и правительством США даёт RC4 специальный статус, который означает, что разрешено экспортировать шифры длиной ключа до 40 бит. 56-битные ключи разрешено использовать заграничным отделениям американских компаний.

2. Описание алгоритма

3. Генератор ключевого потока RC4

Ядро алгоритма состоит из функции генерации ключевого потока. Эта функция генерирует последовательность битов (ki), которая затем объединяется с открытым текстом (mi) посредством суммирования по модулю два. Так получается шифрограмма (ci):

Расшифровка заключается в регенерации этого ключевого потока (ki) и сложении его и шифрограммы (ci) по модулю два. В силу свойств суммирования по модулю два на выходе мы получим исходный незашифрованный текст(mi):

Другая главная часть алгоритма -- функция инициализации, которая использует ключ переменной длины для создания начального состояния генератора ключевого потока.

RC4 -- фактически класс алгоритмов, определяемых размером его блока. Этот параметр n является размером слова для алгоритма. Обычно, n = 8, но в целях анализа можно уменьшить его. Однако для повышения безопасности необходимо увеличить эту величину. Внутреннее состояние RC4 представляется в виде массива слов размером 2n и двух счетчиков, каждый размером в одно слово. Массив известен как S-бокс oн всегда содержит перестановку 2n возможных значений слова. Два счетчика обозначены через i и j.

4. Алгоритм инициализации RC4

Алгоритм инициализации RC4 также называется алгоритмом ключевого расписания (англ. Key-Scheduling Algorithm or KSA). Этот алгоритм использует ключ, сохраненный в Key, и имеющий длину L байт. Инициализация начинается с заполнения массива S, далее этот массив перемешивается путем перестановок определяемых ключом. Так как только одно действие выполняется над S, то должно выполняться утверждение, что S всегда содержит все значения кодового слова.

Генератор ключевого потока RC4 переставляет значения, хранящиеся в S, и каждый раз выбирает различное значение из S в качестве результата. В одном цикле RC4 определяется одно n-битное слово K из ключевого потока, которое в последующем суммируется с исходным текстом для получения зашифрованного текста. Эта часть алгоритма называется генератором псевдослучайной последовательности (англ. Pseudo-Random Generation Algorithm or PRGA).

5. Безопасность

В отличие от современных шифров (таких, как в eSTREAM), RC4 не использует отдельной оказии (англ. nonce) наряду с ключом. Это значит, что если один ключ должен использоваться в течение долгого времени для шифрования нескольких потоков, сама криптосистема, использующая RC4, должна комбинировать оказию и долгосрочный ключ для получения потокового ключа для RC4. Один из возможных выходов -- генерировать новый ключ для RC4 с помощью хэш-функции от долгосрочного ключа и оказии. Однако, многие приложения, использующие RC4, просто конкатенируют ключ и оказию. Из-за этого и слабого расписания ключей, используемого в RC4, приложение может стать уязвимым.

Здесь будут рассмотрены некоторые атаки на шифр и методы защиты от них.

6. Манипуляция битами

Шифр RC4 крайне уязвим к манипуляции битами, если он не реализован верным образом. И поэтому он был признан устаревшим многими софтверными компаниями, такими как Microsoft. Например, в .NET Framework от Microsoft отсутствует реализация RC4.

7. Исследования Руза и восстановление ключа из перестановки

В 1995 году Андрю Руз (англ. Andrew Roos) экспериментально пронаблюдал, что первый байт ключевого потока коррелирован с первыми тремя байтами ключа, а первые несколько байт перестановки после алгоритма расписания ключей (англ. KSA) коррелированны с некоторой линейной комбинацией байт ключа. Эти смещения не были доказаны до 2007 года, когда Пол, Рафи и Мэйтрэ доказали коррелированность ключа и ключевого потока. Также Пол и Мэйтрэ доказали коррелированность перестановки и ключа. Последняя работа также использует коррелированность ключа и перестановки для того, чтобы создать первый алгоритм полного восстановления ключа из последней перестановки после KSA, не делая предположений о ключе и векторе инициализации (англ. IV or Initial Vector). Этот алгоритм имеет постоянную вероятность успеха в зависимости от времени, которая соответствует квадратному корню из сложности полного перебора. Позднее было сделано много работ о восстановлении ключа из внутреннего состояния RC4.

8. Атака Флурера, Мантина и Шамира (ФМШ)

В 2001 году, Флурер, Мантин и Шамир опубликовали работу об уязвимости ключевого расписания RC4. Они показали, что среди всех возможных ключей, первые несколько байт ключевого потока являются совсем неслучайными. Из этих байт можно с высокой вероятностью получить информацию об используемом шифром ключе. И если долговременный ключ и оказия (англ. nonce) просто конкатенируются для создания ключа шифра RC4, то этот долговременный ключ может быть получен с помощью анализа достаточно большого количества сообщений, зашифрованных с использованием данного ключа. Эта уязвимость и некоторые связанные с ней эффекты были использованы при взломе шифрования WEP в беспроводных сетях стандарта IEEE 802.11. Это показало необходимость скорейшей замены WEP, что повлекло за собой разработку нового стандарта безопасности беспроводных сетей WPA.

Криптосистему можно сделать невосприимчивой к этой атаке, если отбрасывать начало ключевого потока. Таким образом, модифицированный алгоритм называется «RC4-drop[n]», где n -- количество байт из начала ключевого потока, которые следует отбросить. Рекомендовано использовать n = 768, консервативная оценка составляет n = 3072.

9. Атака Кляйна

В 2005 году Андреас Кляйн представил анализ шифра RC4, в котором он указал на сильную коррелированность ключа и ключевого потока RC4. Кляйн проанализировал атаки на первом раунде (подобные атаке ФМШ), на втором раунде и возможные их улучшения. Он также предложил некоторые изменения алгоритма для усиления стойкости шифра. В частности, он утверждает, что если поменять направление цикла на обратное в алгоритме ключевого расписания, то можно сделать шифр более стойким к атакам типа ФМШ.

10. Комбинаторная проблема

В 2001 году Ади Шамир и Ицхак Мантин первыми поставили, комбинаторную проблему, связанную с количеством всевозможных входных и выходных данных шифра RC4. Если из всевозможных 256 элементов внутреннего состояния шифра известно x элементов из состояния (x ? 256), то, если предположить, что остальные элементы нулевые, максимальное количество элементов, которые могут быть получены детерминированным алгоритмом за следующие 256 раундов также равно x. В 2004 году это предположение было доказано Сорадюти Полом (англ. Souradyuti Paul) и Бартом Прэнилом (англ. Bart Preneel).

Список литературы

1. Брюс Шнайер. Прикладная криптография 2-е издание

2. www.ssl.stu.neva.ru/psw/crypto/algorithms.html

3. П.А. Анохин. Анализ обобщения Алгоритма RC4

Размещено на Allbest.ru