Безопасность 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.


Содержание раздела