Фортуна (ГПСЧ) - Fortuna (PRNG)

Фортуна это криптографически безопасный генератор псевдослучайных чисел (PRNG) разработан Брюс Шнайер и Нильс Фергюсон и издана в 2003 году. Названа в честь Фортуна, римская богиня случая. FreeBSD использует Fortuna для / dev / случайный и / dev / urandom символически связан с ним, начиная с FreeBSD 11.[1] Операционные системы Apple перешли на Fortuna с первого квартала 2020 года.[2]

дизайн

Фортуна - это семья безопасных ГПСЧ; его конструкция оставляет некоторые возможности выбора для разработчиков. Он состоит из следующих частей:

  • Сам генератор, который когда-то засеянный создаст неопределенное количество псевдослучайных данных.
  • В энтропия аккумулятор, который собирает действительно случайные данные из различных источников и использует их для повторного заполнения генератора, когда поступает достаточно новой случайности.
  • Начальный файл, в котором хранится достаточно состояния, чтобы компьютер мог начать генерировать случайные числа сразу после загрузки.

Генератор

Генератор основан на любом хорошем блочный шифр. Практическая криптография предлагает AES, Змея или Twofish. Основная идея - запустить шифр в режим счетчика, зашифровывая последовательные значения увеличивающегося счетчика.

С 128-битным блочным шифром это приведет к статистически идентифицируемым отклонениям от случайности; например, генерируя 264 действительно случайные 128-битные блоки будут давать в среднем около одной пары идентичных блоков, но среди первых двух нет никаких повторяющихся блоков.128 производится 128-битным шифром в режиме счетчика. Поэтому ключ меняется периодически: не более 1 МиБ данных (216 128-битные блоки) генерируется без смены ключа. В книге отмечается, что блочные шифры с размером блока 256 бит (или больше), которые в то время не пользовались большой популярностью, не имеют этой статистической проблемы.

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

Аккумулятор энтропии

Накопитель энтропии спроектирован таким образом, чтобы быть устойчивым к атакам "инъекций", без необходимости использования сложных (и неизбежно ненадежных) оценок энтропии. Есть несколько «бассейнов» энтропии; каждый источник энтропии равномерно распределяет предполагаемую энтропию по пулам; и (вот ключевая идея) на пзасев генератора, пула k используется только если п делится на 2k. Таким образом kый бассейн используется только 1/2k времени. Другими словами, пулы с более высокими номерами (1) реже вносят вклад в повторные посевы, но (2) собирают большее количество энтропии между повторными посевами. Повторное заполнение выполняется путем хеширования указанных пулов энтропии в ключ блочного шифра с использованием двух итераций SHA-256.

Посев

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

Этот вывод зависит от наличия достаточного количества пулов. Fortuna использует 32 пула и ограничивает повторное заполнение не более 10 раз в секунду. Тогда исчерпание пулов займет около 13 лет, что Фергюсон и Шнайер считают достаточно долгим для практических целей. Более параноидальные разработчики или разработчики, требующие генерации случайных данных с колоссальной скоростью и, соответственно, частого повторного заполнения, могут использовать большее количество пулов.

Альтернативы

Фортуна отличается от более ранней Алгоритм тысячелистника семья Шнайера, Келси и Фергюсона в основном занимается накоплением энтропии. Ярроу требовал, чтобы каждый источник энтропии сопровождался механизмом оценки фактической поставляемой энтропии, и использовал только два пула; и его предлагаемый вариант (называемый Тысячелистник-160) используемый SHA-1 вместо повторения SHA-256.

Анализ

Анализ и предлагаемое усовершенствование Fortuna были сделаны в 2014 году.[3]

Смотрите также

использованная литература

  1. ^ "случайный (4)". www.freebsd.org. Получено 2020-10-01.
  2. ^ «Генерация случайных чисел». Служба поддержки Apple. Получено 2020-10-26.
  3. ^ Ю. Додис, А. Шамир, Н. Стивенс-Давидовиц, Д. Вичс, «Как съесть свою энтропию и иметь ее тоже - оптимальные стратегии восстановления для взломанных ГСЧ» Криптология Архив ePrint, Отчет 2014/167, 2014. https://eprint.iacr.org/2014/167.pdf

Общее

  • Нильс Фергюсон и Брюс Шнайер, Практическая криптография, опубликованный Wiley в 2003 году. ISBN  0-471-22357-3.
  • Джон Виега, «Практическое генерирование случайных чисел в программном обеспечении», acsac, стр. 129, 19-я Ежегодная конференция по приложениям компьютерной безопасности (ACSAC '03), 2003 г.

внешние ссылки