Я понимаю, как работают стандартные генераторы случайных чисел. Но при работе с криптографией случайные числа действительно должны быть случайными.
Я знаю, что есть инструменты, которые читают космический белый шум, чтобы помочь создать безопасные хэши, но на вашем стандартном ПК этого нет.
Как криптографически безопасный генератор случайных чисел получает свои значения без повторяющихся паттернов?
Криптографически безопасный генератор случайных чисел, как вы могли бы использовать для генерации ключей шифрования, работает путем сбора энтропии - то есть непредсказуемого ввода - из источника, который другие люди не могут наблюдать.
Например,/dev/random (4) в Linux собирает информацию об изменении времени аппаратных прерываний из таких источников, как жесткие диски, возвращающие данные, нажатия клавиш и входящие сетевые пакеты. Этот подход безопасен при условии, что ядро не переоценивает, сколько энтропии оно собрало. Несколько лет назад оценки энтропии из разных источников были уменьшены, что сделало их гораздо более консервативными. Здесь объяснение того, как Linux оценивает энтропию.
Ничто из перечисленного не является особенно высокой пропускной способностью. /dev/random (4), вероятно, безопасен, но он поддерживает эту безопасность, отказываясь выдавать данные, как только он не может быть уверен, что эти данные безопасно случайны. Если вы хотите, например, генерировать много криптографических ключей и nonces, тогда вы, вероятно, захотите обратиться к генераторам случайных чисел оборудования.
Часто аппаратные RNG предназначены для выборки из разницы между двумя генераторами, которые работают с близкой к одной и той же скорости, но скорости которых немного изменяются в зависимости от теплового шума. Если я правильно помню, генератор случайных чисел, который используется для лотереи премиальных облигаций Великобритании, ERNIE, работает таким образом.
Альтернативные схемы включают выборку шума на ПЗС (см. lavaRND), радиоактивный распад (см. hotbits) или атмосферный шум (см. random.org или просто подключите AM-радиостанцию где-то, кроме станции, в вашу звуковую карту). Или вы можете прямо спросить пользователя компьютера ударить по клавиатуре, как сумасшедший шимпанзе, в течение минуты, независимо от того, что плавает ваша лодка.
Извиняюсь за отсутствие встроенных ссылок, но, видимо, мне приходится записывать большую часть своей жизни на этом веб-сайте, прежде чем мне разрешат опубликовать больше.
РЕДАКТИРОВАТЬ: берите это. Поскольку некоторые люди были достаточно любезны в этой сумке с костями, чтобы щелкнуть ее вверх-вниз, я, видимо, позволил поместить остальные ссылки в настоящее время. Спасибо, добрые люди! ^ _ ^
EDIT: как указал andras, я думал только о некоторых наиболее распространенных схемах сбора энтропии. Ответ Томаса Порнина и Ответ Йоханнеса Рёсселя, оба делают хорошие задания, объясняя, как можно идти по мангровой совокупности энтропии в чтобы снова передать бит.
Для криптографических целей необходимо, чтобы поток был "вычислительно неотличим от равномерно случайных бит". "Вычислительно" означает, что он не должен быть действительно случайным, только для того, чтобы он казался кому-либо без доступа к Богу, собственному компьютеру.
На практике это означает, что система должна сначала собрать последовательность из 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, выход которого XORed с данными шифровать), документировать их и продвигать анализ криптографами. Портфель eSTREAM содержит семь проектов PRNG, которые считались достаточно безопасными (т.е. Они сопротивлялись анализу, а криптографы, как правило, хорошо понимали, почему они сопротивлялись). Среди них четыре "оптимизированы для программного обеспечения". Хорошей новостью является то, что, хотя эти новые PRNG кажутся намного более безопасными, чем RC4, они также заметно быстрее (речь идет о сотнях мегабайт в секунду, здесь). Три из них являются "бесплатными для любого использования" и предоставляется исходный код.
С точки зрения дизайна, PRNG повторно использует многие элементы блочных шифров. Используются те же концепции лавины и диффузии битов в широкое внутреннее состояние. В качестве альтернативы, достойный PRNG может быть построен из блочного шифра: просто используйте n-разрядную последовательность как ключ в блочном шифре и заширите последовательные значения счетчика (выраженные в виде последовательности m-бит, если блок-шифр использует m- бит). Это создает псевдослучайный поток битов, который является вычислительно неотличимым от случайного, до тех пор, пока блочный шифр является безопасным, а полученный поток не больше, чем m * 2 ^ (m/2) бит (при m = 128 это означает около 300 миллиардов гигабайт, что достаточно для большинства целей). Этот вид использования известен как режим счетчика (CTR).
Обычно блочный шифр в режиме CTR работает не так быстро, как выделенный потоковый шифр (точка шифрования потока заключается в том, что, теряя гибкость блочного шифра, ожидается более высокая производительность). Однако, если у вас есть один из новейших процессоров Intel с инструкциями AES-NI (которые в основном представляют собой реализацию AES в аппаратном обеспечении, интегрированный в CPU), то AES с режимом CTR даст непревзойденную скорость (несколько гигабайт в секунду).
Прежде всего, точка криптографически защищенного PRNG не должна генерировать совершенно непредсказуемые последовательности. Как вы заметили, отсутствие чего-то, что генерирует большие объемы (более или менее) истинной случайности 1 делает невозможным.
Итак, вы прибегаете к чему-то, что трудно предсказать. "Жесткий" означает здесь, что он длится долгое время, и в это время все, что было необходимо, было бы устаревшим в любом случае. Есть ряд математических алгоритмов, которые играют определенную роль в этом - вы можете получить представление, если вы возьмете некоторые известные CSPRNG и посмотрите, как они работают.
Наиболее распространенными вариантами построения такого PRNG являются:
Также иногда используются функции хеширования на счетчике. Википедия больше об этом.
Общие требования заключаются в том, что невозможно определить исходный вектор инициализации из потока бит генератора и что следующий бит не может быть легко предсказан.
Что касается инициализации, большинство CSPRNG используют различные источники, доступные в системе, начиная от действительно случайных вещей, таких как линейный шум, прерывания или другие события в системе, до других вещей, таких как определенные ячейки памяти, и c. Вектор инициализации предпочтительнее действительно случайный и не зависит от математического алгоритма. Эта инициализация в течение некоторого времени была нарушена при внедрении OpenSSL в Debian, что привело к серьезным проблемам безопасности.
1 У кого тоже есть свои проблемы, и нужно быть осторожным в устранении предвзятости, поскольку такие вещи, как тепловой шум, имеют разные характеристики в зависимости от температуры - у вас почти всегда есть предвзятость и необходимость его устранения. И это не тривиальная задача сама по себе.
Чтобы генератор случайных чисел считался криптографически защищенным, он должен быть защищен от нападения противника, который знает алгоритм и (большое) количество ранее сгенерированных бит. Это означает, что кто-то с этой информацией не может восстановить какое-либо скрытое внутреннее состояние генератора и дать предсказания о том, какие последующие разряды будут получены с точностью более 50%.
Генераторы обычных псевдослучайных чисел, как правило, не криптографически безопасны, так как восстановление внутреннего состояния из ранее выходных битов является общим тривиальным (часто все внутреннее состояние - это только последние N бит, создаваемые напрямую). Любой генератор случайных чисел без хороших статистических свойств также не криптографически защищен, так как его выход хотя бы предсказуем, даже не зная внутреннего состояния.
Итак, что касается того, как они работают, любая хорошая криптосистема может использоваться как криптографически безопасный генератор случайных чисел - использовать криптосистему для шифрования вывода "нормального" генератора случайных чисел. Так как противник не может восстановить вывод обычного текста генератора нормальных случайных чисел, он не может атаковать его напрямую. Это несколько круговое определение, которое задает вопрос о том, как вы заставляете криптосистему защищать ее, что представляет собой еще одну проблему.
Каждый генератор будет использовать свою собственную стратегию высева, но здесь немного от документация по API Windows на CryptGenRandom
С помощью Microsoft CSP CryptGenRandom использует одно и то же случайное число генератор, используемый другими компонентами безопасности. Это позволяет процессов для внесения вклада в общесистемное семя. CryptoAPI хранит промежуточное случайное семя с каждым пользователем. Чтобы сформировать семена для генератор случайных чисел, вызывающее приложение поставляет биты, которые он может имеют, например, ввод данных с клавиатуры или клавиатуры, которые затем в сочетании с сохраненными семенами и различными системными данными и пользователем такие данные, как идентификатор процесса и идентификатор потока, системные часы, системное время, системный счетчик, состояние памяти, кластеры свободного диска, хэшированный блок пользовательской среды. Этот результат используется для генератор псевдослучайных чисел (PRNG).
В Windows Vista с пакетом обновления 1 (SP1) и более поздних версий реализация PRNG на основе антирецептурного режима AES, указанного в NIST Используется специальная публикация 800-90. В Windows Vista, хранилище Windows Server 2003 и Windows XP, PRNG, указанный в Федеральной информации Стандарт обработки (FIPS) 186-2. Если приложение имеет доступ к хорошему случайному источнику, он может заполнить буфер pbBuffer некоторыми случайные данные перед вызовом CryptGenRandom. Затем CSP использует эти данные для дальнейшего рандомизации его внутреннего семени. Допускается опускать шаг инициализации буфера pbBuffer перед вызовом CryptGenRandom.