id: Гость   вход   регистрация
текущее время 04:29 29/03/2024
Автор темы: ntldr, тема открыта 18/11/2007 15:45 Печать
Категории: криптография, случайные числа
создать
просмотр
ссылки

оцените PRNG


За основу данного prng взят prng из исходников TrueCrypt. В моей реализации используются аналогичные алгоритмы для накопления энтропии и миксования пула, но переделана функция получения случайных чисел из пула. Для увеличения стойкости от предсказания предыдущих и следующих состояний prng, на выход идет не состояние пула, а sha1 хеш его части. После чтения каждых 20 байт пула производиться обновление состояния пула.
В качестве основного источника энтропии используются внешние данные передаваемые приложением, в качестве дополнительного источника используютя значения возвращаемые 20 функциями ядра windows. Данная реализация не приспособлена для получения больших обьемов случайных данных, ставилась задача получить максимальную стойкость при генерации ключей.


Жду ваших комментариев по поводу реализации и рекомендаций по ее улучшению (интересует только безопасность, производительность не требуется).
http://freed0m.org/prng.c


 
На страницу: 1, 2, 3, 4 След.
Комментарии
— ntldr (22/11/2007 16:20)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20

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

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

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

P. S. почему-то ни в TrueCrypt ни в OpenSSL не используется стандарт из этого документа? Может быть есть причина?
— unknown (22/11/2007 16:44, исправлен 22/11/2007 16:46)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Тем, что они из того же документа :) Раз туда пропихнули один бекдор, то неужели не могли пропихнуть два?

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

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

Кроме описания, там есть псевдокод
— unknown (22/11/2007 16:45)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
P. S. почему-то ни в TrueCrypt ни в OpenSSL не используется стандарт из этого документа? Может быть есть причина?

Этот стандарт от NIST появился позже.
— Гость (22/11/2007 17:27)   <#>
использует в качестве констант 32-битные слова, полученные извлечением кубического корня из первых 64 простых чисел.
Это как нибудь обосновано, или просто красивое оформление для бэкдора "потолка"(с которого всё, в конечном счёте, и берётся)?

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

Так ведь исходники то старые. А если в новых сервис паках вдруг обнаружится "улучшение"? Тогда уж надо использовать те старые исходники, или искать восстановленные реверсинженирингом новые.
— unknown (22/11/2007 17:46, исправлен 22/11/2007 17:48)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
или просто красивое оформление для бэкдора "потолка"(с которого всё, в конечном счёте, и берётся)

От балды это якобы придумано, от чего же ещё?
Бэкдор потолка? В потолке открылся люк, не волнуйся – это глюк! ;-)
— ntldr (22/11/2007 19:01)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20

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

Я сейчас раздизасмил 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.
— ntldr (23/11/2007 14:20, исправлен 23/11/2007 14:28)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Последняя редация 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 и его источников энтропии.
— Гость (24/11/2007 11:04)   <#>
указано, что частый reseed даёт нежелательные корреляции и уменьшает эффективную энтропию.

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

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

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

На этом разработку prng.c можно заканчивать, т.к. имхо уже реализован параноидальный запас стойкости.
Если производительность не критична, можно AES ещё добавить. Вот и unknown вроде как благосклонно к этому отнёсся.
— Гость (24/11/2007 11:22)   <#>
хотя бы так:

seed.seed1 += PsGetCurrentProcess();
— Гость (24/11/2007 12:52)   <#>
ещё лучше
seed.seed5 += KeGetCurrentProcessorNumber()+1;

А то у многих только один процессор. Под номером 0 :)
— ntldr (25/11/2007 03:44)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20

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

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

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

Прибавление константы не улучшает и не ухудшает свойства алгоритма, а значит не имеет смысла.
— Гость (25/11/2007 15:48)   <#>
Прибавление константы не имеет смысла.

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

seed.seed24 = counter++;

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



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

А зачем же тогда конкурс объявили?
— Гость (25/11/2007 16:24)   <#>
можно AES ещё добавить

Лучше Whirlpool, но это надо добавлять ещё код, а AES уже присутствует.
— ntldr (25/11/2007 19:26)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20

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

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

Не, Whirlpool слишком уж громоздкий и тормозной, и с ним частый reseed будет серьезно задерживать к примеру открытые тома (при этой операции вызывается rnd_reseed_now). Ну а использовать Whirlpool только в rnd_get_bytes... так это получиться уже 3 разных хеша в программе, а нафиг оно надо? Вот выйдет стандарт sha-3, тогда посмотрим стоит ли менять все на него или нет.
— Гость (04/12/2007 17:36)   <#>
Генерация истинно случайных чисел на основе шума звуковых карт Там ещё есть список литературы.
На страницу: 1, 2, 3, 4 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3