Тестирование и проверка реализаций RNG

Проверка генераторов случайных чисел сталкивается с фундаментальной проблемой: действительно случайные последовательности и псевдослучайные последовательности, созданные хорошим PRNG, выглядят одинаково для статистических проверок. Никакая проверка последовательности конечной длины не может доказать, что последовательность случайна, — статистика способна лишь обнаружить неслучайность с определённой степенью уверенности. Проверка позволяет убедиться, что RNG не содержит очевидных смещений или закономерностей, но не может доказать криптографическую безопасность. Проверка криптографических RNG преследует две разные цели: (1) статистическое качество — проверка того, что распределение выходных данных выглядит равномерным и независимым; (2) криптографическая стойкость — проверка правильности реализации алгоритма DRBG и выполнения заявленных требований безопасности. Для этого нужны разные подходы к проверке.

NIST SP 800-22 содержит 15 статистических проверок для оценки битовых последовательностей. В их число входят: проверка частоты (однобитовая) — доля единиц должна быть близка к 0,5; проверка частоты блоков — частота единиц в каждом блоке длиной m бит; проверка серий — количество непрерывных серий одинаковых битов; проверка самой длинной серии — длина самой длинной серии единиц; проверка ранга двоичной матрицы — ранг двоичных матриц, сформированных из последовательности; спектральная проверка (DFT) — обнаружение периодических закономерностей; проверка совпадения перекрывающихся шаблонов — подсчёт вхождений определённых шаблонов; универсальная статистическая проверка Маурера — сжатие последовательности и измерение степени её сжатия. Каждая проверка выдаёт значение p; значение p < 0,01 указывает на неслучайность. Проверки выполняются на последовательностях длиной от 1 миллиона до 1 миллиарда битов.

TestU01 (Л’Экюе и Симар, 2007) — это комплексный набор статистических проверок, широко используемый сообществом специалистов по RNG. SmallCrush: 10 проверок, около 35 секунд, подходит для быстрых проверок. Crush: 144 проверки, около 2 часов. BigCrush: 160 проверок, около 24 часов. Проверки BigCrush выявляют тонкие корреляции, которые не обнаруживает NIST SP 800-22. Хорошо спроектированные криптографические DRBG (HMAC_DRBG, CTR_DRBG) без труда проходят BigCrush — для алгоритмов полиномиального времени их выходные данные вычислительно неотличимы от случайных. Некриптографические PRNG (вихрь Мерсенна, линейные конгруэнтные генераторы) не проходят некоторые проверки BigCrush. Провал проверки BigCrush — серьёзный признак того, что RNG не следует использовать в криптографических целях.

SP 800-90B и 90A определяют проверки работоспособности, которые DRBG должны непрерывно выполнять во время работы. Непрерывная проверка RNG (CRNGT): каждый сгенерированный блок сравнивается с предыдущим; если блоки совпадают (RNG зафиксирован на одном значении), DRBG должен перейти в состояние ошибки и прекратить генерацию. Проверка числа повторений: если одно и то же значение в последовательных выборках повторяется чаще, чем это статистически ожидаемо с учётом оценки энтропии, проверка завершается неуспешно. Проверка адаптивной доли: если наиболее часто встречающееся значение появляется в окне больше порогового числа раз, проверка завершается неуспешно. Эти проверки работоспособности обнаруживают сбои источника энтропии (зафиксировавшийся датчик, аппаратную неисправность HWRNG) до того, как они незаметно нарушат формирование криптографических ключей.

PractRand — современный инструмент проверки RNG, предназначенный для потоковой оценки: он анализирует последовательность по мере её генерации, а не требует заранее заданной длины. Он применяет проверки промежутков, распределения битов и спектральные проверки с адаптивной точностью. PractRand особенно хорошо обнаруживает RNG, которые создают хорошие короткие последовательности, но выявляют закономерности после генерации миллиардов битов. Криптографические DRBG создают выходные данные, которые PractRand не может отличить от случайных независимо от длины последовательности, — это практическое определение вычислительной неотличимости. PractRand также используют для оценки источников энтропии: например, для проверки выходных данных /dev/urandom и RDRAND с целью обнаружения аппаратных неисправностей или систематических смещений.

Программа проверки криптографических алгоритмов (CAVP) предоставляет официальные проверочные векторы для DRBG из SP 800-90A. Проверка CAVP включает передачу реализации в автоматизированную систему проверок NIST вместе с векторами проверки известного ответа (KAT): получив заданные входные данные энтропии, одноразовое значение, строку персонализации и дополнительные входные данные, реализация должна выдать точно ожидаемые выходные биты. CAVP не проверяет статистические свойства — она проверяет алгоритмическую корректность. Для сертификации FIPS 140-3 требуется проверка CAVP всех криптографических алгоритмов, используемых в пределах границы модуля. Проверочные векторы CAVP доступны всем на сервере ACVP (автоматизированного протокола проверки криптографии) NIST и интегрированы в наборы проверок OpenSSL, mbedTLS и BoringSSL.

Прежде чем DRBG можно будет безопасно инициализировать, источник энтропии должен пройти проверку. SP 800-90B определяет: (1) оценку энтропии — измерение фактической энтропии на бит с помощью статистических проверок (оценка минимальной энтропии); (2) проверки при запуске — проверку того, что источник энтропии выдаёт корректные данные до первого использования; (3) проверки по запросу — необязательные проверки, запускаемые приложением; (4) проверки работоспособности источника шума — обнаружение ухудшения состояния оборудования. Распространённые источники энтропии и их оценочная энтропия на бит: CPU RDRAND/RDSEED (примерно 1 бит/бит, аппаратно сертифицированы); /dev/urandom (смешивает несколько источников, оценка энтропии консервативна); кольцевой генератор TRNG (0,5–0,9 бит/бит в зависимости от конструкции); шум ADC (0,1–0,5 бит/бит). Для проверки по SP 800-90B требуется лабораторная проверка с использованием специализированного оборудования.

Виртуальные среды создают особые сложности при тестировании RNG. VM могут сталкиваться с низкой энтропией при запуске (при отсутствии аппаратных событий) или после восстановления снимка (состояние сбрасывается). Контейнеры Docker используют RNG ядра хоста совместно — контейнер не может напрямую проверить качество лежащей в его основе энтропии. Тесты для развёртываний в VM: (1) Измеряйте время до завершения чтения из /dev/random — длительное ожидание указывает на недостаточную энтропию. (2) Проверяйте наличие дублирующихся UUID или ключей, сгенерированных параллельно в экземплярах VM (это реальный режим отказа, задокументированный для облачных развёртываний). (3) Убедитесь, что в VM загружен VIRTIO-RNG (virtio_rng.ko) — он обеспечивает передачу энтропии от хоста к гостевой системе. (4) Проведите аудит последовательности запуска приложения: не происходит ли генерация ключей до появления достаточного объёма энтропии?

Тестирование безопасности RNG при разветвлении процессов предотвращает уязвимость, которую трудно заметить: когда процесс разветвляется, родительский и дочерний процессы используют одно и то же состояние DRBG, из-за чего генерируют идентичные последовательности. Для обнаружения запустите N дочерних процессов, сгенерируйте UUID в каждом и убедитесь, что все UUID уникальны. Если какие-либо два совпадают, RNG не защищён от разветвления процессов. OpenSSL исправила ошибку безопасности при разветвлении процессов в 2020 году (CVE-2020-1971 напрямую не касалась DRBG, но характер проблемы был похожим). В текущей версии OpenSSL используется обновление начального значения на основе PID: если PID изменился после последнего вызова (что указывает на разветвление процесса), для DRBG автоматически выполняется пересев. Чтобы проверить это, выполните тест до и после разветвления, а затем подтвердите, что пересев произошёл, проверив различие результатов.

Практический контрольный список для аудита реализаций RNG: (1) Инициализируется ли RNG из OS (getrandom, BCryptGenRandom), а не начальными значениями на основе времени? (2) Является ли тип DRBG механизмом, одобренным NIST SP 800-90A (хеширование, HMAC, CTR)? (3) Достаточна ли длина начального значения для заявленного уровня безопасности? (4) Инициируется ли пересев периодически или после фиксированного числа вызовов генерации? (5) Обрабатывает ли реализация безопасность при разветвлении процессов (выполняет ли пересев после разветвления)? (6) Включены ли проверки работоспособности и останавливают ли они систему при сбое? (7) Обнуляется ли состояние при завершении работы? (8) Выполняются ли в CI/CD тесты с известными ответами и тестовые векторы CAVP? (9) Документируются ли оценки энтропии и подтверждаются ли они проверкой? (10) Для требований FIPS: сертифицирован ли модуль по FIPS 140-3?

Исторические сбои RNG показывают, насколько серьёзными могут быть последствия. Debian OpenSSL (2006–2008): исправление случайно удалило две строки кода сбора энтропии, уменьшив пул начальных значений до пространства PID размером 15 бит — для всей пользовательской базы Debian было создано всего 32 767 возможных ключей SSH. Все ключи хостов SSH и пользовательские ключи, созданные Debian, пришлось заменить. Кошельки Bitcoin на Android (2013): SecureRandom в Android использовал засевание на уровне Java, которое на некоторых устройствах не работало, из-за чего в подписях ECDSA появлялись повторяющиеся значения k — это напрямую раскрывало закрытые ключи. Sony PS3 (2010): в подписях прошивки ECDSA использовала постоянное одноразовое значение, что позволяло извлечь закрытый ключ из двух подписей (одинаковое k в разных сообщениях раскрывает ключ с помощью простой алгебры).

Статистические тесты (NIST SP 800-22, TestU01 BigCrush, PractRand) проверяют качество вывода, но не могут доказать криптографическую безопасность. Тесты с известными ответами CAVP проверяют алгоритмическую корректность реализаций SP 800-90A. Тесты источника энтропии SP 800-90B (оценка минимальной энтропии, проверки работоспособности) проверяют входные данные для начального заполнения. Непрерывный тест RNG (CRNGT) обнаруживает застывший вывод в реальном времени. Для развёртываний в VM и контейнерах необходимы передача энтропии (VIRTIO-RNG) и проверки энтропии при запуске. Тестирование безопасности при разветвлении процессов проверяет, что дочерние процессы не наследуют состояние DRBG родителя. Реальные сбои (Debian, Android) показывают, что ошибки RNG напрямую приводят к компрометации криптографических ключей. Контрольные списки аудита формализуют эти проверки для развёртываний в рабочей среде.