id: Гость   вход   регистрация
текущее время 17:54 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 След.
Комментарии
— Гость (19/11/2007 01:16)   <#>
Пишите комментарии в тексте, это вам совет...
Чтобы не говорить *ять когда вы заглянете в свой же код через n лет, и чтобы не говорили *ять те люди, которые будут читать ваш код после Вас.
— SATtva (19/11/2007 11:38)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Согласен с предыдущим оратором. Код простой, но не всё с ходу очевидно.
— ntldr (19/11/2007 14:22)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
А по поводу самого алгоритма замечания будут?
— Гость (19/11/2007 19:11)   <#>
Для простоты:
Представьте себе учебник по физике или математике, в котором нет вообще ни одного слова кроме формул и графиков, нет даже указаний на то какая переменная что означает. Считайте, что код без комментариев – это именно такой учебник (или книга)...
— Гость (19/11/2007 23:36)   <#>
А по поводу самого алгоритма замечания будут?
Дык ведь это мозги напрягать надо. Гораздо проще общие советы давать :))
— SATtva (20/11/2007 01:24)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Дык ведь это мозги напрягать надо. Гораздо проще общие советы давать :))

Всё бросили, и взялись восстанавливать схему ГСЧ из сишного кода. Хороший это будет анализ? Вряд ли — только те самые "общие советы". На анализ нужно время. К тому моменту, возможно, и автор комментарии добавит в код.
— ntldr (20/11/2007 10:43)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Дада, на понимание функции состоящей из десятка строк кода нужно много времени и куча комментариев. Единственная интересная функция – это rnd_get_bytes, остальное все полный примитив.
Хрен знает какие тут комментарии можно написать, ведь все и так понятно с первого взгляда.
В общем получение случайных данных из пула накопленых случайных байт выглядит так:

1 – R = SHA1(pool[С] + L)
2 – C = C + 20
3 – L = L – 20
4 – pool = not pool
5 – reseed
Где
R – случайное число на выходе генератора, C – текущее положений курсора в пуле (меняется от 0 до 15), L – размер случайного числа которое нам нужно получить.
reseed – функция обновления состояния пула их быстрых источников этнропии.
Каждые 160 бит выходных данных образуются путем хеширования части пула размером в 160 бит и оставшегося размера затребованных данных в байтах. L добавляется перед хешированием с целью обеспечить разный выход PRNG при попадании на вход одного и того же куска пула (это возможно если убрать из кода действие 5). Инвертирование пула на шаге 4 необходимо для внесения дополнительной случайности в процессе интерференции нескольких потоков одновременно обращающихся к пулу (при такой интеференции невозможно предсказать инвертированый или нет байт прочитается из пула). Также инвертирование добавляет немного стойкости к нахождению коллизии sha1 (опять же при допущении отсутствия действия 5). PRNG нечувствителен к коллизиям используемого хеша, поскольку его внутренее состояние обновляется функцией reseed при чтении каждых 160 бит случайных данных.

Быстрые источники энтропии используемые в функции reseed:
1 – PsGetCurrentProcess – функция возаращающая указатель на текущий процесс. При вызове prng минимум их двух процессов (системного и exe программы) дает минмимум 1 случайный бит энтропии.
2 – PsGetCurrentProcessId – возвращает id текущего процесса. Дает 1-2 непредсказуемых бита.
3 – KeGetCurrentThread – возвращает текущий поток. Так как потоков в системе много, и некоторые периодически вызывают reseed, то 2 бита энтропии с нее точно будет.
4 – PsGetCurrentThreadId – возвращает id потока. В среднем 2 случайных бита.
5 – KeGetCurrentProcessorNumber – возвращает номер процессора на котором исполняется код. На однпроцессорных машинах полностью предсказуема, на многопроцессорных возвращает 1-2 случайных бита.
5 – KeQueryInterruptTime – возвращает общее время обработки всех прерываний в системе. Это значение зависит от работы с любым железом, действий пользователя, и.т.д. С полной уверенностью можно сказать, что младшие 16 бит совершенно непредсказуемы.
6 – KeQueryPriorityThread – возвращает динамический приоритет текущего потока. Максимум 1 случайный бит.
7 – KeQueryRuntimeThread – возвращает процессорное время потраченое текущим потоком за весь период его существования. Зависит от процессора, чипсета, системного кода и много чего другого. Минимум 8 случайных бит.
KeQueryPerformanceCounter – возвращает число тиков RTC (real time clock) либо HPET таймера (зависит от реализации HAL). Минимум 8 случайных бит.
8 – __rdtsc – возвращает счетчик тактов процессора. Он меняется с его тактовой частотой (несколько ГГЦ), а значит его значение практически непредсказуемо, и младшие 16 бит можно считать случайными.
9 – ExGetPreviousMode предудущий режим процессора до переключения в ядро. Максимум 1 бит энтропии.
10 – IoGetInitialStack – адрес начала стека для текущего потока. Фиг знает как оценить его случайность, но лишним оно не будет.
11 – IoGetTopLevelIrp – адрес последнего IPR пакета в очереди потока. Про случайность тоже не знаю.
12 – MmQuerySystemSize – постоянное число характеризующее размер установленой памяти.
13 – ExUuidCreate – возвращает 128 битное число от PRNG ядра. Не знаю алгоритм его генерации, но думаю хоть какая-то случайность у него есть.
14 – RtlRandom – предсказуемое, но периодически меняющееся значение.
15 – KeQuerySystemTime – текущее время с точностью до 100нс. Гарантировано 8 случайных бит.
16 – KeQueryTickCount – число тиков таймера от загрузки системы. 2-4 бита.
17 – IoGetStackLimits – возвращает гриницы стека для текущего потока. Уровень случайности неизвестен.

И так, подведем итоги. Всего у нас получается по минимуму 68 бит на вызов, а максимальное значение может быть гораздо выше (зависит от множества факторов). Следовательно зная текущее состояние пула, для предсказания следующего состояния потребуется минимум 2^68 операций. Правда атакующему знать состояние пула не от куда, так как на выход PRNG выдаются только хеши его частей.
Общая величина накапливаемой PRNG энтропии составляет 2560 бит (для заполнения этого значения нужно 30-40 вызовов быстрого источника энтропии, что гарантировано происходит в процессе загрузки системы). При запуске приложения криптодиска оно будет периодически передавать в PRNG случайные данные из дополнительных источников (движения мыши и Windows CryptoAPI), величина случайности которых гораздо больше.

После обновления состояния PRNG производиться миксование его пула. Фунекция миксования пула построена на основе sha1, и обеспечивает зависимость каждого бита пула от всех других его битов, превращая не полностью случайные данные в статистически неотличимые от белого шума. Функция построена аналогично TrueCrypt, и ее описание можно прочитать здесь http://www.truecrypt.org/docs/.....number-generator.php
— SATtva (20/11/2007 13:53)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
В rnd_reseed_now() пул заполняется данными из быстрых источников, так? Насколько я понимаю, данные из источников берутся целиком, а не только их достаточно непредсказуемые части? Да, впоследствии SHA-1 смешивает данные, но всё же полагаться только на алгоритм хэширования мне бы не хотелось.

Смешивание пула после чтения из него вроде бы производится: после чтения из пула вызываются rnd_reseed_now() -> rnd_pool_mix(). Я правильно понял?

Ещё вопрос на понимание (моё понимание).
  1. При первом запуске системы с ещё пустым пулом он будет вначале заполняться данными именно из быстрых источников, не слишком случайными, в общем. Каждый вызов ГСЧ будет добавлять в пул новые данные и перемешивать содержимое.
  2. Затем при запуске программы подключаются дополнительные источники (мышь и CryptAPI; их вызовы выполняет другая часть кода или я в prng.c чего-то не увидел?), также подмешиваемые в пул.
  3. После чтения программой случайных чисел из пула производится его перемешивание.
Урок усвоен верно?
— SATtva (20/11/2007 13:56)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
После чтения программой случайных чисел из пула производится его перемешивание.

Т.е. перемешивание производится после чтения каждого байта из пула.
— ntldr (20/11/2007 14:29)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20

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

Да, правильно.

Вызов rnd_reseed_now вставлен в драйвере в функции wde_add_device и wde_create_close_irp. Первая вызывается при появлении в системе нового устройства, вторая – при открытии и закрытии этого устровйства. На моей системе в процессе загрузки (до появления десктопа) rnd_reseed_now вызывается в общем случае 100 раз.

Эти данные передаются извне, из приложения. Смотрите exe/drvcode.c, функцию _add_seed, эта функция вызывается из main.c.

После чтения 20 байт (размер одного sha1 хеша).
— Гость (20/11/2007 15:44)   <#>
Какие могут быть проблемы при использовании хеша для перемешивания?

NIST encourages application and protocol designers to use the SHA-2 family of hash functions for all new applications and protocols.
— ntldr (20/11/2007 20:54)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
В следующей версии для PRNG будет использоваться хеш SHA512.
SATtva, вы считаете его достаточно безопасным для перемешивания не полностью случайных бит пула?
— Гость (20/11/2007 21:31)   <#>
будет использоваться хеш SHA512

Как минимум SHA256 – у хэша той же стойкости (AES128) должно быть в два раза больше бит. Даже если это не имеет особого смысла для генератора случайных бит, это звучит лучше и улучшает имидж программы. :)
— Гость (21/11/2007 01:49)   <#>
у хэша той же стойкости (AES128)

В программа используется AES256

Значит SHA512
— Гость (21/11/2007 01:53)   <#>
улучшает имидж программы
Ещё не факт. Два хеша вместо одного не так элегантно и занимает больше памяти.
На страницу: 1, 2, 3, 4 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3