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

RC4 (Rivest Cipher 4, также известный как ARC4 — Alleged RC4) — это потоковый шифр, разработанный в 1987 году американским криптографом Рональдом Ривестом для компании RSA Security. Шифр отличается высокой скоростью работы и простотой реализации, что привело к его широкому распространению в протоколах безопасности, таких как WEP, WPA (на ранних этапах), TLS/SSL и в некоторых приложениях. Несмотря на свою популярность, RC4 обладает рядом серьёзных криптографических уязвимостей, которые в конечном итоге привели к его полному отказу от использования в современных стандартах безопасности.

История

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

В 1990-х и начале 2000-х годов RC4 был одним из самых популярных потоковых шифров. Он использовался в протоколе WEP (Wired Equivalent Privacy) для защиты беспроводных сетей Wi-Fi, в протоколе SSL/TLS для защиты веб-трафика, а также в таких системах, как Microsoft Office и BitTorrent. Однако в 2001 году были выявлены первые серьёзные уязвимости, связанные с использованием слабых ключей в WEP. В 2015 году группа исследователей из INRIA и Microsoft опубликовала работу, демонстрирующую атаки на RC4 в TLS, что привело к рекомендациям по отказу от его использования. К 2016 году RC4 был полностью исключён из стандартов TLS.

Устройство и принцип работы

RC4 является потоковым шифром, который генерирует псевдослучайную последовательность битов (гамму), которая затем накладывается на открытый текст с помощью операции XOR. Шифр работает с байтами (8-битными словами) и использует переменную длину ключа, обычно от 40 до 2048 бит.

Алгоритм состоит из двух основных этапов:

1. Инициализация (Key Scheduling Algorithm, KSA):

• Создаётся массив S из 256 байт, заполненный числами от 0 до 255.
• Ключ повторяется до длины 256 байт.
• Выполняется перемешивание массива S с использованием ключа. Для каждого индекса i от 0 до 255 вычисляется индекс j = (j + S[i] + K[i mod len(K)]) mod 256, после чего элементы S[i] и S[j] меняются местами.

1. Генерация псевдослучайной последовательности (Pseudo-Random Generation Algorithm, PRGA):

• Инициализируются индексы i = 0 и j = 0.
• Для каждого байта открытого текста выполняется:
• i = (i + 1) mod 256
• j = (j + S[i]) mod 256
• Меняются местами S[i] и S[j]
• t = (S[i] + S[j]) mod 256
• Ключевой байт K = S[t]
• Полученный ключевой байт XOR-ится с байтом открытого текста для получения шифротекста.

Процесс дешифрования идентичен, так как операция XOR является обратимой.

Классификация

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

• Стандартный RC4 (ARC4): Базовая реализация, описанная выше.
• RC4-drop[n]: Модификация, при которой первые n байтов генерируемой гаммы отбрасываются. Это делается для снижения уязвимости к атакам на ранние этапы генерации (например, RC4-drop[3072] рекомендуется для использования в некоторых протоколах).

Применение

Протокол WEP и WPA

Наиболее известное применение RC4 — это протокол WEP, используемый для защиты беспроводных сетей IEEE 802.11. WEP использовал 40-битный или 104-битный ключ, который вводился в RC4. Однако из-за слабой реализации инициализации (использование коротких векторов инициализации — IV) RC4 в WEP оказался крайне уязвим. Атаки, такие как атака Флурера-Мантина-Шамира (FMS) и атака Корека, позволяли восстановить ключ WEP за несколько минут. В протоколе WPA (Wi-Fi Protected Access) для замены WEP использовался Temporal Key Integrity Protocol (TKIP), который также базировался на RC4, но с более сложной схемой управления ключами и проверки целостности. Однако и TKIP со временем был признан уязвимым.

Протокол TLS/SSL

RC4 был одним из наиболее популярных шифров в протоколах SSL и TLS до середины 2010-х годов. Он использовался как альтернатива блочным шифрам (например, AES) из-за своей высокой скорости и низких требований к вычислительным ресурсам. В 2013 году были опубликованы атаки, использующие смещение в гамме RC4, что позволяло восстанавливать части открытого текста. В 2015 году исследователи продемонстрировали атаку, которая могла восстановить куки сессии в HTTPS-трафике, защищённом RC4. В результате, в 2016 году все основные браузеры и серверы прекратили поддержку RC4 в TLS.

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

RC4 также использовался в:

• Microsoft Office: Для защиты документов (старые версии).
• BitTorrent: Для шифрования трафика (протокол Message Stream Encryption).
• Skype: В ранних версиях для шифрования голосового трафика.
• Wi-Fi Protected Access (WPA): В режиме TKIP.

Криптографическая стойкость и уязвимости

Несмотря на свою простоту, RC4 обладает рядом фундаментальных уязвимостей, которые делают его непригодным для использования в современных системах безопасности.

Основные уязвимости:

1. Слабые ключи: Алгоритм инициализации (KSA) генерирует слабые начальные состояния, которые могут быть использованы для восстановления ключа. Это особенно критично в WEP, где IV передаётся в открытом виде.
2. Смещение в гамме: Статистический анализ показывает, что второй байт гаммы RC4 с вероятностью 1/128 равен нулю, а не 1/256, как ожидается. Это смещение позволяет атакующему с высокой вероятностью предсказывать некоторые байты открытого текста.
3. Атаки на основе корреляции: Существуют корреляции между байтами ключа и гаммы, что позволяет атакующему восстанавливать ключ при наличии достаточного количества шифротекстов.
4. Атака «Bar mitzvah» (2015): Атака на протокол TLS, использующая слабости RC4 для восстановления сессионных куки.
5. Атака «Royal Holloway» (2013): Атака, использующая смещение в гамме для восстановления открытого текста в HTTPS-трафике.

Современный статус

В 2015 году Internet Engineering Task Force (IETF) выпустил RFC 7465, который официально запретил использование RC4 в протоколах TLS. В 2016 году все основные браузеры (Google Chrome, Mozilla Firefox, Microsoft Edge, Apple Safari) и серверы (Apache, Nginx) прекратили поддержку RC4. На сегодняшний день RC4 считается полностью скомпрометированным и не рекомендуется к использованию ни в каких новых проектах. Для обеспечения безопасности данных рекомендуется использовать современные аутентифицированные шифры, такие как AES-GCM или ChaCha20-Poly1305.

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

• Название «RC4» расшифровывается как «Rivest Cipher 4», но также может означать «Ron's Code 4».
• Алгоритм RC4 был настолько прост, что мог быть реализован в виде нескольких строк кода на языке C.
• Из-за того, что исходный код был опубликован без разрешения RSA Security, термин «ARC4» (Alleged RC4) часто используется для обозначения реализации, не являющейся официальной.
• RC4 использовался в протоколе WEP, который был настолько уязвим, что взлом сети Wi-Fi, защищённой WEP, мог быть выполнен за несколько минут с помощью общедоступных инструментов.

Источники

• Rivest, R. L. (1987). The RC4 Encryption Algorithm. RSA Data Security, Inc.
• Fluhrer, S., Mantin, I., & Shamir, A. (2001). Weaknesses in the Key Scheduling Algorithm of RC4.
• AlFardan, N. J., Bernstein, D. J., Paterson, K. G., Poettering, B., & Schuldt, J. C. N. (2013). On the Security of RC4 in TLS.
• RFC 7465 (2015). Prohibiting RC4 Cipher Suites.
• Vanhoef, M., & Piessens, F. (2015). All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS.