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

Question

Я понимаю, как работают стандартные генераторы случайных чисел. Но при работе с криптографией случайные числа действительно должны быть случайными.

Я знаю, что есть инструменты, которые читают космический белый шум , чтобы помочь генерировать безопасные хэши, но на вашем стандартном ПК этого нет.

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

Answer 1

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

Например, / dev / random (4) в Linux собирает информацию о различиях во времени аппаратных прерываний из таких источников, как жесткие диски, возвращающие данные, нажатия клавиш и входящие сетевые пакеты. Этот подход безопасен при условии, что ядро ​​не переоценивает, сколько энтропии оно собрало. Несколько лет назад оценки энтропии из разных источников были уменьшены, что сделало их гораздо более консервативными. Вот объяснение того, как Linux оценивает энтропию .

Ничто из перечисленного не является особенно высокопроизводительным. / dev / random (4), вероятно, является безопасным, но он поддерживает эту безопасность, отказываясь выдавать данные, если не уверен, что эти данные надежно случайны. Если вы хотите, например, сгенерировать лот криптографических ключей и одноразовых номеров, то вам, вероятно, следует прибегнуть к аппаратным генераторам случайных чисел.

Часто аппаратные ГСЧ рассчитаны на выборку из разницы между парой осцилляторов, которые работают с почти одинаковой скоростью, но скорости которых слегка варьируются в зависимости от теплового шума. Если я правильно помню, генератор случайных чисел, который используется для лотереи премиальных облигаций Великобритании, ERNIE, работает таким образом.

Альтернативные схемы включают выборку шума на ПЗС (см. lavaRND ), радиоактивного распада (см. hotbits ) или атмосферного шума (см. random.org , или просто подключите AM-радио, настроенное где-то, кроме станции, к вашей звуковой карте). Или вы можете напрямую попросить пользователя компьютера стукнуть по клавиатуре, как невменяемый шимпанзе , на минуту, что бы ни плыло на вашей лодке.

Как указывал Андрас, я думал только о некоторых наиболее распространенных схемах сбора энтропии. ответ Томаса Порнина и ответ Йоханнеса Ресселя оба хорошо объясняют, как можно исказить накопленную энтропию, чтобы снова раздать ее кусочки.

Answer 2

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

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

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

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

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

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

Answer 3

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

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

Наиболее распространенные варианты построения такого PRNG:

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

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

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

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

---

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

Answer 4

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

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

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

Answer 5

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

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

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