Безопасность GSM - история, анализ, вскрытие
         

Безопасность GSM: история, анализ, вскрытие


kiwibyrd@mail.ru

Для начала - две цитаты. Две диаметрально противоположные точки зрения, которые сразу же дадут читателю представление об остроте проблемы.

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

А вот мнение Питера Гутмана, весьма известного хакера-криптографа из Оклендского университета (Новая Зеландия): "Имея ситуацию, когда целый ряд компаний продает оборудование для перехвата GSM (причем делается это уже в течение определенного времени и с весьма открытой рекламой в Сети), этот директор по безопасности "либо лжет, либо некомпетентен, либо и то, и другое разом" (цитируя строку из книги Deep Crack). Интересно то, что сейчас все рекламирующие данное оборудование фирмы устроили ограниченный доступ на свои сайты, по-видимому, для поддержания мифа о том, что "не существует аппаратуры, способной осуществлять такой перехват"" [2].

За последние годы в Интернете и СМИ не раз вспыхивали дискуссии как вокруг самой защиты системы мобильной связи GSM, так и вокруг многочисленных уже случаев ее компрометации. По сути дела, почти всем уже ясно, что GSM - это классический пример провала стратегии, именуемой на Западе



Что такое защита GSM и как она создавалась


В принципе, по своему замыслу, цифровая система мобильной связи GSM вполне могла бы быть чрезвычайно защищенной. В основе ее лежит свод документов под названием "Меморандум о понимании стандарта GSM" или MoU Groupe Special Mobile standard. Этот Меморандум был подготовлен на излете Холодной войны по инициативе ведущих телекоммуникационных компаний Западной Европы. Разрабатывал техническую документацию GSM Европейский институт стандартов по телекоммуникациям (ETSI) [3], а в создании схемы безопасности, в целом призванной защитить новую систему от перехвата, прослушивания и мошенничества, активное участие приняли спецслужбы стран НАТО.

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

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

А8 - алгоритм генерации криптоключа, по сути дела однонаправленная функция, которая берет фрагмент выхода от A3 и превращает его в сеансовый ключ для A5;

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

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

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

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



Использованные источники:


[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, (Commercial-In-Confidence).

[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, http://www.scard.org/gsm/

[9] Making a working copy of your SIM card (GSM Phone Cloning), http://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

#bn {display:block;} #bt {display:block;}



Клонирование


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

Возглавлял группу Марк Брисено, директор так называемой "Ассоциации разработчиков смарт-карт" или SDA (Smartcard Developer Association), представляющей интересы разработчиков программного обеспечения для смарт-карт. Избрав своей целью стойкость GSM к попыткам клонирования, исследователи занялись обратной разработкой модуля SIM. Это та самая смарт-карта, что вставляется в сотовый телефон, содержит алгоритмы A3-A8 и однозначно идентифицирует абонента. В процессе подготовки к работам по вскрытию содержимого чипа, в руки к исследователям неисповедимыми путями попало описание "алгоритма COMP128" - наиболее широко распространенной практической реализации A3-A8 в SIM-модулях. Эта документация помогла быстрее и полностью восстановить всю необходимую информацию о схеме. После этого Брисено пригласил для ее анализа двух молодых, но уже известных криптоаналитиков, аспирантов Калифорнийского университета в Беркли Дэвида Вагнера и Иэна Голдберга. Тем понадобилось всего несколько часов, чтобы отыскать в схеме фатальные прорехи и разработать метод извлечения из карты секретного содержимого с помощью всего 219 опросов чипа смарт-карты.

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

"Если Вас интересует, я могу за небольшую плату в $100 сделать работающую копию Вашей или чужой SIM карточки. Копия практически ничем не отличается от оригинала. Никаких печатных плат, никаких проводов! Карточка маленькая, аккуратная, красивая. Утечка данных исключена. Однако, Вам необходимо привезти или прислать Вашу карточку в Москву или Самару. Наши филиалы работают круглосуточно. Процесс займет 15 часов. Вы получите то преимущество, что не будете платить за вторую карточку никакую ежемесячную абонементную плату. Вы можете сделать копию для своих друзей или родственников. Если Вы договоритесь с человеком, который не платит из собственного кармана за каждую минуту разговора, то можете сделать и для себя! Это новейшая технология клонирования SIM карточек ..." [9]

Но "новейшая технология клонирования" - это еще далеко не все в арсенале умельцев.



Перехват


Об имеющихся на рынке средствах перехвата и мониторинга GSM (сама возможность чего отрицается официальными представителями MoU) наиболее красноречиво рассказывают реальные объявления в Интернете. Чтобы не ходить далеко, процитируем текст веб-страницы одного из виртуальных магазинов, развернутых в России (адрес ныне уже умершей ссылки http://www.rinet.ru/~uandi/gsm/):

"



Первые утечки, первые тревожные звонки


Как бы строго ни контролировались коммерческие секреты, понятно, что широкое распространение продукции рано или поздно приводит к утечкам информации. В GSM они стали появляться уже в начале 90-х годов. К 1994 году основные детали алгоритма A5 уже были известны. Во-первых, British Telecom передала всю техническую документацию Брэдфордскому университету, забыв заключить соглашение о неразглашении информации. Во-вторых, описание A5 появилось в материалах одной из конференций в Китае. Короче говоря, детали о конструкции алгоритма понемногу стали просачиваться в печать, и в конце концов кембриджские ученые М.Роэ и Р.Андерсон опубликовали восстановленную по этим деталям примерную криптосхему в Интернете [4].

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

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


Прошла еще пара лет, и до анализа A5 дошли руки у сербского криптографа д-ра Йована Голича, наиболее, вероятно, авторитетного в академических кругах специалиста по поточным шифрам [6]. С чисто теоретических позиций он описал атаку, позволяющую вскрывать начальные заполнения регистров всего по 64 битам шифрпоследовательности с трудозатратами около 240. (Справедливости ради надо, правда, отметить, что в реальности данная атака оказалась значительно более трудоемкой. Проведенный в стенах Microsoft эксперимент действительно привел к вскрытию ключа, но понадобилось для этого около двух недель работы 32-узлового кластера машин PII-300 [7]. Практичной такую атаку никак не назовешь.) Однако, в той же работе Голича [6] был описан и еще один метод, известный в криптоанализе под общим названием "балансировка время-память", позволяющий существенно сокращать время вскрытия за счет интенсивных предвычислений и хранения предварительных данных в памяти. Так, к примеру, можно было сократить количество опробований вариантов ключа всего до 222 , но для этого требовались 64 терабайта дисковой памяти (что, понятное дело, тоже трудно назвать реалистическими цифрами). Но сама идея атаки четко продемонстрировала метод постепенного выхода на реальное соотношение параметров.

(Подробности о начальном этапе анализа A5 и прочие технические детали относительно алгоритмов GSM можно найти по адресу http://kiwibyrd.chat.ru/gsm/)

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


SbO


, что в зависимости от чувства юмора расшифровывают либо как Security by Obscurity ("безопасность упрятыванием"), либо как Security by Ostrich ("безопасность по-страусиному"). На протяжении примерно десяти лет постепенно обнажались типичные пороки и неудобства вымирающей ныне стратегии, согласно которой степень защиты системы в значительной степени увязывается с сохранением в тайне как особенностей конструкции, так и случаев ее компрометации. Увы, тот факт, что система GSM от рождения несет в себе перечисленные порочные черты, является вполне естественным. Просто потому, что рождалась GSM в соответствующих исторических условиях и от вполне определенных родителей.



Система профессионального тестирования и мониторинга GSM


Данное устройство является нашей новейшей разработкой, в которой использованы наиболее передовые технологии вскрытия криптографических алгоритмов A8, A3, A5 и т.д., применяемых в сетях GSM. Используя наше уникальное аппаратное и программное обеспечение, "Система ..." будет отслеживать звонки в границах выделенной области, оставаясь подключенной к соединению. Она будет выводить на дисплей управляющие команды, идущие на телефон и от телефона, отслеживать речевой канал (голос) и резервный канал (где проходят: SIM - номер модуля идентификации абонента, IMSI - международный идентификатор абонента мобильной связи, TMSI - временный идентификатор абонента, SAK- ключ аутентификации абонента, PIN - номер персональной идентификации и другая информация). Процесс декодирования и выполнения всех калькуляций занимает около 2,5 минут, так что длительность телефонного соединения, которое вы отслеживаете, должна быть по крайней мере такого же порядка, чтобы устройство мониторинга могло обработать и проверить всю информацию, включая соответствующие значения для программирования нового SIM (т.е. для клонирования GSM-телефона). Программное и аппаратное обеспечение позволяют отслеживать конкретные номера телефонов. Можно создавать "файлы регистрации данных" (data log files) для последующего анализа, а аудио-информацию можно записывать для контроля с помощью звукозаписывающего оборудования (в поставку не входит). В комплект поставки входит подробное Руководство и программное обеспечение для Windows или DOS. Данная система разработана для 900 Мгц GSM-сетей. Цена - 4500 долларов. Все заказы оплачиваются через Western Union или трансфером банк-банк."



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


Хотя в MoU признают, что вскрываемость шифра и была целью разработки A5/2, тем не менее в официальных результатах анализа SAGE сказано, что им неизвестно ни о каких криптографических дефектах в A5/2.

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

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



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


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

-



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


В 64-битном ключе, который A8 генерирует для A5, последние 10 бит обнулены. Это совершенно умышленное ослабление системы примерно в 1000 раз.

-



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


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

-



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


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

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

***



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


Один из членов Smartcard Developer Association, использующий псевдоним "Лаки Грин" , недавно подвел промежуточный итог своим изысканиям в области соотношения декларируемой и истинной безопасности системы GSM [11]. Формулировки его звучат весьма задиристо, но нельзя не согласиться, что у них имеется солидное обоснование.

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

Затем , в конкретном применении к GSM, Лаки Грин перечисляет следующие компрометирующие систему слабости, обнаруженные исследователями SDA:

-



Вскрытие A5/1. Пока только теоретическое, но впечатляющее


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

Ади Шамира называют "патриархом израильской криптографии". Еще в 1977 году совместно с американцами Райвестом и Адлеманом Шамир разработал знаменитую криптосхему с открытым ключом RSA (здесь "S" - это Shamir). В 80-е годы, помимо сильных криптоаналитических работ, им разработано несколько криптографических протоколов и криптосхем. В начале 90-х совместно с Эли Бихамом Шамиром разработан метод дифференциального криптоанализа, ставший основой практически всех современных методов исследования и вскрытия блочных шифров. Его новая совместная с Бирюковым работа - это, возможно, первое обращение Шамира к анализу поточных шифров на основе регистров сдвига. Сам он говорит о разработанном методе вскрытия А5 следующее: "Это весьма сложная идея, реализуя которую мы наступаем на многих фронтах, чтобы накопить несколько небольших преимуществ, но сложенные все вместе они дают большой выигрыш. Но статью нашу было нелегко написать. Нелегко ее и читать".

Изложим суть работы в нескольких фразах. Новый метод атаки использует тонкие слабости в структуре регистров сдвига, необратимый механизм их движения, а также частые перезагрузки регистров, применяемые в GSM. В итоге такая атака позволяет отыскивать ключ менее чем за секунду на персональном компьютере, имеющем 128 Мб RAM и два жестких диска по 73 Гб, путем анализа выхода алгоритма в течение первых двух минут телефонного разговора (сразу отметим, что это весьма щедрое теоретическое допущение, поскольку две минуты открытого текста в реальных условиях получить не так просто). Для успеха атаки требуется предварительная и поддающаяся распараллеливанию подготовка данных, сложность которой может варьироваться от 238 до 248 шагов. Для подтверждения теоретических расчетов авторы действительно менее чем за секунду нашли 64-битный ключ шифрпоследовательности, порожденной алгоритмом A5/1 в версии SDA (отметим, что факт реальной длины ключа в 54 бита ими не использовался).

Сейчас полученные израильскими математиками результаты тщательно изучаются криптографами, но выводы из всей этой истории практически очевидны.



в ассоциации SDA были полностью


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