В принципе, по своему замыслу, цифровая система GSM вполне могла бы быть чрезвычайно защищенной. В основе ее лежит свод документов под названием «Меморандум о понимании стандарта GSM» или MoU Groupe Special Mobile standard. Этот Меморандум был подготовлен на излете Холодной войны по инициативе ведущих телекоммуникационных компаний Западной Европы. Разрабатывал техническую документацию GSM Европейский институт стандартов по телекоммуникациям (ETSI), а в создании схемы безопасности, в целом призванной защитить новую систему от перехвата, прослушивания и мошенничества, активное участие приняли спецслужбы стран НАТО [КВ93].
Основу системы безопасности GSM составляют три секретных алгоритма (вплоть до конца 2003 г. официально так и не раскрытые, сообщаемые лишь тем, кому это требуется по необходимости - поставщикам оборудования, операторам связи и т.д.):
• A3 - алгоритм аутентификации, защищающий телефон от клонирования;
• А8 - алгоритм генерации криптоключа, по сути дела, однонаправленная функция, которая берет фрагмент выхода от A3 и превращает его в сеансовый ключ для А5;
• А5 - собственно алгоритм шифрования оцифрованной речи для обеспечения конфиденциальности переговоров. В GSM используются две основные разновидности алгоритма: А5/1 - «сильная» версия шифра для избранных стран и А5/2 - ослабленная для всех остальных. (В 2000-е годы для следующего поколения мобильной связи, G3, создан совершенно новый криптоалгоритм, получивший название А5/3. Еще имеется вариант А5/0 - это когда режим шифрования вроде как включен, но в действительности его нет, поскольку вместо битов ключа используются одни нули.)
Мобильные станции (телефоны) снабжены смарт-картой (SIM), содержащей A3 и А8, а в самом телефоне имеется чип с алгоритмом А5. Базовые станции также снабжены чипом с А5 и «центром аутентификации», использующим алгоритмы АЗ-А8 для идентификации мобильного абонента и генерации сеансового ключа шифрования.
Вся эта архитектура при надлежащем исполнении и качественных алгоритмах призвана гарантировать надежную аутентификацию пользователя, обеспечивая защиту мобильных станций от клонирования и прочих методов мошенничества, а также качественное шифрование конфиденциальных переговоров. Собственно говоря, именно это и декларируется компаниями, успешно занимающимися разворачиванием GSM по всему миру и уже охватившими услугами удобной связи многие сотни миллионов человек на планете.
Но реальность такова, что спецслужбы, занятые защитой правительственной связи, одновременно вовлечены и в деятельность противоположного рода: перехват и дешифрование коммуникаций в разведывательных целях. По этой причине, как свидетельствуют очевидцы, вокруг степени защиты GSM бушевали немалые страсти, поскольку спецслужбы стран НАТО имели довольно разные точки зрения на этот счет. Германия настаивала на сильных алгоритмах, поскольку имела самую длинную границу с коммунистическим блоком, другие же страны склонялись к ослабленному варианту. В конце концов в качестве основы криптосхемы для А5 была избрана французская военная разработка [RA94].
Первые утечки, первые тревоги
Как бы строго ни контролировались коммерческие секреты, понятно, что широкое распространение продукции рано или поздно приводит к утечкам информации. В GSM они стали появляться уже в начале 90-х годов. К 1994 году основные детали алгоритма А5 уже были известны. Во-первых, British Telecom передала всю техническую документацию Брэдфордскому университету, забыв заключить соглашение о неразглашении информации. Во-вторых, описание А5 появилось в материалах одной из конференций в Китае. Короче говоря, детали о конструкции алгоритма понемногу стали просачиваться в печать, и в конце концов кембриджские ученые М. Роу и Р. Андерсон опубликовали восстановленную по этим деталям примерную криптосхему в Интернете.
Представляет схема собой следующее. А5 реализует поточный шифр на основе трех линейных регистров сдвига с неравномерным движением. Такого рода схемы на языке специалистов именуются «криптографией военного уровня» и при верном выборе параметров способны обеспечивать очень высокую стойкость шифра. Однако, в А5 длины регистров выбраны очень короткими - 19, 22 и 23 бита. Начальное заполнение этих регистров в сумме и дает 64-битный сеансовый ключ шифрования в GSM. Уже одни эти укороченные длины регистров дают теоретическую возможность для хорошо известной криптографам лобовой атаки, когда перебирают заполнение двух первых регистров, восстанавливая содержимое третьего регистра по выходной шифрующей последовательности.
Регистры сдвига в схеме А5 имеют не только короткую длину, но и слабые прореженные полиномы обратной связи. Это дает шансы на успех еще одной атаке - корреляционному анализу, позволяющему вскрывать ключ по просачивающейся в выход информации о заполнении регистров. В июне 1994 года д-р Саймон Шеферд из Брэдфордского университета должен был представить на коллоквиуме IEEE в Лондоне свой корреляционный способ вскрытия А5. Однако, в последний момент его выступление было запрещено спецслужбой GCHQ, Штаб-квартирой правительственной связи. Доклад был сделан лишь на закрытой секции и опубликован в засекреченном сборнике [SS94].
Прошла еще пара лет, и до анализа А5 дошли руки у сербского криптографа д-ра Иована Голича, наиболее, вероятно, авторитетного в академических кругах специалиста по поточным шифрам [JG97]. С чисто теоретических позиций он описал атаку, позволяющую легко вскрывать начальные заполнения регистров всего по 64 битам шифрпоследовательности. (Справедливости ради надо, правда, отметить, что в реальности данная атака оказалась значительно более трудоемкой. Проведенный в стенах Microsoft эксперимент [PL98] действительно привел к вскрытию ключа, но понадобилось для этого около двух недель работы 32-узлового кластера машин РП-300. Практичной такую атаку никак не назовешь. Правда, и репутация у криптоэкспертов Microsoft, мягко говоря, не блестящая.) Но в той же работе Голича был описан и еще один метод, известный в криптоанализе под общим названием «балансировка время-память», позволяющий существенно сокращать время вскрытия за счет интенсивных предвычислений и хранения предварительных данных в памяти. Так, к примеру, можно было сократить количество опробований вариантов ключа всего до смешных 222 (вскрытие просто «влет»), но для этого требовались 64 терабайта дисковой памяти (что, понятное дело, тоже трудно назвать приемлемыми цифрами для практичной атаки). Но сама идея четко продемонстрировала метод постепенного выхода на реальное соотношение параметров.
А вскоре пошли и сигналы уже о действительном вскрытии защиты системы GSM.
Клонирование и перехват
В апреле 1998 г. группа компьютерных экспертов и криптографов из Калифорнии широко объявила и продемонстрировала, что ей удалось клонировать мобильный телефон стандарта GSM. Ранее всеми по умолчанию предполагалось, что цифровые сети GSM гораздо надежнее защищены от этой напасти, приносящей миллионные убытки сетям аналоговой сотовой телефонии [SC98].
Возглавлял группу Марк Брисено (в Сети более известный как Лаки Грин), глава ассоциации SDA (Smartcard Developer Association), представляющей интересы разработчиков программного обеспечения для смарт-карт. Избрав своей целью определить степень стойкости GSM к попыткам клонирования, исследователи занялись обратной разработкой модуля SIM - той самой смарт-карты, что вставляется в сотовый телефон, содержит алгоритмы АЗ-А8 и однозначно идентифицирует абонента. В процессе подготовки к работам по вскрытию содержимого чипа, в руки к исследователям неисповедимыми путями попало описание «алгоритма COMF128» - наиболее широко распространенной практической реализации АЗ-А8 в SIM-модулях. Эта документация помогла быстрее и полностью восстановить всю необходимую информацию о схеме. После этого Брисено пригласил для ее анализа двух молодых, но уже известных криптоаналитиков, аспирантов Калифорнийского университета в Беркли Дэвида Вагнера и Иэна Голдберга. Тем понадобилось всего несколько часов, чтобы отыскать в схеме фатальные прорехи и разработать метод извлечения из смарт-карты секретного содержимого с помощью 219 опросов чипа (примерно 8 часов).
Представители консорциума GSM, как это принято, сразу же объявили полученные результаты «лабораторными» и не несущими реальной угрозы пользователям сотовой связи. По сути, угроза была представлена «нереальной» лишь на том основании, что в США обладание оборудованием для клонирования и публичная практическая демонстрация разработанной атаки являются противозаконными. Но уже очень скоро стали появляться сообщения о демонстрации клонирования телефонов GSM в странах с иным законодательством, в частности, в Германии [СС98].
