id: Гость   вход   регистрация
текущее время 23:55 28/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 (21/11/2007 07:58)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Впринципе для данного применения без разницы какой хеш использовать. Но если sha512 будет выглядеть круче и вызывать больше доверия, то использую его. Всеравно этот PRNG не нуждается в особой производительности, а значит можно себе позволить перестраховаться.
Из других изменений я планирую делать rnd_reseed_now два раза: перед генерацией числа и после нее, и при чтении каждых 64х байт (размер sha512 хеша) брать хеш не от части, а от всего пула. Это должно дать зависимость каждого выходного байта от всего пула в целом, хотя и медленее по скорости.
Может кто-то назовет такие изменения лишними, но я хочу получить максимальный запас по стойкости, чтобы в этом ни у кого не возникало сомнения.
— SATtva (21/11/2007 09:13)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Из других изменений я планирую делать rnd_reseed_now два раза: перед генерацией числа и после нее, и при чтении каждых 64х байт (размер sha512 хеша) брать хеш не от части, а от всего пула.

Мне это нравится. Лишним это не будет.
— Гость (21/11/2007 11:59)   <#>
Всеравно этот PRNG не нуждается в особой производительности, а значит можно себе позволить перестраховаться.
И это правильно. Лучше перебдеть, чем недобдеть! :) Экономить лучше на дорогих вещах, а из недорогих брать лучшие!
— ntldr (21/11/2007 15:31)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
http://freed0m.org/prng.c обновлен с учетом вышеуказаных изменений.
— Гость (21/11/2007 19:27)   <#>
KeQuerySystemTime(&seed.seed20);
KeQueryTickCount(&seed.seed21);

Стоящие рядом, эти вызовы выдают сильно коррелирующие значения. Если между ними будут другие операторы с непостоянным временем исполнения (например один из этих вызовов можно поставить в начало процедуры) корреляция может слегка уменьшится.
— unknown (22/11/2007 10:05, исправлен 22/11/2007 10:08)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Извините за неконструктивную критику, но... может чтение литературы по генераторам располагаем к пессимизму, т.к. эта теория до сих пор толком не проработана.

Вообще, чтобы оценить стойкость генератора, нужно написать работу fileнаподобие этой.

А чтобы спроектировать генератор, нужно впервую очередь опять писать такого вида теоретическую работу и лишь в конце код для примера.

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

А на уровне общих знаний, интуитивно-эмпирическим путём, по принципу, "чтобы выглядело похоже" – это любительство.

Или придётся найти и использовать готовый стандарт, не внося никаких изменений, положившись на честность и компетентность разработчиков, для чего стандарты и делаются.
— ntldr (22/11/2007 11:55)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Предлагаете доверять таким стандартам? Нет уж, спасибо, лучше я буду доверять свойствам известных криптоптимитивов и собственному здравому смыслу.
В моем случае предсказаные следующего выхода PRNG по предыдущему сводиться к нахождению коллизии хеша sha512 и угадыванию случайности вносимой двумя вызовами rnd_reseed_now, которые вносят по минимуму 136 случайных бит, а по максимуму в 2-3 раза больше. Более того, дело осложняется добавлением к хешу длины сообщения, инвертированием и перемешиванием пула. Как вы думетете, реально?

В крайнем случае можно использовать параллельно два prng. Какой нибудь стандарт и эту реализацию. Хуже от этого не будет, но я считаю это уже написанием лишнего кода.
— Гость (22/11/2007 12:46)   <#>
чтобы спроектировать генератор
Надо учесть, что обычно в таких случаях заботятся о производительности, откуда и трудности. Тут же эффективность не критична.

инвертированием и перемешиванием пула.
Может лучше ещё в добавок зашифровать его разок-другой с помощью AES256? И кода много писать не надо :)

можно использовать параллельно два prng
Или последовательно. А можно сделать одним из seed'ов. Или поXORить.

Вот, например Cryptographically Secure Random number on Windows without using CryptoAPI
— unknown (22/11/2007 13:32)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Может лучше ещё в добавок зашифровать его разок-другой с помощью AES256? И кода много писать не надо :)

можно использовать параллельно два prng

Или последовательно. А можно сделать одним из seed'ов. Или поXORить.


Если б не упоминание AES, то можно было бы подумать, что это рассуждения в духе хакеров-шифрпанков начала 90-хх :-)

Разработка /dev/{u}random для Linux тоже велась по принципу: давайте наворотим что-нибудь посложнее, это не спасло его от нестойкости.

Просто этим же израильским криптографам пришлось поплеваться пока восстанавливали алгоритм работы из открытого кода и пытались его формализовать "reverse engeneering of open source code", но в итоге они доказали, что сложные навороты только ослабили стойкость.

Кстати, в их же работах указано, что частый reseed даёт нежелательные корреляции и уменьшает эффективную энтропию.
— ntldr (22/11/2007 14:15, исправлен 22/11/2007 14:20)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Дада, несомненно математически "чистый" PRNG на асимметрике с бекдором от NSA это хорошо. А "грязные" PRNG на хешах это плохо и недостойно высокой академической науки, хоть вздомать их никто еще не удосужился.
Собственно даже простейшая констркуция R = H(seed + counter) уже упирается в стойкость хеша H...

Собственно учтите, что из этого PRNG за раз читаются маленькие ключи шифрования, а не гигабайты данных. Гигабаты из него будет при всем желании прочитать затруднительно, ввиду очень невысокой производительности rnd_get_bytes.
— unknown (22/11/2007 15:01, исправлен 22/11/2007 15:06)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
А "грязные" PRNG на хешах это плохо и недостойно высокой академической науки, хоть вздомать их никто еще не удосужился.
Собственно даже простейшая констркуция R = H(seed + counter) уже упирается в стойкость хеша H...

В том же документе NIST, где был Dual_EC_DRBG с закладкой, остальные устроены как раз и на хэшах и на блочных шифрах. Там даже физические генераторы описаны.

Но даже простейшие конструкции вида R = H(seed + counter) вполне себе удостаиваются внимания "высокой академической науки" в многостраничных трудах и для них тоже расписывают трёхэтажные формулы. Наверное чтобы побольше извести бумаги для принтеров :-)

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

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

Кто сможет точно описать модель Вашего генератора, если не в цифрах, то в буквах (при эффективной энтропии пула \epsilon в рамках модели \alpha затраты противника будут стремиться к \omega)?
— Гость (22/11/2007 15:11)   <#>
с бекдором от NSA
Кто нибудь может сказать, откуда берутся константы в той же SHA?
Может стоит модифицировать эти константы (тем же SHA), и применять модифицированную SHA вместе с оригинальной исходя из гипотезы, что одна из них окажется надёжной?

придётся найти и использовать готовый стандарт
Чего посоветуете? И какое у вас мнение о генераторе из майкрософтовского CryptoAPI?
— unknown (22/11/2007 15:11)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Дада, несомненно математически "чистый" PRNG на асимметрике с бекдором от NSA это хорошо.

Конечно хорошо :-) Для NSA. Для организаций своей страны им нужны стойкие алгоритмы. Но с закладкой для своих же. Чтобы врагам не достались :-)
— ntldr (22/11/2007 15:33)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20

Конечно можно, но имхо не стоит того. Тем более что я практически на 100% уверен, что модифицируя криптопримитивы сделаю только хуже.

Пока я его кода не видел, мое мнение сводиться к тому, что CryptoAPI лучше чем ничего. Но не более того. Сегодня подниму исходники windows, и если среди них удасться найти нужную часть, то выскажу более подробное мнение.
— unknown (22/11/2007 15:34, исправлен 22/11/2007 15:35)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Кто нибудь может сказать, откуда берутся константы в той же SHA?

Оттуда же... Константы к SHA-1, наверное были придуманы в самом NSA.

SHA-256 использует в качестве констант 32-битные слова, полученные извлечением кубического корня из первых 64 простых чисел.
SHA-384 и SHA-512 используют для получения констант тот же метод, только более длинный ряд простых чисел и 64-битные слова.

А чем не нравятся Hash_DRBG, HMAC_DRBG и CTR_DRBG из того же документа NIST?
На страницу: 1, 2, 3, 4 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3