Вот несколько мыслей.Если вы нетерпеливы, переходите к заключению, в конце.
1.Что такое безопасное начальное число?
Безопасность определяется только относительно модели атаки.Здесь мы хотим получить последовательность из n битов, которая имеет n битов энтропии по отношению к атакующему: простыми словами, любой из возможных 2 n значения для этой последовательности одинаково вероятны с точки зрения атакующего.
Эта модель относится к информации , доступной атакующему.Приложение, которое генерирует и использует начальное число (обычно в PRNG), знает точное начальное число;является ли семя «безопасным», не является абсолютным свойством семени или даже процесса генерации семени.Важным является количество информации, которую злоумышленник имеет о процессе генерации.Этот уровень информации широко варьируется в зависимости от ситуации;например, в многопользовательской системе (скажем, Unix-подобной, с аппаратным разделением приложений) точная синхронизация обращений к памяти может показать информацию о том, как номинально защищенный процесс считывает память.Даже удаленный злоумышленник может получить такую информацию;это было продемонстрировано (в лабораторных условиях) для шифрования AES (в типичных реализациях AES используются внутренние таблицы с шаблонами доступа, зависящими от ключа; злоумышленник принудительно пропускает кэш и обнаруживает их с помощью точной синхронизации ответовсервер).
Необходимо учитывать время жизни семян.Семя безопасно, пока оно остается неизвестным для атакующего;это свойство должно оставаться верным впоследствии.В частности, не должно быть возможности восстановить начальное значение из выдержек из последующего вывода PRNG.В идеале, даже получение полного состояния PRNG в какой-то момент не должно давать никакой подсказки относительно того, какие биты PRNG производил заранее.
Смысл, который я хочу здесь подчеркнуть, состоит в том, что начальное число является «безопасным», только если оно используетсяв контексте, где он может оставаться защищенным, что более или менее подразумевает криптографически безопасный PRNG и некоторое защищенное от взлома хранилище.Если такое хранилище доступно, то наиболее безопасное начальное число - это то, которое было сгенерировано один раз , давным-давно, и использовалось в защищенном PRNG, размещенном на защищенном от несанкционированного доступа оборудовании.
К сожалению,такое оборудование дорогое (оно называется HSM и стоит несколько сотен или тысяч долларов), и эту стоимость обычно трудно оправдать (плохое начальное число не помешает работе системы; это обычная проблема непроверяемостибезопасность).Следовательно, принято использовать «в основном программные» решения.Поскольку программное обеспечение плохо подходит для обеспечения долгосрочного конфиденциального хранения, срок службы семени произвольно сокращается: периодически создается новое семя.В Fortuna такое повторное заполнение должно происходить как минимум один раз на каждый мегабайт сгенерированных псевдослучайных данных.
Подводя итог, можно сказать, что в установке без HSM безопасное начальное число - это то, чтоможет быть получено относительно легко (поскольку мы будем делать это довольно часто), используя данные, которые злоумышленник не может собрать.
2.Микширование
Случайные источники данных не дают хороших однородных битов (каждый бит имеет значение 1 с вероятностью точно 0,5 , а значения битов не зависят друг от друга).Вместо этого случайные источники производят значения в наборах, специфичных для источника.Эти значения могут быть закодированы как последовательности битов, но вы не получите своих денег: чтобы иметь n битов энтропии, вы должны иметь значения, которые при кодировании используют гораздо больше, чем n бит.
Используемый здесь криптографический инструмент - это PRF , который принимает ввод произвольной длины и выдает n -битный вывод.Криптографически защищенный PRF такого типа моделируется как случайный оракул : в краткосрочной перспективе вычислительно невозможно предсказать что-либо о выходе оракула на данном входе, не пытаясь его выполнить.
Прямо сейчас у нас есть хеш-функций . Хеш-функции должны выполнять несколько защитных свойств, а именно: устойчивость к прообразам, второстепенным изображениям и столкновениям. Обычно мы анализируем хеш-функции, пытаясь понять, как они отличаются от модели случайного оракула. Здесь есть важный момент: PRF, который следует модели случайного оракула, будет хорошей хеш-функцией, но могут быть хорошие хэш-функции (в смысле устойчивости к прообразам и столкновениям), которые, тем не менее, легко отличить от случайного оракула. , В частности, функции SHA-2 (SHA-256, SHA-512 ...) считаются безопасными, но отходят от модели случайного оракула из-за "атаки с расширением длины" (дано ч (м) , возможно вычислить ч (м || м ') для частично ограниченного сообщения м' , не зная м ). Атака с удлинением длины, по-видимому, не обеспечивает какой-либо возможности создания прообразов или столкновений, но показывает, что эти хэш-функции не являются случайными оракулами. Для участия в конкурсе SHA-3 NIST заявил, что кандидаты не должны допускать такого "увеличения длины".
Следовательно, этап смешивания не простой. Лучше всего по-прежнему прямо сейчас использовать SHA-256 или SHA-512 и переключиться на SHA-3, когда он выбран (это должно произойти примерно в середине 2012 года).
3. Источники
Компьютер является детерминированной машиной. Чтобы получить некоторую случайность, вы должны смешать в результате некоторые измерения физического мира.
Философское примечание: в какой-то момент вы должны доверять некоторым умным парням, которые могут носить лабораторные халаты или получать деньги за фундаментальные исследования. Когда вы используете хеш-функцию, такую как SHA-256, вы на самом деле доверяете кучке криптографов, когда они говорят вам: мы искали недостатки, очень серьезные и в течение нескольких лет, и не нашли ни одного. Когда вы используете распадающуюся часть радиоактивного вещества со счетчиком Гейгера, вы доверяете некоторым физикам, которые говорят: мы очень серьезно искали способы предсказать, когда сработает ядро следующего атома, но мы не нашли ни одного. Обратите внимание, что в данном конкретном случае к «физикам» относятся такие люди, как Беккерель, Резерфорд, Бор или Эйнштейн, а «очень усердно» означает «накопленные исследования более чем за столетие», так что вы находитесь не совсем на неисследованной территории. И все же в безопасности все еще есть немного веры.
Некоторые компьютеры уже включают аппаратное обеспечение, которое генерирует случайные данные (то есть, которое использует и измеряет физический процесс, который, насколько физик может сказать, является достаточно случайным). VIA C3 (линейка x86-совместимых процессоров) имеет такое оборудование. Как ни странно, Commodore 64, домашний компьютер 30-летней давности, также имел аппаратный RNG (или, по крайней мере, Wikipedia , по крайней мере).
За исключением специального оборудования, вы должны использовать любые физические события, которые вы можете получить. Как правило, вы будете использовать нажатия клавиш, входящие пакеты Ethernet, движения мыши, доступ к жесткому диску ... каждое событие приходит с некоторыми данными и происходит в измеримый момент (современные процессоры имеют очень точные часы благодаря счетчикам циклов). Эти моменты и содержимое данных события могут быть накоплены как источники энтропии. Это гораздо проще для самой операционной системы (которая имеет прямой доступ к аппаратному обеспечению), чем для приложений, поэтому обычный способ сбора начального числа - это запросить операционную систему (в Linux это называется /dev/random или /dev/urandom [у обоих есть свои преимущества и проблемы, выберите свой яд]; в Windows звоните CryptGenRandom()).
В крайнем случае это Java-апплеты до 1.2, до добавления java.security.SecureRandom; Поскольку Java очень эффективна для изоляции кода приложения от аппаратного обеспечения, получение случайного начального числа было сложной задачей. Обычное решение состояло в том, чтобы два или три потока работали одновременно и безумно переключались между потоками, чтобы число переключений потоков в секунду было несколько случайным (по сути, это пытается извлечь случайность посредством синхронизации действий планировщика ОС, которые зависят о том, что также происходит на машине, включая события, связанные с оборудованием). Это было довольно неудовлетворительно.
Проблема с временными мерами заключается в том, что злоумышленник также знает, какое сейчас время. Если злоумышленник имеет аппликативный доступ к машине, он также может прочитать счетчик циклов.
Некоторые люди предложили использовать звуковые карты в качестве источников "белого шума", установив усилитель на максимум (даже в настоящее время на серверах есть звук). Другие приводят доводы в пользу включения веб-камер (мы знаем, что видео с веб-камер «шумные», и это хорошо для случайности, даже если веб-камера направлена к стене); но серверы с веб-камерами не распространены. Вы также можете пропинговать внешний сетевой сервер (например, www.google.com) и посмотреть, сколько времени потребуется, чтобы вернуться (но это может заметить злоумышленник, следящий за сетью).
Прелесть шага смешения с хэш-функцией заключается в том, что энтропия может только накапливаться; добавление данных не повредит, даже если эти данные не случайны. Просто запишите как можно больше с помощью хэш-функции. Хэш-функции работают довольно быстро (хорошая реализация SHA-512 будет обрабатывать более 150 МБ / с на обычном ПК с использованием одного ядра), и заполнение происходит не так часто.
4. Заключение
Используйте HSM . Они стоят несколько сотен или тысяч долларов, но разве ваши секреты не стоят намного дороже? HSM включает в себя аппаратное обеспечение RNG, запускает алгоритм PRNG и сохраняет семена с защитой от взлома. Кроме того, большинство HSM уже сертифицированы в соответствии с различными национальными правилами (например, FIPS 140 в США и уровнями EAL в Европе).
Если вы настолько дешевы, что не купите HSM, или если вы хотите защитить данные, которые на самом деле не очень полезны, то создайте криптографически безопасный PRNG, используя начальное число, полученное хэшированием lot физических мер. Все, что исходит от некоторого оборудования, должно быть хешировано вместе с моментом (считайте «счетчик циклов»), в который были получены эти данные. Вы должны хешировать данные по мегабайту здесь. Или, что еще лучше, не делайте это: просто используйте возможности, предлагаемые вашей операционной системой, которая уже содержит такой код.