о безопасности GSM-сетей
Для начала - две цитаты. Две диаметрально противоположные точки зрения, которые сразу же дадут представление об остроте проблемы.
Вот что говорит Джеймс Моран, директор подразделения, отвечающего в консорциуме GSM за безопасность и защиту системы от мошенничества: "Никто в мире не продемонстрировал возможность перехвата звонков в сети GSM. Это факт... Насколько нам известно, не существует никакой аппаратуры, способной осуществлять такой перехват".
А вот мнение Питера Гутмана, весьма известного криптографа из Оклендского университета (Новая Зеландия): "Имея ситуацию, когда целый ряд компаний продает оборудование для перехвата GSM (причем делается это уже в течение определенного времени и с весьма открытой рекламой в Сети), этот директор по безопасности "либо лжет, либо некомпетентен, либо и то, и другое разом" (цитируя строку из книги Deep Crack). Интересно то, что сейчас все рекламирующие данное оборудование фирмы устроили ограниченный доступ на свои сайты, по-видимому, для поддержания мифа о том, что "не существует аппаратуры, способной осуществлять такой перехват".
За последние годы в Интернете и СМИ не раз вспыхивали дискуссии как вокруг самой защиты системы мобильной связи GSM, так и вокруг многочисленных уже случаев ее компрометации. По сути дела, почти всем уже ясно, что GSM - это классический пример провала стратегии, именуемой на Западе SbO, что в зависимости от чувства юмора расшифровывают либо как Security by Obscurity ("безопасность упрятыванием"), либо как Security by Ostrich ("безопасность по-страусиному"). На протяжении примерно десяти лет постепенно обнажались типичные пороки и неудобства вымирающей ныне стратегии, согласно которой степень защиты системы в значительной степени увязывается с сохранением в тайне как особенностей конструкции, так и случаев ее компрометации. Увы, тот факт, что система GSM от рождения несет в себе перечисленные порочные черты, является вполне естественным. Просто потому, что рождалась GSM в соответствующих исторических условиях и от вполне определенных родителей.
что такое защита GSM и как она создавалась
В принципе, по своему замыслу, цифровая система мобильной связи GSM вполне могла бы быть чрезвычайно защищенной. В основе ее лежит свод документов под названием "Меморандум о понимании стандарта GSM" или MoU Groupe Special Mobile standard. Этот Меморандум был подготовлен на излете Холодной войны по инициативе ведущих телекоммуникационных компаний Западной Европы. Разрабатывал техническую документацию GSM Европейский институт стандартов по телекоммуникациям (ETSI), а в создании схемы безопасности, в целом призванной защитить новую систему от перехвата, прослушивания и мошенничества, активное участие приняли спецслужбы стран НАТО.
Основу системы безопасности GSM составляют три секретных алгоритма (официально не раскрытые и поныне, сообщаемые лишь тем, кому это требуется по необходимости - поставщикам оборудования, операторам связи и т.д.):
- А3 - алгоритм аутентификации, защищающий телефон от клонирования;
- А8 - алгоритм генерации криптоключа, по сути дела однонаправленная функция, которая берет фрагмент выхода от A3 и превращает его в сеансовый ключ для A5;
- A5 - собственно алгоритм шифрования оцифрованной речи для обеспечения конфиденциальности переговоров. В GSM используются две основные разновидности алгоритма: A5/1 - сильная версия шифра для избранных стран и A5/2 - ослабленная для всех остальных.
Мобильные станции (телефоны) снабжены смарт-картой, содержащей A3 и A8, а в самом телефоне имеется ASIC-чип с алгоритмом A5. Базовые станции также снабжены ASIC-чипом с A5 и "центром аутенитификации", использующим алгоритмы A3-A8 для идентификации мобильного абонента и генерации сеансового ключа.
Вся эта архитектура при надлежащем исполнении и качественных алгоритмах призвана гарантировать надежную аутентификацию пользователя, обеспечивая защиту мобильных станций от клонирования и прочих методов мошенничества, а также качественное шифрование конфиденциальных переговоров. Собственно говоря, именно это и декларируется компаниями, успешно занимающимися разворачиванием GSM по всему миру.
Но реальность такова, что спецслужбы, занятые защитой правительственных коммуникаций, одновременно вовлечены и в деятельность противоположного рода: перехват и дешифрование коммуникаций в разведывательных целях. По этой причине, как свидетельствуют очевидцы, вокруг степени защиты GSM бушевали немалые страсти, поскольку спецслужбы стран НАТО имели довольно разные точки зрения на этот счет. Германия настаивала на сильных алгоритмах, поскольку имела самую длинную границу с коммунистическим блоком, другие же страны склонялись к ослабленному варианту. В конце концов в качестве основы криптосхемы для A5 была избрана французская разработка.
первые утечки информации
Как бы строго ни контролировались коммерческие секреты, понятно, что широкое распространение продукции рано или поздно приводит к утечкам информации. В GSM они стали появляться уже в начале 90-х годов. К 1994 году основные детали алгоритма A5 уже были известны. Во-первых, British Telecom передала всю техническую документацию Брэдфордскому университету, забыв заключить соглашение о неразглашении информации. Во-вторых, описание A5 появилось в материалах одной из конференций в Китае. Короче говоря, детали о конструкции алгоритма понемногу стали просачиваться в печать, и в конце концов кембриджские ученые М. Роэ и Р .Андерсон опубликовали восстановленную по этим деталям примерную криптосхему в Интернете.
A5 реализует поточный шифр на основе трех линейных регистров сдвига с неравномерным движением. Такого рода схемы на языке специалистов именуются "криптографией военного уровня" и при верном выборе параметров способны обеспечивать очень высокую стойкость шифра. Однако в А5 длины регистров выбраны очень короткими - 19, 22 и 23 бита, что в сумме и дает 64-битный сеансовый ключ шифрования в GSM. Уже одни эти укороченные длины регистров дают теоретическую возможность для хорошо известной лобовой атаки, когда перебирают заполнение двух первых регистров (сложность порядка 240), восстанавливая содержимое третьего регистра по выходной шифрующей последовательности (с общей сложностью порядка 245). Регистры сдвига в схеме A5 имеют не только короткую длину, но и слабые прореженные полиномы обратной связи. Это дает шансы на успех еще одной атаке - корреляционному анализу, позволяющему вскрывать ключ по просачивающейся в выход информации о заполнении регистров. В июне 1994 года д-р Саймон Шеферд из Брэдфордского университета должен был представить на коллоквиуме IEE в Лондоне свой корреляционный способ вскрытия A5. Однако в последний момент его выступление было запрещено Штаб-квартирой правительственной связи, британским аналогом американского АНБ. Доклад был сделан лишь на закрытой секции и опубликован в засекреченном сборнике.
Прошло еще пару лет, и до анализа A5 дошли руки у сербского криптографа доктора Йована Голича, наиболее, вероятно, авторитетного в академических кругах специалиста по поточным шифрам. С чисто теоретических позиций он описал атаку, позволяющую вскрывать начальные заполнения регистров всего по 64 битам шифрпоследовательности с трудозатратами около 240 (справедливости ради надо, правда, отметить, что в реальности данная атака оказалась значительно более трудоемкой. Проведенный в стенах Microsoft эксперимент действительно привел к вскрытию ключа, но понадобилось для этого около двух недель работы 32-узлового кластера машин PII-300! Практичной такую атаку никак не назовешь). Однако, в той же работе Голича был описан и еще один метод, известный в криптоанализе под общим названием "балансировка время-память", позволяющий существенно сокращать время вскрытия за счет интенсивных предвычислений и хранения предварительных данных в памяти. Так, к примеру, можно было сократить количество опробований вариантов ключа всего до 222 , но для этого требовались 64 терабайта дисковой памяти (что, понятное дело, тоже трудно назвать реалистическими цифрами). Но сама идея атаки четко продемонстрировала метод постепенного выхода на реальное соотношение параметров. А вскоре пошли и сигналы о реальном вскрытии защиты системы GSM.
клонирование
В апреле 1998 г. группа компьютерных экспертов из Калифорнии широко объявила и продемонстрировала, что ей удалось клонировать мобильный телефон стандарта GSM. Ранее всеми по умолчанию предполагалось, что цифровые сети GSM гораздо надежнее защищены от этой напасти, приносящей миллионные убытки сетям аналоговой сотовой телефонии.
Возглавлял группу Марк Брисено, директор так называемой "Ассоциации разработчиков смарт-карт" или SDA (Smartcard Developer Association), представляющей интересы разработчиков программного обеспечения для смарт-карт. Избрав своей целью стойкость GSM к попыткам клонирования, исследователи занялись обратной разработкой модуля SIM. Это та самая смарт-карта, что вставляется в сотовый телефон, содержит алгоритмы A3-A8 и однозначно идентифицирует абонента. В процессе подготовки к работам по вскрытию содержимого чипа, в руки к исследователям неисповедимыми путями попало описание "алгоритма COMP128" - наиболее широко распространенной практической реализации A3-A8 в SIM-модулях. Эта документация помогла быстрее и полностью восстановить всю необходимую информацию о схеме. После этого Брисено пригласил для ее анализа двух молодых, но уже известных криптоаналитиков - аспирантов Калифорнийского университета в Беркли Дэвида Вагнера и Иэна Голдберга. Тем понадобилось всего несколько часов, чтобы отыскать в схеме фатальные прорехи и разработать метод извлечения из карты секретного содержимого с помощью всего 219 опросов чипа смарт-карты.
Представители консорциума GSM, естественно, сразу же объявили полученные результаты "лабораторными" и не несущими реальной угрозы пользователям сотовой связи, поскольку в США обладание оборудованием для клонирования и публичная практическая демонстрация разработанной атаки являются противозаконными. Но уже очень скоро стали появляться сообщения о демонстрации клонирования телефонов GSM в странах с иным законодательством, в частности, в Германии.
вскрытие A5/2
В начале 1999 года в ассоциации SDA были полностью восстановлены и проверены на реальных тестовых векторах криптосхемы алгоритмов A5/1 и A5/2. Обратное восстановление A5/2 подтвердило уже имевшуюся информацию, что в этой схеме добавлен еще один короткий регистр длиной 17 бит, управляющий движением бит в остальных трех регистрах. Вагнеру и Голдбергу очень быстро удалось продемонстрировать, что в этих условиях для вскрытия системы достаточно лобовым перебором (сложность 216) отыскать заполнение управляющего регистра. Делается это всего по двум фреймам сеанса связи длиной по 114 бит (в системе GSM первые два фрейма шифрпоследовательности известны, поскольку шифруются одни нули). Другими словами, вскрытие такого шифра осуществляется что называется "на лету", за 15 миллисекунд работы персонального компьютера.
тотально ослабленная защита
Один из членов Smartcard Developer Association, использующий псевдоним "Лаки Грин" , недавно подвел промежуточный итог своим изысканиям в области соотношения декларируемой и истинной безопасности системы GSM. Формулировки его звучат весьма задиристо, но нельзя не согласиться, что у них имеется солидное обоснование.
Лаки Грин пишет: "Мой опыт работы с GSM показывает, что разведывательные службы, стоящие как известно, за всеми криптоалгоритмами GSM, используют в своей работе весьма специфический подход. Разведслужбы компрометируют любой и каждый компонент криптосистемы, какой только можно скомпрометировать. Разведслужбы, имея такую возможность, ослабляют компонент просто потому, что могут это сделать, а не потому, что им это нужно. Это как бы извращенное воплощение в целом правильного принципа многократной избыточности".
Затем, в конкретном применении к GSM, Лаки Грин перечисляет следующие компрометирующие систему слабости, обнаруженные исследователями SDA: - Скомпрометирована эффективная длина сеансового ключа. В 64-битном ключе, который A8 генерирует для A5, последние 10 бит обнулены. Это совершенно умышленное ослабление системы примерно в 1000 раз.
- Скомпрометирована система аутентификации и алгоритм генерации секретного ключа. Известно, что о слабостях в COMP128, обнаруженных нами в 1998 году, участники GSM MoU были официально уведомлены еще в 1989 году. То есть задолго до широкого распространения GSM. Имеющаяся в MoU "группа экспертов по алгоритмам безопасности" (SAGE), состоящая из людей, фамилии которых неизвестны по сию пору, сохранила в тайне это открытие и не стала информировать о нем даже собственно членов MoU. В результате всего этого разведслужбы имеют возможность клонировать телефоны и вычислять секретные ключи абонентов непосредственно в ходе сеанса связи.
- Скомпрометирован сильный алгоритм шифрования A5/1. В этом шифре с 64-битным ключом имеются многочисленные конструктивные дефекты, приводящие к стойкости, не превышающей стойкость шифра с 40-битным ключом (другими словами, стойкость понижена на 6 порядков или в миллион раз). Непостижимо, каким образом столь очевидный дефект мог быть упущен французскими военными разработчиками.
- Скомпрометирован более слабый алгоритм шифрования A5/2. Хотя в MoU признают, что вскрываемость шифра и была целью разработки A5/2, тем не менее в официальных результатах анализа SAGE сказано, что им неизвестно ни о каких криптографических дефектах в A5/2.
Чтобы обеспечить перехват и дешифрование GSM-трафика, было бы достаточно скомпрометировать эффективную длину ключа. Было бы достаточно скомпрометировать алгоритм генерации ключа. Было бы достаточно скомпрометировать алгоритм шифрования. Но спецслужбы сделали все три эти вещи. Такое можно назвать лишь "хорошо продуманной гарантированно избыточной компрометацией".
И наконец, еще один очень существенный нюанс. Все это шифрование в системе GSM осуществляется только на канале между мобильным телефоном и базовой станцией, то есть в "эфирной" части передачи. При наличии санкции суда на прослушивание звонков правоохранительные органы всегда имеют возможность подключиться непосредственно к базовым станциям /* а того лучше – к коммутаторам, не надо лазить черте где ;) – прим. ред. */, где уже нет никакого шифрования. Так что единственной причиной для тотального ослабления криптозащиты оказывается "нелегальный доступ" без каких бы то ни было ордеров и санкций.
вскрытие A5/1 - пока только теоретическое, но впечатляющее
Израильские криптографы Ади Шамир и Алекс Бирюков опубликовали статью, в которой описан разработанный ими весьма нетривиальный, но по теоретическим расчетам очень эффективный метод вскрытия алгоритма A5/1.
Ади Шамира называют "патриархом израильской криптографии". Еще в 1977 году совместно с американцами Райвестом и Адлеманом Шамир разработал знаменитую криптосхему с открытым ключом RSA (здесь "S" - это Shamir). В 80-е годы, помимо сильных криптоаналитических работ, им разработано несколько криптографических протоколов и криптосхем. В начале 90-х совместно с Эли Бихамом Шамиром разработан метод дифференциального криптоанализа, ставший основой практически всех современных методов исследования и вскрытия блочных шифров. Его новая совместная с Бирюковым работа - это, возможно, первое обращение Шамира к анализу поточных шифров на основе регистров сдвига. Сам он говорит о разработанном методе вскрытия А5 следующее: "Это весьма сложная идея, реализуя которую мы наступаем на многих фронтах, чтобы накопить несколько небольших преимуществ, но сложенные все вместе они дают большой выигрыш. Но статью нашу было нелегко написать. Нелегко ее и читать".
Изложим суть работы в нескольких фразах. Новый метод атаки использует тонкие слабости в структуре регистров сдвига, необратимый механизм их движения, а также частые перезагрузки регистров, применяемые в GSM. В итоге такая атака позволяет отыскивать ключ менее чем за секунду на персональном компьютере, имеющем 128 Мб RAM и два жестких диска по 73 Гб, путем анализа выхода алгоритма в течение первых двух минут телефонного разговора. Для успеха атаки требуется предварительная и поддающаяся распараллеливанию подготовка данных, сложность которой может варьироваться от 238 до 248 шагов. Для подтверждения теоретических расчетов авторы действительно менее чем за секунду нашли 64-битный ключ шифрпоследовательности, порожденной алгоритмом A5/1 в версии SDA (отметим, что факт реальной длины ключа в 54 бита ими не использовался). Сейчас полученные израильскими математиками результаты тщательно изучаются криптографами, но выводы из всей этой истории практически очевидны.
выводы
Итак, ныне уже почти все эксперты в области защиты информации сходятся во мнении, что разработка мер безопасности для широко используемых систем в тайне от общественности - это в корне порочный путь. Единственный способ гарантировать надежную безопасность - это дать возможность проанализировать систему всему сообществу специалистов.
Наиболее отрадно то, что данную истину, похоже, признали и в консорциуме GSM. Цитировавшийся в самом начале статьи Джеймс Моран, ведающий сейчас алгоритмами безопасности GSM, говорит следующее: "Когда эти шифры разрабатывались в 1989 году, широкая публикация алгоритмов не была распространенным подходом. Однако, создаваемые ныне алгоритмы будут опубликованы для предварительного их изучения".
литература (для особо дотошных)
1. "Cell Phone Crypto Penetrated ", Wired News, 6 декабря 1999.
2. Peter Gutmann, "Re: Forthcoming Biryukov/Shamir result against A5/1 GSM privacy algorithm", posting to cryptography@c2.net mailing list, 7 декабря 1999 г.
3. Klaus Brunnstein, "Mobile ComSec in Europe (A5) ", RISKS DIGEST, Volume 14 : Issue 60, 12 мая 1993 г.
4. Ross Anderson, "Subject: A5", posting to Newsgroups: sci.crypt, alt.security, uk.telecom; 17 июня 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 июня 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 октября 1998 г.
Lucky Green , "More NSAKEY musings", Crypto-Gram, 15 сентября, 1999 г.
Автор неизвестен.
Вот что говорит Джеймс Моран, директор подразделения, отвечающего в консорциуме GSM за безопасность и защиту системы от мошенничества: "Никто в мире не продемонстрировал возможность перехвата звонков в сети GSM. Это факт... Насколько нам известно, не существует никакой аппаратуры, способной осуществлять такой перехват".
А вот мнение Питера Гутмана, весьма известного криптографа из Оклендского университета (Новая Зеландия): "Имея ситуацию, когда целый ряд компаний продает оборудование для перехвата GSM (причем делается это уже в течение определенного времени и с весьма открытой рекламой в Сети), этот директор по безопасности "либо лжет, либо некомпетентен, либо и то, и другое разом" (цитируя строку из книги Deep Crack). Интересно то, что сейчас все рекламирующие данное оборудование фирмы устроили ограниченный доступ на свои сайты, по-видимому, для поддержания мифа о том, что "не существует аппаратуры, способной осуществлять такой перехват".
За последние годы в Интернете и СМИ не раз вспыхивали дискуссии как вокруг самой защиты системы мобильной связи GSM, так и вокруг многочисленных уже случаев ее компрометации. По сути дела, почти всем уже ясно, что GSM - это классический пример провала стратегии, именуемой на Западе SbO, что в зависимости от чувства юмора расшифровывают либо как Security by Obscurity ("безопасность упрятыванием"), либо как Security by Ostrich ("безопасность по-страусиному"). На протяжении примерно десяти лет постепенно обнажались типичные пороки и неудобства вымирающей ныне стратегии, согласно которой степень защиты системы в значительной степени увязывается с сохранением в тайне как особенностей конструкции, так и случаев ее компрометации. Увы, тот факт, что система GSM от рождения несет в себе перечисленные порочные черты, является вполне естественным. Просто потому, что рождалась GSM в соответствующих исторических условиях и от вполне определенных родителей.
что такое защита GSM и как она создавалась
В принципе, по своему замыслу, цифровая система мобильной связи GSM вполне могла бы быть чрезвычайно защищенной. В основе ее лежит свод документов под названием "Меморандум о понимании стандарта GSM" или MoU Groupe Special Mobile standard. Этот Меморандум был подготовлен на излете Холодной войны по инициативе ведущих телекоммуникационных компаний Западной Европы. Разрабатывал техническую документацию GSM Европейский институт стандартов по телекоммуникациям (ETSI), а в создании схемы безопасности, в целом призванной защитить новую систему от перехвата, прослушивания и мошенничества, активное участие приняли спецслужбы стран НАТО.
Основу системы безопасности GSM составляют три секретных алгоритма (официально не раскрытые и поныне, сообщаемые лишь тем, кому это требуется по необходимости - поставщикам оборудования, операторам связи и т.д.):
- А3 - алгоритм аутентификации, защищающий телефон от клонирования;
- А8 - алгоритм генерации криптоключа, по сути дела однонаправленная функция, которая берет фрагмент выхода от A3 и превращает его в сеансовый ключ для A5;
- A5 - собственно алгоритм шифрования оцифрованной речи для обеспечения конфиденциальности переговоров. В GSM используются две основные разновидности алгоритма: A5/1 - сильная версия шифра для избранных стран и A5/2 - ослабленная для всех остальных.
Мобильные станции (телефоны) снабжены смарт-картой, содержащей A3 и A8, а в самом телефоне имеется ASIC-чип с алгоритмом A5. Базовые станции также снабжены ASIC-чипом с A5 и "центром аутенитификации", использующим алгоритмы A3-A8 для идентификации мобильного абонента и генерации сеансового ключа.
Вся эта архитектура при надлежащем исполнении и качественных алгоритмах призвана гарантировать надежную аутентификацию пользователя, обеспечивая защиту мобильных станций от клонирования и прочих методов мошенничества, а также качественное шифрование конфиденциальных переговоров. Собственно говоря, именно это и декларируется компаниями, успешно занимающимися разворачиванием GSM по всему миру.
Но реальность такова, что спецслужбы, занятые защитой правительственных коммуникаций, одновременно вовлечены и в деятельность противоположного рода: перехват и дешифрование коммуникаций в разведывательных целях. По этой причине, как свидетельствуют очевидцы, вокруг степени защиты GSM бушевали немалые страсти, поскольку спецслужбы стран НАТО имели довольно разные точки зрения на этот счет. Германия настаивала на сильных алгоритмах, поскольку имела самую длинную границу с коммунистическим блоком, другие же страны склонялись к ослабленному варианту. В конце концов в качестве основы криптосхемы для A5 была избрана французская разработка.
первые утечки информации
Как бы строго ни контролировались коммерческие секреты, понятно, что широкое распространение продукции рано или поздно приводит к утечкам информации. В GSM они стали появляться уже в начале 90-х годов. К 1994 году основные детали алгоритма A5 уже были известны. Во-первых, British Telecom передала всю техническую документацию Брэдфордскому университету, забыв заключить соглашение о неразглашении информации. Во-вторых, описание A5 появилось в материалах одной из конференций в Китае. Короче говоря, детали о конструкции алгоритма понемногу стали просачиваться в печать, и в конце концов кембриджские ученые М. Роэ и Р .Андерсон опубликовали восстановленную по этим деталям примерную криптосхему в Интернете.
A5 реализует поточный шифр на основе трех линейных регистров сдвига с неравномерным движением. Такого рода схемы на языке специалистов именуются "криптографией военного уровня" и при верном выборе параметров способны обеспечивать очень высокую стойкость шифра. Однако в А5 длины регистров выбраны очень короткими - 19, 22 и 23 бита, что в сумме и дает 64-битный сеансовый ключ шифрования в GSM. Уже одни эти укороченные длины регистров дают теоретическую возможность для хорошо известной лобовой атаки, когда перебирают заполнение двух первых регистров (сложность порядка 240), восстанавливая содержимое третьего регистра по выходной шифрующей последовательности (с общей сложностью порядка 245). Регистры сдвига в схеме A5 имеют не только короткую длину, но и слабые прореженные полиномы обратной связи. Это дает шансы на успех еще одной атаке - корреляционному анализу, позволяющему вскрывать ключ по просачивающейся в выход информации о заполнении регистров. В июне 1994 года д-р Саймон Шеферд из Брэдфордского университета должен был представить на коллоквиуме IEE в Лондоне свой корреляционный способ вскрытия A5. Однако в последний момент его выступление было запрещено Штаб-квартирой правительственной связи, британским аналогом американского АНБ. Доклад был сделан лишь на закрытой секции и опубликован в засекреченном сборнике.
Прошло еще пару лет, и до анализа A5 дошли руки у сербского криптографа доктора Йована Голича, наиболее, вероятно, авторитетного в академических кругах специалиста по поточным шифрам. С чисто теоретических позиций он описал атаку, позволяющую вскрывать начальные заполнения регистров всего по 64 битам шифрпоследовательности с трудозатратами около 240 (справедливости ради надо, правда, отметить, что в реальности данная атака оказалась значительно более трудоемкой. Проведенный в стенах Microsoft эксперимент действительно привел к вскрытию ключа, но понадобилось для этого около двух недель работы 32-узлового кластера машин PII-300! Практичной такую атаку никак не назовешь). Однако, в той же работе Голича был описан и еще один метод, известный в криптоанализе под общим названием "балансировка время-память", позволяющий существенно сокращать время вскрытия за счет интенсивных предвычислений и хранения предварительных данных в памяти. Так, к примеру, можно было сократить количество опробований вариантов ключа всего до 222 , но для этого требовались 64 терабайта дисковой памяти (что, понятное дело, тоже трудно назвать реалистическими цифрами). Но сама идея атаки четко продемонстрировала метод постепенного выхода на реальное соотношение параметров. А вскоре пошли и сигналы о реальном вскрытии защиты системы GSM.
клонирование
В апреле 1998 г. группа компьютерных экспертов из Калифорнии широко объявила и продемонстрировала, что ей удалось клонировать мобильный телефон стандарта GSM. Ранее всеми по умолчанию предполагалось, что цифровые сети GSM гораздо надежнее защищены от этой напасти, приносящей миллионные убытки сетям аналоговой сотовой телефонии.
Возглавлял группу Марк Брисено, директор так называемой "Ассоциации разработчиков смарт-карт" или SDA (Smartcard Developer Association), представляющей интересы разработчиков программного обеспечения для смарт-карт. Избрав своей целью стойкость GSM к попыткам клонирования, исследователи занялись обратной разработкой модуля SIM. Это та самая смарт-карта, что вставляется в сотовый телефон, содержит алгоритмы A3-A8 и однозначно идентифицирует абонента. В процессе подготовки к работам по вскрытию содержимого чипа, в руки к исследователям неисповедимыми путями попало описание "алгоритма COMP128" - наиболее широко распространенной практической реализации A3-A8 в SIM-модулях. Эта документация помогла быстрее и полностью восстановить всю необходимую информацию о схеме. После этого Брисено пригласил для ее анализа двух молодых, но уже известных криптоаналитиков - аспирантов Калифорнийского университета в Беркли Дэвида Вагнера и Иэна Голдберга. Тем понадобилось всего несколько часов, чтобы отыскать в схеме фатальные прорехи и разработать метод извлечения из карты секретного содержимого с помощью всего 219 опросов чипа смарт-карты.
Представители консорциума GSM, естественно, сразу же объявили полученные результаты "лабораторными" и не несущими реальной угрозы пользователям сотовой связи, поскольку в США обладание оборудованием для клонирования и публичная практическая демонстрация разработанной атаки являются противозаконными. Но уже очень скоро стали появляться сообщения о демонстрации клонирования телефонов GSM в странах с иным законодательством, в частности, в Германии.
вскрытие A5/2
В начале 1999 года в ассоциации SDA были полностью восстановлены и проверены на реальных тестовых векторах криптосхемы алгоритмов A5/1 и A5/2. Обратное восстановление A5/2 подтвердило уже имевшуюся информацию, что в этой схеме добавлен еще один короткий регистр длиной 17 бит, управляющий движением бит в остальных трех регистрах. Вагнеру и Голдбергу очень быстро удалось продемонстрировать, что в этих условиях для вскрытия системы достаточно лобовым перебором (сложность 216) отыскать заполнение управляющего регистра. Делается это всего по двум фреймам сеанса связи длиной по 114 бит (в системе GSM первые два фрейма шифрпоследовательности известны, поскольку шифруются одни нули). Другими словами, вскрытие такого шифра осуществляется что называется "на лету", за 15 миллисекунд работы персонального компьютера.
тотально ослабленная защита
Один из членов Smartcard Developer Association, использующий псевдоним "Лаки Грин" , недавно подвел промежуточный итог своим изысканиям в области соотношения декларируемой и истинной безопасности системы GSM. Формулировки его звучат весьма задиристо, но нельзя не согласиться, что у них имеется солидное обоснование.
Лаки Грин пишет: "Мой опыт работы с GSM показывает, что разведывательные службы, стоящие как известно, за всеми криптоалгоритмами GSM, используют в своей работе весьма специфический подход. Разведслужбы компрометируют любой и каждый компонент криптосистемы, какой только можно скомпрометировать. Разведслужбы, имея такую возможность, ослабляют компонент просто потому, что могут это сделать, а не потому, что им это нужно. Это как бы извращенное воплощение в целом правильного принципа многократной избыточности".
Затем, в конкретном применении к GSM, Лаки Грин перечисляет следующие компрометирующие систему слабости, обнаруженные исследователями SDA: - Скомпрометирована эффективная длина сеансового ключа. В 64-битном ключе, который A8 генерирует для A5, последние 10 бит обнулены. Это совершенно умышленное ослабление системы примерно в 1000 раз.
- Скомпрометирована система аутентификации и алгоритм генерации секретного ключа. Известно, что о слабостях в COMP128, обнаруженных нами в 1998 году, участники GSM MoU были официально уведомлены еще в 1989 году. То есть задолго до широкого распространения GSM. Имеющаяся в MoU "группа экспертов по алгоритмам безопасности" (SAGE), состоящая из людей, фамилии которых неизвестны по сию пору, сохранила в тайне это открытие и не стала информировать о нем даже собственно членов MoU. В результате всего этого разведслужбы имеют возможность клонировать телефоны и вычислять секретные ключи абонентов непосредственно в ходе сеанса связи.
- Скомпрометирован сильный алгоритм шифрования A5/1. В этом шифре с 64-битным ключом имеются многочисленные конструктивные дефекты, приводящие к стойкости, не превышающей стойкость шифра с 40-битным ключом (другими словами, стойкость понижена на 6 порядков или в миллион раз). Непостижимо, каким образом столь очевидный дефект мог быть упущен французскими военными разработчиками.
- Скомпрометирован более слабый алгоритм шифрования A5/2. Хотя в MoU признают, что вскрываемость шифра и была целью разработки A5/2, тем не менее в официальных результатах анализа SAGE сказано, что им неизвестно ни о каких криптографических дефектах в A5/2.
Чтобы обеспечить перехват и дешифрование GSM-трафика, было бы достаточно скомпрометировать эффективную длину ключа. Было бы достаточно скомпрометировать алгоритм генерации ключа. Было бы достаточно скомпрометировать алгоритм шифрования. Но спецслужбы сделали все три эти вещи. Такое можно назвать лишь "хорошо продуманной гарантированно избыточной компрометацией".
И наконец, еще один очень существенный нюанс. Все это шифрование в системе GSM осуществляется только на канале между мобильным телефоном и базовой станцией, то есть в "эфирной" части передачи. При наличии санкции суда на прослушивание звонков правоохранительные органы всегда имеют возможность подключиться непосредственно к базовым станциям /* а того лучше – к коммутаторам, не надо лазить черте где ;) – прим. ред. */, где уже нет никакого шифрования. Так что единственной причиной для тотального ослабления криптозащиты оказывается "нелегальный доступ" без каких бы то ни было ордеров и санкций.
вскрытие A5/1 - пока только теоретическое, но впечатляющее
Израильские криптографы Ади Шамир и Алекс Бирюков опубликовали статью, в которой описан разработанный ими весьма нетривиальный, но по теоретическим расчетам очень эффективный метод вскрытия алгоритма A5/1.
Ади Шамира называют "патриархом израильской криптографии". Еще в 1977 году совместно с американцами Райвестом и Адлеманом Шамир разработал знаменитую криптосхему с открытым ключом RSA (здесь "S" - это Shamir). В 80-е годы, помимо сильных криптоаналитических работ, им разработано несколько криптографических протоколов и криптосхем. В начале 90-х совместно с Эли Бихамом Шамиром разработан метод дифференциального криптоанализа, ставший основой практически всех современных методов исследования и вскрытия блочных шифров. Его новая совместная с Бирюковым работа - это, возможно, первое обращение Шамира к анализу поточных шифров на основе регистров сдвига. Сам он говорит о разработанном методе вскрытия А5 следующее: "Это весьма сложная идея, реализуя которую мы наступаем на многих фронтах, чтобы накопить несколько небольших преимуществ, но сложенные все вместе они дают большой выигрыш. Но статью нашу было нелегко написать. Нелегко ее и читать".
Изложим суть работы в нескольких фразах. Новый метод атаки использует тонкие слабости в структуре регистров сдвига, необратимый механизм их движения, а также частые перезагрузки регистров, применяемые в GSM. В итоге такая атака позволяет отыскивать ключ менее чем за секунду на персональном компьютере, имеющем 128 Мб RAM и два жестких диска по 73 Гб, путем анализа выхода алгоритма в течение первых двух минут телефонного разговора. Для успеха атаки требуется предварительная и поддающаяся распараллеливанию подготовка данных, сложность которой может варьироваться от 238 до 248 шагов. Для подтверждения теоретических расчетов авторы действительно менее чем за секунду нашли 64-битный ключ шифрпоследовательности, порожденной алгоритмом A5/1 в версии SDA (отметим, что факт реальной длины ключа в 54 бита ими не использовался). Сейчас полученные израильскими математиками результаты тщательно изучаются криптографами, но выводы из всей этой истории практически очевидны.
выводы
Итак, ныне уже почти все эксперты в области защиты информации сходятся во мнении, что разработка мер безопасности для широко используемых систем в тайне от общественности - это в корне порочный путь. Единственный способ гарантировать надежную безопасность - это дать возможность проанализировать систему всему сообществу специалистов.
Наиболее отрадно то, что данную истину, похоже, признали и в консорциуме GSM. Цитировавшийся в самом начале статьи Джеймс Моран, ведающий сейчас алгоритмами безопасности GSM, говорит следующее: "Когда эти шифры разрабатывались в 1989 году, широкая публикация алгоритмов не была распространенным подходом. Однако, создаваемые ныне алгоритмы будут опубликованы для предварительного их изучения".
литература (для особо дотошных)
1. "Cell Phone Crypto Penetrated ", Wired News, 6 декабря 1999.
2. Peter Gutmann, "Re: Forthcoming Biryukov/Shamir result against A5/1 GSM privacy algorithm", posting to cryptography@c2.net mailing list, 7 декабря 1999 г.
3. Klaus Brunnstein, "Mobile ComSec in Europe (A5) ", RISKS DIGEST, Volume 14 : Issue 60, 12 мая 1993 г.
4. Ross Anderson, "Subject: A5", posting to Newsgroups: sci.crypt, alt.security, uk.telecom; 17 июня 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 июня 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 октября 1998 г.
Lucky Green , "More NSAKEY musings", Crypto-Gram, 15 сентября, 1999 г.
Автор неизвестен.
Сетевые решения. Статья была опубликована в номере 09 за 2005 год в рубрике save ass…
