Безопасное смешивание источников энтропии

Question

Давайте предположим, что мы генерируем очень большие (например, 128 или 256-битные) числа, которые служат ключами для блочного шифра.

Давайте далее предположим, что мы носим шляпы из фольги (по крайней мере, когда снаружи).

Будучи настолько параноиком, мы хотим быть уверенными в нашей доступной энтропии, но мы не полностью доверяем какому-либо конкретному источнику.Может быть, правительство фальсифицирует наши монеты.Может быть, эти кости очень тонко взвешены.Что, если аппаратные прерывания, поступающие в /dev/random, будут немного слишком согласованными?(Помимо того, что мы параноики, мы настолько ленивы, что не хотим создавать все вручную ...)

Итак, давайте смешаем их все.

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

Достаточно ли использовать SHA-256 поверх объединенных байтов?

(И да, в какой-то момент я собираюсь забрать копию Cryptography Engineering.:))

Answer 1

Поскольку вы упоминаете /dev/random - по крайней мере, в Linux, /dev/random питается алгоритмом, который делает очень многое из того, что вы описываете. Он берет несколько источников энтропии с различным доверием и смешивает их в «пул энтропии», используя полиномиальную функцию - для каждого входящего нового байта энтропии он xor'd в пул, а затем весь пул перемешивается с смешивающая функция. Когда необходимо получить некоторую случайность из пула, весь пул хэшируется с помощью SHA-1 для получения выходных данных, затем пул снова смешивается (и на самом деле происходит еще несколько хеширования, свертывания и искажения, чтобы убедиться, что реверсировать процесс примерно так же сложно, как реверсировать SHA-1). В то же время происходит множество операций учета - каждый раз, когда некоторая энтропия добавляется в пул, оценка количества битов энтропии, которые она стоит, добавляется в учетную запись, и каждый раз, когда некоторые байты извлекаются из В пуле это число вычитается, и случайное устройство блокируется (в ожидании большей внешней энтропии), если учетная запись опустится ниже нуля. Конечно, если вы используете «случайное» устройство, блокировка не происходит, и пул просто продолжает хэшироваться и смешиваться, чтобы генерировать больше байтов, что превращает его в PRNG вместо RNG.

Во всяком случае ... это на самом деле довольно интересно и довольно хорошо прокомментировано - вы можете изучить его. drivers/char/random.c в дереве linux-2.6.

Answer 2

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

Это не отличается от подхода, используемого при растягивании ключа (хотя здесь нет необходимости в нескольких итерациях).

Answer 3

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

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

Если вам случится быть невероятно параноидальным и иметь немного денег, это можетбыло бы весело купить «правду» (в зависимости от того, насколько вы убеждены в квантовой механике) Квантовый генератор случайных чисел .

- Правка:

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

Answer 4

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

Самым простым алгоритмом является (улучшенный) алгоритм Ван Неймана. Вы можете найти детали в этом PDF: http://security1.win.tue.nl/~bskoric/physsec/files/PhysSec_LectureNotes.pdf на странице 27.

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