Как работает криптографически безопасный генератор случайных чисел?
Я понимаю, как работают стандартные генераторы случайных чисел. Но при работе с crytpography, случайные числа действительно должны быть случайными.
Я знаю, что есть инструменты, которые читают космический белый шум чтобы помочь создать безопасные хэши, но ваш стандартный компьютер не имеет этого.
Как криптографически безопасный генератор случайных чисел получить его значения не повторяются?
5 ответов:
например, /dev / random (4) в Linux собирает информацию об изменении времени аппаратных прерываний из таких источников, как жесткие диски, возвращающие данные, нажатия клавиш и входящие сетевые пакеты. Этот подход является безопасным при условии, что ядро не переоценивайте, сколько энтропии он собрал. Несколько лет назад оценки энтропии из различных источников были все уменьшены, что делает их гораздо более консервативными. Вот это объяснение того, как Linux оценивает энтропию.
ни один из вышеперечисленных является особенно высокой пропускной способностью. /dev / random (4) вероятно, безопасен, но он поддерживает эту безопасность, отказываясь выдавать данные, как только он не может быть уверен, что эти данные надежно случайны. Если вы хотите, например, сгенерируйте много криптографических ключей и nonces, то вы, вероятно, захотите прибегнуть к аппаратным генераторам случайных чисел.
часто аппаратные ГСЧ предназначены для выборки из разности между парой генераторов, которые работают с близкой к той же скорости, но чьи скорости слегка варьируются в зависимости от теплового шума. Если я правильно помню, генератор случайных чисел, который используется для лотереи премиальных облигаций Великобритании, Эрни, работает так путь.
альтернативные схемы включают выборку шума на ПЗС-матрице (см. lavaRND), радиоактивного распада (см. hotbits) или атмосферный шум (см. random.org, или просто подключите AM-радио, настроенное где-то кроме станции, к вашей звуковой карте). Или вы можете напрямую попросить пользователя компьютера стучать по клавиатуре, как сумасшедший шимпанзе на минуту, что плывет лодка.
приносим извинения за отсутствие встроенные ссылки, но, по-видимому, я должен записать больше своей жизни на этом веб-сайте, прежде чем мне разрешат публиковать больше.
изменить: отставить. Поскольку некоторые люди были достаточно добры к этому мешку с костями, чтобы щелкнуть эту заостренную вещь слева, мне, по-видимому, разрешено поместить остальные ссылки. Спасибо вам добрые люди! ^_^
EDIT: как отметил Андрас, я только думал поговорить о некоторых из наиболее распространенных схем сбора энтропии. Томас Порнин ответ и ответ Йоханнеса Ресселя оба делают хорошую работу по объяснению того, как можно исказить собранную энтропию, чтобы снова передать ее кусочки.
для криптографических целей необходимо, чтобы поток был "вычислительно неотличим от равномерно случайных битов". "Вычислительно" означает, что он не должен быть действительно случайным, только то, что он кажется таковым любому, кто не имеет доступа к собственному компьютеру Бога.
на практике это означает, что система сначала должна собрать последовательность 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 делает это невозможным.
Итак, вы прибегаете к чему-то, что только hard предсказать. "Трудно" здесь означает, что это занимает неизмеримо много времени, к тому времени все, что было необходимо, в любом случае устарело бы. Там есть ряд математических алгоритмов, которые играют определенную роль в этом-вы можете получить представление, если вы возьмете некоторые известные CSPRNGs и посмотрите, как они работают.
наиболее распространенными вариантами построения такого PRNG являются:
- используя потоковый шифр, который уже выводит (предположительно безопасный) псевдослучайный битовый поток.
- использование блочного шифра в режиме счетчика
хэш-функции на счетчике также иногда используются. В Википедии есть подробнее об этом.
общие требования заключаются в том, что невозможно определить исходный вектор инициализации из битового потока генератора и что следующий бит не может быть легко предсказан.
Что касается инициализации, большинство CSPRNGs используют различные источники, доступные в системе, начиная от действительно случайных вещей, таких как шум линии, прерывания или другие события в системе до других вещей, таких как определенные места памяти и т. д. вектор инициализации предпочтительно действительно случайный и не зависящий от математического алгоритма. Эта инициализация была нарушена в течение некоторого времени в реализации OpenSSL Debian, что привело к серьезным проблемам безопасности.
1 у которого тоже есть свои проблемы, и нужно быть осторожным в устранении смещения, поскольку такие вещи, как тепловой шум, имеют разные характеристики в зависимости от температуры-у вас почти всегда есть смещение и нужно его устранить. И это не тривиальная задача в себя.
для того, чтобы генератор случайных чисел следует считать криптографически защищенного, in должен быть защищен от атаки противника, который знает алгоритм и (большое) количество ранее сгенерированных битов. Это означает, что кто-то с этой информацией не может восстановить какое-либо скрытое внутреннее состояние генератора и дать предсказания о том, какие следующие биты будут получены с точностью более 50%.
нормальное псевдослучайное число генераторы, как правило, не являются криптографически безопасными, так как восстановление внутреннего состояния из ранее выведенных битов обычно тривиально (часто все внутреннее состояние-это только последние n бит, полученные непосредственно). Любой генератор случайных чисел без хороших статистических свойств также не является криптографически безопасным, так как его выход, по крайней мере, предсказуем даже без знания внутреннего состояния.
Итак, что касается того, как они работают, любая хорошая криптосистема может быть использована в качестве криптографически безопасный генератор случайных чисел-используйте криптосистему для шифрования вывода "нормального" генератора случайных чисел. Так как противник не может восстановить открытый текстовый вывод обычного генератора случайных чисел, он не может атаковать его напрямую. Это несколько круговое определение напрашивается вопрос о том, как вы вводите криптосистему, чтобы сохранить ее в безопасности, что является целой другой проблемой.
каждый генератор будет использовать свою собственную стратегию посева, но вот немного от документация Windows API по CryptGenRandom
в Microsoft CSPs CryptGenRandom используется одно и то же случайное число генератор используется другими компонентами безопасности. Это позволяет многочисленным процессы для внесения вклада в общесистемное семя. Магазины интерфейса CryptoAPI в промежуточное случайное семя с каждым пользователем. Чтобы сформировать семя для генератор случайных чисел, вызывающее приложение поставляет биты он мог бы есть-например, мышь или клавиатура ввода времени-которые затем совмещенный как с сохраненным семенем, так и с различными системными данными и потребителем данные, такие как идентификатор процесса и идентификатор потока, системные часы, системное время, системный счетчик, состояние памяти, свободные кластеры дисков, блок хэшированной пользовательской среды. Этот результат используется для посева генератор псевдослучайных чисел (ГПСЧ).
в Windows Vista с пакетом обновления 1 (SP1) и более поздними версиями реализация режима счетчика AES на основе PRNG, указанного в NIST Используется специальная публикация 800-90. В Windows Vista, Хранилище Windows Сервер 2003 и Windows XP, PRNG, указанный в Федеральной информации Используется стандарт обработки (FIPS) 186-2. Если приложение имеет доступ к хорошему случайному источнику, он может заполнить буфер pbBuffer с некоторым случайные данные перед вызовом CryptGenRandom. Затем CSP использует эти данные чтобы еще больше рандомизировать его внутреннее семя. Допустимо опустить этот шаг инициализации буфера pbBuffer перед вызовом CryptGenRandom.
Comments