оцените PRNG

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

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

В контексте этой дискуссии интерес может представлять то, как реализован ГСЧ в PGP.

Очень мутно и неясно там сделано. В моем ГСЧ одним из достоинств является простота, благодаря чему очень легко понять на чем основана его стойкость.
В близжайшее время я напишу статью с подробным исследованием свойств своего ГСЧ.

AES'у ещё туда добавьте!

> seed.seed1 += PsGetCurrentProcess();

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

Ещё это сглаживается негативный эффект от слишком частого reseed'а:

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

Почему же не сделали?

Почему же не сделали?

Потому что я затрудняюсь предсказать эффект от наложения куска памяти из стека на значения возврата апи. Вдруг там будет противоположное число? Тогда можно только ухудшить результат.

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

я затрудняюсь предсказать

В этом и есть суть случайности! :)

Ну хорошо, если вы боитесь непредсказуемости значений неинициализированных переменных, проинициализируйте их! А при получении новых "случайных" значений лучше будет использовать и значения, полученные ранее (например, как было сказано выше, используя += вместо = ) – таким образом, выход будет зависеть от всех "случайных" значений, что были за время работы генератора, а не только от тех, что в момент вызова очередного reseed'а.

интересует только безопасность, производительность не требуется

что позволит увеличить производительность reseed

хм...

В этом и есть суть случайности! :)

Я неточно выразился. Я затрудняюсь сказать не вызовет ли это понижения реальной энтропии за счет корреляций в входных данных.

таким образом, выход будет зависеть от всех "случайных" значений, что были за время работы генератора, а не только от тех, что в момент вызова очередного reseed'а.

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

хм...

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

В dc 0.3 введен еще один prng предназначеный для быстрой генерации случайных чисел для затирания старого содержимого секторов диска. Он основан на AES в режиме CTR, и инициализируется от основного rng.
Код последней версии rng вы можете посмотреть здесь http://freed0m.org/prng.c

Сейчас я немного перерабатываю архитектуру генератора с целью сделать его свойства более обосноваными и пишу статью с их обоснованием.
Блок-схема нового варианта выглядит так:

Краткое описание алгоритма: Входные данные с малой энтропией подаются на вход rng в качестве seed. Здесь они хешируются вместе с счетчиком числа reseed и timestamp, добавление этих параметров нужно для предотавращения появления одинаковых значений на выходе хеша при одинаковых входных seed, и как следствие – зацикливания значений в пуле. Информация добавляется в пул путем сложения по модулю 2⁸ с уже имеющимся содержимым.

Mix function – функция перемешивающся пул, т.е. создающая нелинейную зависимость между всеми битами пула. Функция построена на sha512 хешах и имеет свойство однонаправлености. Мишкирование пула применяется перед извлечением случайных чисел и после него.

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

Прошу прокомментировать эту схему.

Везде используется SHA – а вот если его взломают? Может где-то лучше использовать AES?

AES? А может его взломают?
SHA обладает важным свойством – одностороннестью.

AES? А может его взломают?

Вероятность взлома SHA и AES меньше вероятности взлома только SHA.

SHA обладает важным свойством – одностороннестью.

AES, при неизвестном пароле, тоже.

И откуда ключ брать? Случайно генерировать? А каким ГСЧ? :)

Одно из свойств ГСЧ которого я хочу добиться – сохранение backward security при компрометации злоумышлеником содержимого памяти после генерации ключей.
Представим что злоумышленик узнал значание пула генератора. В моей схеме перемешивание пула при генерации происходит два раза: до нее (что создает зависимость выдаваемого числа от всех битов пула) и после (что защищает от компрометации сгенерированых ранее ключей атакой на память).
Т.е. для компрометации уже сгенерированых ключей атакующий должен будет обратить следующую конструкцию:
pool₀ = pool₀ + SHA(pool₀ || pool₁ ... pool_n)
pool₁ = pool₁ + SHA(SHA(pool₀ || pool₁ ... pool_n) || pool₁ ... pool_n)
...

Давайте теперь подумаем насколько критичен генератор к свойствам SHA. В данном случае критически важное свойство хеш-функции – равномерное статистические распределение выхода при неравномерном входе. Эта характеристика обеспечивает равномерное распределение генерируемых ключей.

Допустим атакующий может получить коллизию хеша. Что это ему дает?
Допустим атакующий может найти второй прообраз. Что это ему дает?

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

Есть общие соображения, которые не надо принимать как руководство к действию и из которых я сам пока не могу сделать никаких конкретных выводов ;-)

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

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

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

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

Одно из решений было предложено Шнайером и компанией в ГПСЧ Фортуна.

Он предложил ввести не один пул, а много (32 штуки), причём каждый последующий заполняется в два раза медленнее предыдущего, таким образом последний переполнится только через 12 лет, когда компьютер скорее всего можно будет выкинуть.

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

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

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

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

Генератор Фортуна не был взломан или убедительно атакован. Но такой дизайн почему-то подвергался множеству критических замечаний со стороны криптографов. В чём там точно дело, может в избыточности и непрактичности?

Однако предлагались ГПСЧ с двумя пулами – быстрым и медленным, или рабочим и ключевым (из которого данные напрямую не считываются).

Кроме того, Шнайер предлагал использовать хэш (SHA) и блочный шифр (AES или любой другой приемлемый) обязательно совместно. Всё объяснение сводилось к тому, что любые хэш-функции в рамках его конструкции ненадёжны, они выполняют только впомогательную роль, на совместном использовании блочного шифра настаивалось.

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

В других работах предлагалась ещё такая экзотическая идея – после любой операции с пулом (считывание-подмешивание данных) или хотя бы серии операций (чтобы не делать слишком много вычислении подряд), перемешивать весь пул. Т.е., если бы размер пула был 4096 байт, его бы следовало обрабатывать не блоками хэшей с выходом 512 бит, а некой гипотетической хэш-функцией с выходом 4096*8 бит. Понятно, что такая криптографическая функция может быть только составной. Например используются специальные режимы шифрования (CBC-счётчик), упакованные в трёхраундовую сеть Файстеля с использованием ключевого пула для полного перемешивания рабочего пула.

Однако это тоже сложно, избыточно и ресурсоёмко. Чтобы уменьшить ресурсоёмкость применяют различные хитрости, которые к сожалению делают генераторы ещё более запутанными.

Кажется, что конкретной пользы от всех этих рассуждений мало, но почему-то в теоретических работах делают гораздо более сильные допущения о возможностях атакующего, пытаются построить более сильную защиту, а потом доказывают, что её теоретическая стойкость меньше, чем 2¹²⁸. Вообще, стойкость генератора оценить сложно, с одной стороны эти мифические шаги атаки частично привязаны к медленной пользовательской машине, а не к суперкомпьютеру взломщика, с другой стороны модель угрозы не такая, как для других протоколов.

Новая схема RNG с учетом вышесказаного:


Я решил добавить сюда ключевой пул который заполняется параллельно с основным, но его содержимое никогда не выводиться. Он используется в качестве ключа, которым зашифровывается выход хеша. Моя конструкция и так производительностью не отличается, так что добавление в нее AES особо не скажется на производительности.
Теоретически теперь стойкость к предсказанию пула опирается сразу на два криптопримитива: AES и SHA-512. Если атакующий может взломать их оба сразу, то защищаться от него бесполезно, т.к. в этом случае проще будет атаковать не ГСЧ, а сами зашифрованые данные.

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

Для сведения вероятности этого к нулю, у меня используется избыточное количество источников энтропии. Здесь я не буду перечислять их все, т.к. позже я собираюсь описать все это в статье.