оцените PRNG
За основу данного prng взят prng из исходников TrueCrypt. В моей реализации используются аналогичные алгоритмы для накопления энтропии и миксования пула, но переделана функция получения случайных чисел из пула. Для увеличения стойкости от предсказания предыдущих и следующих состояний prng, на выход идет не состояние пула, а sha1 хеш его части. После чтения каждых 20 байт пула производиться обновление состояния пула.
В качестве основного источника энтропии используются внешние данные передаваемые приложением, в качестве дополнительного источника используютя значения возвращаемые 20 функциями ядра windows. Данная реализация не приспособлена для получения больших обьемов случайных данных, ставилась задача получить максимальную стойкость при генерации ключей.
Жду ваших комментариев по поводу реализации и рекомендаций по ее улучшению (интересует только безопасность, производительность не требуется).
http://freed0m.org/prng.c
Ссылки
[link1] http://www.truecrypt.org/docs/random-number-generator.php
[link2] http://csrc.nist.gov/groups/ST/hash/policy.html
[link3] http://www.wisdom.weizmann.ac.il/~ranraz/publications/Ptwosour.ps
[link4] https://www.pgpru.com/novosti/2007/backdoorvellipticheskihkrivyh
[link5] http://blogs.msdn.com/michael_howard/archive/2005/01/14/353379.aspx
[link6] https://www.pgpru.com/novosti/2006/0325konceptualjnajanestojjkostjgpschvlinux
[link7] https://www.pgpru.com/novosti/2007/nestojjkostjvgpschwindowspozvoljaetbystrovskryvatjkljuchiisslsoedinenija
[link8] http://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод
[link9] https://www.pgpru.com/novosti/2007/0511nistopublikovalkommentariiktrebovanijamnakonkursshs
[link10] http://paginas.terra.com.br/informatica/paulobarreto/WhirlpoolPage.html
[link11] http://leo.yuriev.ru/114
[link12] https://www.pgpru.com/biblioteka/statji/analiznadezhnostipgp/analizishodnogokoda/sluchajjnyechisla
Пишите комментарии в тексте, это вам совет...
Чтобы не говорить *ять когда вы заглянете в свой же код через n лет, и чтобы не говорили *ять те люди, которые будут читать ваш код после Вас.
Согласен с предыдущим оратором. Код простой, но не всё с ходу очевидно.
А по поводу самого алгоритма замечания будут?
Для простоты:
Представьте себе учебник по физике или математике, в котором нет вообще ни одного слова кроме формул и графиков, нет даже указаний на то какая переменная что означает. Считайте, что код без комментариев – это именно такой учебник (или книга)...
Дык ведь это мозги напрягать надо. Гораздо проще общие советы давать :))
Всё бросили, и взялись восстанавливать схему ГСЧ из сишного кода. Хороший это будет анализ? Вряд ли — только те самые "общие советы". На анализ нужно время. К тому моменту, возможно, и автор комментарии добавит в код.
Дада, на понимание функции состоящей из десятка строк кода нужно много времени и куча комментариев. Единственная интересная функция – это 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[link1]
В rnd_reseed_now() пул заполняется данными из быстрых источников, так? Насколько я понимаю, данные из источников берутся целиком, а не только их достаточно непредсказуемые части? Да, впоследствии SHA-1 смешивает данные, но всё же полагаться только на алгоритм хэширования мне бы не хотелось.
Смешивание пула после чтения из него вроде бы производится: после чтения из пула вызываются rnd_reseed_now() -> rnd_pool_mix(). Я правильно понял?
Ещё вопрос на понимание (моё понимание).
- При первом запуске системы с ещё пустым пулом он будет вначале заполняться данными именно из быстрых источников, не слишком случайными, в общем. Каждый вызов ГСЧ будет добавлять в пул новые данные и перемешивать содержимое.
- Затем при запуске программы подключаются дополнительные источники (мышь и CryptAPI; их вызовы выполняет другая часть кода или я в prng.c чего-то не увидел?), также подмешиваемые в пул.
- После чтения программой случайных чисел из пула производится его перемешивание.
Урок усвоен верно?Т.е. перемешивание производится после чтения каждого байта из пула.
Да, для того чтобы не терять ни одного случайного бита. Не слишком случайные части тоже периодически изменяются, и вносят свой вклад в общий результат. Не хотелось бы отбрасывать биты которые могут быть хоть сколько нибудь случайными. Какие могут быть проблемы при использовании хеша для перемешивания?
Да, правильно.
Вызов rnd_reseed_now вставлен в драйвере в функции wde_add_device и wde_create_close_irp. Первая вызывается при появлении в системе нового устройства, вторая – при открытии и закрытии этого устровйства. На моей системе в процессе загрузки (до появления десктопа) rnd_reseed_now вызывается в общем случае 100 раз.
Эти данные передаются извне, из приложения. Смотрите exe/drvcode.c, функцию _add_seed, эта функция вызывается из main.c.
После чтения 20 байт (размер одного sha1 хеша).
В следующей версии для PRNG будет использоваться хеш SHA512.
SATtva, вы считаете его достаточно безопасным для перемешивания не полностью случайных бит пула?
Как минимум SHA256 – у хэша той же стойкости (AES128) должно быть в два раза больше бит. Даже если это не имеет особого смысла для генератора случайных бит, это звучит лучше и улучшает имидж программы. :)
Значит SHA512
Ещё не факт. Два хеша вместо одного не так элегантно и занимает больше памяти.
Впринципе для данного применения без разницы какой хеш использовать. Но если sha512 будет выглядеть круче и вызывать больше доверия, то использую его. Всеравно этот PRNG не нуждается в особой производительности, а значит можно себе позволить перестраховаться.
Из других изменений я планирую делать rnd_reseed_now два раза: перед генерацией числа и после нее, и при чтении каждых 64х байт (размер sha512 хеша) брать хеш не от части, а от всего пула. Это должно дать зависимость каждого выходного байта от всего пула в целом, хотя и медленее по скорости.
Может кто-то назовет такие изменения лишними, но я хочу получить максимальный запас по стойкости, чтобы в этом ни у кого не возникало сомнения.
Мне это нравится. Лишним это не будет.
И это правильно. Лучше перебдеть, чем недобдеть! :) Экономить лучше на дорогих вещах, а из недорогих брать лучшие!
http://freed0m.org/prng.c обновлен с учетом вышеуказаных изменений.
KeQuerySystemTime(&seed.seed20);
KeQueryTickCount(&seed.seed21);
Стоящие рядом, эти вызовы выдают сильно коррелирующие значения. Если между ними будут другие операторы с непостоянным временем исполнения (например один из этих вызовов можно поставить в начало процедуры) корреляция может слегка уменьшится.
Извините за неконструктивную критику, но... может чтение литературы по генераторам располагаем к пессимизму, т.к. эта теория до сих пор толком не проработана.
Вообще, чтобы оценить стойкость генератора, нужно написать работу наподобие этой[link3].
А чтобы спроектировать генератор, нужно впервую очередь опять писать такого вида теоретическую работу и лишь в конце код для примера.
Не думаю, что среди пишущих в форум есть специалист такого уровня, который ещё и захочет этим заняться.
А на уровне общих знаний, интуитивно-эмпирическим путём, по принципу, "чтобы выглядело похоже" – это любительство.
Или придётся найти и использовать готовый стандарт, не внося никаких изменений, положившись на честность и компетентность разработчиков, для чего стандарты и делаются.
Предлагаете доверять таким[link4] стандартам? Нет уж, спасибо, лучше я буду доверять свойствам известных криптоптимитивов и собственному здравому смыслу.
В моем случае предсказаные следующего выхода PRNG по предыдущему сводиться к нахождению коллизии хеша sha512 и угадыванию случайности вносимой двумя вызовами rnd_reseed_now, которые вносят по минимуму 136 случайных бит, а по максимуму в 2-3 раза больше. Более того, дело осложняется добавлением к хешу длины сообщения, инвертированием и перемешиванием пула. Как вы думетете, реально?
В крайнем случае можно использовать параллельно два prng. Какой нибудь стандарт и эту реализацию. Хуже от этого не будет, но я считаю это уже написанием лишнего кода.
Надо учесть, что обычно в таких случаях заботятся о производительности, откуда и трудности. Тут же эффективность не критична.
Может лучше ещё в добавок зашифровать его разок-другой с помощью AES256? И кода много писать не надо :)
Или последовательно. А можно сделать одним из seed'ов. Или поXORить.
Вот, например Cryptographically Secure Random number on Windows without using CryptoAPI[link5]
Если б не упоминание AES, то можно было бы подумать, что это рассуждения в духе хакеров-шифрпанков начала 90-хх :-)
Разработка /dev/{u}random для Linux тоже велась по принципу: давайте наворотим что-нибудь посложнее, это не спасло его от нестойкости[link6].
Просто этим же израильским криптографам пришлось поплеваться пока восстанавливали алгоритм работы из открытого кода и пытались его формализовать "reverse engeneering of open source code", но в итоге они доказали, что сложные навороты только ослабили стойкость.
Кстати, в их же работах указано, что частый reseed даёт нежелательные корреляции и уменьшает эффективную энтропию.
Дада, несомненно математически "чистый" PRNG на асимметрике с бекдором от NSA это хорошо. А "грязные" PRNG на хешах это плохо и недостойно высокой академической науки, хоть вздомать их никто еще не удосужился.
Собственно даже простейшая констркуция R = H(seed + counter) уже упирается в стойкость хеша H...
Собственно учтите, что из этого PRNG за раз читаются маленькие ключи шифрования, а не гигабайты данных. Гигабаты из него будет при всем желании прочитать затруднительно, ввиду очень невысокой производительности rnd_get_bytes.
В том же документе NIST, где был Dual_EC_DRBG с закладкой, остальные устроены как раз и на хэшах и на блочных шифрах. Там даже физические генераторы описаны.
Но даже простейшие конструкции вида R = H(seed + counter) вполне себе удостаиваются внимания "высокой академической науки" в многостраничных трудах и для них тоже расписывают трёхэтажные формулы. Наверное чтобы побольше извести бумаги для принтеров :-)
И что, на это вся надежда? Допустим, были сгенерированы два ключа для разных приложений в очень короткий промежуток времени. (например захотите сделать основной и вложенный контейнеры). Один ключ противник узнал (неважно откуда), сможет ли он узнать другой ключ? Пусть эффективная энтропия пула очень мала (опять же неважно сколько источников системных событий туда напихать, важен принцип), у противника есть модель быстрого предсказания исходных значений пула, а с учётом небольшой разности времени двух генераций, энтропия будет ещё меньше.
Кто сможет точно описать модель Вашего генератора, если не в цифрах, то в буквах (при эффективной энтропии пула \epsilon в рамках модели \alpha затраты противника будут стремиться к \omega)?
Кто нибудь может сказать, откуда берутся константы в той же SHA?
Может стоит модифицировать эти константы (тем же SHA), и применять модифицированную SHA вместе с оригинальной исходя из гипотезы, что одна из них окажется надёжной?
Чего посоветуете? И какое у вас мнение о генераторе из майкрософтовского CryptoAPI?
Конечно хорошо :-) Для NSA. Для организаций своей страны им нужны стойкие алгоритмы. Но с закладкой для своих же. Чтобы врагам не достались :-)
Конечно можно, но имхо не стоит того. Тем более что я практически на 100% уверен, что модифицируя криптопримитивы сделаю только хуже.
Пока я его кода не видел, мое мнение сводиться к тому, что CryptoAPI лучше чем ничего. Но не более того. Сегодня подниму исходники windows, и если среди них удасться найти нужную часть, то выскажу более подробное мнение.
Оттуда же... Константы к SHA-1, наверное были придуманы в самом NSA.
SHA-256 использует в качестве констант 32-битные слова, полученные извлечением кубического корня из первых 64 простых чисел.
SHA-384 и SHA-512 используют для получения констант тот же метод, только более длинный ряд простых чисел и 64-битные слова.
А чем не нравятся Hash_DRBG, HMAC_DRBG и CTR_DRBG из того же документа NIST?
Именно от этой модели угрозы и требуется в первую очередь защититься, поэтому я ввел не прямой вывод из пула как в TrueCrypt, а хеширование.
При незнании противником содержимого пула, безопасность prng опирается на безопасность sha512. Для взлома необходимо всего-лишь реверсировать хеш (именно реверсировать, а не найти коллизию). Т.е. восстановить состояние пула по выходу хеша. Почему не подходит коллизия? А потому, что если H(x) = H(x'), то H(x + y) != H(x' + y), где y – вносимые на шаге reseed данные. Для того чтобы пытаться совершить атаку на основе предсказания вносимых в reseed данных, надо сначала знать состояние пула.
Тем, что они из того же документа :) Раз туда пропихнули один бекдор, то неужели не могли пропихнуть два?
Правда ничего с ходу удтверждать не буду, надо будет на досуге проанализировать Hash_DRBG. Кстати, вы случайно не подскажете где можно найти образец реализации этого алгоритма, так как я лучше понимаю исходный код, чем описания в документе.
P. S. почему-то ни в TrueCrypt ни в OpenSSL не используется стандарт из этого документа? Может быть есть причина?
А почти все стандарты на шифрование, хэширование, подписи и пр. идут от NIST, который имеет давние исторические связи с NSA. А Нил Коблитц предупреждал, что криптографическое сообщество коррумпировано с двух сторон: со стороны госструктур, которые дают основные заказы и контролируют даже частные университеты в западных странах и со стороны коммерческих структур, которым нужна чаще видимость безопасности, маркетинг и экономия на всём. А вы что хотели?
Кроме описания, там есть псевдокод
Этот стандарт от NIST появился позже.
Это как нибудь обосновано, или просто красивое оформление для
бэкдора"потолка"(с которого всё, в конечном счёте, и берётся)?Так ведь исходники то старые. А если в новых сервис паках вдруг обнаружится "улучшение"? Тогда уж надо использовать те старые исходники, или искать восстановленные реверсинженирингом новые.
От балды это якобы придумано, от чего же ещё?
Бэкдор потолка? В потолке открылся люк, не волнуйся – это глюк! ;-)
Это и есть обоснование того, что числа взяты с потолка, а не злонамереным образом. Вероятность нахождения уязвимых "обоснованых" чисел гораздо меньше, чем произвольно выбраных.
Я сейчас раздизасмил 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[link7]
В общем, использовать этот 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 и его источников энтропии.
А не сделать ли из каждого источника энтропии линейный конгруэнтный генератор[link8]? Например так:
seed.seed1 = PsGetCurrentProcess();
seed.seed1 = 1664525*seed.seed1+1013904223;
В этом случае не будет существенна скорость изменения источника.
Если производительность не критична, можно 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++)
А зачем же тогда конкурс объявили[link9]?
Лучше Whirlpool[link10], но это надо добавлять ещё код, а AES уже присутствует.
Имеет. Счетчик числа reseed не совсем предсказуемая величина. Не имеет смысла конструкция вида seed.seed24 += 5
Не согласен, начальное значение seed5 неизвестно и изменяется в зависимости от вызывающего кода.
Не, Whirlpool слишком уж громоздкий и тормозной, и с ним частый reseed будет серьезно задерживать к примеру открытые тома (при этой операции вызывается rnd_reseed_now). Ну а использовать Whirlpool только в rnd_get_bytes... так это получиться уже 3 разных хеша в программе, а нафиг оно надо? Вот выйдет стандарт sha-3, тогда посмотрим стоит ли менять все на него или нет.
Генерация истинно случайных чисел на основе шума звуковых карт[link11] Там ещё есть список литературы.
В контексте этой дискуссии интерес может представлять то, как реализован ГСЧ в PGP[link12].
Очень мутно и неясно там сделано. В моем ГСЧ одним из достоинств является простота, благодаря чему очень легко понять на чем основана его стойкость.
В близжайшее время я напишу статью с подробным исследованием свойств своего ГСЧ.
AES'у ещё туда добавьте!
Ещё это сглаживается негативный эффект от слишком частого reseed'а: Почему же не сделали?
Потому что я затрудняюсь предсказать эффект от наложения куска памяти из стека на значения возврата апи. Вдруг там будет противоположное число? Тогда можно только ухудшить результат.
Лучше будет хешировать все данные перед добавлением в пул, и за счет этого сократить число полных микширований пула, что позволит увеличить производительность reseed и повесить его на большее число разных событий.
В этом и есть суть случайности! :)
Ну хорошо, если вы боитесь непредсказуемости значений неинициализированных переменных, проинициализируйте их! А при получении новых "случайных" значений лучше будет использовать и значения, полученные ранее (например, как было сказано выше, используя += вместо = ) – таким образом, выход будет зависеть от всех "случайных" значений, что были за время работы генератора, а не только от тех, что в момент вызова очередного reseed'а.
хм...
Я неточно выразился. Я затрудняюсь сказать не вызовет ли это понижения реальной энтропии за счет корреляций в входных данных.
Генератор с самого начала сделан так, что выход зависит от всех значений, т.к. при добавлении случайных данных в пул старые значения не удаляются. Но корелляции здесь замаскированы хешированием, и не могут привести к снижению энтропии.
В данном случае увеличение производительности reseed напрямую ведет к увеличению безопасности, так как позволит собирать энтропию от большего числа событый.
В dc 0.3 введен еще один prng предназначеный для быстрой генерации случайных чисел для затирания старого содержимого секторов диска. Он основан на AES в режиме CTR, и инициализируется от основного rng.
Код последней версии rng вы можете посмотреть здесь http://freed0m.org/prng.c
Сейчас я немного перерабатываю архитектуру генератора с целью сделать его свойства более обосноваными и пишу статью с их обоснованием.
Блок-схема нового варианта выглядит так:
Краткое описание алгоритма: Входные данные с малой энтропией подаются на вход rng в качестве seed. Здесь они хешируются вместе с счетчиком числа reseed и timestamp, добавление этих параметров нужно для предотавращения появления одинаковых значений на выходе хеша при одинаковых входных seed, и как следствие – зацикливания значений в пуле. Информация добавляется в пул путем сложения по модулю 28 с уже имеющимся содержимым.
Mix function – функция перемешивающся пул, т.е. создающая нелинейную зависимость между всеми битами пула. Функция построена на sha512 хешах и имеет свойство однонаправлености. Мишкирование пула применяется перед извлечением случайных чисел и после него.
Извлечение данных из пула происходит через хеш для предотвращения утечки содержимого пула. При извлечении каждых 512 бит данных хешируется 512 битный кусок пула, размер оставшегося для извлечения куска и счетчик числа извлечений данных из пула. Цель добавления этих двух переменных опять же в получении разных выходных значений при одинаковом значении пула.
Прошу прокомментировать эту схему.
Везде используется SHA – а вот если его взломают? Может где-то лучше использовать AES?
AES? А может его взломают?
SHA обладает важным свойством – одностороннестью.
Вероятность взлома SHA и AES меньше вероятности взлома только SHA.
AES, при неизвестном пароле, тоже.
И откуда ключ брать? Случайно генерировать? А каким ГСЧ? :)
Одно из свойств ГСЧ которого я хочу добиться – сохранение backward security при компрометации злоумышлеником содержимого памяти после генерации ключей.
Представим что злоумышленик узнал значание пула генератора. В моей схеме перемешивание пула при генерации происходит два раза: до нее (что создает зависимость выдаваемого числа от всех битов пула) и после (что защищает от компрометации сгенерированых ранее ключей атакой на память).
Т.е. для компрометации уже сгенерированых ключей атакующий должен будет обратить следующую конструкцию:
pool0 = pool0 + SHA(pool0 || pool1 ... pooln)
pool1 = pool1 + SHA(SHA(pool0 || pool1 ... pooln) || pool1 ... pooln)
...
Давайте теперь подумаем насколько критичен генератор к свойствам SHA. В данном случае критически важное свойство хеш-функции – равномерное статистические распределение выхода при неравномерном входе. Эта характеристика обеспечивает равномерное распределение генерируемых ключей.
Допустим атакующий может получить коллизию хеша. Что это ему дает?
Допустим атакующий может найти второй прообраз. Что это ему дает?
Очевидно, что если генерируется менее 640 байт случайных чисел за время накопления такой энтропии, то атакующий бессилен даже в случае возможности полностью реверсировать SHA за одну операцию, потому что результат генерации будет не псевдослучайным, а истинно случайным.
Есть общие соображения, которые не надо принимать как руководство к действию и из которых я сам пока не могу сделать никаких конкретных выводов ;-)
Рассмотрим чисто гипотетическую ситуацию, упрощенную, которая никогда не может произойти в реальности. Есть некий вымышленный суперпротивник, который умеет и хэши за какое-то конечное время инвертировать и процессы внутри компьютера предсказывать.
Предположим, что такой идеализированный противник в некоторый момент времени смог подобрать значение счётчиков и таймера, и построить модель, которая ловко подбирает и эти значения, и значения низкоэнтропийных данных на входе и получить нужную часть значений выхода. Поскольку возможности такого противника стремятся к бесконечности или к максимальному пределу, то с точки зрения такого противника суммарная энтропия данных, поступающая на вход генератора равна нулю. Тогда вычисленная, фиктивная энтропия пула для него быстро исчерпается и тоже станет равной как бы нулю, он раскроет внутреннее значение пула. При сохранении своих возможностей он сможет предсказывать значения генератора.
Понятно, что защититься от такого противника невозможно. Но можно значительно уменьшить вероятность появления для него удобного момента для атаки, сведя время его ожидания к большой величине, затруднить построение гипотетической модели предсказания низкоэнтропийных данных до предела, а вероятность атаки сделать близкой к нулю.
И нужно это не только для теоретических упражнений. это используется в качестве предпосылок доказательства, что генератор действительно хорошо справляется с задачей получения малого количества криптостойких высокоэнтропийных данных из большого количества низкоэнтропийных.
Одно из решений было предложено Шнайером и компанией в ГПСЧ Фортуна.
Он предложил ввести не один пул, а много (32 штуки), причём каждый последующий заполняется в два раза медленнее предыдущего, таким образом последний переполнится только через 12 лет, когда компьютер скорее всего можно будет выкинуть.
Перед выходом генератора берётся хэш значение всех пулов. таким образом убивается много зайцев сразу.
Батарея пулов будет хранить энтропию от всех наработанных состояний генератора, таким образом противник не сможет дождаться её исчерпания и падения до минимума, даже если начнёт предсказывать или контролировать события на входе, а для построения модели входов ему нужно будет учесть все когда-либо поступившие в генератор данные с момента его запуска, а не за какой-то конкретный интервал (на самом деле это упрощение, всё несколько сложнее).
Кроме того, таким образом более равномерно перемешиваются данные от быстрых и медленных источников энтропии, какими бы медленными они не были. Даже если какой-то непрактичный источник генерирует 1 бит в сутки, то за год 256 бит набрать можно и они корректно смешаются с быстрыми источниками!
Другое дело, что всё это имеет смысл только если генератор работает непрерывно (например на уровне ядра ОС) и в течении долгого времени до начала генерации ключа. Кроме того, желательно, чтобы после генерации ключа и до начала атаки тоже прошло побольше времени. Т.е. и свойство PFS и защита от идеализированного противника не абсолютны.
Генератор Фортуна не был взломан или убедительно атакован. Но такой дизайн почему-то подвергался множеству критических замечаний со стороны криптографов. В чём там точно дело, может в избыточности и непрактичности?
Однако предлагались ГПСЧ с двумя пулами – быстрым и медленным, или рабочим и ключевым (из которого данные напрямую не считываются).
Кроме того, Шнайер предлагал использовать хэш (SHA) и блочный шифр (AES или любой другой приемлемый) обязательно совместно. Всё объяснение сводилось к тому, что любые хэш-функции в рамках его конструкции ненадёжны, они выполняют только впомогательную роль, на совместном использовании блочного шифра настаивалось.
Практически никто из криптографов такой запутанный комплексный дизайн не одобрил и все генераторы стараются строить только на одном криптопримитиве (или блочный шифр, или хэш, или MAC, ну не считая экзотики из области теории чисел).
В других работах предлагалась ещё такая экзотическая идея – после любой операции с пулом (считывание-подмешивание данных) или хотя бы серии операций (чтобы не делать слишком много вычислении подряд), перемешивать весь пул. Т.е., если бы размер пула был 4096 байт, его бы следовало обрабатывать не блоками хэшей с выходом 512 бит, а некой гипотетической хэш-функцией с выходом 4096*8 бит. Понятно, что такая криптографическая функция может быть только составной. Например используются специальные режимы шифрования (CBC-счётчик), упакованные в трёхраундовую сеть Файстеля с использованием ключевого пула для полного перемешивания рабочего пула.
Однако это тоже сложно, избыточно и ресурсоёмко. Чтобы уменьшить ресурсоёмкость применяют различные хитрости, которые к сожалению делают генераторы ещё более запутанными.
Кажется, что конкретной пользы от всех этих рассуждений мало, но почему-то в теоретических работах делают гораздо более сильные допущения о возможностях атакующего, пытаются построить более сильную защиту, а потом доказывают, что её теоретическая стойкость меньше, чем 2128. Вообще, стойкость генератора оценить сложно, с одной стороны эти мифические шаги атаки частично привязаны к медленной пользовательской машине, а не к суперкомпьютеру взломщика, с другой стороны модель угрозы не такая, как для других протоколов.
Новая схема RNG с учетом вышесказаного:
Я решил добавить сюда ключевой пул который заполняется параллельно с основным, но его содержимое никогда не выводиться. Он используется в качестве ключа, которым зашифровывается выход хеша. Моя конструкция и так производительностью не отличается, так что добавление в нее AES особо не скажется на производительности.
Теоретически теперь стойкость к предсказанию пула опирается сразу на два криптопримитива: AES и SHA-512. Если атакующий может взломать их оба сразу, то защищаться от него бесполезно, т.к. в этом случае проще будет атаковать не ГСЧ, а сами зашифрованые данные.
Для сведения вероятности этого к нулю, у меня используется избыточное количество источников энтропии. Здесь я не буду перечислять их все, т.к. позже я собираюсь описать все это в статье.