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

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

1 из членов Smartcard Developer Association, использующий псевдоним "Lucki Green" , не очень давно подвел промежуточный конец собственным изысканиям в области соотношения истинной и декларируемой безопасности системы GSM . Формулировки его звучат вполне задиристо, однако нельзя не согласиться, что у них есть солидное обоснование.

Lucki Green пишет:

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

После, в конкретном применении к GSM, Lucki Green перечисляет следующие компрометирующие систему слабости, обнаруженные исследователями 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-трафика, было бы довольно скомпрометировать эффективную длину ключа. Было бы довольно скомпрометировать алгоритм создании ключа. Было бы довольно скомпрометировать алгоритм шифровки. Однако спецслужбы сделали все 3 эти вещи. Такое возможно назвать только "неплохо продуманной гарантированно излишней компрометацией".

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

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

Наконец, в декабре 1999 г. пришло еще одно известие. Израильские криптографы Ади Шамир (A.Shamir) и Алекс Бирюков (A.Biruckov) разместили статью, в которой описан разработанный ими вполне нетривиальный, однако по теоретическим расчетам весьма эффективный способ вскрытия алгоритма A5/1.

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

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

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

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

"Сейчас мы будем делать по-другому"

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

Наиболее отрадно то, что данную истину, похоже, признали и в консорциуме GSM. Джеймс Моран (D.Moran), ведающий сегодня алгоритмами безопасности GSM, заявляет следующее:

Когда эти шифры разрабатывались в 1989 г., широкая публикация алгоритмов не была распространенным подходом. Однако, создаваемые сейчас алгоритмы будут обнародованы для предварительного их изучения.

Последние курьезы

Ошибка при создании роумингово протокола, используемого в мобильных телефонах стандарта GSM, позволяет перехватывать телефонный диалог. Маленькая хитрость - просто заставьте телефон думать, что он где-то в другом месте.

Стандарт GSM наиболее известный стандарт сотовой связи в Европе и Азии. В Америке этот стандарт использует всего около 6.5 млн человек, однако их количество начинает увеличиваться, т.к. стандарт обеспечивает довольно простой роуминг в азиатских и европейских странах. Роуминг и "многоязычность" GSM - ахиллесова пята стандарта. Производители не могут вывозить системы кодирования в отдельные страны, к примеру, подвергшиеся санкциям ООН, по этой причине обычная версия протокола GSM не использует кодирование.

Само по себе это не сложность, - считает Дэвид Вагнер (David Wagner), проф. компьютерных наук Калифорнийского Университета, - однако GSM к тому же не удостоверяет подлинность базовых станций - устройств, обеспечивающих связь с трубками, а это уже потенциально опасно.

По заключению экспертов, возможно сделать фальшивую базовую станцию, эмитирующую сигнал настоящей станции и заставляющей мобильные телефоны подключаться к нему. Затем подделка, условно говоря, сообщает телефону -- "ты в Ираке, не используй кодирование" -- и незащищенный сигнал будет проходить м/у фальшивой станцией к настоящей станции и трубке. Поддельная станция располагается посередине м/у настоящей и собственно телефоном, перехватывая их связь, однако при том, ни станция, ни телефон не знают о ее присутствии. Многие ученые опасались подобной ошибки в системе безопасности еще несколько лет тому назад, однако это, по заверениям Вагнера, было "неплохо хранящимся секретом". "Мы знали об этом, как о технической проблеме, однако не увидели причин ее демонстрировать," - заявил Джеймс Моран (James Moran), директор по безопасности GSM Association. Он прибавил, что создание перехватывающего устройства потребует серьезных технических навыков. Моран заявил, что в следующем стандарте GSM эта сложность будет устранена.

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