Генератор "случайных" чисел Windows XP далек от случайности

Лео Доррендорф (Leo Dorrendorf), Цви Гуттерман (Zvi Gutterman) из Еврейского университета в Иерусалиме, и Бенни Пинкас (Вenny Pinkas) из университета Хайфы исследовали генератор псевдослучайных чисел операционной системы Windows 2000. Ученым удалось без помощи со стороны Microsoft восстановить бинарный код PRNG (около 10 тыс. строк ассемблерного кода) и изучить его алгоритм (исполняемый через вызов функции CryptGenRandom) на предмет наличия уязвимостей.

Генераторы случайных чисел дороги, так как физические источники действительно случайных данных труднодоступны. Поэтому в операционных системах, как правило, задействованы генераторы псевдослучайных чисел (Pseudorandom Number Generator, PRNG). PRNG - это алгоритмы, преобразующие наборы битов в определенные последовательности, причем одинаковые наборы на входе будут давать одни и те же последовательности на выходе.

В качестве источника стартовых наборов битов PRNG используют "пул энтропии" - данные, получаемые от физических процессов, происходящих в системе. Например, это могут быть данные о дисковых операциях и нажатии клавиш пользователем. Кроме "пула энтропии" в WRNG (PRNG Windows) используется потоковый шифр RC4 и хэш-функция SHA-1.

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

Каждый процесс в системе задействует отдельную копию генератора, а генерация "энтропии" WRNG происходит только после выдачи 128 Кбайт данных. Это значит, что обновление генератора для некоторых процессов в системе происходит очень редко. Используемый потоковый шифр RC4 имеет высокую производительность, но не защищает от атаки, нацеленной на вычисление предыдущих результатов.

В результате вычислительная сложность атаки на WRNG невелика. Для определения предыдущих результатов она составляет O(2²³), а последующих - O(1).

Windows Vista, Server 2003 SP2 и Server 2008 не имеют описанной уязвимости PRNG. В Microsoft планируют устранить ошибку ХР, выпустив специальное обновление еще до выхода Windows XP Service Pack 3.