оцените PRNG

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

При незнании противником содержимого пула, безопасность prng опирается на безопасность sha512. Для взлома необходимо всего-лишь реверсировать хеш (именно реверсировать, а не найти коллизию). Т.е. восстановить состояние пула по выходу хеша. Почему не подходит коллизия? А потому, что если H(x) = H(x'), то H(x + y) != H(x' + y), где y – вносимые на шаге reseed данные. Для того чтобы пытаться совершить атаку на основе предсказания вносимых в reseed данных, надо сначала знать состояние пула.

Тем, что они из того же документа :) Раз туда пропихнули один бекдор, то неужели не могли пропихнуть два?
Правда ничего с ходу удтверждать не буду, надо будет на досуге проанализировать Hash_DRBG. Кстати, вы случайно не подскажете где можно найти образец реализации этого алгоритма, так как я лучше понимаю исходный код, чем описания в документе.

P. S. почему-то ни в TrueCrypt ни в OpenSSL не используется стандарт из этого документа? Может быть есть причина?

Тем, что они из того же документа :) Раз туда пропихнули один бекдор, то неужели не могли пропихнуть два?

А почти все стандарты на шифрование, хэширование, подписи и пр. идут от NIST, который имеет давние исторические связи с NSA. А Нил Коблитц предупреждал, что криптографическое сообщество коррумпировано с двух сторон: со стороны госструктур, которые дают основные заказы и контролируют даже частные университеты в западных странах и со стороны коммерческих структур, которым нужна чаще видимость безопасности, маркетинг и экономия на всём. А вы что хотели?

Кстати, вы случайно не подскажете где можно найти образец реализации этого алгоритма, так как я лучше понимаю исходный код, чем описания в документе.

Кроме описания, там есть псевдокод

P. S. почему-то ни в TrueCrypt ни в OpenSSL не используется стандарт из этого документа? Может быть есть причина?

Этот стандарт от NIST появился позже.

использует в качестве констант 32-битные слова, полученные извлечением кубического корня из первых 64 простых чисел.

Это как нибудь обосновано, или просто красивое оформление для бэкдора "потолка"(с которого всё, в конечном счёте, и берётся)?

Сегодня подниму исходники windows

Так ведь исходники то старые. А если в новых сервис паках вдруг обнаружится "улучшение"? Тогда уж надо использовать те старые исходники, или искать восстановленные реверсинженирингом новые.

или просто красивое оформление для бэкдора "потолка"(с которого всё, в конечном счёте, и берётся)

От балды это якобы придумано, от чего же ещё?
Бэкдор потолка? В потолке открылся люк, не волнуйся – это глюк! ;-)

Это и есть обоснование того, что числа взяты с потолка, а не злонамереным образом. Вероятность нахождения уязвимых "обоснованых" чисел гораздо меньше, чем произвольно выбраных.

Я сейчас раздизасмил prng винды и кинул на это дело беглый взгляд. Собственно вот что могу про все это сказать:
Функция CryptGenRandom вызывает CPGenRandom из дефолтового криптопровайдера rsaenh.dll. В CPGenRandom производится генерация числа по стандарту FIPS 186. Береться sha1 от пула prng, после чего хеш отправляется на выход, а к пулу добавляется digest + 1 по модулю 2^512. Добавляется численно (пул обрабатывается как большое число). Цикл повторяется до тех пор, пока запрашиваемый обьем случайных данных не будет заполнен. Реализация вроде похожа на правильную, но детально код я не восстанавливал.
Начальная энтропия для пула береться от другого prng, реализованого в advapi32.dll (через функцию SystemFunction036).
Функция SystemFunction036 хранит свой пул случайных данных, миксуя их с помощью MD4 хеша. Случайные данные эта функция получает из глобальных переменных в коде advapi32, а также запрашивает у драйвера ksecdd.sys через его IOCTL с номером 390008h. При запросе на генерацию случайного числа, сначала происходит миксование пула, затем reseed с использованием \Device\KsecDD, затем данными пула инициализируется ключ rc4, после чего rc4 генерирует выходное случайное число.
Сам ksecdd.sys я уже не смотрел, но имхо он должен производить накопление энтропии в kernel mode.

Мое мнение об этом prng: сделано муторно, использование rc4 дает повод для сомнений в стойкости, но не все так страшно как писали в статье https://www.pgpru.com/novosti/.....juchiisslsoedinenija
В общем, использовать этот prng непосредственно для генерации ключей я бы не стал, но в качестве дополнительного источника энтропии сойдет очень неплохо.

Помоему авторы этой статьи ничего не дизассемблировали, а посмотрели файл ntagimp1.c из исходников NT4. Там действительно полный ахтунг, очень мало источников этропии + rc4 прямо на выходе + очень редкий reseed.

Последняя редация http://freed0m.org/prng.c
Изменения:

1 – Разнесены вызовы KeQuerySystemTime и KeQueryTickCount для уменьшения корреляции между ними.
2 – Добавлено внесение дополнительной этропии от счетчика тактов на этапе миксования пула. Измененная строка теперь выглядит так: rnd_pool[i + n] += hval[n] + (u_char)(__rdtsc());
Тоесть к пулу мы добавляет значение хеша и младшие 8 бит от счетчика тактов процессора. xor заменен на сложение по модулю 2^8 по причине того, что малое изменение бит добавляемого числа может менять больше бит результата, и операция не так быстро зацикливается. У последовательных вызовов rdtsc будет весьма сильная корреляция, и это изменение должно обеспечить лучшее использование малых величин случайности.
На другие свойства функции rnd_pool_mix это изменение не влияет, так как по прежнему обеспечивается зависимость всех бит пула от друг друга, а добавление rdtsc в худшем случае сводиться к константе (которая при характеристиках значения хеша идеентичным случайным, не может ухудшить стойкость).
3 – Добавлен дополнительный источник энтропии – поле trash в структуре seed_data. Это поле нигде не заполняется, и при вызове содержит части стека оставшиеся от работы исполняемого ранее кода. В худшем случае этот источник не вносит и не теряет никакой энтропии, ну а в реальном случае там будет хрен знает что (остатки памяти ядра).

На этом разработку prng.c можно заканчивать, т.к. имхо уже реализован параноидальный запас стойкости. Единственное планируемое улучшение – это увеличение числа юзермодных источников энтропии.
+ планируется написать статью с обоснованием принципов работы этого rng и его источников энтропии.

указано, что частый reseed даёт нежелательные корреляции и уменьшает эффективную энтропию.

А не сделать ли из каждого источника энтропии линейный конгруэнтный генератор? Например так:

seed.seed1 = PsGetCurrentProcess();
seed.seed1 = 1664525*seed.seed1+1013904223;

В этом случае не будет существенна скорость изменения источника.

На этом разработку prng.c можно заканчивать, т.к. имхо уже реализован параноидальный запас стойкости.

Если производительность не критична, можно AES ещё добавить. Вот и unknown вроде как благосклонно к этому отнёсся.

хотя бы так:

seed.seed1 += PsGetCurrentProcess();

ещё лучше
seed.seed5 += KeGetCurrentProcessorNumber()+1;

А то у многих только один процессор. Под номером 0 :)

Это не имеет смысла, так как энтропии это не добавляет и не уменьшает, а статистические характеристики обеспечиваются хешем.

Добавить конечно можно, но неужели в sha512 кто-то сомневается? Не хочеться городить друг на друга ничем не обоснованые изменения, пусть даже они ухудшить результат не могут.

Это полезное дополнение. Начальное заполнение структуры seed неизвестно, и это позволит не терять дополнительную халявную случайность.

Прибавление константы не улучшает и не ухудшает свойства алгоритма, а значит не имеет смысла.

Прибавление константы не имеет смысла.

Тогда не имеет смысла и это:


Когда
KeGetCurrentProcessorNumber() == 0
тогда
( seed.seed5 += KeGetCurrentProcessorNumber() ) == 0
а
( seed.seed5 += KeGetCurrentProcessorNumber()+1 ) == (seed.seed24 = counter++)

неужели в sha512 кто-то сомневается?

А зачем же тогда конкурс объявили?

можно AES ещё добавить

Лучше Whirlpool, но это надо добавлять ещё код, а AES уже присутствует.

Имеет. Счетчик числа reseed не совсем предсказуемая величина. Не имеет смысла конструкция вида seed.seed24 += 5

Не согласен, начальное значение seed5 неизвестно и изменяется в зависимости от вызывающего кода.

Не, Whirlpool слишком уж громоздкий и тормозной, и с ним частый reseed будет серьезно задерживать к примеру открытые тома (при этой операции вызывается rnd_reseed_now). Ну а использовать Whirlpool только в rnd_get_bytes... так это получиться уже 3 разных хеша в программе, а нафиг оно надо? Вот выйдет стандарт sha-3, тогда посмотрим стоит ли менять все на него или нет.

Генерация истинно случайных чисел на основе шума звуковых карт Там ещё есть список литературы.