Fluhrer Mantin Shamir атака

Атака Флюрера — Мантина — Шамира (Fluhrer, Mantin and Shamir attack, FMS-атака) — это метод криптоанализа, направленный на восстановление секретного ключа потокового шифра RC4. Атака была разработана в 2001 году криптографами Скоттом Флюрером (Scott Fluhrer), Ициком Мантином (Itsik Mantin) и Ади Шамиром (Adi Shamir). Она основана на анализе статистических аномалий в начальной части генерируемой гаммы (ключа шифрования) и позволяет эффективно восстанавливать ключ при наличии большого количества перехваченных сообщений, зашифрованных с использованием слабых ключей или известных начальных векторов (IV). FMS-атака стала одной из самых известных практических реализаций атаки на WEP (Wired Equivalent Privacy) — протокол безопасности беспроводных сетей стандарта IEEE 802.11.

История и предпосылки

Шифр RC4 был разработан Роном Ривестом в 1987 году и долгое время оставался коммерческой тайной компании RSA Security. В 1994 году его алгоритм был анонимно опубликован в интернете, после чего RC4 получил широкое распространение в различных протоколах, включая SSL/TLS и WEP. К началу 2000-х годов RC4 считался достаточно стойким для практического применения, однако его реализация в протоколе WEP содержала фундаментальную уязвимость.

В 2001 году Скотт Флюрер, Ицик Мантин и Ади Шамир опубликовали работу «Weaknesses in the Key Scheduling Algorithm of RC4» (Уязвимости в алгоритме планирования ключей RC4), в которой впервые описали атаку, основанную на слабых начальных векторах. Эта работа показала, что при определённых условиях злоумышленник может восстановить секретный ключ, перехватив всего несколько тысяч пакетов данных в сети Wi-Fi. Атака стала сенсацией в криптографическом сообществе и привела к постепенному отказу от WEP в пользу более защищённых протоколов WPA и WPA2.

Принцип работы

FMS-атака использует две ключевые особенности RC4:

1. Алгоритм планирования ключей (KSA — Key Scheduling Algorithm): На этом этапе из секретного ключа (обычно 40 или 104 бита для WEP) и открыто передаваемого начального вектора (IV) формируется начальное состояние S-блока (массива из 256 байт).
2. Генератор псевдослучайной последовательности (PRGA — Pseudo-Random Generation Algorithm): На этом этапе из S-блока генерируется поток псевдослучайных байтов (гамма), который накладывается на открытый текст (XOR) для получения шифротекста.

Слабые начальные векторы

В протоколе WEP начальный вектор (IV) передаётся в открытом виде вместе с каждым пакетом. Флюрер, Мантин и Шамир обнаружили, что некоторые IV (так называемые «слабые IV») приводят к тому, что первые байты гаммы RC4 сильно коррелируют с определёнными байтами секретного ключа. Слабые IV имеют вид (A, 255, X), где A — байт, который нужно атаковать, а X — произвольный байт. В ходе атаки злоумышленник перехватывает тысячи пакетов, содержащих слабые IV, и использует статистические методы для выявления наиболее вероятных значений байтов ключа.

Этапы атаки

1. Сбор данных: Перехват большого количества пакетов (обычно от 5 000 до 20 000 для 40-битного ключа и до 1 000 000 для 104-битного ключа), зашифрованных с использованием WEP. Из каждого пакета извлекается IV и первый байт шифротекста.
2. Фильтрация: Отбор пакетов, содержащих слабые IV, соответствующие атакуемому байту ключа.
3. Вычисление вероятности: Для каждого такого пакета на основе первого байта шифротекста и известного IV вычисляется наиболее вероятное значение соответствующего байта секретного ключа.
4. Статистический анализ: После накопления достаточного количества «голосов» за каждый байт ключа выбирается значение с наибольшей частотой. Этот процесс повторяется для каждого байта ключа.
5. Восстановление ключа: После того как все байты ключа определены, злоумышленник получает полный секретный ключ, который затем может быть использован для расшифровки любых пакетов в сети.

Применение к протоколу WEP

Протокол WEP (Wired Equivalent Privacy) был стандартом безопасности для Wi-Fi сетей с 1997 года. Он использовал RC4 для шифрования данных и CRC-32 для контроля целостности. FMS-атака стала основным инструментом для взлома WEP.

Особенности реализации в WEP

• Длина ключа: WEP поддерживал ключи длиной 40 или 104 бита. В обоих случаях к ним добавлялся 24-битный IV, который передавался открыто.
• Слабые IV: В WEP IV генерировался случайным образом или последовательно, что приводило к появлению слабых IV с вероятностью около 1 на 256 для каждого пакета.
• Практическая реализация: Атака была реализована в виде программного обеспечения, например, утилиты aircrack-ng, которая автоматизировала сбор пакетов, фильтрацию слабых IV и восстановление ключа.

Последствия для WEP

FMS-атака показала, что WEP не обеспечивает адекватной защиты. Для взлома 40-битного ключа требовалось перехватить от 5 000 до 10 000 пакетов, что при активном трафике занимало несколько минут. Для 104-битного ключа требовалось около 1 000 000 пакетов, что также было достижимо за разумное время (от нескольких часов до суток). В результате WEP был признан небезопасным и заменён сначала на WPA (использующий TKIP), а затем на WPA2 (использующий AES).

Критика и ограничения

Хотя FMS-атака была революционной, она имела ряд ограничений:

1. Зависимость от слабых IV: Атака эффективна только при наличии достаточного количества пакетов со слабыми IV. Если IV генерируются случайным образом, их доля может быть недостаточной.
2. Длина ключа: Для более длинных ключей (104 бита) требовалось значительно больше пакетов, что делало атаку более медленной.
3. Необходимость перехвата: Атака требует активного перехвата трафика, что может быть затруднено при низкой активности сети.
4. Применимость к другим протоколам: FMS-атака неэффективна против современных реализаций RC4, где IV генерируются случайным образом и не передаются открыто (например, в TLS). Однако она продемонстрировала, что RC4 в целом не является идеальным шифром.

Дальнейшее развитие

После публикации FMS-атаки были разработаны более совершенные методы криптоанализа RC4, в том числе:

• KoreK атака: Улучшенная версия, которая использует не только слабые IV, но и другие статистические аномалии, что позволяет восстанавливать ключ быстрее и с меньшим количеством пакетов.
• PTW атака (Pyshkin, Tews, Weinmann): Метод, основанный на анализе корреляции между ключом и гаммой, который позволяет восстанавливать ключ без необходимости в слабых IV. Эта атака стала стандартом для взлома WEP в современных инструментах, таких как aircrack-ng.

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

• FMS-атака была названа в честь первых букв фамилий её авторов. Ади Шамир является одним из создателей криптосистемы RSA (Rivest–Shamir–Adleman).
• Атака была продемонстрирована на практике в 2001 году, когда группа исследователей взломала WEP-сеть в течение нескольких минут.
• В 2004 году протокол WEP был официально отозван Институтом инженеров электротехники и электроники (IEEE) и заменён на WPA2.
• FMS-атака стала одной из причин, по которой RC4 был исключён из стандартов TLS в 2015 году.

Источники

• Fluhrer, S., Mantin, I., & Shamir, A. (2001). Weaknesses in the Key Scheduling Algorithm of RC4.
• Stubblefield, A., Ioannidis, J., & Rubin, A. D. (2002). Using the Fluhrer, Mantin, and Shamir Attack to Break WEP.
• Tews, E., Weinmann, R. P., & Pyshkin, A. (2007). Breaking 104 Bit WEP in Less Than 60 Seconds.