Ирина Эланс

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

Потоковый шифр Rivest Cipher 4. Особенности алгоритма

Министерство образования и науки Российской Федерации

Федеральное бюджетное образовательное учреждение

высшего профессионального образования

Новосибирский государственный технический университет

Факультет автоматики и вычислительной техники

Кафедра защиты информации

Индивидуальная работа по дисциплине «Теоретические основы компьютерной безопасности»

Потоковый шифр Rivest Cipher 4. Особенности алгоритма

Факультет: АВТ

Группа: АБ-920

Выполнил: Клюев В.Е. Проверил: Абденов А.Ж.

Новосибирск
2011

Содержание

Введение 3

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

Безопасность 7

Манипуляция байтами 7

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

Атака Кляйна 8

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

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

Программная реализация 9

Блок-схема программы 10

Модули и функции программы 11

Инструкция пользователя 12

Главное окно программы 12

Файл 13

Помощь 15

Поле “Ключ” 16

Окно процесса шифрования 16

Последовательность действий 16

Заключение 17

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

Листинг программы 18

Введение

Целью данной работы является изучение алгоритма RC4, рассмотрение его слабых и сильных сторон, определение в каких продуктах и каким образом он используется, а так же программная реализация на языке C++, с использованием программного обеспечения Borland C++ Builder 6.

RC4 (англ. Rivest Cipher 4 или англ. Ron’s Code, также известен как ARCFOUR или ARC4 (англ. Alleged RC4)) — это потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколах SSL и TLS, алгоритме безопасности беспроводных сетей WEP, для шифрования паролей в Windows NT).

Шифр разработан компанией RSA Security, и для его использования требуется лицензия.

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

Основные преимущества шифра — высокая скорость работы и переменный размер ключа. RC4 довольно уязвим, если используются не случайные или связанные ключи, один ключевой поток используется дважды. Эти факторы, а также способ использования могут сделать криптосистему небезопасной (например, WEP).

Алгоритм является симметричным, соответственно, для шифрования и расшифровки используется один и тот же ключ, который передается по защищенным каналам связи. При расшифровке данных автоматически выполняется аутентификация, так как предполагается, что ключ известен лишь двум лицам: отправителю и получателю. Плюсом такого подхода является скорость, минусом - низкая криптостойкость. Симметричные алгоритмы особо уязвимы к атакам типа Mаn-in-the-Middle. В протоколе WEP используется шифрование с помощью 40- или 104-битного ключа, который является статической частью шифра. Как правило, пользователю предлагается два метода введения ключа: HEX-числа и ASCII-символы (для 40-битного ключа - 10-значное HEX-число или пять символов ASCII; для 104-битного - 26 и 13 соответственно). К статической части добавляется динамическая составляющая, которая носит имя вектора инициализации (Initialisation Vector - IV) и весит 24 бита. Таким образом, полная длина ключа равна 64 или 128 битам. В последнее время все чаще встречаются продукты, в которых реализована поддержка ключей с длиной до 256 бит, однако это не сильно повышает стойкость алгоритма, поскольку увеличение длины ключа происходит за счет статической части.

История

Потоковый шифр RC4 был создан Роном Ривестом из RSA Security в 1987 году. Хотя официально сокращение обозначает Rivest Cipher 4, его часто считают сокращением от Ron’s Code.

Шифр являлся коммерческой тайной, но в сентябре 1994 года его описание было анонимно отправлено в рассылку Cypherpunks. Вскоре описание RC4 было опубликовано в ньюс-группе sci.crypt. Именно оттуда исходный код попал на множество сайтов в сети Интернет. Опубликованный шифр давал те же шифротексты на выходе, какие давал подлинный RC4. По-видимому, данный текст был получен в результате анализа исполняемого кода. Опубликованный шифр совместим с имеющимися продуктами, использующими RC4, а некоторые участники телеконференции, имевшие, по их словам, доступ к исходному коду RC4, подтвердили идентичность алгоритмов при различиях в обозначениях и структуре программы.

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

Шифр RC4 применяется в некоторых широко распространённых стандартах и протоколах шифрования таких, как WEP, WPA и TLS.

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

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

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

Рис. 1. Генератор ключевого потока RC4

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

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

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

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

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

Начальное заполнение массива:

for i = 0 to 2n − 1

S[i] = i

Скремблирование:

j = 0

for i = 0 to 2n − 1

j = (j + S[i] + Key[i mod l]) mod 2n

Перестановка (S[i], S[j])

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

Инициализация:

i = 0

j = 0

Цикл генерации:

i = (i + 1) mod 2n

j = (j + S[i]) mod 2n

Перестановка (S[i], S[j])

Результат: K = S[(S[i] + S[j]) mod 2n]

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

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

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

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

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

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

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

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

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

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

Атака Кляйна

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

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

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

Программная реализация

Работа многих поточных шифров основана на линейных регистрах сдвига с обратной связью (LFSR). Это позволяет достичь высокой эффективности реализаций шифра в виде ИС. Но затрудняет программную реализацию таких шифров. Поскольку шифр RC4 не использует LFSR и основан на байтовых операциях, его удобно реализовывать программно. Типичная реализация выполняет от 8 до 16 машинных команд на каждый байт текста, поэтому программная реализация шифра должна работать очень быстро.

Пример реализации RC4 на языке C:

unsigned char S[256];

unsigned int i, j;

/* ключевое расписание */

void rc4_init(unsigned char *key, unsigned int key_length) {

for (i = 0; i < 256; i++)

S[i] = i;

for (i = j = 0; i < 256; i++) {

unsigned char temp;

j = (j + key[i % key_length] + S[i]) & 255;

temp = S[i];

S[i] = S[j];

S[j] = temp;

}

i = j = 0;

}

/* Вывод одного псевдослучайного байта */

unsigned char rc4_output() {

unsigned char temp;

i = (i + 1) & 255;

j = (j + S[i]) & 255;

temp = S[j];

S[j] = S[i];

S[i] = temp;

return S[(temp + S[j]) & 255];

}

Блок-схема программы

Модули и функции программы

Начальная установка вызова формы

fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

Функция открытого текста

Загрузка текста из файла (формат txt):

void OpenText()

Функция шифрования

Выполнение всех процедур, связанных с шифрованием и создание файла с шифротекстом:

void __fastcall TForm1::aEncryptExecute(TObject *Sender)

void __fastcall TForm1::ProcessFile(const AnsiString& pFrom, const AnsiString& pTo)

void __fastcall RC4_InitKey(unsigned char* Key, int KeyLength)

Функция расшифрования

Выполнение всех процедур, связанных с расшифрованием и создание файла с расшифрованным текстом:

void __fastcall TForm1::aDecryptExecute(TObject *Sender)

void __fastcall TForm1::ProcessFile(const AnsiString& pFrom, const AnsiString& pTo)

void __fastcall RC4_InitKey(unsigned char* Key, int KeyLength)

Функция выхода из программы

void __fastcall TForm1::aExitExecute(TObject *Sender)

Функция отображения алгоритма

void __fastcall TForm1::aHelpExecute(TObject *Sender)

Инструкция пользователя

Главное окно программы

Рис. 2. Общий вид программы

Файл

Содержит:

Зашифровать – выбор файла, который необходимо зашифровать. При нажатии открывается интерфейс, позволяющий выбрать файл в проводнике.

Рис. 3. Выбор текстового файла для шифрования

Рис. 4. Шифруемый текст

Расшифровать – выбор файла, который необходимо расшифровать. При нажатии открывается интерфейс, позволяющий выбрать файл в проводнике.

Рис. 5. Выбор текстового файла для расшифрования

Рис. 6. Зашифрованный текст

Выход – выход из программы.

Помощь

Содержит:

Алгоритм – отображает теоретическую информацию об алгоритме, реализуемом в работе.

Рис. 7. Описание работы алгоритма

Поле “Ключ”

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

Окно процесса шифрования

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

Рис. 9. Отображение процесса шифрования

Последовательность действий

Выбрать входной и выходный файлы, ввести ключ, нажать «Зашифровать/Расшифровать». Т.к. алгоритм симметричный, то процессы шифрования и расшифрования аналогичны.

Заключение

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

Алгоритм RC4 — это поточный шифр с переменной длиной ключа, разработанный в 1987 году Рональдом Райвистом для компании RSA Data Security. Как и его «компаньон», блочный шифр RC2, RC4 представляет собой шифр с переменной длиной ключа, пригодный для быстрого магистрального шифрования. Он очень компактен в терминах размера кода и особенно удобен для процессоров с побайтно-ориентированной обработкой. RC4 может шифровать со скоростью около 10 Мбайт/с на процессоре с тактовой частотой 330 Мгц и, подобно RC2, имеет особый статус, значительно упрощающий получение разрешения на экспорт (схема позволяет безболезненно редуцировать длину ключа). В течение семи лет этот алгоритм был фирменным секретом, и подробности о его конструкции предоставлялись только после подписания договора о неразглашении.

В настоящее время алгоритм RC4 реализован в десятках коммерческих криптопродуктов, включая Lotus Notes, Apple Computer’s AOCE, Oracle Secure SQL; он также является частью спецификации стандарта сотовой связи CDPD.

Компания RSA Data Security объявила, что шифр обладает иммунитетом к методам линейного и дифференциального криптоанализа и до сих пор у него не обнаружены короткие циклы. Обычно цитируется заключение закрытой работы криптографа RSA Labs Мэтта Робшоу: «Не имеется известных слабых ключей, и, хотя нет доказательства для нижней границы периодов последовательностей RC4, проведенный теоретический анализ показывает, что период в подавляющем большинстве случаев превышает 10100. Тщательный и всеобъемлющий анализ стойкости RC4 не выявил никаких оснований подвергать сомнению стойкость, обеспечиваемую генератором RC4».

Но реальная степень его безопасности неизвестна, но вскрытие представляется делом нетривиальным. Благодаря его скорости, он может быть использован в некоторых приложениях. Кроме того, алгоритм работает с ключами произвольной длины. По своей сути RC4 представляет собой генератор псевдослучайных чисел, при этом выходные данные генератора используются для операции XOR над потоком данных. Поэтому, чрезвычайно важно, чтобы один и тот же ключ RC4 не использовался для шифровки двух различных сообщений.

Исходные тексты и информацию об RC4 можно найти во многих криптографических библиотеках, например в исходных текстах SSLeay, Crypto++ и Ssh.

Американское правительство обычно разрешает к экспорту шифры RC4 с 40-битными ключами. Такие короткие ключи могут быть легко взломаны правительствами, преступниками и даже дилетантами.

Интересно, что экспортный вариант SSL (Secure Socket Layer корпорации Netscape), где используется шифр RC4-40, был недавно вскрыт по крайней мере двумя независимыми группами. Процесс вскрытия занял порядка восьми дней; в большинстве крупных университетов (или компаний) такой объем вычислительных мощностей доступен любому студенту старших курсов по специальности computer science.

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

Б. Шнайер «Прикладная криптография. 2-е издание. Протоколы, алгоритмы и исходные тексты на языке С». Издано: 2002, "Триумф", 816 стр.
Кузнецов М.В. C++. Мастер-класс в задачах и примерах (+ CD-ROM). Спб.: БХВ-Петербург, 2007.
Э.А. Ишкова С++ начала программирования / Изд. 3-е М.: ООО «Бином-Пресс», 2007. – 368 стр.
Коблиц Н. Курс теории чисел и криптографии. - М.: ТВП, 2001.
Электронный ресурс RC4 – Википедия // http://ru.wikipedia.org/wiki/RC4
Электронный ресурс RSA Laboratories // http://www.rsa.com/rsalabs/node.asp?id=2009
Электронный ресурс http://dic.academic.ru/
Электронный ресурс http://www.des-crypto.ru/cryptography/rc4/
Электронный ресурс http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html
Ермолаев Е. Без проводов и без защиты // Спецвыпуск: Хакер, номер 059 / стр. 18-24. (Журнал).

Листинг программы

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "MainUnit.h"

#include "RC4Unit.h"

#include "AboutUnit.h"

#include "Unit2.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ProcessFile(const AnsiString& pFrom, const AnsiString& pTo)

{

// Если ключевая фраза будет пустой, алгоритм вылетит

if (Edit1->Text == "")

{

Edit1->Text = "DefaultPassPhrase";

}

// Передаем ключевую фразу на генератор матрицы

Memo1->Lines->Add("Инициализация матрицы..");

RC4_InitKey(Edit1->Text.c_str(), Edit1->Text.Length());

Memo1->Lines->Add("Выполнено 256 перестановок");

Memo1->Lines->Add("Открытие файлов..");

// Открываем первый файл на чтение

HANDLE in = CreateFile(pFrom.c_str(), GENERIC_READ, 0, NULL,

OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);

if (in == INVALID_HANDLE_VALUE)

{

Memo1->Lines->Add("..ошибка!");

Application->MessageBox(("Не удалось открыть входной файл: "+pFrom).c_str(), " Ошибка",

Потоковый шифр Rivest Cipher 4. Особенности алгоритма