Флюрер, Мантен и Шамир атакуют
В криптографии атака Флюрера , Мантина и Шамира представляет собой атаку потокового шифра на широко используемый RC4 потоковый шифр . Атака позволяет злоумышленнику восстановить ключ в зашифрованном потоке RC4 из большого количества сообщений в этом потоке.
Атака Флюрера, Мантина и Шамира применима к конкретным методам получения ключей, но не применима в целом к SSL на основе RC4 (TLS) , поскольку SSL генерирует ключи шифрования, которые он использует для RC4, путем хеширования, а это означает, что разные сеансы SSL имеют несвязанные ключи. . [1] Однако тесно связанная с ней атака бар-мицвы , основанная на том же исследовании и обнаруженная в 2015 году, действительно использует те случаи, когда слабые ключи генерируются в процессе шифрования SSL.
Фон
[ редактировать ], Атака Флюрера Мантина и Шамира ( FMS), опубликованная в их статье 2001 года «Слабые стороны алгоритма планирования ключей RC4», [2] использует слабость алгоритма планирования ключей RC4 для восстановления ключа из зашифрованных сообщений. Атака FMS завоевала популярность в инструментах сетевых атак, включая AirSnort , weplab и aircrack , которые используют ее для восстановления ключа, используемого беспроводными сетями, защищенными WEP .
В этом обсуждении будет использоваться приведенный ниже алгоритм планирования ключей RC4 (KSA).
начать ksa(с длиной ключа int, с байтовым ключом[длина ключа]) для меня от 0 до 255 S[i] := я конец для j := 0 для меня от 0 до 255 j := (j + S[i] + key[i mod keylength]) mod 256 своп(S[i],S[j]) конец дляконец
Также будет использоваться следующий алгоритм псевдослучайной генерации (PRGA).
начать prga (с байтом S[256]) я := 0 j := 0 при генерации вывода: я := (я + 1) мод 256 j := (j + S[i]) mod 256 своп(S[i],S[j]) выход S[(S[i] + S[j]) mod 256] в концеконец
Атака
[ редактировать ]В основе атаки FMS лежит использование слабых векторов инициализации (IV), используемых с RC4. RC4 шифрует по одному байту за раз с помощью потока ключей, выдаваемого prga() ; RC4 использует ключ для инициализации конечного автомата через ksa() , а затем непрерывно изменяет состояние и генерирует новый байт потока ключей из нового состояния. Теоретически поток ключей функционирует как случайный одноразовый блокнот , поскольку генератор псевдослучайных чисел управляет выводом на каждом шаге.
При использовании некоторых IV злоумышленник , зная первый байт потока ключей и первые m байтов ключа, может получить ( m + 1)-й байт ключа из-за слабости KSA. Поскольку первый байт открытого текста поступает из заголовка WEP SNAP , злоумышленник может предположить, что он может получить первый байт потока ключей из B ⊕ 0x AA (заголовок SNAP почти всегда равен 0xAA). Отсюда им нужен только IV в форме ( a + 3, n − 1, x ) для индекса ключа a, равного 0, пространства значений элемента n, равного 256 (поскольку 8 бит составляют байт), и любого x . Для начала злоумышленнику нужны IV (3, 255, x ). WEP использует 24-битные IV, длина каждого значения составляет один байт.
Для начала злоумышленник использует IV в качестве первых трех элементов в K[ ]. Они заполняют S-блок S[ ] последовательными значениями от 0 до n , как это делает RC4 при инициализации S-блока из известного K[ ]. Затем они выполняют первые три итерации ksa(), чтобы начать инициализацию S-блока.
После третьего шага злоумышленник может, хотя и не обязательно, получить четвертый байт ключа, используя выходные данные потока ключей O , вычислив (O − j − S [ i ]) mod n = K [ i ] со значением i = 3 на этом этапе.
На данный момент у злоумышленника еще нет четвертого байта ключа. Этот алгоритм не восстанавливает следующий байт ключа; он генерирует возможное значение ключа. Собрав несколько сообщений (например, пакетов WEP) и повторив эти шаги, злоумышленник сгенерирует ряд различных возможных значений. Правильное значение появляется значительно чаще, чем любое другое; злоумышленник может определить значение ключа, распознав это значение и выбрав его в качестве следующего байта. В этот момент они могут снова начать атаку на пятый байт ключа.
Хотя злоумышленник не может атаковать слова ключа не по порядку, он может сохранять сообщения для последующей последовательной атаки на более поздние слова, как только он узнает более ранние слова. Опять же, им нужны только сообщения со слабыми IV, и они могут отбрасывать другие. Благодаря этому процессу они могут собрать большое количество сообщений для атаки на весь ключ; на самом деле, они могут хранить только короткую часть начала этих сообщений, достаточную для проведения атаки до тех пор, пока слово ключа, которое IV позволит им атаковать.
Ссылки
[ редактировать ]- ^ «Реакция безопасности RSA на слабые места в алгоритме планирования ключей RC4» . Лаборатории РСА. 9 сентября 2001 г.
- ^ Флюрер С., Мантин И. и А. Шамир, « Слабые стороны алгоритма планирования ключей RC4 », Избранные области криптографии: SAC 2001, Конспекты лекций по информатике, том. 2259, стр. 1–24, 2001.
