А5/1

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

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

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

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

Описание

Потоковый шифр A5/1 использует три LFSR . Регистр синхронизируется, если его бит синхронизации (оранжевый) совпадает с битом синхронизации одного или обоих двух других регистров.

Передача GSM организована как последовательность пакетов . В типичном канале и в одном направлении один пакет отправляется каждые 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) с нерегулярной тактовой частотой. Три сдвиговых регистра определяются следующим образом:

ЛФСР число	Длина в биты	Обратная связь полиномиальный	Тактирование кусочек	постучал биты
1	19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	8	13, 16, 17, 18
2	22	$x^{22}+x^{21}+1$	10	20, 21
3	23	$x^{23}+x^{22}+x^{21}+x^{8}+1$	10	7, 20, 21, 22

Эти степени были выбраны не случайно: поскольку степени трех регистров относительно просты, период этого генератора является произведением периодов трех регистров. Таким образом, период A5/1 (до повторения) составляет 2^64 бита (2 в 64-й степени).

Биты индексируются, причем младший бит (LSB) равен 0.

Регистры синхронизируются по принципу «стоп/идти» с использованием правила большинства. Каждый регистр имеет связанный бит синхронизации. В каждом цикле проверяется тактовый бит всех трех регистров и определяется мажоритарный бит. Регистр синхронизируется, если бит синхронизации совпадает с битом большинства. Следовательно, на каждом шаге синхронизируются как минимум два или три регистра, и каждый регистр движется с вероятностью 3/4.

Первоначально регистры установлены в ноль. 64-битный секретный ключ К по следующей схеме: в такте Затем за 64 такта подмешивается $0\leq {i}<64$, i -й ключевой бит добавляется к младшему биту каждого регистра с помощью XOR —

$R[0]=R[0]\oplus K[i].$

Затем каждый регистр тактируется.

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

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

Сообщение на экране мобильного телефона с предупреждением об отсутствии шифрования

Опубликован ряд атак на 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.

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

В 2000 году Алекс Бирюков , Ади Шамир и Дэвид Вагнер показали, что A5/1 можно подвергнуть криптоанализу в реальном времени, используя атаку с компромиссом между временем и памятью. на основе более ранней работы Йована Голича. Один компромисс позволяет злоумышленнику восстановить ключ за одну секунду по двум минутам известного открытого текста или за несколько минут по двум секундам известного открытого текста, но сначала он должен выполнить дорогостоящий этап предварительной обработки, который требует 2 ⁴⁸ шаги для вычисления около 300 ГБ данных. Возможны несколько компромиссов между предварительной обработкой, требованиями к данным, временем атаки и сложностью памяти.

В том же году Эли Бихам и Орр Данкельман также опубликовали атаку на A5/1 с общей сложностью работы 2. ^39.91 Тактовая частота A5/1 с учетом 2 ^20.8 биты известного открытого текста . Для атаки требуется 32 ГБ хранилища данных после этапа предварительных вычислений 2. ³⁸ .

Экдал и Йоханссон опубликовали атаку на процедуру инициализации, которая нарушает A5/1 за несколько минут, используя от двух до пяти минут открытого текста разговора. Эта атака не требует этапа предварительной обработки. В 2004 г. Максимов и др. улучшил этот результат до атаки, требующей «менее одной минуты вычислений и нескольких секунд известного разговора». Атака была улучшена Эладом Барканом и Эли Бихамом в 2005 году.

Атаки на A5/1, используемые в GSM

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

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

Мы представляем очень практичный криптоанализ зашифрованной связи GSM, основанный только на зашифрованном тексте, а также различные активные атаки на протоколы GSM. Эти атаки могут даже проникнуть в сети GSM, использующие «невзламываемые» шифры. Сначала мы описываем атаку на A5/2 с использованием только зашифрованного текста, которая требует нескольких десятков миллисекунд зашифрованного беспроводного сотового разговора и позволяет найти правильный ключ на персональном компьютере менее чем за секунду. Мы расширяем эту атаку до (более сложной) атаки только зашифрованного текста на A5/1. Затем мы описываем новые (активные) атаки на протоколы сетей, использующих A5/1, A5/3 или даже GPRS. Эти атаки используют недостатки в протоколах GSM и срабатывают всякий раз, когда мобильный телефон поддерживает слабый шифр, такой как A5/2. Мы подчеркиваем, что эти атаки направлены на протоколы и поэтому применимы всякий раз, когда сотовый телефон поддерживает слабый шифр, например, они также применимы для атаки на сети A5/3 с использованием криптоанализа A5/1. В отличие от предыдущих атак на GSM, которые требуют нереальной информации, например, давно известных периодов открытого текста, наши атаки очень практичны и не требуют знания содержания разговора. Кроме того, мы опишем, как усилить атаки, чтобы противостоять ошибкам приема. В результате наши атаки позволяют злоумышленникам прослушивать разговоры и расшифровывать их либо в режиме реального времени, либо в любое более позднее время.

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

В 2008 году группа The Hackers Choice запустила проект по разработке практической атаки на A5/1. Атака требует создания большой справочной таблицы размером примерно 3 терабайта. Ожидалось, что вместе с возможностями сканирования, разработанными в рамках родственного проекта, группа сможет записывать любой GSM-вызов или SMS, зашифрованные с помощью A5/1, и в течение примерно 3–5 минут получать ключ шифрования и, следовательно, прослушивать вызов и прочитайте SMS в чистом виде. Но таблицы не были опубликованы.

Аналогичная попытка, проект взлома A5/1, была анонсирована на конференции по безопасности Black Hat в 2009 году криптографами Карстеном Нолом и Сашей Крисслером. Таблицы поиска были созданы с использованием Nvidia графических процессоров через одноранговую распределенную вычислительную архитектуру. Начиная с середины сентября 2009 года, в проекте работало 12 эквивалентов Nvidia GeForce GTX 260. По мнению авторов, этот подход можно использовать для любого шифра с размером ключа до 64 бит.

В декабре 2009 года Крис Пейджет и Карстен Нол объявили таблицы атак A5/1 Cracking Project для A5/1. В таблицах используется сочетание методов сжатия, включая радужные таблицы и выделенные цепочки точек. Эти таблицы представляли собой лишь часть заполненной таблицы размером 1,7 ТБ и были рассчитаны в течение трех месяцев с использованием 40 распределенных узлов CUDA , а затем опубликованы через BitTorrent . Совсем недавно проект объявил о переходе на более быстрый код ATI Evergreen вместе с изменением формата таблиц, а Фрэнк А. Стивенсон объявил о разрыве A5/1 с использованием таблиц, сгенерированных ATI.

В документах, опубликованных Эдвардом Сноуденом в 2013 году, говорится, что АНБ «может обрабатывать зашифрованный A5/1».

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

Поскольку степени трех LFSR относительно простые, период этого генератора является произведением периодов трех LFSR, что представляет собой 2^64 бита (2 в 64-й степени).

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

См. также

• А5/2
• КАСУМИ , также известный как А5/3.
• Алгоритм шифрования сотовых сообщений

Примечания

• Роуз, Грег (10 сентября 2003 г.). «Описание новых атак на шифрование GSM» (PDF) . КВАЛКОММ Австралия. Архивировано из оригинала (PDF) 27 сентября 2011 года . Проверено 17 октября 2004 г.
• Максимов, Александр; Томас Йоханссон; Стив Бэббидж (2004). «Улучшенная корреляционная атака на A5/1». Избранные области криптографии 2004 : 1–18.

Внешние ссылки

• Брицено, Марк; Ян Голдберг; Дэвид Вагнер (23 октября 1999 г.). «Педагогическая реализация алгоритмов шифрования GSM A5/1 и A5/2 «конфиденциальность голоса»» . Архивировано из оригинала 8 октября 2018 года . Проверено 23 января 2017 г.
• «Огромный недостаток GSM позволяет хакерам прослушивать голосовые вызовы» . 25 августа 2009 г. Архивировано из оригинала 14 октября 2009 г.
• Хореш, Хадар (3 сентября 2003 г.). «Команда Техниона взламывает шифрование сотовых телефонов GSM» (PDF) . Гаарец . Архивировано из оригинала (PDF) 3 марта 2016 года . Проверено 15 сентября 2019 г.
• Баркан, Элад; Эли Бихам; Натан Келлер (июль 2006 г.). «Мгновенный криптоанализ зашифрованной связи GSM, содержащий только зашифрованный текст (технический отчет CS-2006-07)» . Архивировано из оригинала 27 декабря 2019 года . Проверено 15 сентября 2019 г.
• «Домашняя страница Натана Келлера» . Архивировано из оригинала 4 июня 2008 года.
• «Анимированный SVG, показывающий потоковый шифр A5/1» . Архивировано из оригинала 26 марта 2012 года.