A5 (алгоритм шифрования)

A5/1 используется в Европе и США. A5/2 был целенаправленно ослаблен для некоторых экспортных регионов^[1]. Разработка A5/1 велась в 1987 году, когда применение GSM за пределами Европы не планировалось, а A5/2 был создан в 1989 году. Оба алгоритма поначалу были засекречены, однако общая структура A5/1 просочилась в 1994 году, а полная версия была восстановлена методами обратной разработки в 1999 году Марком Брисено с помощью GSM-телефона. К 2000 году примерно 130 миллионов пользователей GSM полагались на A5/1 для защиты конфиденциальности своих голосовых звонков.

В 1994 году исследователь в области безопасности Росс Андерсон сообщил, что «в середине 1980-х между агентствами радиотехнической разведки стран НАТО шли жаркие споры о том, должно ли шифрование GSM быть сильным. Немцы настаивали, что должно, поскольку у них была длинная граница с Варшавским договором; однако другие страны были иного мнения, и ныне внедренный алгоритм имеет французское происхождение»^[2].

Передача в стандарте GSM организована в виде последовательности «импульсов» (burst). В типичном канале и одном направлении один импульс отправляется каждые 4,615 миллисекунды и содержит 114 информационных бит. Для каждого импульса A5/1 формирует 114-битную последовательность ключевого потока, который затем складывается по XOR с исходными 114 битами до модуляции. Инициализация A5/1 проводится с использованием 64-битного ключа совместно с публично известным 22-битным номером кадра. В ранних реализациях GSM с использованием Comp128v1 10 бит ключа фиксировались в ноль, что давало эффективную длину ключа 54 бита. Эта уязвимость была устранена с появлением Comp128v3, обеспечивающего полноценные 64-битные ключи. При работе в режимах GPRS/EDGE, где ширина радиоканала увеличивается до 348 бит на кадр, для обеспечения конфиденциальности применяется A5/3 в режиме потокового шифра.

A5/1 основан на комбинации трёх регистров сдвига с линейной обратной связью (LFSR) с нерегулярным тактированием. Характеристики регистров приведены в таблице:

№ LFSR	Длина (бит)	Обратная связь	Управляющий бит	Тапы (бит)
1	19	${\displaystyle x^{19}+x^{18}+x^{17}+x^{14}+1}$	8	13, 16, 17, 18
2	22	${\displaystyle x^{22}+x^{21}+1}$	10	20, 21
3	23	${\displaystyle x^{23}+x^{22}+x^{21}+x^{8}+1}$	10	7, 20, 21, 22

Степени регистров выбраны так, что они взаимно просты, следовательно, период генератора равен произведению периодов трёх регистров, то есть 2^64 бит.

Биты индексируются с нуля (наименьший бит — 0).

Регистр сдвигаются по принципу большинства: для каждого такта берутся управляющие биты трёх регистров, определяется значение большинства, и только регистры, управляющие биты которых совпадают со значением большинства, сдвигаются. На каждом такте сдвигается минимум два, иногда три регистра; вероятность сдвига каждого регистра — 3/4.

Изначально регистры обнулены. Затем 64 цикла используется для «смешивания» 64-битного секретного ключа K. На цикле ${\displaystyle 0\leq {i}<64}$ i-й бит ключа XORится с младшим битом каждого регистра:

${\displaystyle R[0]=R[0]\oplus K[i].}$

Далее каждый регистр тактируется.

Затем в течение 22 тактов аналогичным образом добавляются 22 бита номера кадра. После этого схема сдвигается по обычному принципу большинства ещё 100 тактов (выход игнорируется). Затем потоковый шифр генерирует два 114-битных ключевых потока: первый — для нисходящего канала (downlink), второй — для восходящего (uplink).

Было опубликовано множество атак на A5/1, и по рассекреченным внутренним документам АНБ США может регулярно расшифровывать сообщения A5/1^[3].

Некоторые атаки требуют дорогостоящего предварительного этапа обработки, после чего шифр взламывается за минуты или секунды. Изначально уязвимости позволяли лишь пассивные атаки с предположением известного открытого текста. В 2003 году были выявлены более серьёзные слабости, которые позволяют проводить атаки даже по только шифротексту или в активном режиме. В 2006 году Элад Баркан, Эли Бихам и Натан Келлер описали атаки как на A5/1, так и на A5/3 и даже GPRS, которые позволяют перехватывать и дешифровать GSM-разговоры либо в реальном времени, либо позднее.

Профессор Ян Арильд Аудестад отмечал, что на стадии стандартизации с 1982 года изначально для A5/1 предлагалась длина ключа 128 бит — на тот момент считавшаяся надёжной минимум 15 лет. Предполагается, что длина 128 бит была бы устойчива и к появлению квантовых вычислений. Аудестад, Питер ван дер Аренд и Томас Хауг утверждают, что британцы настаивали на более слабом шифровании, чтобы облегчить прослушивание для спецслужб; предлагалась длина ключа в 48 бит, в то время как западные немцы настаивали на усиленной защите от восточногерманской разведки. В итоге был утверждён компромисс — длина ключа 54 бита^[4].

Первую атаку на A5/1 предложил Росс Андерсон в 1994 году. Суть заключалась в угадывании содержимого регистров R1 и R2 полностью и примерно половины R3; тогда процесс тактирования регистров полностью определяется, и по нему можно восстановить вторую половину R3^[2].

В 1997 году Галич представил атаку, основанную на решении систем линейных уравнений со сложностью 2^40,16 (число решений уравнений).

В 2000 году Алекс Бирюков, Ади Шамир и Дэвид Вагнер показали, что A5/1 можно криптоанализировать в реальном времени с помощью аттаки с компромиссом времени и памяти^[5]. Позже этот подход был доработан на основе работы Йована Галича^[6]. Такой компромисс позволяет восстановить ключ за одну секунду при наличии двух минут открытого текста или за несколько минут при двух секундах известного открытого текста, однако требуется предварительно подготовить массив данных объёмом около 300 ГБ (2⁴⁸ шагов). Возможны варианты атаки с различным соотношением времени, данных и объёма памяти.

В том же году Эли Бихам и Орр Данкельман описали атаку на A5/1 с полной трудоёмкостью 2^39,91 тактирований при наличии 2^20,8 битов известного открытого текста. После стадии предварительных вычислений (2³⁸ шагов) потребуется 32 ГБ данных^[7].

Экдаль и Юханссон опубликовали атаку на процедуру инициализации, позволяющую взломать A5/1 за несколько минут с двумя-пятью минутами открытого речевого трафика^[8]. Предварительные вычисления не требуются. В 2004 году Максимов и др. улучшили результат — атака требует менее минуты вычислений и несколько секунд известного открытого текста. В 2005 году атаку доработали Элад Баркан и Эли Бихам^[9].

В 2003 году Баркан и соавторы описали несколько атак на шифрование GSM^[10]. Первый вариант — активная атака: мобильный может быть принуждён к временной работе с заведомо слабым шифром A5/2, который легко взламывается, причём при этом используется тот же ключ, что для A5/1. Второй вариант — атака только по шифротексту с компромиссом времени и памяти, требующая значительных предварительных вычислений.

В 2006 году Элад Баркан, Эли Бихам и Натан Келлер опубликовали расширенную версию работы 2003 года с атаками на семейство A5/X. Авторы отмечали:^[11]

В 2007 году университеты Бохума и Киля запустили проект для создания аппаратного ускорителя криптоанализа COPACOBANA на базе FPGA. Это была первая коммерчески доступная система^[12], использующая быстрые методы компромисса времени и памяти для атаки на A5/1, A5/2 и DES, а также способная реализовывать полный перебор ключей без необходимости в огромных предварительно рассчитанных таблицах.

В 2008 году группа The Hackers Choice инициировала проект по практическому взлому A5/1, в ходе которого требовалось построить таблицу поиска размером ~3 ТБ. Вместе с разработанными инструментами прослушивания планировалось записывать любой GSM-звонок или SMS с шифрованием A5/1, и за 3-5 минут восстанавливать ключ для прослушивания разговора или чтения SMS в открытом виде. Однако таблицы не были опубликованы^[13].

Похожий проект — A5/1 Cracking Project — был представлен на конференции Black Hat 2009 криптографами Карстеном Нолем и Сашей Крисслером. Для вычисления таблиц использовались Nvidia GPGPU по схеме распределённых вычислений. К сентябрю 2009 года проект использовал вычислительные мощности, эквивалентные 12 видеокартам Nvidia GeForce GTX 260, и подход мог применяться к любому шифру с длиной ключа до 64 бит^[14].

В декабре 2009 года были объявлены публичные части таблиц атаки для A5/1 (1,7 ТБ), подсчитанные на 40 вычислительных узлах CUDA за три месяца и опубликованные через BitTorrent^[13]. Впоследствии проект перешёл на ускоренный код под ATI Evergreen, изменился формат таблиц; Фрэнк Стивенсон сообщил о взломе A5/1 с их помощью^[15].

Согласно опубликованным материалам Эдварда Сноудена, в 2013 году АНБ США «может обрабатывать зашифрованные сообщения A5/1»^[16].

Поскольку степени трёх LFSR взаимно просты, период генератора равен произведению периодов, то есть 2^64 бит.

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