Неслучайные случайности

Автор: Киви Берд

Одно из главных светил открытой криптографии, израильский профессор Ади Шамир (Adi Shamir), опубликовал работу без преувеличения взрывного характера. В ней показано, сколь гигантскую роль в стойкости компьютерных систем безопасности играет надежное выявление ошибок программирования, ибо даже мельчайший и почти незаметный баг может иметь роковые последствия. Вместе с ростом числа строк кода в программах, усложняющейся оптимизацией операций и нарастающей длиной слова в процессорах, становится все более вероятным появление ошибок в конечных продуктах, запускаемых в массовое производство. Примером тому может служить случайное открытие в середине 1990-х глубоко спрятавшегося "бага деления" в процессорах Pen-tium. Или совсем недавно обнаруженная ошибка умножения в программе Microsoft Excel.

Если какая-нибудь спецслужба, пишет Шамир, обнаружит (или тайно встроит) хотя бы лишь пару таких целых чисел, произведение которых микропроцессор вычисляет некорректно, то последствия ошибки (даже в единственном бите низкого разряда) будут сокрушительными с точки зрения криптографии и защиты информации в компьютере. Потому что тогда ЛЮБОЙ ключ в ЛЮБОЙ криптопрограмме на основе RSA, работающей на ЛЮБОМ из миллионов компьютеров с этим процессором, может быть взломан с помощью специально подобранного сообщения. Кроме того, по заключению Шамира, аналогичная атака может применяться против любых криптосхем на основе дискретных логарифмов и эллиптических кривых (где вдобавок можно эксплуатировать еще и баги деления). Иначе говоря, мелкий баг способен радикально подрывать стойкость практически всех современных криптосхем с открытым ключом.

Почти наверняка можно утверждать, что нет никакой связи между появлением работы Шамира и одновременной публикацией эссе другого известного криптографа, Брюса Шнайера. Статья посвящена вроде бы совсем другой теме, стандартам на генераторы случайных чисел, но и здесь звучит тот же самый мотив. Генераторы случайных чисел (RNG) играют в криптографии очень важную роль: они применяются для выработки ключей шифрования, векторов инициализации и запросов аутентификации, формирования общего ключа, генерации простых чисел и т. д. Если взломан генератор случайных чисел, то в большинстве случаев можно считать взломанной и всю систему безопасности. Шнайер забил тревогу, когда увидел, что в новый спецвыпуск Национального института стандартов США (NIST Special Publication 800-90), описывающий четыре одобренных к использованию схемы RNG, включен генератор Dual_EC_DRBG, разработанный в недрах американского Агентства национальной безопасности.

Криптографы АНБ, спору нет, слывут очень компетентными специалистами, однако генератор, предложенный этим ведомством в 2006 году, известен независимым исследователям с другой стороны - как довольно странный алгоритм, очень медленный в работе и весьма мутный по конструкции. Более того, на августовской конференции CRYPTO 2007 два аналитика (Dan Shumow и Niels Ferguson) показали, что алгоритм содержит слабость, называемую backdoor, то есть "черный ход". Устроено это примерно так. Dual_EC_DRBG работает на основе аппарата эллиптических кривых, которые задаются определенным набором констант. АНБ не объясняет, почему были выбраны именно эти константы. Но они хотя бы известны. Однако при анализе схемы выяснилось, что эти числа связаны со вторым, секретным набором чисел, которые действуют в качестве "скелета" схемы или мастер-ключа. И если вы знаете эти секретные числа, то всего по 32 байтам выхода можно предсказывать всю генерируемую "случайным генератором" последовательность. Проще говоря - взламывать безопасность, обеспеченную Dual_EC_DRBG, фактически на лету.

Таким образом, следует всячески избегать Dual_EC_DRBG. Однако выбор возможен далеко не всегда. Скажем, генератор случайных чисел, встроенный в ОС Windows, автоматически используется во всех приложениях системы, связанных с защитой информации. И при этом конкретные алгоритмы генерации, используемые в Microsoft для данной цели, никогда открыто не публиковались и не подвергались независимому анализу. Ныне этот пробел восполнила группа израильских криптографов из университетов Иерусалима и Хайфы (Leo Dorrendorf, Zvi Gutterman, Benny Pinkas), которые провели обратную инженерную разработку критичных мест в двоичном коде Windows 2000, в частности, восстановив функцию CryptGenRandom. И обнаружили массу неприятных вещей (eprint.iacr.org/2007/419).

Прежде всего, аналитики нашли уязвимость, позволяющую организовать атаку, эффективно отыскивающую предыдущие состояния генератора, а значит, и вычислять будущие числа на выходе. Кроме того, установлено, что генератор управляется системой таким образом, который многократно усиливает значение уязвимости. А именно - функция запускается в режиме пользователя, а не в режиме ядра, что делает очень легким доступ к состояниям генератора даже без привилегий администратора. В совокупности с другими выявленными слабостями это приводит к тому, что злоумышленник, получив всего лишь одно состояние генератора (например, переполнение буфера), может вычислить 128 килобайт прошлых и будущих "случайных" чисел на выходе алгоритма. Используемых, напомним, в качестве секретных криптопараметров для всех алгоритмов защиты информации в ОС, которая имеет много общего с самой распространенной на сегодня Windows XP. Никто толком не знает, как устроен генератор случайных чисел в XP, но есть веские основания полагать, что он не слишком отличается от Windows 2000.