A5/1

A5/1 — это поточный шифр, используемый в стандарте сотовой связи GSM для шифрования передаваемых данных между абонентским устройством (мобильным телефоном) и базовой станцией. Разработан в 1987 году и первоначально держался в секрете, однако впоследствии его алгоритм был восстановлен и опубликован. A5/1 является одним из трёх вариантов алгоритмов семейства A5 (A5/0, A5/1, A5/2), где A5/1 применяется в странах Европы и Северной Америки, а A5/2 — в других регионах (впоследствии признан уязвимым).

История

Разработка алгоритмов семейства A5 велась в рамках проекта GSM (Global System for Mobile Communications) — глобального стандарта цифровой сотовой связи. Шифр A5/1 был создан в 1987 году группой инженеров, работавших над обеспечением конфиденциальности переговоров. В отличие от многих других криптографических систем, алгоритм A5/1 не был опубликован открыто, а распространялся в закрытых документах, доступных только операторам связи и производителям оборудования. Однако в 1994 году алгоритм был восстановлен методом обратного инжиниринга на основе анализа работы реальных устройств GSM, а в 1999 году — полностью опубликован в открытом доступе.

В 2000-х годах были обнаружены серьёзные уязвимости A5/1, позволяющие взламывать шифрование за секунды или минуты с использованием специализированного оборудования. Это привело к постепенному отказу от A5/1 в пользу более стойких алгоритмов, таких как A5/3 (основанный на блочном шифре KASUMI) и A5/4. Тем не менее, A5/1 остаётся широко распространённым, особенно в старых сетях GSM и в регионах с низкой скоростью обновления инфраструктуры.

Устройство и принцип работы

A5/1 представляет собой поточный шифр, основанный на трёх линейных регистрах сдвига с обратной связью (LFSR). Длина каждого регистра составляет 19, 22 и 23 бита соответственно (всего 64 бита). Ключ шифрования имеет длину 64 бита, однако 10 бит из них фиксированы (обычно устанавливаются в нулевое значение), что фактически снижает эффективную длину ключа до 54 бит.

Регистры сдвига

Каждый из трёх регистров (R1, R2, R3) имеет свою собственную полиномиальную обратную связь, определяющую, как биты сдвигаются и комбинируются. Регистры работают асинхронно: тактовый сигнал для каждого из них управляется специальным механизмом «мажоритарного голосования». На каждом такте вычисляется значение бита «часового» (clocking bit) для каждого регистра. Если значение бита совпадает с большинством (то есть два или три из трёх битов равны 1 или 0), то соответствующий регистр сдвигается. В результате регистры сдвигаются несинхронно, что усложняет криптоанализ.

Генерация ключевого потока

После начальной инициализации (загрузки ключа и номера кадра) регистры начинают генерировать псевдослучайную последовательность битов. Каждый бит этой последовательности вычисляется как XOR (исключающее ИЛИ) выходных битов всех трёх регистров. Полученный поток битов затем складывается по модулю 2 с открытым текстом (речевым сигналом или данными) для получения шифротекста. На приёмной стороне процесс повторяется с тем же ключом и номером кадра, что позволяет восстановить исходные данные.

Инициализация

Перед началом шифрования выполняется инициализация регистров. Для этого используется 64-битный ключ (Kc) и 22-битный номер кадра (Frame Number). Сначала ключ загружается в регистры, затем производится 64 такта, в течение которых регистры сдвигаются без генерации выходного потока. После этого выполняется ещё 22 такта, в ходе которых номер кадра смешивается с состоянием регистров. Затем регистры переводятся в рабочий режим, и начинается генерация ключевого потока.

Криптоанализ и уязвимости

A5/1 считается криптографически слабым алгоритмом. Основные уязвимости связаны с короткой длиной ключа (54 бита) и предсказуемой структурой регистров.

Атаки

• Атака «время-память» (Time-Memory Trade-Off): предложена в 2000 году. Позволяет взломать шифрование за несколько секунд при наличии предварительно вычисленных таблиц. Для этого требуется около 300 ГБ памяти.
• Атака на основе известного открытого текста (Known-Plaintext Attack): при наличии известного фрагмента открытого текста (например, служебных сигналов GSM) можно восстановить ключ за несколько миллисекунд.
• Атака с использованием FPGA (Field-Programmable Gate Array): в 2003 году была продемонстрирована возможность взлома A5/1 за 1 секунду с помощью специализированного оборудования стоимостью около 10 000 долларов.
• Атака на основе радужных таблиц (Rainbow Tables): в 2009 году группа исследователей опубликовала радужные таблицы, позволяющие взломать A5/1 за 2–3 секунды на обычном ПК.

Практические последствия

Уязвимости A5/1 позволяют злоумышленникам перехватывать и расшифровывать телефонные разговоры и SMS-сообщения в сетях GSM. Это стало известно широкой общественности после публикации документов Эдварда Сноудена в 2013 году, где указывалось, что Агентство национальной безопасности США (АНБ) способно массово перехватывать GSM-трафик, зашифрованный A5/1. В ответ на это операторы связи начали постепенно переходить на более стойкие алгоритмы, такие как A5/3 и A5/4.

Применение

A5/1 используется в стандарте GSM для шифрования канала связи между мобильным телефоном и базовой станцией. Шифрование применяется только к данным, передаваемым по радиоканалу (воздушному интерфейсу), и не защищает информацию внутри сети оператора. В зависимости от настроек оператора, шифрование может быть включено или отключено (режим A5/0 — без шифрования). В большинстве сетей GSM шифрование A5/1 включено по умолчанию, однако в некоторых странах (например, в России) операторы могут использовать A5/0 для снижения задержек или совместимости с оборудованием.

Сравнение с другими алгоритмами A5

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

• Алгоритм A5/1 был разработан в условиях секретности, но его восстановление стало возможным благодаря анализу прошивок мобильных телефонов и обратному инжинирингу.
• В 2009 году была опубликована реализация атаки на A5/1 с использованием радужных таблиц, которая позволяла взломать шифрование за 2–3 секунды на обычном ноутбуке.
• Несмотря на уязвимости, A5/1 до сих пор используется в некоторых старых сетях GSM, особенно в развивающихся странах, где обновление оборудования затруднено.
• В 2013 году документы Сноудена подтвердили, что АНБ способно массово перехватывать GSM-трафик, зашифрованный A5/1, что вызвало общественный резонанс и ускорило переход на более стойкие алгоритмы.

Источники

• Briceno, M., Goldberg, I., Wagner, D. (1999). "A Pedagogical Implementation of the GSM A5/1 and A5/2 'Voice Privacy' Encryption Algorithms".
• Biryukov, A., Shamir, A., Wagner, D. (2000). "Real Time Cryptanalysis of A5/1 on a PC".
• Nohl, K., Paget, C. (2009). "GSM: SRSLY?" — доклад на 26-й конференции Chaos Communication Congress.
• Документы Эдварда Сноудена (2013), опубликованные The Guardian и The Washington Post.
• Стандарт GSM 03.20 (ETS 300 926) — спецификация алгоритмов аутентификации и шифрования.