Что показало вскрытие

Архив

Меморандум был подготовлен на излете Холодной войны по инициативе ведущих телекоммуникационных компаний Западной Европы. Техническую документацию GSM разрабатывал Европейский институт стандартов по телекоммуникациям (ETSI) [3], а в создании схемы безопасности активное участие приняли спецслужбы стран НАТО.

Основу системы безопасности GSM составляют три секретных алгоритма (официально не раскрытые и поныне, сообщаемые лишь тем, кому это требуется по необходимости - поставщикам оборудования, операторам связи и т. д.):

- А3 - алгоритм аутентификации, защищающий телефон от клонирования;

- А8 - алгоритм генерации криптоключа;

- A5 - собственно алгоритм шифрования оцифрованной речи для обеспечения конфиденциальности переговоров. В GSM используются две его версии: A5/1 - "сильная" версия шифра для "избранных" стран и A5/2 - ослабленная для нас остальных.

Мобильные станции (телефоны) снабжены смарт-картой, реализующей A3 и A8, а в самом телефоне имеется ASIC-чип с алгоритмом A5. Базовые станции также снабжены ASIC-чипом с A5 и "центром аутентификации", использующим алгоритмы A3-A8 для идентификации мобильного абонента и генерации сеансового ключа.

Вся эта архитектура призвана гарантировать надежную аутентификацию пользователя, обеспечивая защиту мобильных станций от клонирования и прочих методов мошенничества, а также качественное шифрование конфиденциальных переговоров. Собственно говоря, именно это и декларируется компаниями, успешно занимающимися разворачиванием GSM по всему миру и уже охватившими своими услугами от 210 до 250 миллионов человек на планете.

Но реальность такова, что правительственные службы, занятые защитой коммуникаций, одновременно вовлечены и в деятельность противоположного рода: перехват и дешифрование коммуникаций в разведывательных целях. Вокруг степени защиты GSM бушевали немалые страсти, поскольку спецслужбы стран НАТО имели довольно разные точки зрения на этот счет. Германия настаивала на сильных алгоритмах, поскольку имела самую длинную границу с коммунистическим блоком, другие же страны склонялись к ослабленному варианту. В конце концов в качестве основы криптосхемы для A5 была избрана французская разработка [4].

Первый звонок

Как бы строго ни контролировались коммерческие секреты, понятно, что широкое распространение продукции рано или поздно приводит к утечкам информации. В случае с GSM утечки начались в начале девяностых, а к 1994 году основные детали алгоритма A5 уже были известны. В конце концов, кембриджские ученые М. Роэ и

Р. Андерсон опубликовали в Сети восстановленную по этим деталям примерную криптосхему [4].

A5 реализует поточный шифр на основе трех линейных регистров сдвига с неравномерным движением. Такого рода схемы способны обеспечивать очень высокую стойкость шифра, но лишь при верном выборе параметров.

Однако в А5 длины регистров выбраны очень короткими - 19, 22 и 23 бита, что в сумме и дает 64-битный сеансовый ключ шифрования в GSM. Уже одни эти укороченные длины регистров дают теоретическую возможность для хорошо известной лобовой атаки, когда перебирают заполнение двух первых регистров (сложность порядка 240), восстанавливая содержимое третьего регистра по выходной шифрующей последовательности (с общей сложностью порядка 2⁴⁵).

Регистры сдвига в схеме A5 имеют не только короткую длину, но и слабые прореженные полиномы обратной связи. Это дает шансы на успех еще одной атаке - корреляционному анализу, позволяющему вскрывать ключ по просачивающейся в выход информации о заполнении регистров.

В июне 1994 года д-р Саймон Шеферд из Брэдфордского университета должен был представить на коллоквиуме IEE в Лондоне свой корреляционный способ вскрытия A5, но в последний момент его выступление было запрещено Штаб-квартирой правительственной связи, британским аналогом американского АНБ. Доклад был сделан лишь на закрытой секции и опубликован в засекреченном сборнике [5].

Прошла еще пара лет, и до анализа A5 дошли руки у сербского криптографа д-ра Йована Голича, авторитетнейшего в академических кругах специалиста по поточным шифрам [6]. С чисто теоретических позиций он описал атаку, позволяющую вскрывать начальные заполнения регистров всего по 64 битам шифрпоследовательности с трудозатратами около 2⁴⁰.

Справедливости ради надо отметить, что в реальности данная атака оказалась значительно более трудоемкой. Проведенный в стенах Microsoft эксперимент Справедливости ради надо отметить, что в реальности данная атака оказалась значительно более трудоемкой. Проведенный в стенах Microsoft эксперимент действительно привел к вскрытию ключа, но понадобилось для этого около двух недель работы 32-узлового кластера машин Pentium II 300 [7]. Практичной такую атаку никак не назовешь.

В той же работе Голича был описан и еще один метод, известный в криптоанализе под общим названием "балансировка время-память". Он позволяет существенно сокращать время вскрытия за счет интенсивных предвычислений и хранения предварительных данных в памяти. Так, к примеру, можно было сократить количество опробований вариантов ключа всего до 2²² , но для этого требовались 64 терабайта дисковой памяти. Понятно, что это тоже трудно назвать реалистическими цифрами, но сама идея атаки четко продемонстрировала метод постепенного выхода на реальное соотношение параметров (подробности о начальном этапе анализа A5 и прочие технические детали относительно алгоритмов GSM можно найти по адресу http://kiwibyrd.chat.ru/gsm).

Клонирование и перехват: рынок решений

А вскоре пошли и сигналы о реальном вскрытии защиты системы GSM.

В апреле 1998 года группа компьютерных экспертов из Калифорнии широко объявила и продемонстрировала, что ей удалось клонировать мобильный телефон стандарта GSM [8]. Ранее по умолчанию предполагалось, что цифровые сети GSM гораздо надежнее защищены от этой напасти, приносящей миллионные убытки сетям аналоговой сотовой телефонии.

Возглавлял группу Марк Брисено, директор Ассоциации разработчиков смарт-карт (SDA, Smartcard Developer Association, www.scard.org). Избрав своей целью анализ стойкости GSM к попыткам клонирования, исследователи занялись обратной разработкой модуля SIM (это та самая смарт-карта, что вставляется в сотовый телефон, содержит алгоритмы A3-A8 и однозначно идентифицирует абонента).

В процессе подготовки к работам по вскрытию содержимого чипа в руки к исследователям неведомыми путями попало описание алгоритма COMP128 - наиболее широко распространенной практической реализации A3-A8 в SIM-модулях. Эта документация помогла быстрее и полностью восстановить всю необходимую информацию о схеме. После этого приглашенным для ее анализа молодым, но уже известным криптоаналитикам, аспирантам Калифорнийского университета в Беркли Дэвиду Вагнеру и Иэну Голдбергу понадобилось всего несколько часов, чтобы отыскать в схеме фатальные прорехи и разработать метод извлечения из карты секретного содержимого с помощью всего 2¹⁹ опросов чипа смарт-карты.

Представители консорциума GSM сразу же объявили полученные результаты "лабораторными" и не несущими реальной угрозы пользователям сотовой связи, поскольку в США обладание оборудованием для клонирования и публичная практическая демонстрация разработанной атаки являются противозаконными. Но уже очень скоро стали появляться сообщения о демонстрации клонирования телефонов GSM в странах с иным законодательством, в частности, в Германии.

В России тоже времени даром не теряют, и чтобы не быть голословными, мы вынесли в эпиграф объявление с одной из российских Web-страниц. Но "новейшая технология клонирования" - это еще далеко не все в арсенале умельцев. Лишь недавно "умерла" страница www.rinet.ru/~uandi/gsm, на которой рекламировалась "Система профессионального тестирования и мониторинга GSM", стоящая 4500 долларов и позволяющая отслеживать звонки в границах выделенной области, оставаясь подключенной к соединению, выводить на дисплей управляющие команды, идущие на телефон и от телефона, отслеживать речевой канал (голос) и резервный канал (где проходят номер модуля идентификации абонента, международный идентификатор абонента мобильной связи, временный идентификатор абонента, ключ аутентификации абонента, номер персональной идентификации и другая информация). Это - фактически "коробочный" продукт, состоящий из аппаратной и программной частей и руководства пользователя.

Тотально ослабленная защита

Один из членов SDA Лаки Грин недавно подвел промежуточный итог изысканиям в области соотношения декларируемой и истинной безопасности системы GSM.

Лаки Грин пишет: "Мой опыт работы с GSM показывает, что разведывательные службы, стоящие за всеми криптоалгоритмами GSM, используют весьма специфический подход: компрометируют любой и каждый компонент криптосистемы, какой только можно скомпрометировать. Разведслужбы, имея такую возможность, ослабляют компонент просто потому, что могут это сделать, а не потому, что им это нужно". Грин перечисляет следующие результаты изысканий:

- Скомпрометирована эффективная длина сеансового ключа.

- Скомпрометирована система аутентификации и алгоритм генерации секретного ключа.

- Скомпрометированы и "сильный", и "слабый" алгоритмы шифрования: A5/1 и A5/2.

Чтобы обеспечить перехват и дешифрование GSM-трафика, было бы достаточно скомпрометировать только эффективную длину ключа, только алгоритм генерации ключа или только алгоритм шифрования. Но спецслужбы сделали все три эти вещи. Такое можно назвать лишь "хорошо продуманной гарантированно избыточной компрометацией" [11].

И, наконец, еще один очень существенный нюанс. Все шифрование в системе GSM осуществляется только на канале между мобильным телефоном и базовой станцией, то есть в "эфирной" части передачи. При наличии санкции суда на прослушивание звонков правоохранительные органы всегда имеют возможность подключиться непосредственно к базовым станциям, где уже нет никакого шифрования. Так что единственным поводом для тотального ослабления криптозащиты оказывается нелегальный доступ без каких бы то ни было ордеров и санкций.

Вскрытие A5/2 и A5/1

В начале 1999 года в ассоциации SDA были полностью восстановлены и проверены на реальных тестовых векторах криптосхемы алгоритмов A5/1 и A5/2. Обратное восстановление A5/2 подтвердило уже имевшуюся информацию о том, что в этой схеме добавлен еще один короткий регистр длиной 17 бит, управляющий движением бит в остальных трех регистрах. Вагнеру и Голдбергу очень быстро удалось продемонстрировать, что в этих условиях для вскрытия системы достаточно лобовым перебором (сложность 2¹⁶) отыскать заполнение управляющего регистра. Делается это всего по двум фреймам сеанса связи длиной по 114 бит (в системе GSM первые два фрейма шифрпоследовательности известны, поскольку шифруются одни нули). Другими словами, вскрытие такого шифра осуществляется, что называется, "на лету", за 15 миллисекунд работы персонального компьютера [10].

Наконец, в декабре нынешнего года пришло еще одно известие. Израильские криптографы Ади Шамир и Алекс Бирюков опубликовали статью [12], в которой описан разработанный ими весьма нетривиальный, но по теоретическим расчетам очень эффективный метод вскрытия алгоритма A5/1.

Новый метод атаки использует тонкие слабости в структуре регистров сдвига, необратимый механизм их движения, а также частые перезагрузки регистров, применяемые в GSM. В итоге такая атака позволяет отыскивать ключ менее чем за секунду на персональном компьютере, имеющем 128 Мбайт RAM и два жестких диска по 73 Гбайт, путем анализа выхода алгоритма в течение первых двух минут телефонного разговора. Сейчас полученные израильскими математиками результаты тщательно изучаются криптографами, но выводы из всей этой истории очевидны.

"Теперь мы будем делать по-другому"

Увы, тот факт, что система GSM от рождения несет в себе перечисленные порочные черты, является вполне естественным. Просто потому, что рождалась GSM в соответствующих исторических условиях и от вполне определенных родителей.

Ныне уже почти все эксперты в области защиты информации сходятся во мнении, что разработка мер безопасности для широко используемых систем в тайне от общественности - в корне порочный путь. Единственный способ гарантировать надежную безопасность - это дать возможность проанализировать систему всему сообществу специалистов.

Отрадно, что данную истину, похоже, признали и в консорциуме GSM. Цитировавшийся в самом начале статьи Джеймс Моран, ведающий сейчас алгоритмами безопасности GSM, говорит следующее: "Когда эти шифры разрабатывались в 1989 году, широкая публикация алгоритмов не была распространенным подходом. Однако создаваемые ныне алгоритмы будут опубликованы для предварительного их изучения" [1].

Источники[1] - Cell Phone Crypto Penetrated, Wired News 6 Dec 1999.

[2] - Peter Gutmann, Re: Forthcoming Biryukov/Shamir result against A5/1 GSM privacy algorithm, posting to cryptography@c2.net mailing list, 7 Dec 1999.

[3] - Klaus Brunnstein, Mobile ComSec in Europe (A5) // RISKS DIGEST, Volume 14 : Issue 60, 12 May 1993.

[4] - Ross Anderson, Subject: A5, posting to Newsgroups: sci.crypt, alt.security, uk.telecom; 17 Jun 1994.

[5] - Simon J. Shepherd, Cryptanalysis of the GSM A5 Cipher Algorithm // IEE Colloquium on Security and Cryptography Applications to Radio Systems, Digest No. 1994/141, Savoy Place, London, 3 June 1994.

[6] - Jovan Golic, Cryptanalysis of Alleged A5 Stream Cipher, proceedings of EUROCRYPT '97, LNCS 1233, pp. 239-255, Springer-Verlag 1997.

[7] - Paul Leyland, Re: Status of GSM Crypto Attacks, posting to ukcrypto@maillist.ox.ac.uk mailing list, 21 Oct 1998.

[8] - Press release of Smartcard Developer Association, 13 Apr 1998, www.scard.org/gsm.

[9] - Making a working copy of your SIM card (GSM Phone Cloning), www.ussr.to/Russia/gsm.

[10] - David Wagner et al. , The Real-Time Cryptanalysis of A5/2 // Rump Session of Crypto '99, Santa Barbara, August 15-19, 1999.

[11] - Lucky Green , More NSAKEY musings // Crypto-Gram, September 15, 1999.

[12] - Alex Biryukov and Adi Shamir, Real Time Cryptanalysis of the Alleged A5/1 on a PC, preliminary draft, December 9, 1999, http://cryptome.org/a51-bs.htm.