Войти
| Общие | |
|---|---|
| Дизайнеры | Рон Ривест (RSA Security ) |
| Впервые опубликовано | Утечка в 1994 году. (разработан в 1987 году) |
| Детали шифра | |
| Размеры ключа | 40–2048 бит |
| Размер состояния | 2064 бита (1684 эффективных) |
| Раундов | 1 |
| Скорость | 7 циклов на байт на исходном Pentium. Модифицированный предполагаемый RC4 на Intel Core 2: 13,9 цикла на байт |
В криптографии, RC4 (Rivest Cipher 4, также известный как ARC4 или ARCFOUR, что означает предполагаемый RC4, см. Ниже) - это потоковый шифр. Хотя он отличается простотой и скоростью работы программного обеспечения, в RC4 было обнаружено множество уязвимостей, что сделало его небезопасным. Он особенно уязвим, когда начало выходного потока ключевого потока не является отброшены, или когда используются неслучайные или связанные ключи. Особенно проблематичное использование RC4 привело к очень небезопасным протоколам , таким как WE P.
По состоянию на 2015 год есть предположение, что некоторые государственные криптологические агентства могут обладать способностью взламывать RC4 при использовании в протоколе TLS. IETF опубликовал RFC 7465, чтобы запретить использование RC4 в TLS; Mozilla и Microsoft выпустили аналогичные рекомендации.
Был предпринят ряд попыток усилить RC4, в частности Spritz, RC4A, VMPC и RC4.
RC4 был разработан Рон Ривест из RSA Security в 1987 году. Хотя он официально называется «Rivest Cipher 4», аббревиатура RC, как альтернатива, понимается как «Код Рона» (см. Также RC2, RC5 и RC6 ).
RC4 изначально был коммерческой тайной, но в сентябре 1994 года его описание было анонимно отправлено в список рассылки Cypherpunks. Вскоре он был размещен в sci.crypt группе новостей, где в течение нескольких дней был проанализирован Бобом Дженкинсом. Оттуда он распространился на многие сайты в Интернете. Утечка кода была подтверждена как подлинная, поскольку было обнаружено, что его выходные данные совпадают с выходными данными проприетарного программного обеспечения, использующего лицензионную версию RC4. Поскольку алгоритм известен, он больше не является коммерческой тайной. Название RC4 является товарным знаком, поэтому RC4 часто называют ARCFOUR или ARC4 (что означает предполагаемый RC4), чтобы избежать проблем с товарным знаком. RSA Security никогда официально не выпускал алгоритм; Однако Ривест связался со статьей английской Википедии о RC4 в своих заметках по курсу в 2008 году и подтвердил историю RC4 и его кода в своей статье 2014 года.
RC4 стал часть некоторых широко используемых протоколов и стандартов шифрования, таких как WEP в 1997 году и WPA в 2003/2004 годах для беспроводных карт; и SSL в 1995 году и его преемник TLS в 1999 году, пока он не был запрещен для всех версий TLS в соответствии с RFC 7465 в 2015 году из-за RC4 атакует, ослабляя или ломая RC4, используемый в SSL / TLS. Основными факторами успеха RC4 в таком широком диапазоне приложений были его скорость и простота: было очень легко разработать эффективные реализации как в программном, так и в аппаратном обеспечении.
RC4 генерирует псевдослучайный поток битов (ключевой поток ). Как и любой потоковый шифр, их можно использовать для шифрования, комбинируя его с открытым текстом с помощью побитового исключающего или ; расшифровка выполняется таким же образом (поскольку исключающее ИЛИ с заданными данными является инволюцией ). Это похоже на одноразовый блокнот , за исключением того, что используются сгенерированные псевдослучайные биты, а не подготовленный поток.
Для генерации ключевого потока шифр использует секретное внутреннее состояние, которое состоит из двух частей:
Перестановка инициализируется ключом переменной длины , обычно между 40 и 2048 битов с использованием алгоритма планирования ключей (KSA). Как только это будет завершено, поток битов генерируется с использованием алгоритма псевдослучайной генерации (PRGA).
Алгоритм планирования ключей используется для инициализации перестановки в массиве «S». «длина ключа» определяется как количество байтов в ключе и может находиться в диапазоне 1 ≤ длина ключа ≤ 256, обычно от 5 до 16, что соответствует длине ключа от 40 до 128 бит. Сначала массив "S" инициализируется перестановкой идентификаторов . Затем S обрабатывается в течение 256 итераций аналогично основному PRGA, но также одновременно подмешивает байты ключа.
для i из 0 to255 S [i]: = i endfor j: = 0 для i из 0 to255 j: = (j + S [i] + key [i mod keylength]) mod 256 поменять местами значения S [i] и S [j] endfor
Этап поиска RC4. Выходной байт выбирается путем поиска значений S [i] и S [j], суммирования их по модулю 256 и последующего использования суммы в качестве индекса в S; S (S [i] + S [j]) используется как байт ключевого потока, K. Для такого количества итераций, которое необходимо, PRGA изменяет состояние и выводит байт ключевого потока. На каждой итерации PRGA:
Каждый элемент S является заменяется другим элементом не реже одного раза в 256 итераций.
i: = 0 j: = 0 while GeneratingOutput: i: = (i + 1) mod 256 j: = (j + S [i]) mod 256 swap значения из S [i] и S [j] K: = S [(S [i] + S [j]) mod 256] вывод K end, в то время как
Несколько операционных систем включают arc4random, API, созданный в OpenBSD, обеспечивающий доступ к генератору случайных чисел, изначально основанному на RC4. В OpenBSD 5.5, выпущенном в мае 2014 года, arc4randomбыл изменен для использования ChaCha20. Реализации arc4random в FreeBSD, NetBSD и Linux libbsd также используют ChaCha20. Согласно страницам руководства, поставляемым с операционной системой, в выпуске своих операционных систем для настольных компьютеров и мобильных 2017 года Apple заменила RC4 на AES в своей реализации arc4random. Страницы руководства для нового arc4random включают backronym «A Replacement Call for Random» для ARC4 в качестве мнемоники, поскольку он обеспечивает более качественные случайные данные, чем rand () делает.
Предлагаемые новые генераторы случайных чисел часто сравнивают с генератором случайных чисел RC4.
Несколько атак на RC4 могут отличить его выходные данные от случайной последовательности.
Многие потоковые шифры основаны на регистрах сдвига с линейной обратной связью (LFSR), которые, хотя и эффективны с точки зрения оборудования, менее эффективны с точки зрения программного обеспечения. Дизайн RC4 избегает использования LFSR и идеально подходит для программной реализации, поскольку требует только манипуляций с байтами. Он использует 256 байтов памяти для массива состояний, от S [0] до S [255], k байтов памяти для ключа, от ключа [0] до ключа [k-1] и целочисленных переменных, i, j и K. Выполнение модульного сокращения некоторого значения по модулю 256 может быть выполнено с помощью поразрядного И с 255 (что эквивалентно взятию младшего байта рассматриваемого значения).
Эти тестовые векторы не являются официальными, но удобны для всех, кто тестирует свою собственную программу RC4. Ключи и открытый текст - это ASCII, ключевой поток и зашифрованный текст - в шестнадцатеричном формате.
| Key | Keystream | Открытый текст | Шифрованный текст |
|---|---|---|---|
| Ключ | EB9F7781B734CA72A719… | Обычный текст | BBF316E8D940AF0AD3 |
| Wiki | 6044DB6D41B7… | pedia | 1021BF0420 |
| SecretBack | … 45A01F645FC35B383552544B9BF5 |
В отличие от современного потокового шифра (например, в eSTREAM ), RC4 не принимает отдельный nonce вместе с ключом. Это означает, что если один долгосрочный ключ должен использоваться для безопасного шифрования нескольких потоков, протокол должен указывать, как объединить одноразовый ключ и долгосрочный ключ для генерации ключа потока для RC4. Один из подходов к решению этой проблемы состоит в том, чтобы сгенерировать «свежий» ключ RC4 путем хеширования долгосрочного ключа с помощью nonce. Однако многие приложения, использующие RC4, просто объединяют ключ и одноразовый номер; Слабое расписание ключей RC4 затем приводит к связанным ключевым атакам, таким как атака Флюрера, Мантина и Шамира (которая известна тем, что нарушает WEP стандарт).
Поскольку RC4 является потоковым шифром, он более податлив, чем обычные блочные шифры. Если не используется вместе со строгим кодом аутентификации сообщения (MAC), то шифрование уязвимо для атаки с переворачиванием битов. Шифр также уязвим для атаки потоковым шифром, если он не реализован правильно.
Однако стоит отметить, что RC4, будучи потоковым шифром, в течение некоторого времени был единственным распространенным шифр, невосприимчивый к атаке 2011 BEAST на TLS 1.0. Атака использует известную слабость в способе использования режима цепочки блоков шифров со всеми другими шифрами, поддерживаемыми TLS 1.0, которые все являются блочными шифрами.
В марте 2013 г. были предложены новые сценарии атак Исобе, Охигаши, Ватанабе и Мори, а также Альфарданом, Бернштейном, Патерсоном, Поеттерингом и Шульдтом, которые используют новые статистические смещения в таблице ключей RC4 для восстановления открытого текста с помощью большое количество шифрований TLS.
Использование RC4 в TLS запрещено RFC 7465, опубликованным в феврале 2015 года.
В 1995 году Эндрю Роос экспериментально заметил, что первый байт ключевого потока коррелирует с первыми тремя байтами ключа, а первые несколько байтов перестановки после KSA коррелируют с некоторой линейной комбинацией ключевых байтов. Эти предубеждения оставались необъясненными до 2007 года, когда Гутам Пол, Сиддхешвар Рати и Субхамой Майтра доказали корреляцию ключевой поток, а в другой работе Гутам Пол и Субхамой Майтра доказали корреляцию перестановки ключа. Последняя работа также использовала корреляции перестановка-ключ для разработки первого алгоритма для полного восстановления ключа из окончательной перестановки после KSA, без каких-либо предположений о ключе или векторе инициализации. Этот алгоритм имеет постоянную вероятность успеха за время, которое является квадратным корнем из сложности исчерпывающего поиска ключа. Впоследствии было выполнено множество других работ по реконструкции ключей из внутренних состояний RC4. Субхамой Майтра и Гоутам Пол также показали, что смещения типа Рооса все еще сохраняются, даже если рассматривать индексы вложенных перестановок, например S [S [i]] или S [S [S [i]]]. Эти типы смещений используются в некоторых из более поздних ключевых методов реконструкции для увеличения вероятности успеха.
Ключевой поток, генерируемый RC4, смещен в различной степени в сторону определенных последовательностей, что делает его уязвимым для различительных атак. Лучшая такая атака принадлежит Ицику Мантину и Ади Шамиру, которые показали, что второй выходной байт шифра смещен в сторону нуля с вероятностью 1/128 (вместо 1/256). Это связано с тем, что если третий байт исходного состояния равен нулю, а второй байт не равен 2, то второй выходной байт всегда равен нулю. Такое смещение можно обнаружить, наблюдая только 256 байтов.
Сурадьюти Пол и Барт Пренил из COSIC показали, что первый и второй байты RC4 также были смещены. Количество требуемых выборок для обнаружения этого смещения составляет 2 байта.
и Дэвид МакГрю также продемонстрировали такие атаки, которые отличают ключевой поток RC4 от случайного потока, учитывая гигабайт вывода.
Полная характеристика одного шага RC4 PRGA была проведена Риддхипратимом Басу, Ширшенду Гангули, Субхамой Майтрой и Гутамом Полом. Рассматривая все перестановки, они доказывают, что распределение вывода не является равномерным для данных i и j, и, как следствие, информация о j всегда просачивается в вывод.
В 2001 году, и Шамир сделал новое и удивительное открытие: по всем возможным ключам RC4 статистика для Первые несколько байтов выходного ключевого потока строго неслучайны, что приводит к утечке информации о ключе. Если одноразовый номер и долгосрочный ключ просто объединяются для генерации ключа RC4, этот долгосрочный ключ может быть обнаружен путем анализа большого количества сообщений, зашифрованных этим ключом. Этот и связанные с ним эффекты затем были использованы для взлома шифрования WEP («эквивалентная проводная конфиденциальность»), используемого с 802.11 беспроводными сетями. Это вызвало борьбу за замену WEP на основе стандартов на рынке 802.11 и привело к усилиям IEEE 802.11i, и протоколы WPA.
могут защитить от этой атаки, отбросив начальную часть. ключевого потока. Такой модифицированный алгоритм традиционно называется «RC4-drop [n]», где n - количество отброшенных начальных байтов ключевого потока. По умолчанию SCAN n = 768 байтов, но консервативное значение будет n = 3072 байта.
Атака Fluhrer, Mantin и Shamir не применяется к SSL на основе RC4, поскольку SSL генерирует ключи шифрования, которые он использует для RC4 с помощью хеширования, что означает, что разные сеансы SSL имеют несвязанные ключи.
В 2005 году Андреас Кляйн представил анализ потокового шифра RC4, показывающий больше корреляций между потоком ключей RC4 и key., и использовал этот анализ для создания aircrack-ptw, инструмента, который взламывает 104-битный RC4, используемый в 128-битном WEP, менее чем за минуту. В то время как атака Флюрера, Мантина и Шамира использовала около 10 миллионов сообщений, aircrack-ptw может взломать 104-битные ключи в 40 000 кадров с вероятностью 50% или в 85 000 кадров с вероятностью 95%.
Комбинаторная проблема, связанная с количеством входов и выходов шифра RC4, была впервые поставлена и Ади Шамиром в 2001 году, в результате чего из всех 256 элементов в типичном состоянии RC4, если известно только количество элементов x (x ≤ 256) (все остальные элементы можно считать пустыми), то максимальное количество элементов, которые могут быть получены детерминированно, также равно x в следующих 256 раундов. Эта гипотеза была опровергнута в 2004 году с формальным доказательством, данным Сурадьюти Полом и Барт Пренил.
В 2013 году группа исследователей безопасности из Группа информационной безопасности в Royal Holloway, Лондонский университет сообщила об атаке, которая может стать эффективной с использованием всего 2 зашифрованных сообщений. Хотя это еще не практическая атака для большинства целей, этот результат достаточно близок к такому, что вызвал предположения о вероятности того, что некоторые государственные криптологические агентства могут уже иметь более эффективные атаки, которые делают RC4 небезопасным. Учитывая, что по состоянию на 2013 год большой объем трафика TLS использует RC4, чтобы избежать атак на блочные шифры, которые используют цепочку блоков шифра , если эти гипотетические лучшие атаки существуют, то это приведет к комбинация TLS-с-RC4 небезопасна против таких злоумышленников в большом количестве практических сценариев.
В марте 2015 года исследователь Royal Holloway объявил об улучшениях своей атаки, представив 2 атаки против паролей, зашифрованных с помощью RC4, как они используются в TLS.
На Black Hat Asia 2015 Ицик Мантин представил еще одну атаку против SSL с использованием шифра RC4.
В 2015 году исследователи безопасности из KU Leuven представили новые атаки на RC4 как в TLS, так и в WPA-TKIP. Названная атакой Numerous Occurrence MOnitoring Recovery Exploit (NOMORE), это первая атака такого рода, которая была продемонстрирована на практике. Их атака на TLS может расшифровать безопасный HTTP cookie в течение 75 часов. Атака на WPA-TKIP может быть завершена в течение часа и позволяет злоумышленнику расшифровать и ввести произвольные пакеты.
Как упоминалось выше, самая важная слабость RC4 связана с недостаточным расписанием ключей; первые байты вывода раскрывают информацию о ключе. Это можно исправить, просто отбросив некоторую начальную часть выходного потока. Это известно как RC4-dropN, где N обычно кратно 256, например 768 или 1024.
Было предпринято несколько попыток усилить RC4, в частности Spritz, RC4A, VMPC и RC4.
Сурадьюти Пол и Барт Пренил предложили вариант RC4, который они назвали RC4A.
RC4A использует два массива состояний S1 и S2, и два индекса j1и j2. Каждый раз, когда iувеличивается, генерируются два байта:
Таким образом, алгоритм выглядит так:
All арифметика выполняется по модулю 256 i: = 0 j1: = 0 j2: = 0, в то время как GeneratingOutput: i: = i + 1 j1: = j1 + S1 [i] поменять местами значения из S1 [i] и S1 [j1] выводят S2 [S1 [i] + S1 [j1]] j2: = j2 + S2 [i] меняют местами значения S2 [i] и S2 [j2] output S1 [S2 [i] + S2 [j2]] end while
Хотя алгоритм требовал того же количества операций на один выходной байт, параллелизм выше, чем у RC4, что обеспечивает возможное улучшение скорости.
Хотя этот алгоритм сильнее RC4, он также подвергся атаке: Александр Максимов и команда из NEC разработали способы отличить его результат от действительно случайной последовательности.
Вариативно модифицированная композиция перестановок (VMPC) является другим вариантом RC4. Он использует такое же расписание ключей, что и RC4, с j: = S [(j + S [i] + key [i mod keylength]) mod 256] с повторением 3 × 256 = 768 раз, а не 256, и с дополнительным дополнительные 768 итераций для включения исходного вектора. Функция генерации вывода работает следующим образом:
Вся арифметика выполняется по модулю 256. i: = 0 в то время как GeneratingOutput: a: = S [i] j: = S [j + a] output S [S [S [j] + 1]] Поменять местами S [i] и S [j] (b: = S [j]; S [i]: = b; S [j] : = a)) i: = i + 1 end while
Это было атаковано в тех же документах, что и RC4A, и его можно различить в пределах 2 выходных байтов.
RC4 - это модифицированная версия RC4 с более сложным трехфазным расписанием ключей (примерно в три раза дольше, чем RC4, или такой же, как RC4-drop512) и более сложной функцией вывода, которая выполняет четыре дополнительных поиска в массиве S. для каждого байтового вывода, что примерно в 1,7 раза больше, чем у базового RC4.
Все арифметические операции по модулю 256. << and>>- сдвиг влево и вправо, ⊕ - исключающее ИЛИ, а GeneratingOutput: i : = i + 1 a: = S [i] j: = j + a Обменять S [i] и S [j] (b: = S [j]; S [i]: = b; S [j]: = a) c: = S [i <<5 ⊕ j>>3] + S [j <<5 ⊕ i>>3] вывод (S [a + b] + S [c⊕0xAA]) ⊕ S [ j + b] конец пока
Этот алгоритм существенно не анализировался.
В 2014 году Рональд Ривест выступил с докладом и соавтором статьи об обновленном редизайне под названием Spritz. Аппаратный ускоритель Spritz был опубликован в Secrypt, 2016 и показывает, что из-за множества вложенных вызовов, необходимых для создания выходных байтов, Spritz работает довольно медленно по сравнению с другими хэш-функциями, такими как SHA-3 и наиболее известной аппаратной реализацией RC4.
Алгоритм:
Вся арифметика выполняется по модулю 256, в то время как GeneratingOutput: i: = i + wj: = k + S [j + S [i]] k: = k + i + S [j] поменять местами значения S [i] и S [j] output z: = S [j + S [i + S [z + k]]] end while
Значение w является относительно простым размером массива S. Таким образом, после 256 итераций этого внутреннего цикла значение i (увеличивается на w каждую итерацию) принимает все возможные значения 0... 255, и каждый байт в массиве S был заменен по крайней мере один раз.
Как и другие функции губки, Spritz может использоваться для построения криптографической хеш-функции, детерминированного генератора случайных битов (DRBG ), алгоритма шифрования, поддерживающего аутентифицированное шифрование со связанными данными (AEAD) и т. д.
В 2016 году Баник и Исобе предложили атаку, которая может отличить Spritz от случайного шума.
Если протокол отмечен «(необязательно)», RC4 - это один из нескольких шифров, для использования которых может быть настроена система.
