Введение

Генератор псевдослучайных чисел

Fortuna — криптографически стойкий генератор псевдослучайных чисел (ГПСЧ), разработанный Брюсом Шнайером и Нильсом Фергюсоном и опубликованный в 2003 году. Он назван в честь Фортуны, римской богини случая. FreeBSD использует Fortuna для /dev/random, а /dev/urandom символически связан с ним, начиная с FreeBSD 11. Операционные системы Apple перешли на использование Fortuna с первого квартала 2020 года.

Генератор

Генератор основан на любом надежном блочном шифре. Практическая криптография рекомендует AES, Serpent или Twofish. Основная идея заключается в использовании шифра в режиме счетчика, шифрующего последовательные значения увеличивающегося счетчика. При использовании 128-битного блочного шифра это приведет к статистически обнаруживаемым отклонениям от случайности; например, генерация 2<sup>64</sup> действительно случайных 128-битных блоков в среднем приведет к появлению примерно одной пары идентичных блоков, в то время как среди первых 2<sup>128</sup> блоков, сгенерированных 128-битным шифром в режиме счетчика, повторяющихся блоков не будет. Поэтому ключ меняется периодически: не более 1 Мбайт данных (2<sup>16</sup> 128-битных блоков) генерируется без смены ключа. В книге отмечается, что блочные шифры с размером блока 256 бит (или больше), которые в то время не были широко распространены, не имеют этой статистической проблемы. Ключ также меняется после каждого запроса данных (независимо от его размера), чтобы будущий компромисс ключа не подвергал риску предыдущие выходные данные генератора. Это свойство иногда называют "быстрым уничтожением ключа" или прямой секретностью.

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

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

Сев

Если злоумышленник не сможет контролировать все источники предполагаемой энтропии, поступающей в систему (в этом случае ни один алгоритм не сможет защитить её от компрометации), то найдется такое k, для которого k-й пул накопит достаточно энтропии между повторными засевами, чтобы повторный засев с использованием этого пула обеспечивал безопасность. И этот пул будет использоваться с интервалом, пропорциональным объему накопленной энтропии. Следовательно, система всегда восстановится после атаки внедрения, и время восстановления будет не более чем в постоянное число раз больше теоретического минимума, который потребовался бы, если бы мы могли определить, какие источники энтропии скомпрометированы, а какие нет. Этот вывод зависит от достаточного количества пулов. Fortuna использует 32 пула и ограничивает частоту повторных засевов максимум 10 в секунду. Для исчерпания всех пулов потребуется около 13 лет, что, по мнению Фергюсона и Шнайера, достаточно для практического применения. Более осторожные разработчики или те, кому требуется генерация случайных данных с огромной скоростью и, соответственно, частые повторные засевы, могут использовать большее количество пулов.

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

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

Анализ

В 2014 году был проведен анализ Fortuna и предложено ее улучшение.

Общий

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