CryptGenRandom

CryptGenRandom — функция криптографически стойкого генератора псевдослучайных чисел. Она включена в Microsoft’s Cryptographic Application Programming Interface. Microsoft рекомендует использовать её во всех Win32-программах, где требуется генерация случайных чисел. В 2007 году в работе из Еврейского университета были указаны проблемы в реализации CryptGenRandom под Windows 2000 (предполагая наличие доступа к машине у криптоаналитика). Позднее в Microsoft установили, что эти проблемы
также присутствуют и в Windows XP, а в Windows Vista их уже не наблюдалось. Эти ошибки были исправлены с выходом Windows XP Service Pack 3 в середине 2008 года.

Предпосылки 
Win32 API полностью поддерживает методы защиты от криптографических атак, включая TLS и цифровую подпись. Эта поддержка основана на родных для Windows библиотеках для решения таких криптографических задач, как генерация ключей для алгоритмов RSA или AES. Эти библиотеки используют криптографически стойкий генератор псевдослучайных чисел. CryptGenRandom является стандартным генератором подобного рода для среды разработки под Win32.

Алгоритм 
Microsoft используют одну реализацию CryptGenRandom, основанную на некоторой встроенной функции «RtlGenRandom». В 2007 годы был обнародован лишь общий набросок работы этого алгоритма:

[RtlGenRandom] работает, как указано в FIPS 186-2, приложение 3.1, используя SHA-1 в качестве G-функции. Источниками для энтропии являются:
 ID текущего процесса.
 ID текущей нити исполнения.
 Число тактов с момента последней загрузки.
 Текущее время.
 Различные высокоточные счётчики.
 Хеш-функции MD4 от персональных данных пользователя, таких как логин, имя компьютера, и др.
 Высокоточные внутрипроцессорные счётчики, такие, как RDTSC, RDMSR, RDPMC.
[опущено: длинный список низкоуровневых информационных элементов и счётчиков]
Источник:

Безопасность 
Криптографическая устойчивость генераторов случайных чисел очень важна, поскольку такие генераторы напрямую участвуют в создании динамических ключей. Ключи, потребность в которых возникает «на лету» (например, сеансовые ключи AES TLS для защиты HTTPS сессий на банковских сайтах), также вычисляются с помощью этих генераторов. Таким образом предсказуемость поведения генераторов напрямую позволяет предсказывать значения создаваемых ключей. Поскольку CryptGenRandom является, по факту, стандартным генератором в среде Win32, то его защищенность критически важна для пользователей Windows.

Особенности алгоритма CryptGenRandom официально не опубликованы. Как и любой неопубликованный алгоритм генерации случайных чисел, CryptGenRandom может быть теоретически уязвим из-за использования устаревших алгоритмов или, например, использования нескольких монотонных счётчиков для подсчета энтропии, которые могут быть использованы криптоаналитиком при наличии доступа к системе.

Криптоанализ (Еврейский университет) 
В 2007 году Leo Dorrendorf совместно с группой учёных из Еврейского университета и Хайфского университета опубликовал результаты криптоанализа CryptGenRandom, выявив значительные уязвимости в реализации алгоритма под Windows 2000.

Для того, чтобы воспользоваться этими уязвимостями, злоумышленнику необходимо подвергнуть опасности запущенную программу, которая использует этот генератор случайных чисел. Все недостатки CryptGenRandom зависят от сифонирования битов состояний генератора. Если злоумышленник в состоянии выполнить эту атаку, то с большой долей вероятности он может сломать любой генератор случайных чисел (например, он может просто повторять выходные значения генератора или исправлять их непосредственно в памяти на уже известные величины). Тем не менее учёные из Еврейского университета установили, что криптоаналитику необходимо всего лишь один раз узнать биты состояний для того, чтобы нанести серьёзный удар по безопасности CryptGenRandom. После этого злоумышленник может использовать информацию о битах состояний для получения чисел, сгенерированных алгоритмом во время предыдущих запусков, и тем самым получить доступ к потенциально важной информации, например, к уже отправленным номерам кредитных карт. Это возможно в связи с тем, что CryptGenRandom использует потоковый шифр RC4, который является обратимым в случае хотя бы одного известного состояния. Было замечено, что CryptGenRandom работает в пользовательском режиме, что позволяет любому, кто имеет доступ к операционной системе на пользовательском уровне, получить информацию о состоянии CryptGenRandom для этого процесса, например, используя переполнение буфера. Наконец, CryptGenRandom довольно редко обновляет источники для вычисления энтропии. Проблема усугубляется тем фактом, что каждый Win32-процесс имеет свой собственный экземпляр состояний CryptGenRandom. Такая независимость процессов только увеличивает время несанкционированного использования системы после успешного взлома. Анализ группы учёных под руководством Dorrendorf’а по сути является первой опубликованной работой о функционировании криптостойкого генератора случайных чисел под Windows.

Common Criteria 
Windows 2000, XP и Windows 2003, включая реализации CryptGenRandom() и FIPSGenRandom(), успешно прошли тесты EAL4+. Проверка безопасности алгоритмов выявила полное соответствие требуемым нормам EAL4, документация доступна на портале Common Criteria. Отсюда можно сделать вывод о том, что зарекомендовавшая себя система поверки EAL4 работает хорошо в большинстве случаев, но не включает в себя более глубокий криптоанализ.

FIPS-проверки 
Следующие реализации генераторов случайных чисел Microsoft были успешно протестированы:
Windows Vista (сертификат 321)
Windows 2003 Enhanced Cryptographic Provider (rsaenh.dll) (сертификат 316)
Windows 2003 Enhanced DSS and Diffie-Hellman Cryptographic Provider (dssenh.dll) (сертификат 314)
Windows 2003 Kernel Mode Cryptographic Module (fips.sys) (сертификат 313)
Windows CE and Windows Mobile Enhanced Cryptographic Provider (rsaenh.dll) (сертификат 292)
Windows CE and Windows Mobile Enhanced Cryptographic Provider (rsaenh.dll) (сертификат 286)
Windows CE Enhanced Cryptographic Provider (rsaenh.dll) (сертификат 66)

Эти тесты «предназначены для проверки соответствия различным утвержденным спецификациям генераторов случайных чисел, а не для оценки уровня безопасности продукции. […] Таким образом, проверка не должна быть истолкована как оценка или одобрение общей безопасности продукции». Отсюда можно сделать выводы о том, что такие проверки могут обходить стороной некоторые особенности генераторов случайных чисел (например, используемые группой учёных из Еврейского университета).

Исходный код 
Существует целый ряд утилит для получения доступа к исходному коду программ компании Microsoft (обычно защищены EULA), но невозможно поделиться этим самым кодом с общественностью.

Разборка (Disassembly) 
Библиотеки для платформ Windows можно разобрать с помощью таких инструментов, как IDA Pro и objdump. Кроме того, в отличие от большинства поставщиков программ с закрытым исходным кодом, Microsoft предоставляет отладочные символы для своих бинарных файлов. В результате эти файлы часто оценивают сторонние практики. Упомянутая выше атака Dorrendorf’а базировалась именно на таких разборках.

Альтернативные средства

API-уровень 
Разработчики Windows имеют несколько альтернативных средств доступа к функциям CryptGenRandom. Эти варианты вызывают тот же алгоритм, имеют тот же уровень безопасности, но, возможно, имеют и другие преимущества.

Использование RtlGenRandom 
«Исторически, мы всегда говорили разработчикам не использовать такие функции, как rand(), для генерации ключей и паролей. Гораздо лучше использовать функции вроде CryptGenRandom, которые являются криптографически устойчивыми генераторами случайных чисел. Проблема с использованием именно CryptGenRandom связана с необходимостью подключения CryptoAPI (CryptAcquireContext и подобные), что, впрочем, приемлемо, если другие функции из CryptoAPI вами уже используются. По умолчанию в Windows XP CryptGenRandom вызывает функцию ADVAPI32!RtlGenRandom, которая не требует подключения всего набора CryptAPI. На самом деле новая функция Whidbey CRT rand_s() вызывает RtlGenRandom.

Использование RNGCryptoServiceProvider 
Программисты, пользующиеся .Net, должны использовать класс RNGCryptoServiceProvider.

Языки программирования 
 рекомендуется использовать функцию rand_s из библиотеки Microsoft C++ (основана на RtlGenRandom).
 функция os.urandom() языка Python в операционных системах Windows вызывает CryptGenRandom.

См. также 
 Криптографически стойкий генератор псевдослучайных чисел
 Атака на ГПСЧ
 CryptoAPI

Примечания

Ссылки 
 Microsoft documentation for CryptGenRandom
 Cryptographically Secure Random number on Windows without using CryptoAPI
 Overview of Windows 2000 Common Criterion evaluation
 Microsoft Shared Source licensing programs
 Microsoft FIPS 140 evaluations

Генераторы псевдослучайных чисел
Криптографически стойкие генераторы псевдослучайных чисел
Программные интерфейсы Microsoft
Технологии безопасности Microsoft Windows