Статистические атаки на RC4. Отличительные признаки WPA

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:56, 27 сентября 2015.
Statistical Attack on RC4
Distinguishing WPA
Statistical attack RC4.png
Авторы Pouyan Sepehrdad, Serge Vaudenay, Martin Vuagnoux
Опубликован 2010 г.
Сайт EPFL CH-1015 Lausanne, Switzerland
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. В данной статье мы разработаем несколько инструментов для работы с наборами смещений при анализе RC4. Затем мы покажем, как с помощью оптимизированных подходов взломать на основе 4000 пакетов WEP, при условии, что первые байты открытого текста известны для каждого пакета. Мы дадим описание схожих атаки и для WPA. Вначале мы опишем отличительный признак WPA сложности и преимуществом в , который использует пакетов. Затем, основываясь на некоторых атаках восстановления частичного временного ключа, мы получим полный 128-битный временный ключ, используя пакетов. Это удастся сделать и при сложности . На сегодняшний день это наилучшая атака на WPA. Мы полагаем, что наш анализ способствует большему пониманию безопасности RC4.

Введение

RC4 был создан Ривестом в 1987 г. Алгоритм являлся коммерческой тайной, пока не был размещен в открытом доступе в 1994 г. В настоящее время RC4 широко применяется в SSL/TLS и беспроводных технологиях связи Wi-Fi 802.11. Ранее cтандарт 802.11 [1] был защищен алгоритмом WEP (Wired Equivalent Privacy), который теперь из-за наличия уязвимостей безопасности заменяется на WPA (Wi-Fi Protected Access).

В WEP применяется RC4 с совместно используемым ключом. Каждый пакет зашифровывается путем сложения по модулю 2 с ключевым потоком, сгенерированным RC4. Ключ алгоритма - совместно используемый ключ, предваряемый тремя байтами вектора инициализации IV. IV передается в незашифрованном виде для самосинхронизации. В связи с этим было предложено несколько атак на полный алгоритм RC4, и их результаты оказались поразительными. Действительно, злоумышленник знает, что ключ является константой за исключением IV, который уже известен. Активный злоумышленник может даже изменить IV. В настоящее время WEP считается крайне ненадежным, так как пассивный злоумышленник может легко восстановить весь ключ, полагая, что первые байты каждого кадра открытого текста известны. Такое оказывается возможным из-за спецификаций протокола.

Вдобавок к генерации ключей WPA обеспечивает схему защиты целостности пакета, которая предотвращает возможность модификации или повторной передачи IV. Следовательно, имеет смысл рассматривать только пассивные атаки восстановления ключа.

Для того, чтобы разрешить указанную выше проблему, объединение крупнейших производителей компьютерной техники и беспроводных устройств Wi-Fi (Wi-Fi Alliance) заменило WEP на WPA [1]. В основе равноправной аутентификации лежит IEEE 802.1X, с которым согласован обычный режим аутентификации на базе совместно используемого ключа (WPA-Pre-Shared Key, WPA-PSK). Аутентификация создает временный ключ (Temporary Key, TK). ТК необходим в протоколе целостности временного ключа (Temporary Key Integrity Protocol, TKIP) для генерации ключей на каждый передаваемый пакет данных (Per-Packet Keys, PPK). Идея выработки из TK временных ключей адресов передачи (Temporal Transmitter Adress Key, TTAK) используется для ограниченного числа кадров. Каждый кадр применяет к TTAK и счетчику команд (TKIP Sequence Counter, TSC) простое преобразование для того, чтобы выработать RC4-пакетные ключи PPK. Здесь также первые 3 байта ключа RC4 известны (фактически они зависят от счетчика).

Вдобавок к генерации ключа WPA обеспечивает схему защиту целостности пакета, которая предотвращает от повторного использования или модификации IV. В связи с чем могут быть рассмотрены только пассивные атаки восстановления ключа.

Наша работа.В данной статье мы разработаем инструменты для работы с наборами смещений.В соответствии с нашей концепцией мы затем проанализируем несколько статистических методов восстановления частичного ключа. Мы применим их, чтобы восстановить 8 слабых битов ключа TK алгоритма WPA при использовании от до пакетов. Кстати, мы проанализируем подобным образом WEP и покажем, что наилучшие на сегодняшний день атаки все еще могут быть улучшены. Вслед за этим мы превратим атаку восстановления частичного ключа в настоящий отличительный признак для WPA. Наконец, мы выполним восстановление полного ключа сессии со сложностью и пакетов.

Обзор существующих работ. Напомним три подхода к криптоанализу RC4: атаки, основанные на уязвимостях Алгоритма Ключевого Расписания (KSA), атаки, использующие уязвимости Алгоритма Псевдослучайного Генератора (PRGA), и анализ "черного ящика".

Что касается KSA, одной из первых опубликованных уязвимостей RC4, то она была обнаружена Рузом (Roos) [2] в 1995 г. Эта корреляция связывает байты секретного ключа с начальным состоянием Руз (Roos) [2] и Вагнер (Wagner) [3] определили классы слабых ключей, раскрывающих секретный ключ в том случае, если известны первые байты ключа. Данное свойство активно использовалось для вскрытия WEP (см. [4],[5],[6],[7],[8],[9],[10],[11],[12]). Другая категория результатов связана с проблемой инверсии KSA: она заключается в задаче восстановления секретного ключа при заданном конечном состоянии KSA [13],[14].

Относительно PRGA следует сказать, что его исследование было в значительной степени мотивировано дифференциальным криптоанализом [15],[16],[17],[18] или восстановлением из байтов ключевого потока начального состояния [19],[20],[21],[22] со сложностью для лучшей атаки восстановления состояния. Существенное изучение PRGA выявляет смещения выходных байтов ключевого потока в работах [23],[24]. Миронов (Mironov) в [25] предлагает обязательно отбрасывать первые 512 байт начального ключевого потока для того, чтобы исключить возможность возникновения описанных выше уязвимостей.

Дженкинс (Jenkins) в 1996 г. опубликовал на своем веб-сайте [26] два смещения в PRGA алгоритма RC4. Эти смещения были обобщены Мантином (Mantin) в его магистерской диссертации [27]. Пол (Paul), Рати (Rathi) и Майтра (Maitra) [28] открыли в 2008 г.индекс смещенного выхода в первом слове ключевого потока, сгенерированного PRGA. Другое смещение в PRGA было экспериментально обнаружено Майтрой (Maitra) и Полом (Paul) [29]. Наконец, Сепердад (Sepehrdad), Водени (Vaudeney) и Вуагну (Vuagnoux) [9] выявили в PRGA 48 новых корреляций и 9 новых корреляций между битами ключа и ключевым потоком. Все это привело к созданию в настоящее время самой быстрой атаки на WEP.

Как правило, атаки восстановления ключа на RC4 должны привязывать уязвимости KSA к уязвимостям PRGA для того, чтобы установить соотношение между словами секретного ключа и словами ключевого потока. Некоторые смещения PRGA [30],[28],[29] были успешно привязаны к корреляции Руза [2], чтобы обеспечить возможность атак по известному открытому тексту. Другой принцип - анализ "черного ящика", не требует никаких привязок. Это было использовано в [9].

В 2004 г. Моэн (Moen), Раддум (Raddum) и Хоул (Hole) [31] выяснили, что получение, по крайней мере, двух пакетных ключей RC4 в алгоритме WPA ведет к полному восстановлению временного ключа и ключа проверки целостности сообщения. В случае успешного восстановления двух ключей одного и того же сегмента из последовательных пакетов может быть применена атака Моэна, Раддума и Хоула. Это приводит к возможности атаки восстановления ключа TK на WPA со сложностью при использовании 2 пакетов. Практически все известные и новые атаки восстановления ключа на WEP могут быть применены и к WPA, если бы некоторые пакеты имели один и тот же ключ RC4. Действительно, только атака Флурера (Fluhrer), Мантина (Mantin) и Шамира (Shamir) [5] является исключением из этого правила. Однако WPA использует разные секретные ключи для каждого зашифрованного пакета. В 2009 г. Тьюс (Tews) и Бек (Beck) [10] нашли реальную атаку на WPA-PSK для вставки данных в зашифрованное сообщение. Обратите внимание, что эта атака не восстанавливает ключ зашифрования и требует некоторые дополнительные особенности качества обслуживания (описаны стандартом IEEE 802.11e), по умолчанию не задействованные.

Содержание статьи. Сначала, в разделе 2, мы представим RC4, WEP и WPA, известные смещения в RC4 и некоторые инструменты для возможности управления наборами смещений байтов целевого ключа. Затем, для выявления отдельных "слабых битов" временного ключа, в разделе 3 мы исследуем атаку восстановления ключа. Мы покажем ее применение к WEP в разделе 4 и вслед за этим, в разделе 5, опишем отличительный признак WPA и восстановление полного временного ключа WPA.

Предварительные замечания

Описание RC4 и обозначения

Поточный шифр RC4 состоит из двух алгоритмов: Алгоритма Ключевого Расписания (Key Scheduling Algorithm, KSA) и Алгоритма Псевдослучайного Генератора (Pseudo Random Generator Algorithm, PRGA). Состояние алгоритма RC4 определяется двумя регистрами (словами) и и одним массивом (из слов) определяющим перестановку на KSA генерирует начальное состояние для PRGA из произвольного ключа состоящего из слов, как показано на Сх. 1. KSA начинает с массива где и обменивает местами пар в зависимости от значения секретного ключа В конце работы KSA получаем начальное состояние

Как только готово начальное состояние оно начинает использоваться вторым алгоритмом RC4, PRGA. Его роль заключается в выработке ключевого потока слов, длиной впоследствии складываемых по модулю 2 с открытым текстом для получения зашифрованного сообщения. Таким образом, RC4 вычисляет цикл PRGA каждый раз, когда согласно алгоритму на Сх. 1 необходимо новое слово ключевого потока Обратите внимание, что всякий раз, когда генерируется слово ключевого потока, внутреннее состояние RC4 обновляется.

Обозначения. В данной статье, мы определим все операторы, такие, как сложение, вычитание и умножение, в группе где (т.е. слова являются байтами). Так, должно читаться, как

KSA
1: for to do
2:     
3: end for
4:
5: for to do
6:    
7:     swap
8: end for
PRGA
1:
2:
3: loop
4:     
5:    
6:     swap
7:     выход
8: end loop
Сх. 1. Алгоритмы KSA и PRGA

Пусть соответственно, обозначает значение перестановки, определяемой массивом и индексом после ого раунда в KSA (соответственно, в PRGA). Также обозначим Пусть (соответственно, ) является значением после ого раунда в KSA (соответственно, в PRGA), где раунды нумеруются в соответствии с Таким образом, KSA имеет раунды а PRGA - KSA и PRGA определяются следующим образом:

KSA

    

    
PRGA
    
    


    

Описание WEP

WEP [32] использует 3-байтовый IV, сцепленный с секретным ключом из 40 или 104 бит (5 или 13 байт), как и ключ RC4. Так, размер ключа RC4 или 64, или 128 бит. В данной статье мы не рассматриваем случай 40-битового ключа. Итак, Имеем:

где IVi обозначает й байт и - зафиксированная секретная часть ключа. Теоретически значение IV должно быть произвольным, но на практике он представляет собой счетчик, главным образом, формата little-endian, инкрементируемый на единицу вский раз после зашифрования очередного 802.11b-кадра. Иногда некоторые отдельные значения IV пропускаются, чтобы помешать осуществлению особых атак на основе "слабых IV". Таким образом, каждый пакет использует слегка отличный ключ. Затем RC4 генерирует ключевой поток, складываемый по модулю 2 с открытым текстом для получения зашифрованного текста.

Хорошо известно [33], что значительная часть открытого текста практически постоянна и что другие байты могут быть предсказаны. Они соответствуют заголовку LLC, заголовку SNAP и нескольком байтам инкапсулированного кадра TCP/IP. Например, складывая по модулю 2 первые байты шифртекста с константным значением 0хАА, получим первые байты ключевого потока. В таком случае, даже если эти атаки и называются атаками по известному открытому тексту, на деле имеется только шифртекст.

Описание WPA

Для защиты от атаки Флурера-Мантина-Шамира [5] WPA включает ключ хэш-функции [34], Код Целостности Сообщения (Message Integrity Code, MIC) [35] и схему управления ключами на базе 802.1Х [36] для исключения возможности повторного использования ключа и облегчения распространения ключей.

128-битовый Временной Ключ (Temporal Key, TK) является посессионным ключом. Он вырабатывается из схемы управления ключами во время аутентификации и представляет собой входное значение фазы 1 (phase1) хэш-функции ключа (алгоритма перемешивания ключей) вместе с 48-битовым Адресом Передачи (Transmitter Address, TA) и 48-битовым Счетчиком Последовательности TKIP (TKIP Sequence Counter, TSC), часто также называемым IV. Мы не будем полььзоваться последним наименованием, чтобы не путать его с первыми 3 байтами ключа RC4 (которые в действительности только зависят от TSC, но не равны ему).

TK может быть применен для зашифрования пакетов. Каждый пакет имеет 48-битовый индекс TSC, который делится на IV32 и IV16. Счетчик IV32 увеличивается на единицу каждый раз в пакетов. Пакет зашифровывается 128-битовым RC4KEY, вырабатываемым из TK, TSC и некоторых других параметров (например, адресов устройств), которые можно считать постоянными и известными злоумышленнику. Для WEP первые три байта RC4KEY зависят только от TSC, так, что они не секретны. Механизм выработки состоит из двух фаз. Первая фаза не зависит от IV16 и в целях эффективности выполняется каждые пакетов. Она создает 80-битовый ключ TTAK носящий в стандарте название TKIP-перемешенного Адреса Передачи и Ключа (TKIP-mixed Transmitter Address and Key, TTAK) (но обозначаемый в спарвочном коде, как P1K).

TTAK = phase1(TK, TA, IV32)

Вторая фаза использует TK и IV16 для выработки 96-битового ключа PPK, который затем преобразует в RC4KEY:

RC4KEY = phase2(TK, TTAK, IV16)

Выработка ключа в WPA основывается на совместно используемом ключе, как показано на Сх. 2 (без параметров протокола, таких, как TA).

WPA Key Derivation based on PKKAM.png
Сх. 2. Выработка ключа WPA на основе аутентификации совместно используемым ключом

RC4KEY легко вычисляется из PPK, TK и IV16 следующим образом:

RC4KEY[0] = high8(IV16)
RC4KEY[2] = low8(IV16)
RC4KEY[4] = low8(PPK[0])
RC4KEY[6] = low8(PPK[1])
RC4KEY[1] = (high8(IV16) или 0х020) и 0х7f
RC4KEY[3] = low8((PPK[5] (TK[1] TK[0])) >> 1)
RC4KEY[5] = high8(PPK[0])
RC4KEY[7] = high8(PPK[1])

Вследствие чего примем RC4KEY и IV чтобы использовать те же обозначения, что и в WEP. По принятому соглашению TTAK и PPK рассматриваются, как вектора 16-битовых слов. TK и RC4KEY - как вектора 8-битовых слов. Вектора нумеруются, начиная с 0.

Обратите внимание, что фильтр предупреждает использование некоторых классов слабых IV. На самом деле, только одного класса слабых IV, обнаруженного Флурером, Мантином и Шамиром [5].

Смещения в RC4

На протяжении всей данной статьи мы считаем Пусть обозначает ключевой поток, вырабатываемый из посредством RC4. Первые байты кадра открытого текста обычно известны (см. [12]), так же, как и IV, первые 3 байта То есть, мы предполагаем, что злоумышленник может использовать и IV в атаке по известному открытому тексту.

Пусть является множеством целых чисел, равных индексам уже известных байтов ключа. Назовем ключом значение clue для всех байт с индексами, лежащими в В исходном состоянии имеем и clue = IV.

При данном множестве индексов и индексе допустим, что имеется список row пар в которых является функцией такой, что для каждого ключа clue имеем:

clue

Для упрощения, допустим, что при данных и clue все clue попарно различны. Далее предположим, что результаты clue с отличными независимы. Также примем, что вида clue clue где clue лежит в области определения размером просто функция сжатия данных до минимально необходимого.

Будем использовать список классов смещений и Табл. 1 (см. [9]). Говоря более конкретно, нам понадобятся ряды row из Табл. 2, взятой из [33]. Эта таблица применима к RC4 в целом, но может быть преобразована к контексту WEP или WPA благодаря Действительно, имеем для и Определим deduce как множество всех таких, что мы можем вычислить используя то свойство, основанное на значениях с индексами в Например, deduce и deduce Затем мы трансформируем вышеупомянутую таблицу, удаляя некоторые ряды для ключей, который могут быть выведены из других, и соединяя ряды, приводящие к одному и тому же байту ключа. То есть, определим row следующим образом: если deduce то ряд имеет единственное "смещение" clue с вероятностью так как может быть вычислено из clue.

Табл. 1. Классы смещений в RC4[П 1]
Ряд
Описание
См. подробнее
MaitraPaul
[29]
KleinImproved
[12]
SVV_bb_000
[9]
SVV_bb_003
[9]
SVV_008
[9]
SVV_009
[9]


Табл. 2. Таблица безусловных смещений в RC4 по известным Байтам Ключа
Смещения
MaitraPaul
KleinImproved
SVV_bb_000
KleinImproved
MaitraPaul
SVV_bb_003
KleinImproved
MaitraPaul
KleinImproved
MaitraPaul
KleinImproved
MaitraPaul
SVV_008
SVV_009
KleinImproved
MaitraPaul
KleinImproved
MaitraPaul
KleinImproved
SVV_008
SVV_009
KleinImproved
KleinImproved

В противном случае, ряд представляет собой конкатенацию всех row для в deducededuce Например, row имеет единственное смещение, row row и

row rowrowrow

При наличии двух списков индексов байтов и составим новую таблицу где список рядов имеет вид: row, row, ... , row. Например, и является списком индексов байтов ключа, последовательно вычисляемых с помощью смещений. Допустим, что минимальное множество в смысле отсутствия строго меньшего множества с тем же самым deduce Далее примем, что минимальное множество в смысле отсутствия строго меньшего множества с тем же самым и deduce Например, минимально для а уже нет. Обозначим принадлежащий к множеству, размером При данном пусть длина ряда для в При данном кортеже таком, что для каждого собирая вместе все ые смещения ряда получим собранное в одно целое смещение для определения из и ключа Обратите внимание, что по техническим причинам нам, может быть, потребуется хранить элементы в Вот почему у нас могут быть ряды для в с единым смещением вероятности 1. Пусть

является количеством возможных собранных в единое целое смещений. Для удобства пронумеруем собранные в одно целое смещения индексом изменяющимся от 1 до и каждое количество определяет кортеж Итак, -ое смещение определяется clue с вероятностью

где вероятность ого смещения в ряду, соответствующим в

Пусть это увеличенная в степени до количества байтов и байтов, и пусть оно участвует в любом из равенств со смещениями из Например, так как смещения для основаны на и а смещения для и основаны на и Далее, для вычисления требуется IV. Таким образом, в общем, имеем 8 байтов: для и IV. При наличи ключевого потока определим ,clue как вектор всех и clue байтов, необходимых в дальнейшем. Также определим

Для простоты будем пользоваться обозначениями и в то время, как имеется ли в виду или будет ясно из контекста. То есть, область имеет размер и переводит область определения элементов в область из элементов.

В дальнейшем используем следующее:

для целого числа и

называется накопленным смещением порядка В нижеследующей таблице приведено несколько примеров накопленных смещений.

Условные смещения в RC4

Расширим понятие смещения до понятия условного смещения. Допустим, что для каждого существует функций и соответствующих предикатов таких, что:

,clue,clue

для некоторой вероятности Далее считаем, что

,clue

и частоту возникновения плотностью смещения. Для упрощения бдем считать, что для некоторого данного и clue, все предложенные ,clue при фиксированных ,clue попарно различны. В дальнейшем будем считать, что события ,clue с различными независимы. Также примем, что и имеют вид ,clue,clue и ,clue,clue где ,clue лежит в области определения размера

Мы применяем условные смещения в Табл. 5. Все из них за исключением SVV_db были взяты из Корека (Korek) [7] (также они могут быть заимствованы из Aircrack, см. [37],[12]). Мы применили несколько новых формул для вычисления их вероятностей, которые приведены в Приложении.

При наличии двух минимальных множеств байтовых индексов и как было дано и в предыдущем разделе, сформируем таблицу и составим список собранных в единое целое смещений, в которых вероятности и плотности преумножены. Определим

и

соответственно представляет собой обычный соотв. со специальным корректирующим фактором, зависящим от некоторого значения Эта корректировка может быть произвольной. Она появиться при анализе в рразделе 3. Значения могут быть легко вычислены следующим путем:

В дальнейшем при считаем, что для приближения Таким образом, вычислим так же, как и но при добавлении условия деления обычного для безусловного смещения.

Приближенные значения позволяют вычислить с невысокой сложностью. А именно, мы можем рассчитать все необходимые за время где суммарное количество смещений, хотя число собранных в единое целое смещений порядка может быть очень велико.

Дополнительные определения

Обозначим

В частности,

Атака слабых битов на основе смещений

8 битов TK называют слабыми , так как они имеют простую зависимость от битов PPK . Эти биты представляют собой 7 наиболее значимых битов TK[0] и, по крайней мере, один значимый бит TK[1]. Дадим определение статистическим атакам, используя следующие отображения:

IVm

где -ый ключевой поток, использующий IVm, сжатая информация для вычисления несколько байтов RC4 ключа для вычисления некоторые данные о TK, которые требуется восстановить, применяя статистику. Обозначим через количество возможных значений для .

Первая атака: восстановление нескольких слабых битов TK

Мы пользуемся и При заданных злоумышленник может вычислить и Имеем

PPK
low8PPK

Таким образом, при данных злоумышленник может рассчитать high7 посредством

low7

суммарное количество возможных и суммарное количество возможных Имеем суммарное количество ,IV

Мы можем восстановить 7 слабых битов следующим образом: для каждого подходящего значения каждого пакета и каждого соответствующего кортежу в случае выполнения общего условия ,IVm определим ,IVm как значение байтов ключа RC4, подсказанное смещением по пакету котороя является истинным с вероятностью . Пусть предполагаемое значение рассчитанное указанным ранее способом. Пусть равен некоторому магическому коэффициенту (в дальнейшем будет оптимизирован), если ,IVm или равен 0 в противном случае. Допустим, что где суммарное количество необходимых пакетов. Очевидно, что значение с вероятностью в то время, как другие возникают произвольно. Примем, что неверные решения появляются с одной и той же вероятностью

Если неверное значение, то тогда точно не установлено, является ли корректным или нет. Так как сбалансировано, неправильное значений имеет значений принадлежащих множеству из неверных значений. Итак, предположим, что верно с вероятностью а для некорректных представляют собой случайные переменные с ожидаемыми значениями

в том случае, если ложное.

Если верное значение, то оно истинно с вероятностью для верного и когда один из ложных прообразов на То есть, с общей вероятностью Таким образом, для корректных являются случайными переменными с ожидаемымми значениями

Разница между этими двумя ожидаемыми значениями важна, но не таже самая, что и для разброса значений. Так как каждый берется с грубой вероятностью то допускаем, что разброс всех приблизительно равен Пусть оператор разницы между распределениями хороших и плохих . Имеем

Где обозначает ожидаемое значение переменной для любого плохого . Здесь мы убрали индекс у в выражении и , так как не зависят от конкретного значения . Пусть будет такой, что . Вероятность того, что правильный меньше, чем неверный , равна . То есть, ожидаемое количество неправильных с большими равно

Итак,

Взяв производную от числителя и знаменателя дроби относительно и приравняв их, получим, что оптимальное значение достигается для

Это приводит, в свою очередь, к

Таким образом, можем четко проследить, где возникает поправка .

Механизм атаки выглядит следующим образом:

1: присвоить и
2: инициализировать счетчики нулями
3: for to do
4: for to do
5: if ,IVm выполняется then
6: вычислить ,IVm и предполагаемые
7: вычислить
8: увеличить на
9: end if
10: end for
11: end for
12: выход

Очевидно, что сложность по времени составляет . Сложность измеряется по количеству исполняемых инструкций if. Она должна иметь сложность, в сущности эквивалентную выполнению фазы 2 (phase2) выработки ключа. Объем требуемой памяти имеет порядок величины . Далее следуют разновидности атаки:

1: присвоить и
2: инициализировать таблицу нулями
3: for to do
4: for всех возможных , таких, что выполняется do
5: вычислить
6: увеличить на
7: end for
8: end for
9: инициализировать счетчики нулями
10: for to do
11: for всех do
12: вычислить ,IVm
13: увеличить на
14: end for
15: end for
16: выход

Теперь сложность по времени составляет , а объем требуемой памяти - . Таким образом, можно сказать, что сложность равна

Две кривые сложности пересекаются в значении при .

Для имеем и . В Табл. 3 сведены значения сложностей с использованием и без использования условных смещений. Как видим, при игнорировании условных смещений требуется примерно на 30% больше пакетов, но при этом сложность намного ниже из-за меньшего . Таким образом, в данном случае условные смещения не приносят никакой пользы.

Вторая атака

Пусть и low1TK последними слабыми битами. При данных IV и получим путем

high1

Итак, мы применили первую атаку с такими и . Так как , то у нас есть большее количество смещений. Из равенств и имеем и .

Для имеем и . Сложности приведены в Табл. 3. Опять же, условные смещения здесь оказываются не слишком полезными. Также отсюда явно следует,что такой выбор приводит к атаке, лучшей в отношении чем та, что описана в разделе 3.1, хотя и сложность несколько выше вследствие большего .

Атаки слиянием

Наличие двух данных атак с множествами соответственно для покрытия независимых соответственно приводит к характеристикам соответственно соответственно соответственно соответственно , при этом возникает единственная проблема: как соединить два отсортированных списка и . Можно воспользоваться подходом Джунода-Водени (Junod-Vaudenay) [38]. Для этого отсортируем пары согласно их коэффициенту вероятности появления, полученному путем перемножения коэффициентов вероятности появления обоих членов каждой пары. Предположим, что все независимы, нормально распределены с отклонением и математическим ожиданием, равным или или . При данном коэффициент для , являющийся верным значением исходя из наблюдения , равен:


Таким образом, при перемноженожении членов такого вида для пар значений их сортировка по возрастанию результата произведения эквивалентна их сортировке по увеличению значения

С теми же допущениями, что и в [15], оказываемся в ситуации, в которой распределено по нормальному закону. Имеем

Итак, , среднее количество неподходящих пар с большим весом, чем у верной пары, составляет . В общем и целом, можем использовать

и см. для и . Мы вправе применять эти правила соединения для слияния двух предыдущих атак. Результаты получим из Табл. 3.

Табл. 3 показывает сложность при слиянии предыдущих атак для восстановления 8-ми слабых битов TK. Их можно сравнить с атаками при использовании напрямую соединенного в единое множества . Как несложно заметить, атаки слиянием с малым намного лучше.

Табл. 3. Сложности некоторых атак для восстановления битов TK[П 2]
Описание Условное смещение
1u Раздел 3.1
нет
Раздел 3.1
да
2u Раздел 3.2
нет
Раздел 3.2
да
3u Объединение 1u и 2u
нет
3c Объединение 1c и 2c
да
4u
нет
4c
да


Можно предположить, что мы могли бы получить результаты лучше, если бы взяли только для вычисления коэффициента вероятности появления для полный вектор вместо . Выполнив еще раз вычисления, получим

Если хорошее и плохое, то экспонента в сумме имеет порядок . Если плохое и хорошее, то экспонента имеет порядок . Когда оба значения плохие, то она имеет порядок . Таким образом, остается сравнивать один коэффициент порядка с остальными порядка . Известно, что неверный коэффициент больше превосходит правильный с вероятностью . При перемножении независимых коэффициентов вероятности появления для и , если считать приблизительно равными , то получим коэффициент вероятности появления олного и того же вида на основе . Это подтверждает вышеуказанное правило сортировки пар в соответствии с их весом .

Атаки на WEP

Применим первую атаку с мы только хотим восстановить байты ключа, которые одинаковы для всех пакетов. Эта атака создает в виде списка рейтинг возможных по убыванию вероятности появления.

Применяем следующую атаку:

1: вычислить рейтинг для и
2: for каждого в do
3: выполнить рекурсивную атаку по входу
4:end for
5: остановка: атака не удалась

рекурсивная атака с входом

6:if then
7: вычислить рейтинг для и
8: укоротить до первых значений
9: for каждого в do
10: выполнять рекурсивную атаку по входу
11: end for
12: else
13: for каждого do
14: проверить ключ и остановиться, если он верный
15: end for
16: end if

Пусть для и будет используемым в атаке на . Аналогично, пусть , и будут их параметрами согласно равенствам . Пусть класс корректных значений в . Известно, что . Как легко заметить, . Согласно закону больших чисел? вероятность того, что меньше, чем , равна , так, что вероятность успеха составляет , а сложность

Чтобы приблизиться к оптимальному выбору , положим для некоторых : . Вероятность успеха в таком случае . Мы можем скорректировать , таким образом, что она достигнет 50%, в результате чего получим в зависимости от . Вычисления показали, что лучшие значения достигаюьися при . Для этого положим . На сх. 3 мы построили график зависимости от .

Обратите внимание, что данные вычисления подразумевают действительные значения для . Так как они должны быть целыми числами, то сложность для действительных может быть несколько выше. Например, для откладываемая нами на графике сложность - . Имея дело с суммарными значениями, можем попробовать взять для и для . Тогда получим и вероятность успеха в 51%.

Заметьте, что без условных смещений тот же самый анализ с 4000 дает сложность порядка . В таком случае, эти смещения имеют существенное значение.

Fig3 rc4.png
Сх. 3. Логарифмическая сложность взлома WEP в зависимости от информационной сложности

Атаки на WPA

Отличительные особенности WPA

Первая атака может превращается в отличительный признак следующим образом. Ожидаемое значение и отклонение от истинного составляют приблизительно и соответственно. Случайная переменная превосходит с вероятностью . В то же время, если заменим пакеты WPA некоторыми произвольными последовательностями, все счетчики будут иметь ожидаемые значения и отклонение, приблизительно равное . Вероятность того, что данный счетчик превысит составляет . Вероятность того, что любой из счетчиков превысит это значение, ниже, чем . Таким образом, условие представляет собой отличительный признак тех же и , что и в первой атаке, и с превосходством более, чем . Мы подобрали оптимальное . Итак, Adv с

Мы пользуемся теми же значениями, что и раньше, и ориентируемся на Adv . Возьмем из , из , и нижнюю границу превосходства из . Качества отличительных признаков собраны в Табл. 4. Кроме того, атака, основанная на , лучше в смысле количества пакетов, но не в плане сложности. Она выполняется, задействуя пакетов, со сложностью . Другая атака, на базе , работает с большим на 30% числом пакетов , без условных смещений, но с гораздо лучшей сложностью .

Табл. 4. Сложности некоторых отличительных признаков WPA[П 3]
Условное смещение
1u
нет