RC4: Уязвимости и замена потокового шифра

Введение

Шифр потока

В криптографии RC4 (Rivest Cipher 4, также известный как ARC4 или ARCFOUR, что означает "предполагаемый RC4", см. ниже) является шифром потока. Несмотря на свою простоту и высокую скорость работы в программном обеспечении, в RC4 обнаружено множество уязвимостей, делающих его небезопасным. Он особенно уязвим, когда начальная часть выходного потока ключей не отбрасывается или используются неслучайные или связанные ключи. Особенно проблемное использование RC4 привело к созданию крайне небезопасных протоколов, таких как WEP. По состоянию на 2015 год существует мнение, что некоторые государственные криптографические службы могут обладать возможностью взлома RC4 при использовании в протоколе TLS. Было предпринято несколько попыток усилить RC4, в частности Spritz, RC4A, VMPC и RC4+.

История

RC4 был разработан Роном Ривестом из RSA Security в 1987 году. Хотя он официально называется "Rivest Cipher 4", аббревиатура RC также может интерпретироваться как "Ron's Code" (см. также RC2, RC5 и RC6). RC4 изначально был коммерческой тайной, но в сентябре 1994 года его описание было анонимно опубликовано в рассылке Cypherpunks. Вскоре оно появилось в новостной группе sci.crypt, где Боб Дженкинс взломал его всего за несколько дней. Оттуда он распространился по многим сайтам в Интернете. Утечка кода была подтверждена как подлинная, поскольку его вывод соответствовал выводу проприетарного программного обеспечения, использующего лицензированный RC4. Поскольку алгоритм известен, он больше не является коммерческой тайной. Название RC4 является зарегистрированным товарным знаком, поэтому RC4 часто называют ARCFOUR или ARC4 (что означает "предполагаемый RC4"), чтобы избежать проблем с товарным знаком. RSA Security никогда официально не публиковала алгоритм; однако Ривест в 2008 году добавил ссылку на статью о RC4 в английской Википедии в свои конспекты курса, а в 2014 году подтвердил историю RC4 и его код в своей статье. В OpenBSD 5.5, выпущенном в мае 2014 года, была внесена модификация для использования ChaCha20. Реализации arc4random в FreeBSD и NetBSD также используют ChaCha20. Linux обычно использует glibc, которая не предлагала arc4random до 2022 года. Вместо этого функцию предоставляла отдельная библиотека libbsd, которая была обновлена для использования ChaCha20 в 2016 году. В 2022 году glibc добавила свою собственную версию arc4random, также основанную на ChaCha20. Согласно страницам руководства, поставляемым с операционной системой, в выпуске операционных систем macOS и iOS 2017 года Apple заменила RC4 на AES в своей реализации arc4random. Предлагаемые новые генераторы случайных чисел часто сравниваются с генератором случайных чисел RC4. Несколько атак на RC4 способны отличить его выходные данные от случайной последовательности. Поскольку RC4 является потоковым шифром, он более подвержен манипуляциям, чем обычные блочные шифры. Если он не используется вместе с надежным кодом аутентификации сообщений (MAC), то шифрование уязвимо для атаки с изменением битов. Шифр также уязвим для атаки на потоковый шифр, если он реализован неправильно. Однако стоит отметить, что RC4, будучи потоковым шифром, в течение некоторого времени был единственным распространенным шифром, устойчивым к атаке BEAST 2011 года на TLS 1.0. Атака использует известную слабость в способе использования режима цепочки блоков шифров со всеми другими шифрами, поддерживаемыми TLS 1.0, которые являются блочными шифрами. В марте 2013 года Isobe, Ohigashi, Watanabe и Morii, а также AlFardan, Bernstein, Paterson, Poettering и Schuldt предложили новые сценарии атак, использующие новые статистические смещения в таблице ключей RC4 для восстановления открытого текста при большом количестве шифрований TLS. Использование RC4 в TLS запрещено RFC 7465, опубликованным в феврале 2015 года.

RC4 was designed by Ron Rivest of RSA Security in 1987. While it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code" (see also RC2, RC5 and RC6). RC4 was initially a trade secret, but in September 1994, a description of it was anonymously posted to the Cypherpunks mailing list. It was soon posted on the sci. crypt newsgroup, where it was broken within days by Bob Jenkins. From there, it spread to many sites on the Internet. The leaked code was confirmed to be genuine, as its output was found to match that of proprietary software using licensed RC4. Because the algorithm is known, it is no longer a trade secret. The name RC4 is trademarked, so RC4 is often referred to as ARCFOUR or ARC4 (meaning alleged RC4) to avoid trademark problems. RSA Security has never officially released the algorithm; Rivest has, however, linked to the English Wikipedia article on RC4 in his own course notes in 2008 and confirmed the history of RC4 and its code in a 2014 paper by him. In OpenBSD 5.5, released in May 2014, was modified to use ChaCha20. The implementations of arc4random in FreeBSD, NetBSD also use ChaCha20. Linux typically uses glibc, which did not offer arc4random until 2022. Instead, a separate library, libbsd, offers the function; it was updated to use ChaCha20 in 2016. In 2022, glibc added its own version of arc4random, also based on ChaCha20. According to manual pages shipped with the operating system, in the 2017 release of macOS and iOS operating systems, Apple replaced RC4 with AES in its implementation of arc4random. Proposed new random number generators are often compared to the RC4 random number generator. Several attacks on RC4 are able to distinguish its output from a random sequence. Because RC4 is a stream cipher, it is more malleable than common block ciphers. If not used together with a strong message authentication code (MAC), then encryption is vulnerable to a bit flipping attack. The cipher is also vulnerable to a stream cipher attack if not implemented correctly. It is noteworthy, however, that RC4, being a stream cipher, was for a period of time the only common cipher that was immune to the 2011 BEAST attack on TLS 1.0. The attack exploits a known weakness in the way cipher block chaining mode is used with all of the other ciphers supported by TLS 1.0, which are all block ciphers. In March 2013, there were new attack scenarios proposed by Isobe, Ohigashi, Watanabe and Morii, as well as AlFardan, Bernstein, Paterson, Poettering and Schuldt that use new statistical biases in RC4 key table to recover plaintext with large number of TLS encryptions. The use of RC4 in TLS is prohibited by RFC 7465 published in February 2015.

Побочные уступки Роуса и реконструкция ключа от пермутации

В 1995 году Эндрю Рус экспериментально обнаружил, что первый байт ключевого потока коррелирует с первыми тремя байтами ключа, а первые несколько байтов перестановки после KSA коррелируют с некоторой линейной комбинацией байтов ключа. Эти смещения оставались необъяснимыми до 2007 года, когда Гоутам Пол, Сиддхешвар Рати и Субхамой Майтра доказали корреляцию между ключевым потоком и ключом, а в другой работе Гоутам Пол и Субхамой Майтра доказали корреляцию между перестановкой и ключом. В последней работе также использовались корреляции между перестановкой и ключом для разработки первого алгоритма для полной реконструкции ключа из конечной перестановки после KSA, без каких-либо предположений о ключе или векторе инициализации. Этот алгоритм имеет постоянную вероятность успеха за время, равное квадратному корню от сложности полного перебора ключей. Впоследствии было проведено множество других исследований по реконструкции ключа из внутренних состояний RC4. Субхамой Майтра и Гоутам Пол также показали, что смещения типа Roos сохраняются даже при рассмотрении вложенных индексов перестановки, таких как или . Эти типы смещений используются в некоторых более поздних методах реконструкции ключа для повышения вероятности успеха.

Склонные выходы RC4

Ключевой поток, генерируемый RC4, в различной степени смещен в сторону определенных последовательностей, что делает его уязвимым для атак по различию. Наиболее эффективная такая атака была разработана Ициком Мантином и Ади Шамиром, которые показали, что второй выходной байт шифра смещен к нулю с вероятностью 1/128 (вместо 1/256). Это происходит из-за того, что если третий байт исходного состояния равен нулю, а второй байт не равен 2, то второй выходной байт всегда будет равен нулю. Этот сдвиг можно обнаружить, проанализировав всего 256 байтов. Souradyuti Paul и Bart Preneel из COSIC показали, что первый и второй байты RC4 также подвержены смещению. Для обнаружения этого смещения требуется 225 образцов. Скотт Флюрер и Дэвид МакГрю также продемонстрировали атаки, позволяющие отличить ключевой поток RC4 от случайного потока, используя гигабайт выходных данных. Полная характеристика одного шага генератора псевдослучайных чисел RC4 (PRGA) была выполнена Риддхипратимом Басу, Ширшенду Гангули, Субхамоем Майтра и Готамом Полом. Рассмотрев все перестановки, они доказали, что распределение выходных данных не является равномерным при заданных значениях i и j, и, как следствие, информация о j всегда просачивается в выходной поток.

Фюрер, Мантин и Шамир атакуют

В 2001 году Флюрер, Мантин и Шамир сделали новое и неожиданное открытие: статистика первых нескольких байтов выходного потока ключей для всех возможных ключей RC4 значительно отличается от случайной, выдавая информацию о ключе. Если nonce и долгосрочный ключ просто объединяются для генерации ключа RC4, то этот долгосрочный ключ можно восстановить, анализируя большое количество сообщений, зашифрованных этим ключом. Эта и связанные с ней уязвимости были затем использованы для взлома шифрования WEP ("проводной эквивалент приватности"), применяемого в беспроводных сетях 802.11. Это спровоцировало поиск замены WEP, основанной на стандартах, на рынке 802.11, и привело к разработке IEEE 802.11i и WPA. Протоколы могут защититься от этой атаки, отбрасывая начальную часть потока ключей. Такой модифицированный алгоритм традиционно называется "RC4 drop[n]", где n – количество отбрасываемых начальных байтов потока ключей. Значение по умолчанию в SCAN – n = 768 байт, но более консервативным значением будет n = 3072 байта. Атака Флюрера, Мантина и Шамира не применима к SSL, использующему RC4, поскольку SSL генерирует ключи шифрования для RC4 с помощью хеширования, что означает, что различные сеансы SSL используют не связанные между собой ключи.

Атака Кляйна

В 2005 году Андреас Клейн представил анализ потокового шифра RC4, выявив больше взаимосвязей между ключевым потоком RC4 и ключом. Эрик Тьюс, Ральф Филипп Вайнманн и Андрей Пычкин использовали этот анализ для создания aircrack ptw – инструмента, который взламывает 104-битный RC4, применяемый в 128-битном WEP, менее чем за минуту. В то время как атака Флюэра, Мантина и Шамира требовала около 10 миллионов сообщений, aircrack ptw способен взломать 104-битный ключ, используя 40 000 кадров с вероятностью 50% или 85 000 кадров с вероятностью 95%.

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

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

Атака на Рояль Холлоуэй

В 2013 году группа исследователей в области безопасности из группы информационной безопасности Королевского колледжа Лондона сообщила об атаке, которая может стать эффективной, используя всего 234 зашифрованных сообщения. Хотя в настоящее время это не представляет собой практическую угрозу в большинстве случаев, полученный результат достаточно близок к тому, чтобы вызвать предположения о том, что некоторые государственные криптографические службы могут уже располагать более эффективными методами, делающими RC4 небезопасным. Учитывая, что значительная часть TLS-трафика использует RC4 для защиты от атак на блочные шифры с использованием цепочечного шифрования блоков, существование этих гипотетических, более эффективных атак сделает комбинацию TLS и RC4 уязвимой для злоумышленников во многих практических сценариях.

Бар-мицва атака

На конференции Black Hat Asia 2015 Ицик Мантин представил новую атаку на SSL, использующую шифр RC4.

Атака NOMORE

В 2015 году исследователи безопасности из KU Leuven представили новые атаки на RC4, применимые как к TLS, так и к WPA TKIP. Атака, получившая название Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE), стала первой атакой подобного рода, продемонстрированной в реальных условиях. Их атака на TLS способна расшифровать защищенный HTTP-cookie за 75 часов. Атака на WPA TKIP может быть завершена в течение часа и позволяет злоумышленнику расшифровывать и внедрять произвольные пакеты данных.

Варианты RC4

Как упоминалось выше, наиболее важной слабостью RC4 является недостаточный алгоритм генерации ключевого потока; первые байты выходных данных раскрывают информацию о ключе. Это можно исправить, просто отбрасывая некоторую начальную часть выходного потока. Это известно как RC4 dropN, где N обычно является кратным 256, например, 768 или 1024. Было предпринято несколько попыток усилить RC4, в частности Spritz, RC4A, VMPC и RC4+.

Сприц

В 2014 году Рональд Ривест выступил с докладом и стал соавтором статьи об обновлённой переработке под названием Spritz. Аппаратный ускоритель Spritz был опубликован в Secrypt в 2016 году и показал, что из-за множественных вложенных вызовов, необходимых для генерации выходных байтов, Spritz работает заметно медленнее по сравнению с другими хеш-функциями, такими как SHA-3 и наилучшей известной аппаратной реализацией RC4. Как и другие функции типа "губка", Spritz может быть использован для построения криптографической хеш-функции, детерминированного генератора случайных битов (DRBG), алгоритма шифрования, поддерживающего аутентифицированное шифрование с дополнительными данными (AEAD) и т.д. В 2017 году Баник, Изобе и Мории предложили простое исправление, устраняющее уязвимость в первых двух байтах ключевого потока, требующее всего одного дополнительного обращения к памяти без существенного ухудшения производительности программного обеспечения.