Введение

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

История и использование

A5/1 используется в Европе и Соединенных Штатах. A5/2 был намеренным ослаблением алгоритма для определенных экспортных регионов. A5/1 был разработан в 1987 году, когда использование GSM за пределами Европы еще не планировалось, а A5/2 – в 1989 году. Хотя изначально оба алгоритма держались в секрете, общая структура была раскрыта в 1994 году, а сами алгоритмы были полностью восстановлены Марком Брисено в 1999 году на основе анализа GSM-телефона. В 2000 году около 130 миллионов абонентов GSM полагались на A5/1 для защиты конфиденциальности своих голосовых коммуникаций. Исследователь в области безопасности Росс Андерсон сообщил в 1994 году, что "в середине 1980-х годов между разведывательными службами НАТО разгорелся острый спор о том, следует ли делать шифрование GSM надежным. Немцы настаивали на этом, поскольку они граничили с Варшавским договором, но другие страны придерживались иного мнения, и алгоритм, который был принят, является французской разработкой."

Безопасность

Было опубликовано несколько атак на A5/1, и Агентство национальной безопасности США способно регулярно расшифровывать сообщения A5/1 согласно опубликованным внутренним документам. Некоторые атаки требуют дорогостоящего этапа предварительной обработки, после которого шифр может быть взломан за минуты или секунды. Изначально, уязвимости проявлялись в виде пассивных атак, использующих предположение о наличии известного открытого текста. В 2003 году были обнаружены более серьезные уязвимости, которые могут быть использованы в сценарии, когда доступен только шифротекст, или активным злоумышленником. В 2006 году Элад Баркан, Эли Бихам и Натан Келлер продемонстрировали атаки на A5/1, A5/3 и даже GPRS, позволяющие злоумышленникам перехватывать разговоры по мобильным телефонам GSM и расшифровывать их в реальном времени или в любое другое время. По словам профессора Яна Арильда Аудестада, в процессе стандартизации, начавшемся в 1982 году, для A5/1 первоначально предлагалась длина ключа 128 бит. В то время предполагалось, что 128 бит будут безопасны как минимум в течение 15 лет. В настоящее время считается, что 128 бит останутся безопасными и после появления квантовых вычислений. Аудестад, Питер ван дер Аренд и Томас Хауг утверждают, что британцы настаивали на более слабом шифровании, при этом Хауг сообщил, что британский делегат объяснил это необходимостью облегчить прослушивание для британской секретной службы. Британцы предложили длину ключа 48 бит, в то время как западногерманцы хотели более надежное шифрование для защиты от шпионажа со стороны Восточной Германии, поэтому компромиссным вариантом стала длина ключа 54 бита.

Известные атаки с помощью открытого текста

Первое нападение на A5/1 было предложено Россом Андерсоном в 1994 году. Основная идея Андерсона заключалась в том, чтобы угадать полное содержимое регистров R1 и R2 и примерно половину регистра R3. Таким образом, определяется синхронизация всех трех регистров, и вторую половину R3 можно вычислить, основываясь на более ранних работах Джована Голика. Один из вариантов позволяет злоумышленнику восстановить ключ за одну секунду, имея две минуты известного открытого текста, или за несколько минут, имея две секунды известного открытого текста, но для этого ему сначала необходимо выполнить дорогостоящий этап предварительной обработки, требующий 248 шагов для вычисления около 300 ГБ данных. Возможны различные компромиссы между предварительной обработкой, объемом необходимых данных, временем атаки и сложностью по памяти. В том же году Эли Бихам и Орр Дункельман также опубликовали атаку на A5/1 с общей вычислительной сложностью 239,91 тактов A5/1, при наличии 220,8 бит известного открытого текста. Атака требует 32 ГБ памяти для хранения данных после этапа предварительных вычислений, состоящего из 238 шагов. Экдал и Йоханссон опубликовали атаку на процедуру инициализации, которая взламывает A5/1 за несколько минут, используя от двух до пяти минут открытого текста разговора. Эта атака не требует этапа предварительной обработки. В 2004 году Максимов и др. улучшили этот результат, предложив атаку, требующую "менее одной минуты вычислений и нескольких секунд известного разговора". Атака была дополнительно улучшена Эладом Барканом и Эли Бихамом в 2005 году.

Атаки на A5/1 в GSM

В 2003 году Баркан и др. опубликовали несколько атак на шифрование GSM. Первая – это активная атака. Телефоны GSM можно заставить временно использовать значительно более слабый шифр A5/2. A5/2 легко взломать, при этом телефон использует тот же ключ, что и для более стойкого алгоритма A5/1. Описана также вторая атака на A5/1 – атака на основе компромисса между временем и памятью, работающая только с шифротекстом и требующая большого объема предварительных вычислений. В 2006 году Элад Баркан, Эли Бихам и Нейтан Келлер опубликовали полную версию своей статьи 2003 года, содержащую атаки на шифры A5/X. Авторы утверждают:

В 2007 году университеты Бохума и Киля начали исследовательский проект по созданию массивно-параллельного криптографического ускорителя на основе FPGA под названием COPACOBANA. COPACOBANA стала первым коммерчески доступным решением, использующим методы быстрого компромисса между временем и памятью, которое можно было использовать для атаки на популярные алгоритмы A5/1 и A5/2, применяемые в шифровании голоса GSM, а также на стандарт шифрования данных (DES). Он также позволяет проводить атаки методом полного перебора на GSM, устраняя необходимость в больших предварительно вычисленных таблицах поиска. В 2008 году группа The Hackers Choice запустила проект по разработке практической атаки на A5/1. Для этой атаки требуется создание большой таблицы поиска объемом около 3 терабайт. Вместе с возможностями сканирования, разработанными в рамках сопутствующего проекта, группа рассчитывала записывать любые GSM-вызовы или SMS, зашифрованные с помощью A5/1, и в течение примерно 3–5 минут получать ключ шифрования, а затем прослушивать вызов и читать SMS в открытом виде. Однако таблицы так и не были опубликованы. В последнее время проект объявил о переходе на более быстрый код ATI Evergreen, а также об изменении формата таблиц, и Фрэнк А. Стивенсон сообщил об успешных взломах A5/1 с использованием таблиц, сгенерированных ATI. В документах, попавших в сеть благодаря Эдварду Сноудену в 2013 году, говорится, что АНБ "может обрабатывать зашифрованные данные A5/1".

Использование A5/1 в качестве генератора псевдослучайных чисел

Поскольку степени трех LFSR взаимно просты, период этого генератора равен произведению периодов трех LFSR, что составляет 2^64 бита (2 в степени 64). Можно было бы подумать об использовании A5/1 как псевдослучайного генератора с 64-битным начальным значением (размером ключа), но это ненадежно. Он теряет свою случайность всего после 8 МБ данных (что соответствует периоду самого большого из трех регистров).