7.4. Ошибки в генераторах псевдослучайных чисел

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

Пожалуй, самый известный пример — ошибка в реализации протокола SSr (Secure Sockets Rауег) в браузере Netscape.

Взлом 128-битового шифрования в Netscape
Компания Netscape разработала протокол SSL и реализовала его в своем браузере. Данные, передаваемые посредством SSL, зашифровывались алгоритмом RC4 со 128-битовым ключом. 17 сентября 1995 года Йен Голдберг (Ian Goldberg) сообщил о том, что ему в сотрудничестве с Дэвидом Вагнером (David Wagner) удалось обнаружить уязвимость в процедуре выбора 128-битового ключа для алгоритма RC4. Недостаток процедуры заключался в том, что начальное состояние генератора псевдослучайных чисел основывалось на трех значениях: идентификаторе процесса, генерирующего ключ, идентификаторе его родительского процесса и текущем времени. Учитывая то, что значительную часть информации о номерах процессов и времени можно было предугадать, пространство возможных ключей сократилось с 2¹²⁸ до 2²⁰, и на поиск ключа шифрования уходило всего 25 секунд.

Следующий пример снова связан с шифрованием в архивах формата ZIP. Атака на основе известного открытого текста применима только в том случае, если фрагмент открытого текста доступен (например, когда несколько файлов зашифровано с одним паролем и один из файлов есть в расшифрованном виде). Однако выяснилось, что в некоторых случаях удается получить достаточный для проведения атаки объем открытого текста из вспомогательных структур, создаваемых архиватором.

Генератор псевдослучайных чисел в InfoZIP
Согласно спецификации ZIP, после загрузки ключа необходимо зашифровать 12 байт до того, как начать шифровать данные файла. Последний из этих 12 байт является младшим байтом контрольной суммы файла, которая хранится в заголовке архива в незашифрованном виде. Это позволяет определять неправильный пароль с вероятностью 55/г5б после расшифровки всего 12байт. Остальные байты обычно выбираются случайным образом.
Существует открытая реализация библиотеки для работы с архивами формата ZIP, называемая InfoZIP. В этой библиотеке из 12 дополнительных байт не один, а два последних байта содержат младшие байты контрольной суммы файла. Для генерации случайных байт используется алгоритм, идентичный rand () из стандартной библиотеки Microsoft Visual C++. Зная 4 байта выхода этого алгоритма, можно получить начальное состояние генератора и полностью предсказать его выход.
Псевдослучайные байты, полученные при помощи этого генератора, используются в InfoZIP таким образом, что для каждого файла в архиве генерируется 10 байт и один из них хранится в архиве в незашифрованном виде. Это позволяет при наличии в архиве пяти файлов, зашифрованных с одним паролем и подряд (без повторной инициализации генератора), найти начальное состояние генератора. А зная выход генератора и значения двух младших байт контрольной суммы для каждого из пяти файлов, можно определить ключ шифрования всех этих файлов менее чем за час.
Кстати, стоит отметить, что популярный архиватор WinZIP как раз основан на InfoZIP, а значит, созданные им архивы могут быть расшифрованы таким способом.

Последний пример связан с генерацией ключей RSA в программе, предназначенной для защиты других программ от несанкционированного тиражирования.

Ключи RSA-1024 в ASProtect
ASProtect представляет собой средство защиты программ от несанкционированного тиражирования, исследования и внесения изменений. Исполняемый файл при обработке его ASProtect зашифровывается и автоматически расшифровывается при загрузке в память. Но некоторые фрагменты, по желанию разработчика, могут оставаться зашифрованными до тех пор, пока не будет введен правильный регистрационный ключ.
Одна из возможностей, предоставляемых ASProtect, заключается в том, что разработчик генерирует пару ключей RSA-1024: открытый ключ хранится в программе, а секретный используется для генерации лицензий. Использование RSA-1024 обеспечивает невозможность генерации (и подделки) лицензий без знания секретного ключа.
По неподтвержденной информации, 1 января 2001 года Алексей Солодовников (автор ASProtect) получил от представителей группы DAMN по электронной почте генератор ключей к своей собственной программе. Примерно в это же время в Интернете были выложены генераторы лицензий еще к нескольким десяткам программ, защищенных ASProtect с использованием RSA-1024.
Взлом оказался возможен из-за того, что для генерации ключа RSA-1024 использовалась стандартная функция rand(), а начальное состояние генератора задавалось как:
(time(NDLL)   + GetCurrentThreadld())   Л GetTickCount{))
Похоже, в ASProtect использовалась некоторая криптографическая библиотека, в которой была функция  trueRandByte (), которая просто возвращала
(unsigned    char)rand().
В результате оказалось возможным подобрать ключ RSA-1024 ко многим программам. В настоящее время эта ошибка уже исправлена, и новые ключи не могут быть найдены подобным способом.

Далее приводятся алгоритмы (листинг 7.2), по которым функционируют некоторые широко используемые некриптографические генераторы псевдослучайных чисел. Коллекция собрана участниками форума www.reveKing.net

Листинг 7.2. Генераторы псевдослучайных чисел, входящие в стандартные библиотеки популярных языков программирования

static   unsigned   int   seed;

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