(ноябрь 2007)
Одно из главных светил открытой криптографии, израильский профессор Ади Шамир (Adi Shamir, более всего знаменитый как «S» в криптосхеме RSA), опубликовал работу без преувеличения взрывного характера (Microprocessor Bugs Can Be Security Disasters).
Суть исследования сводится к тому, сколь гигантскую роль в стойкости компьютерных систем безопасности играет надежное выявление ошибок программирования, ибо даже мельчайший и почти незаметный баг может иметь роковые последствия.
Вместе с ростом строк кода в программах, усложняющейся оптимизацией операций и нарастающей длиной слова в процессорах, становится все более вероятным появление невыявленных ошибок в конечных продуктах, запускаемых в массовое производство.
Примером тому может служить случайное открытие в середине 1990-х – глубоко спрятавшийся «баг деления» в процессорах Pentium. Или совсем недавно обнаруженная ошибка умножения в программе Microsoft Excel.
В новой же статье Шамира показано, что если какая-нибудь спецслужба обнаружит (или тайно встроит) хотя бы лишь одну пару таких целых чисел, произведение которых в каком-нибудь популярном микропроцессоре вычисляется некорректно (даже в единственном бите низкого разряда), то последствия этой ошибки будут сокрушительными с точки зрения криптографии и защиты информации в компьютере.
Потому что тогда ЛЮБОЙ ключ в ЛЮБОЙ криптопрограмме на основе RSA, работающей на ЛЮБОМ из миллионов компьютеров с этим процессором, может быть тривиально взломан с помощью единственного сообщения специально подобранного вида.
Кроме того, по заключению Шамира, аналогичная атака может применяться против любых криптосхем на основе дискретных логарифмов и эллиптических кривых (где, кроме того, можно эксплуатировать еще и баги деления). Иначе говоря, невыявленный вовремя мелкий баг способен радикально подрывать стойкость практически всех современных криптосхем с открытым ключом.
Почти наверняка можно утверждать, что нет никакой прямой связи между появлением работы Шамира и одновременной публикацией в США эссе другого известного криптографа, Брюса Шнайера (Strange Story of Dual_EC_DRBG). Эта статья посвящена вроде бы совсем другой теме, стандартам на генераторы случайных чисел, но и здесь определенно звучит тот же самый мотив.
Генераторы случайных чисел, или 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. И обнаружили массу неприятных вещей (Cryptanalysis of the Random Number Generator of the Windows OS).
Прежде всего, аналитики нашли уязвимость, позволяющую организовать атаку, эффективно отыскивающую предыдущие состояния генератора и таким образом вычислять будущие числа на выходе. Кроме того, установлено, что генератор управляется системой таким образом, который многократно усиливает роль этой уязвимости. А именно, функция запускается в режиме пользователя, а не в режиме ядра, что делает очень легким доступ к состояниям генератора даже без привилегий администратора.
В совокупности с другими выявленными слабостями это приводит к тому, что злоумышленник, получив всего лишь одно состояние генератора (например, переполнением буфера), может вычислить 128 килобайт прошлых и будущих «случайных» чисел на выходе алгоритма. Используемых, напомним, в качестве секретных криптопараметров для всех алгоритмов защиты информации в ОС. Которая имеет много общего с самой распространенной на сегодня ОС Win XP.
Никто толком не знает, как устроен генератор случайных чисел в XP, но есть веские основания полагать, что он не особо отличается от Win 2000.
___
(Подробнее о работе израильских исследователей и о стойкости криптографии в ОС Windows см. Хитрости крипторемесла.)
kiwi arXiv 