Алгоритм Fortuna

Fortuna — это семейство криптографически стойких генераторов псевдослучайных чисел. Алгоритм разработан Брюсом Шнайером и Нильсом Фергюсоном и впервые описан в их книге «Практическая криптография»[1]. По словам авторов, алгоритм был создан во время работы над книгой и является значительным усовершенствованием алгоритма Ярроу.

Структура алгоритма

Система Fortuna состоит из трёх частей:

• Собственно генератор, инициализируемый начальным числом (англ. seed) фиксированной длины и выдающий произвольное количество псевдослучайных бит.
• Аккумулятор энтропии, собирающий случайные данные из различных источников и изменяющий начальное число генератора всякий раз, когда накоплено достаточное число энтропии.
• Система управления файлом начального числа, обеспечивающая возможность генерации псевдослучайных чисел непосредственно после перезагрузки компьютера.

Генератор

В качестве генератора можно использовать любой безопасный блочный шифр (в книге «Практическая криптография» предлагаются такие шифры, как AES (Rijndael), Serpent и Twofish) в режиме счётчика. Иными словами, в ответ на каждый запрос пользователя/приложения генератор производит псевдослучайные данные посредством шифрования последовательных натуральных чисел (значений счётчика). При этом в качестве исходного ключа используется начальное число, а после каждого запроса происходит обновление ключа: алгоритм генерирует 256 бит псевдослучайных данных с помощью старого ключа и использует полученное значение в качестве нового ключа. Это делается для того, чтобы злоумышленник не смог узнать предыдущие состояния генератора, даже если ему стало известно текущее состояние после очередного запроса. Кроме того, блочный шифр в режиме счётчика производит неповторяющиеся 16-байтовые блоки с периодом 2^128 в то время, как в истинных случайных данных при таких длинах последовательности с большой вероятностью должны встречаться одинаковые значения блоков. Поэтому для улучшения статистических свойств псевдослучайной последовательности максимальный размер данных, которые могут быть выданы в ответ на один запрос, ограничивается 2^20 байт (при такой длине последовательности вероятность найти одинаковые блоки в истинно случайном потоке составляет порядка 2^−97).

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

Аккумулятор собирает истинно случайные данные из внешних источников энтропии и равномерно распределяет их по 32 пулам (англ. pool).

Источники энтропии

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

Пулы

Каждый источник энтропии распределяет события равномерно и циклически по 32 пулам ${\displaystyle P_{0},P_{1},\ldots ,P_{31}}$. Добавление события в пул означает его конкатенацию с уже имеющейся в пуле строкой. Всякий раз, когда объём содержимого пула ${\displaystyle P_{0}}$ становится достаточно большим, происходит обновление начального числа (то есть ключа шифрования) генератора посредством хеширования содержимого одного или нескольких пулов, причём пул ${\displaystyle P_{0}}$ участвует в каждом обновлении, пул ${\displaystyle P_{1}}$ — в каждом втором обновлении, пул ${\displaystyle P_{2}}$ — в каждом четвёртом обновлении и так далее. Таким образом, каждый последующий пул используется реже предыдущего и успевает накопить большее число энтропии. Это позволяет автоматически отражать атаки, при которых злоумышленник обладает информацией о части источников энтропии — рано или поздно происходит обновление ключа, задействующее энтропии больше, чем способен предсказать криптоаналитик. При этом можно показать, что время автоматического восстановления системы после атаки превосходит минимально возможное не более, чем в 64 раза (последнее справедливо, вообще говоря, только в случае, когда в системе имеется достаточное число пулов; для выполнения этого условия Fortuna требует производить обновления не более 10 раз в секунду: если бы существовал 33-й пул, при данной частоте обновлений он был бы впервые использован не ранее, чем через 13 лет после начала работы алгоритма).

Файл начального числа

Файл начального числа содержит начальное число, передаваемое генератору при инициализации Fortuna. Он позволяет генератору производить псевдослучайные данные ещё до того, как в системе наберётся достаточное количество энтропии. Файл считывается при запуске, после чего его содержимое немедленно обновляется. По мере поступления энтропии, файл периодически перезаписывается (авторы рекомендуют генерировать новый файл начального числа каждые 10 минут, однако стоит учитывать также особенности конкретного приложения и скорость сбора энтропии в системе).

Отличия от Yarrow

Основным отличием Fortuna от Yarrow является иной подход к работе аккумулятора энтропии — Yarrow требовал наличия механизмов оценки количества энтропии и использовал только два пула.

Критика

Некоторые исследователи выражают сомнения в практичности использования данного алгоритма из-за слишком экономного использования энтропии, и, как следствие, некоторой вероятности кратковременной компрометации[2].

Реализации

• Реализация Fortuna на языке C++
• Реализация Fortuna на языке Python (Python Cryptography Toolkit)
• Патч, реализующий поддержку Fortuna, для ядра Linux
• Реализация Fortuna на языке Javascript (Javascript Crypto Library)

См. также

• Алгоритм Ярроу
• Алгоритм Блюма — Блюма — Шуба
• Криптографически стойкий генератор псевдослучайных чисел

Примечания

1. Нильс Фергюсон, Брюс Шнайер. Практическая Криптография = Practical Cryptography. — Вильямс, 2005. — 416 с. — ISBN 5-8459-0733-0.
2. John Viega. Practical Random Number Generation in Software (англ.) // 19th Annual Computer Security Applications Conference. — 2003. — P. 129. Архивировано 25 сентября 2020 года.