Алгоритм Fortuna

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Структура алгоритма[править | править вики-текст]

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

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

Генератор[править | править вики-текст]

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

Аккумулятор энтропии[править | править вики-текст]

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

Источники энтропии[править | править вики-текст]

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

Пулы[править | править вики-текст]

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

Файл начального числа[править | править вики-текст]

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

Отличия от Yarrow[править | править вики-текст]

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

Критика[править | править вики-текст]

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

Реализации[править | править вики-текст]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  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.