Как криптографически безопасный генератор случайных чисел работает?

Каждый генератор будет использовать свою собственную стратегию заполнения, но вот фрагмент из документации Windows API на CryptGenRandom

С Microsoft CSP CryptGenRandom использует тот же генератор случайных чисел , что и другие компоненты безопасности. . Это позволяет множеству процессов вносить вклад в общесистемное начальное число. CryptoAPI хранит промежуточное случайное начальное число для каждого пользователя. Чтобы сформировать начальное число для генератора случайных чисел , вызывающее приложение предоставляет биты, которые у него могут быть - например, ввод времени с помощью мыши или клавиатуры, - которые затем объединяются с обоими сохраненные начальные числа и различные системные данные и данные пользователя , такие как идентификатор процесса и идентификатор потока, системные часы, системное время, системный счетчик, состояние памяти, свободные кластеры дисков, {{1 }} хешированный блок пользовательской среды. Этот результат используется для заполнения генератора псевдослучайных чисел (ГПСЧ).

В Windows Vista с пакетом обновления 1 (SP1) и более поздних версий используется реализация ГПСЧ на основе режима счетчика AES, указанная в специальной публикации NIST 800-90. В Windows Vista, Windows Storage Server 2003 и Windows XP используется ГПСЧ, указанный в Федеральном стандарте обработки информации (FIPS) 186-2. Если приложение имеет доступ к хорошему случайному источнику, оно может заполнить буфер pbBuffer некоторыми случайными данными перед вызовом CryptGenRandom. Затем CSP использует эти данные для дальнейшей рандомизации своего внутреннего начального числа. Допустимо опустить этап инициализации буфера pbBuffer перед вызовом CryptGenRandom.

Прежде всего, цель криптографически защищенного ГПСЧ не в генерации совершенно непредсказуемых последовательностей. Как вы заметили, отсутствие чего-то, что генерирует большие объемы (более или менее) истинной случайности ¹ , делает это невозможным.

Итак, вы прибегаете к чему-то, что только трудно предсказать. «Жесткий» здесь означает, что это занимает невероятно много времени, и к тому времени все, для чего это было необходимо, в любом случае устареет. Есть ряд математических алгоритмов, которые играют в этом роль - вы можете получить представление, если возьмете несколько хорошо известных CSPRNG и посмотрите, как они работают.

Наиболее распространенными вариантами построения такого ГПСЧ являются:

• Использование потокового шифра, который уже выводит (предположительно безопасный) псевдослучайный поток битов.
• Использование блочного шифра в режиме счетчика

Также иногда используются хеш-функции счетчика. В Википедии есть больше об этом .

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

Что касается инициализации, большинство CSPRNG используют различные источники, доступные в системе, от действительно случайных вещей, таких как линейный шум, прерывания или другие события в системе, до других вещей, таких как определенные области памяти и т. Д. Вектор инициализации предпочтительно является действительно случайным и не зависит от математического алгоритма. Эта инициализация на некоторое время была нарушена в реализации OpenSSL в Debian, что привело к серьезным проблемам с безопасностью.

¹ Что тоже имеет свои проблемы, и нужно быть осторожным в устранении смещения, поскольку такие вещи, как тепловой шум, имеют разные характеристики в зависимости от температуры - у вас почти всегда есть смещение, и его необходимо устранить. И это само по себе нетривиальная задача.

Для криптографических целей необходимо, чтобы поток был «вычислительно неотличим от равномерно случайных битов». «Вычислительно» означает, что это не обязательно должно быть действительно случайным, только то, что оно кажется таковым любому, у кого нет доступа к собственному компьютеру Бога.

На практике это означает, что система должна сначала собрать последовательность из n истинно случайных битов. n должно быть достаточно большим, чтобы помешать исчерпывающему поиску, т.е. будет невозможно попробовать все 2 ^ n комбинации из n битов. Это достигается применительно к сегодняшним технологиям, пока n больше 90 или около того, но криптографы просто любят степени двойки, поэтому обычно используют n = 128 .

Эти n случайных битов получаются путем сбора «физических событий», которые должны быть непредсказуемыми с точки зрения физики. Обычно используется синхронизация: у ЦП есть счетчик циклов, который обновляется несколько миллиардов раз в секунду, и некоторые события происходят с неизбежным джиттером (входящие сетевые пакеты, движения мыши, нажатия клавиш ...). Система кодирует эти события, а затем «сжимает» их, применяя криптографически безопасную хеш-функцию, такую ​​как SHA-256 (вывод затем усекается, чтобы получить наши n бит).Здесь важно то, что кодирование физических событий имеет достаточную энтропию : грубо говоря, упомянутые события могли в совокупности предполагать по крайней мере 2 ^ n комбинаций. Хэш-функция, по своему определению, должна хорошо концентрировать эту энтропию в n -битной строке.

Когда у нас есть n бит, мы используем PRNG (генератор псевдослучайных чисел), чтобы получить столько битов, сколько необходимо. ГПСЧ называется криптографически безопасным, если, предполагая, что он работает с достаточно широким неизвестным n -битным ключом, его выход в вычислительном отношении неотличим от равномерно случайных битов. В 90-е годы популярным выбором был RC4 , который очень прост в реализации и довольно быстр. Однако оказалось, что у него есть измеримые погрешности, то есть он не был таким неотличимым, как изначально хотелось. Проект eSTREAM заключался в сборе новых конструкций для ГПСЧ (фактически потоковых шифров, потому что большинство потоковых шифров состоит из ГПСЧ, выходные данные которого объединяются с помощью XOR с данными для шифрования), их документирования и содействия анализу криптографами. Портфолио eSTREAM содержит семь проектов ГПСЧ, которые были признаны достаточно безопасными (т.е. они сопротивлялись анализу, а криптографы, как правило, хорошо понимали , почему они сопротивлялись). Среди них четыре «оптимизированы для программного обеспечения». Хорошая новость заключается в том, что, хотя эти новые ГПСЧ кажутся намного более безопасными, чем RC4, они также заметно быстрее (здесь мы говорим о сотнях мегабайт в секунду).Три из них «бесплатны для любого использования», и предоставляется исходный код.

С точки зрения дизайна, ГПСЧ повторно используют многие элементы блочных шифров. Используются те же концепции лавины и распространения долот в более широкое внутреннее состояние. В качестве альтернативы, достойный ГПСЧ может быть построен из блочного шифра: просто используйте n -битную последовательность в качестве ключа в блочном шифре и зашифруйте последовательные значения счетчика (выраженные как m ] -битовая последовательность, если блочный шифр использует m -битовых блоков). Это создает псевдослучайный поток битов, который в вычислительном отношении неотличим от случайного, пока блочный шифр безопасен, а размер создаваемого потока не превышает m * 2 ^ (m / 2) бит ( для m = 128 это означает около 300 миллиардов гигабайт, так что этого достаточно для большинства целей). Такой вид использования известен как режим счетчика (CTR) .

Обычно блочный шифр в режиме CTR не такой быстрый, как выделенный потоковый шифр (суть потокового шифра в том, что, теряя гибкость блочного шифра, ожидается лучшая производительность). Однако, если у вас есть один из самых последних ЦП от Intel с инструкциями AES-NI (которые в основном представляют собой аппаратную реализацию AES, интегрированную в ЦП), тогда AES с режимом CTR даст непревзойденная скорость (несколько гигабайт в секунду).

Для того чтобы генератор случайных чисел считался криптографически безопасным, он должен быть защищен от атаки противника, знающего алгоритм и (большое) количество ранее сгенерированных битов. Это означает, что человек, обладающий такой информацией, не сможет восстановить скрытое внутреннее состояние генератора и предсказать, какими будут следующие сгенерированные биты с точностью более 50%.

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

Итак, что касается того, как они работают, любая хорошая криптосистема может быть использована в качестве криптографически безопасного генератора случайных чисел - используйте криптосистему для шифрования выхода "обычного" генератора случайных чисел. Поскольку противник не может восстановить открытый текст на выходе обычного генератора случайных чисел, он не может атаковать его напрямую. Это несколько круговое определение, и возникает вопрос о том, как вы передаете ключ криптосистеме для обеспечения ее безопасности, что является совершенно другой проблемой.