RC4

RC4 (Rivest Cipher 4, также известный как ARC4 — Alleged RC4) — это потоковый шифр, разработанный в 1987 году американским криптографом Рональдом Ривестом. Алгоритм относится к классу симметричных шифров, где для шифрования и дешифрования используется один и тот же ключ. RC4 получил широкое распространение благодаря своей простоте, высокой скорости работы и возможности реализации в программном обеспечении с минимальными вычислительными ресурсами. На протяжении десятилетий он применялся в таких протоколах, как WEP (Wired Equivalent Privacy), WPA (Wi-Fi Protected Access) и SSL/TLS, однако к началу 2010-х годов в его конструкции были обнаружены критические уязвимости, что привело к постепенному отказу от использования RC4 в современных системах безопасности.

История

Разработка и распространение

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

Пик популярности

В 1990-х и начале 2000-х годов RC4 стал одним из самых распространённых потоковых шифров в мире. Он был интегрирован в протоколы защиты беспроводных сетей WEP (1997) и WPA (2003), а также в протоколы SSL (Secure Sockets Layer) и его преемника TLS (Transport Layer Security). Простота реализации и высокая производительность сделали RC4 предпочтительным выбором для встраиваемых систем, браузеров и приложений с ограниченными ресурсами.

Упадок и отказ

Первые признаки уязвимости RC4 были обнаружены ещё в 2001 году, когда криптографы выявили статистические смещения в выходной последовательности шифра. В 2013 году группа исследователей опубликовала работу, демонстрирующую возможность атаки на протокол TLS с использованием RC4. К 2015 году большинство браузеров и серверов прекратили поддержку RC4, а в 2016 году организация Internet Engineering Task Force (IETF) официально объявила об отказе от использования RC4 в протоколах TLS. В настоящее время алгоритм считается небезопасным и не рекомендуется к применению.

Принцип работы

Общая схема

RC4 является потоковым шифром, который генерирует псевдослучайную последовательность битов (гамму), которая затем накладывается на открытый текст с помощью операции XOR (исключающее ИЛИ). Дешифрование происходит аналогично: зашифрованный текст XOR-ится с той же самой гаммой, восстанавливая исходные данные. Алгоритм состоит из двух основных этапов: инициализация (Key Scheduling Algorithm, KSA) и генерация псевдослучайной последовательности (Pseudo-Random Generation Algorithm, PRGA).

Инициализация (KSA)

На этапе KSA создаётся массив S из 256 байтов (от 0 до 255), который изначально заполняется значениями, равными их индексам. Затем массив многократно переставляется с использованием ключа шифрования. Ключ может иметь длину от 1 до 256 байт, но на практике чаще всего используются ключи длиной 40, 56, 64, 128 или 256 бит. Алгоритм KSA выполняет 256 итераций, на каждой из которых вычисляется индекс j = (j + S[i] + K[i mod key_length]) mod 256, после чего элементы S[i] и S[j] меняются местами. В результате получается переставленный массив S, который служит начальным состоянием для генерации гаммы.

Генерация гаммы (PRGA)

На этапе PRGA алгоритм генерирует бесконечную последовательность байтов гаммы. Для каждого байта выполняются следующие шаги:

1. Увеличивается индекс i на 1 (по модулю 256).
2. Вычисляется индекс j = (j + S[i]) mod 256.
3. Элементы S[i] и S[j] меняются местами.
4. Вычисляется индекс t = (S[i] + S[j]) mod 256.
5. Значение S[t] является очередным байтом гаммы.

Полученный байт гаммы затем XOR-ится с байтом открытого текста, давая байт шифротекста.

Классификация и варианты

Стандартный RC4

Базовая версия алгоритма с массивом S размером 256 байт и ключом переменной длины. Используется в большинстве реализаций.

RC4-drop[n]

Вариант, в котором первые n байт гаммы отбрасываются перед началом шифрования. Это делается для устранения начальных статистических смещений, характерных для стандартного RC4. Наиболее распространённым является RC4-drop[768] или RC4-drop[3072].

Spritz

В 2014 году Рональд Ривест предложил модифицированную версию RC4 под названием Spritz, которая исправляет известные уязвимости, сохраняя общую архитектуру потокового шифра. Однако Spritz не получил широкого распространения из-за более низкой производительности по сравнению с современными шифрами (AES, ChaCha20).

Применение

Беспроводные сети

RC4 использовался в протоколе WEP для шифрования трафика в сетях Wi-Fi. Однако из-за слабости алгоритма и короткой длины ключа (40 или 104 бита) WEP был взломан в 2001 году. Протокол WPA, пришедший на смену WEP, также применял RC4, но с более сложной схемой управления ключами и использованием протокола TKIP (Temporal Key Integrity Protocol). В 2008 году были найдены атаки и на WPA, что привело к переходу на WPA2 с шифром AES.

Протоколы SSL/TLS

До 2015 года RC4 был одним из поддерживаемых шифров в протоколах SSL и TLS. Он использовался как альтернатива блочным шифрам (например, AES) в ситуациях, где требовалась высокая скорость или совместимость со старыми устройствами. После публикации атаки «Bar Mitzvah» (2015) и других работ, демонстрирующих возможность восстановления открытого текста, поддержка RC4 была прекращена.

Другие применения

RC4 также применялся в некоторых криптографических библиотеках, в протоколах VPN (например, PPTP), в системах защиты PDF-файлов и в ряде коммерческих продуктов. Однако к 2020 году почти все крупные разработчики исключили RC4 из своих продуктов.

Критика и уязвимости

Статистические смещения

Основная проблема RC4 заключается в том, что его выходная последовательность не является равномерно случайной. Уже в 2001 году было показано, что второй байт гаммы с вероятностью 1/128 равен нулю (вместо ожидаемой 1/256). Позднее были обнаружены и другие смещения, которые позволяют злоумышленнику, перехватившему большое количество зашифрованных сообщений, статистически восстановить открытый текст.

Атака на WEP

В 2001 году криптографы Скотт Флюрер, Ицик Мантин и Ади Шамир опубликовали атаку на WEP, использующую слабости RC4. Атака FMS (Flurer, Mantin, Shamir) позволяла восстановить ключ шифрования после перехвата нескольких тысяч пакетов. Впоследствии были разработаны более эффективные атаки (например, атака Корека), которые сократили необходимое количество пакетов до нескольких десятков тысяч.

Атака на TLS (2013)

В 2013 году группа исследователей из Королевского университета в Белфасте и Технического университета Дармштадта продемонстрировала атаку на протокол TLS, использующий RC4. Атака позволяла восстановить часть открытого текста (например, cookie сессии) после перехвата от 2^24 до 2^26 зашифрованных сообщений. В 2015 году была опубликована улучшенная версия атаки («Bar Mitzvah»), которая требовала всего 2^13 сообщений.

Отсутствие аутентификации

RC4, как и многие потоковые шифры, не обеспечивает аутентификацию данных. Это делает его уязвимым для атак с изменением шифротекста (bit-flipping attacks), при которых злоумышленник может модифицировать зашифрованное сообщение, не зная ключа. Для защиты от таких атак требуется использование дополнительных механизмов аутентификации (например, HMAC).

Интересные факты

• Название «RC4» официально не расшифровывается, но по общепринятой версии означает «Rivest Cipher 4». Существуют также шуточные расшифровки, например «Ron’s Code 4».
• Алгоритм RC4 был настолько прост, что его можно было реализовать всего в нескольких строках кода на языке C.
• В 2010 году компания Microsoft рекомендовала отключить RC4 в своих продуктах, а в 2015 году полностью удалила поддержку этого шифра из Windows.
• Несмотря на уязвимости, RC4 до сих пор используется в некоторых старых устройствах (например, в принтерах и маршрутизаторах), где обновление прошивки невозможно.

Источники

• Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. — 2nd ed. — John Wiley & Sons, 1996. — ISBN 0-471-11709-9.
• Fluhrer S., Mantin I., Shamir A. Weaknesses in the Key Scheduling Algorithm of RC4 // Selected Areas in Cryptography. — 2001. — Vol. 2259. — P. 1–24.
• Mantin I., Shamir A. A Practical Attack on Broadcast RC4 // Fast Software Encryption. — 2001. — Vol. 2355. — P. 152–164.
• AlFardan N., Bernstein D., Paterson K., Poettering B., Schuldt J. On the Security of RC4 in TLS // USENIX Security Symposium. — 2013. — P. 305–320.
• RFC 7465 — Prohibiting RC4 Cipher Suites. — IETF, 2015.