Все знают, что лучший генератор случайных чисел — это устройство, оцифровывающее выход с очень чувствительного микрофона, стоящего на солнечном берегу моря где-нибудь в районе диких пляжей Бали.
Если у вас такого устройства нет, то прошу под кат.
Итак, вам постоянно нужны хорошие случайные данные. Для генерации ключей шифрования, соли, паролей, не важно. Важно их качество.
Допустим, у вас есть хороший криптостойкий ГПСЧ, который вы когда то инициализировали каким то большим числом (seed) и с тех пор его не меняли.
Если злой фсбшник хакер каким то образом узнает это число, то сможет восстановить всю последовательность, а это уже совсем не хорошо.
Поэтому, логично периодически этот ГПСЧ заново инициализировать новым, хорошим, случайным числом.
Получается, чтобы генерировать хорошие случайные числа, нам нужны хорошие случайные числа. Круг замкнулся.
Шум
Или, говоря более строгим языком, источник энтропии. Конечно, в идеале он должен быть физической природы, но в среде выполнения ПО их тоже хватает. Не таких хороших, конечно, но тем не менее.
Грубо говоря, любые изменяемые во времени данные могут служить источником шума. Например:
- Входящие/исходящие запросысообщения
- Состояние ОС (объем свободной памятизагрузка CPU)
- текущие координаты мыши
- различные счетчики
- текущий снимок экрана
Чем таких источников больше, тем лучше. По одному они могут представлять довольно скудные данные, но их комбинации дают хороший поток более-менее непредсказуемых данных, которые нам так нужны.
Если вы ограничены в источниках энтропии, то вот вам рецепт как подсобрать её почти на пустом месте:
- Запускаем отдельный поток, в котором в бесконечном цикле инкрементим целочисленную перменную
- Раз в миллисекунду смотрим из другого потока на её последний бит и сохраняем (не мешая ей инкрементиться)
- Через 1 сек у вас есть ~1000 бит энтропии неплохого качества
Можно варьировать количество бит, которые вы забираете из этой переменной раз в миллисекунду. Качество энтропии будет обратно пропорционально количеству взятых бит, но зато скорость её генерации будет в количество бит выше.
Так же, можно ждать больше чем 1 мсек, тогда влияние побочных процессов на этот доставаемый последний бит будет еще больше, а соответственно, качество его «случайности» улучшится.
Минусы у такого генератора очевидны:
- Очень низкая скорость генерации.
- Полная загрузка одного из ядер процессора на время работы
Но он неплохо подходит на роль «seedирующего» для более быстрых товарищей по цеху.
Fortuna
Итак, у нас есть какое то количество источников энтропии, что с ними делать?
Постоянно кормить ими ГПСЧ
Такой ГПСЧ называется continuously-seeded pseudo-random number generator. и Fortunа за авторством товарищей Шнайера и Фергюсона является замечательным представителем такого генератора.
Она состоит из двух уровней.
- Пулы энтропии
- Внутренний генератор
Первых аж 32 штуки, они представляют собой ни что иное, как 32 хэша(любых, на ваш выбор), в которые по принципу карусели складывается входящая энтропия. Эти хэши в период сбора не финализируются( т.е. не вычисляют окончательное значение), таким образом накапливая случайные данные в процессе работы.
Чтобы было проще представить, эти 32 хэша до поры до времени как будто хэшируют большие большие- прибольшие файлы и никак не дохэшируют. Выделенное жирным важно, далее будет объяснение
То есть, пришло вам новое сообщение/запрос, вы его отдали фортуне, она попросила пул №1 его обработать.
Сгенерировали несколько байт генератором описанным выше, тоже туда же, она уже отдала их второму.
И так далее.
Поскольку это хэши, то все входящие данные не аккумулируются в памяти, а изменяют их внутреннее состояние, т.е. память не тратится.
И так, у нас есть 32 откормленных пула, что дальше?
Сначала немного про
Внутренний генератор
Он представляет из себя блочный шифр(AES, например) и счетчик(число, размером с блок AES, увеличивающееся на 1 каждый раз когда кто то просит новые данные). То есть, задача счетчика просто в том, чтобы каждый раз шифровались разные данные.
Не важно какие, их всё равно шифруют случайным ключом.
Этот генератор фактически и есть та штука, которая выдает наружу случайные данные, которые получаются путём шифрования счетчика случайным ключом.
При этом, каждый раз когда мы просим у него очередную порцию случайных данных, он генерирует немного больше чем нужно, а излишек используя как новый ключ шифрования для себя самого.
Т.е., например попросили мы у генератора 100 байт, он сгенерировал 116, отдал нам 100, а 16(128 бит) использовал как новый ключ шифрования для блочного шифра.
При этом счетчик не обнуляется, а каждое следующее его значение шифруется разными ключами.
In the mix
Откуда берется самое первое значение ключа шифрования для генератора и как работает система пулов?
Изначально внутренний генератор инициализируется внешними данными, как и все обычные генераторы. Тут никакого волшебства.
Но когда количество байт, обработанных пулом(хэшем) под номером 1 превышает некоторый порог (64 байта), начинается самая красивая часть алгоритма.
Fortuna ведет счет таким срабатываниям. Называются этот счетчик Reseed Count и обозначает «Сколько раз мы сменили ключ шифрования внутреннего генератора?»
От текущего Reseed count зависит набор пулов, которые будут участвовать в генерации нового ключа шифрования
Поскольку пулов у нас 32, то «степень их вовлеченности» зависит от того, до какой степени двойки добрался Reseed count.
Первый пул используется каждый раз.
Второй — если остаток от деления Reseed count на 2 равен нулю
третий — если остаток от деления Reseed count на 4 равен нулю
и.т.д
То есть, чем выше номер пула, тем реже он используется и дольше накапливает энтропию. 32й пул накопит её только через 2^32 операций reseed.
Reseed
Итак, пришло время сменить ключ шифрования у внутреннего генератора.
Мы, наконец, финализируем хэши тех пулов, которые участвуют в текущем Reseed. Получаем массивчик байт размером количество участвующих пулов*количество байт хэша.
И отдаём его внутреннему генератору.
Генератор эти все байтики берет, туда же подмешивает текущий свой ключ шифрования (который, как мы помним, меняется каждый раз после генерации данных), тоже всё хэширует и этот хэш использует как новый ключ шифрования для внутреннего генератора.
Всё.
Нафига всё это?
Система пулов делает Фортуну самовосстанавливающейся. Если вначале у вас в пулы приходили хорошие данные, а потом стали приходить плохие, то очередной reseed с пулом, в котором осталась энтропия от хороших данных восстановит баланс сил во вселенной.
Так же, можно заметить, что предыдущая информация, от которой зависит генерация случайных данных (та самая энтропия) не теряется. При каждом reseed новые ключи подмешиваются к текущему, а не заменяют его.
Дополнительно
Авторы Fortuna рекомендуют раз в несколько минут генерить пару килобайт случайных данных и сохранять их на диск, чтобы при следующем запуске приложения не собирать изначальную энтропию незнамо где, а сразу заинитить Фортуну хорошими данными.
На этом всё, спасибо за внимание.
Автор: Scratch
