Свежий взлом GSM: о чём речь

29. December 2009, 19:35 Безопасность, Компьютеры и ПО, Криптология, Электроника

В СМИ сегодня пишут (вот, например, на “Ленте”), что “хакер взломал GSM”. Речь идёт о работе Карстена Нола (Karsten Nohl), а точнее, речь о завершении важного этапа работы. Подробности реального положения дел такие: атаки на алгоритм шифрования A5/1, используемый GSM для защиты переговоров в радиоэфире, известны уже лет десять. Правда, известны они были скорее в теории, а не на практике. Для получения доступного практичного механизма перехвата и дешифровки GSM-разговоров (SMS, конечно, тоже) в пассивном режиме не хватало предвычисленной базы данных (таблиц ключей), делающей возможным раскрытие произвольного ключа за разумное время.

Нол в 2008-2009 гг. создал проект по генерации нужных таблиц, предложив поучаствовать в создании распределённой вычислительной сети добровольцам. В итоге, сейчас нужные таблицы вычислены общими усилиями и, как утверждают, доступны в P2P-сетях. Тут нужно отметить, что полная “таблица ключей” для A5/1 – требует очень большого объёма для хранения, и огромного машинного времени для вычисления. Поэтому использовался отработанный на “взломах” хешированных (например, MD5) паролей метод: в БД сохранются не все возможные “ключевые варианты” (в таком случае, дискового пространства потребовалось бы слишком много), а лишь определённая их часть, представленная в виде “сжатой” структуры (так называемые rainbow tables), многократно ускоряющей перебор ключей. Это известный в криптологии подход, позволяющий найти “алгоритмический компромисс” между количеством вычислений и объёмом памяти. В данном случае подход, похоже, качественно реализовали на практике (что далеко не всегда удаётся).

Интересно, что для генерации таблиц ключей использовались системы с современными графическими ускорителями (3D-ускорители для игрушек), которые, как известно, позволяют многократно ускорить многие криптографические операции. Вот какая польза от компьютерных игр. (Между прочим, летом 2008-го года с помощью кластера из нескольких сотен Sony PlayStation исследователи реализовали на практике уязвимость в SSL, выпустив полностью валидный, но при этом поддельный SSL-сертификат.)

Кстати, имея соответствующее радиооборудование, получать ключи для дешифрования GSM-трафика можно было и раньше, в активном режиме, используя запрос к телефону с фиктивной базовой станции. Сейчас же речь идёт о быстром пассивном методе: записали трафик из эфира и за какие-то минуты (быстрее?) расшифровали, вычислив ключ.

Адрес записки: https://dxdt.ru/2009/12/29/2868/

Похожие записки:



Далее - мнения и дискуссии

(Сообщения ниже добавляются читателями сайта, через форму, расположенную в конце страницы.)

Комментарии читателей блога: 13

  • 1 <t> // 30th December 2009, 22:30 // Читатель kaschey написал:

    3D-ускорители для игрушек оптимизированы для плавающих чисел. То есть умножения, сложения чисел Single и (реже) Double почти не отстают от умножения, сложения целых чисел.
    Вывод: 3D-ускорители тут помочь не могут.

    А вот дешевизна приставок важный фактор.

    А вот с качественной рализацией вы, Александр, в точку попали. Программистов способных писать первоклассный код почти нет. Почти все пишут много, быстро, знают 10 языков, 100 технологий и т. п. А вот довести какую-нибудь достаточно сложную задачу до ума почти никто не может.

    Анекдот в тему:
    Разум, как и все во вселенной, величина постоянная. А население-то растёт!

  • 2 <t> // 30th December 2009, 23:23 // Читатель arcman написал:

    > Вывод: 3D-ускорители тут помочь не могут.

    а MD5 как тогда на GPU считают?

  • 3 <t> // 31st December 2009, 12:25 // Александр Венедюхин:

    3D-ускорители для игрушек оптимизированы для плавающих чисел.

    Ну а какая разница-то? Там операции всё равно целочисленные по своей природе.

  • 4 <t> // 31st December 2009, 19:03 // Читатель kaschey написал:

    >>> Ну а какая разница-то? Там операции всё равно целочисленные по своей природе.

    Смысл всех этих ускорителей приблизить скорость операций с плавающими числами к скорости с целыми. А так умножение или сложение двух плавающих чисел раз в 10 медленнее, чем целых. Сопроцессор всегда оперирует с 80-разрядными числами Extended, а ускоритель, жертвуя точностью, с 32-разрядными Single, но с двумя сразу! Вот и вся хитрость. И числа короткие и по два в раз. Но с целыми-то ЦП лучше управится.

    >>> а MD5 как тогда на GPU считают?

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

    Ещё про криптографические алгоритмы:
    Они долгие по перебору, но не требовательные к памяти. Поэтому для шифрования и вычисления хэшей удобно использовать много дешевых параллельных схем вместо одного дорогого универсального компьютера. Есть специальные криптографические чипы. Он стоит не много, но один “100” персоналок махом сделает, потому что считает “100” блоков одновременно.
    Вспомните микропроцессорные карточки Сбербанка – Сберкарт, там такая схема спрятана. Цена не сопоставима даже с 3D-ускорителем. Теперь представляете, что может криптографический чип. А в 3D-ускорителе ни одной специальной схемы нет. Ради изврата, конечно, можно криптографических шейдеров для видюхи написать, но не практично же (микроскопом гвозди забивать)!

  • 5 <t> // 31st December 2009, 20:28 // Александр Венедюхин:

    Жуть какая! Ну нельзя же настолько быть не в теме, и что-то ещё утверждать! Читайте, прежде всего, здесь: http://www.gpgpu.ru/. Например, подборка ссылок по MD5: http://www.gpgpu.ru/reviews/gpu-md5.html

    Ну и вообще, нужно иметь в виду, что даже операции с вещественными числами (наверное, Вы их изволите называть “плавающими”?) на современных процессорах, они целочисленные по своей математической природе, ну просто процессор так устроен. И как раз в графических ускорителях много “дешёвых параллельных схем” – поэтому и используют их с успехом.

  • 6 <t> // 31st December 2009, 21:04 // Читатель Jeff Zanooda написал:

    > А так умножение или сложение двух плавающих чисел раз в 10 медленнее, чем целых.
    Процессор 80286 умножал целые числа быстрее, чем сопроцессор 80287 числа с плавающей точкой. Но это когда ж было. Начиная с 80486 такой разницы нет, не говоря уж о всяких пентиумах.

  • 7 <t> // 1st January 2010, 18:16 // Читатель Сергей написал:

    для kaschey:

    можете заглянуть вот сюда:
    http://http.developer.nvidia.com/GPUGems3/gpugems3_part06.html

    еще могу порекомендовать документы описывающие внутреннее устройство gpu той же nvidia (это по поводу “дешевых параллельных схем”).

  • 8 <t> // 3rd January 2010, 18:56 // Читатель lossen написал:

    как видно, здесь собрались специалисты по GPU, а не по GSM ;)
    A5/1 не используется в России и странах бывшего Союза – экспортные ограничения, у нас используется А5/2 – а для него еще никто не сгенерил “таблиц ключей” так что можно спать спокойно, – в эфире вас никто не прослушает

  • 9 <t> // 3rd January 2010, 22:10 // Александр Венедюхин:

    Ох-ох! А A5/2 – он вообще совсем не стойкий, для него таблицы и не нужны – без таблиц раскрывается. Читайте, хотя бы, литературу внимательнее, прежде чем комментировать.

  • 10 <t> // 3rd January 2010, 23:56 // Читатель Валентин написал:

    для Александр Венедюхин:
    про А5.2 хотелось бы увидеть ссылки на авторитетные источники

  • 11 <t> // 4th January 2010, 00:19 // Александр Венедюхин:

    Легко: http://shipilov.com/link.html

  • 12 <t> // 4th January 2010, 10:32 // Читатель somewan написал:

    Дилетанты просто слабо ощущают разницу между ?компрометацией шифра? и возможностью это практически использовать. Зато можно вволю пошуметь про Голактеко Опасносте!!

  • 13 <t> // 5th January 2010, 05:59 // Читатель Jeff Zanooda написал:

     Лучше A5/0 использовать. Аргументы – в статье про видео с американских беспилотников.