Как операционная система создает энтропию для случайных семян?

В Linux файлы /dev/randomи/dev/urandom файлы являются блокирующими и неблокирующими (соответственно) источниками псевдослучайных байтов.

Их можно читать как обычные файлы:

$ hexdump /dev/random
0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa
0000010 5652 1f08 ccb8 9ee2 d85c 7c6b ddb2 bcbe
0000020 f841 bd90 9e7c 5be2 eecc e395 5971 ab7f
0000030 864f d402 74dd 1aa8 925d 8a80 de75 a0e3
0000040 cb64 4422 02f7 0c50 6174 f725 0653 2444
...

Многие другие варианты Unix предоставляют /dev/randomи /dev/urandomбез различий между блокировкой и неблокировкой.

Эквивалент Windows - это CryptGenRandom()функция .

Как операционная система генерирует псевдослучайность?

Название и тело вашего вопроса задать два разных вопроса: как операционная система создает энтропии (это должно быть действительно Получает энтропии), и как он генерирует псевдо-хаотичность от этой энтропии. Я начну с объяснения разницы.

Откуда берется случайность?

Генераторы случайных чисел (ГСЧ) бывают двух типов:

• Генераторы псевдослучайных чисел (PRNG), также называемые генераторами детерминированных случайных битов (DRBG) или их комбинациями, являются детерминированными алгоритмами, которые поддерживают внутреннее состояние переменной фиксированного размера и вычисляют их выходные данные из этого состояния.
• Аппаратный генератор случайных чисел (HRNG), также называемый «истинными» генераторами случайных чисел, основан на физических явлениях. «Правда» - это немного неправильное название, потому что нет источников информации, которые, как известно, являются действительно случайными , есть только источники информации, которые, как известно, не являются предсказуемыми.

Некоторые приложения, такие как моделирование физических явлений, могут удовлетворяться случайными числами, которые проходят статистические тесты. Другие приложения, такие как генерация криптографических ключей, требуют более сильного свойства: непредсказуемости . Непредсказуемость - это свойство безопасности, а не (только) статистическое свойство: это означает, что злоумышленник не может угадать выходные данные генератора случайных чисел. (Точнее, вы можете измерить качество ГСЧ, измерив вероятность того, что злоумышленник угадает каждый бит выхода ГСЧ. Если вероятность заметно отличается от 1/2, ГСЧ является плохим.)

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

Криптография требует секретности : злоумышленник не должен быть в состоянии выяснить данные, которые вошли в условия. Существуют криптографически безопасные генераторы псевдослучайных чисел (CSPRNG): алгоритмы PRNG, выходные данные которых пригодны для использования в криптографических приложениях, в дополнение к хорошим статистическим свойствам . Одним из свойств, которые делают CSPRNG криптографически безопасным, является то, что его выходные данные не позволяют злоумышленнику восстановить внутреннее состояние (знание всех битов, кроме одного, созданного CSPRNG, не помогает найти пропущенный бит). Я не буду вдаваться в то, как сделать CSPRNG, потому что это легко - вы можете следовать рецептам, данным профессиональными криптографами (используйте стандартныйалгоритм, такой как Hash_DRBG, HMAC_DRBG или CTR_DRBG от NIST SP 800-90A ) или ANSI X9.31 PRNG . CSPRNG требует два свойства своего состояния для обеспечения безопасности:

• Состояние должно храниться в тайне с самого начала и всегда (хотя раскрытие состояния не будет раскрывать прошлые результаты).
• Состояние должно быть линейным: RNG никогда не должен запускаться дважды из одного и того же состояния.

Архитектура генератора случайных чисел

На практике почти все хорошие генераторы случайных чисел объединяют CSPRNG с одним или несколькими источниками энтропии . Короче говоря, энтропия - это мера непредсказуемости источника данных. Основать генератор случайных чисел исключительно на аппаратном RNG сложно:

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

Таким образом, ГСЧ в операционной системе почти всегда работает так :

1. Накопить достаточную энтропию, чтобы построить непредсказуемое внутреннее состояние.
2. Запустите CSPRNG , используя накопленную энтропию в качестве начального числа, то есть в качестве начального значения внутреннего состояния.
3. По желанию периодически смешивайте дополнительную энтропию во внутреннем состоянии. (Это не является строго необходимым, поскольку энтропия не «расходуется» с какой-либо измеримой скоростью . Она помогает против определенных угроз, которые протекают в состоянии ГСЧ без ущерба для всей системы.)

Служба генерации случайных чисел является частью работы операционной системы, потому что для сбора энтропии требуется доступ к оборудованию, а источники энтропии составляют общий ресурс: операционная система должна собирать их и извлекать из них выходные данные, которые подходят для приложений. В операционной системе требуется псевдослучайное кондиционирование источников энтропии; он также может быть криптографически безопасным, поскольку это не является принципиально сложным (и это требуется в операционных системах, где приложения не доверяют друг другу; в полностью взаимодействующих системах каждое приложение должно было бы запускать свой собственный CSPRNG внутри, если операционная система все равно не предоставил)

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

Некоторое внимание должно быть уделено сохраненному состоянию. Помните, как я сказал, что состояние должно быть линейным? Если вы дважды загрузитесь с одного и того же состояния диска, вы получите одинаковые выходные данные ГСЧ. Если это возможно в вашей среде, вам нужен другой источник энтропии. Будьте осторожны при восстановлении из резервных копий или при клонировании виртуальной машины . Одним из методов клонирования является смешивание сохраненной энтропии с некоторыми данными об окружающей среде, которые являются предсказуемыми, но уникальными (например, время и MAC-адрес); имейте в виду, что если данные среды предсказуемы, любой, кто владеет сохраненным состоянием ВМ, может восстановить начальное значение разветвленного экземпляра ВМ.

Источники энтропии

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

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

• тепловой шум
• лавинный шум от лавинного шума
• различные типы (комбинации) генераторов , такие как кольцевые генераторы
• радиоактивный распад
• различные квантовые явления, которые я не мог объяснить
• акустический шум
• шум камеры

NIST SP800-90B содержит рекомендации по проектированию аппаратного обеспечения ГСЧ. Оценить аппаратный RNG сложно . Аппаратный ГСЧ, как правило, - это деликатные звери, которых нужно использовать с осторожностью: многим типам требуется некоторое время после загрузки и некоторое время между считываниями для дестабилизации, они часто чувствительны к условиям окружающей среды, таким как температура и т. Д.

Процессоры Intel x86-64, основанные на архитектуре Ivy Bridge, предоставляют RdRandинструкцию, которая обеспечивает вывод из CSPRNG, засеянного тепловым шумом . Большинство процессоров смартфонов содержат аппаратный источник энтропии, хотя Android не всегда использует его.

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

Если вы хотите посмотреть на пример, вы можете взглянуть на Linux, но будьте осторожны, что он не идеален . В частности, /dev/randomблокирует слишком часто (потому что блокирует до тех пор, пока не будет доступно достаточно энтропии, с чрезмерно консервативным представлением об энтропии), тогда /dev/urandomкак почти всегда хорошо, за исключением первой загрузки, но не дает указаний, когда у него недостаточно энтропии. В Linux есть драйверы для многих устройств HRNG , и в них накапливается энтропия от различных устройств (включая устройства ввода ) и тайминги дисков .

Если у вас есть (конфиденциальное) постоянное хранилище, вы можете использовать его для сохранения энтропии от одной загрузки к другой, как указано выше. Первой загрузки является деликатным время: система может находиться в довольно предсказуемом состоянии в тот момент, особенно на серийных устройствах , которые в основном работают с завода таким же образом. Некоторым встроенным устройствам, которые имеют постоянное хранилище, предоставляется начальное начальное значение на фабрике (произведенное ГСЧ, работающим на компьютере на фабрике). В виртуализированных серверных средах начальная энтропия может быть обеспечена при создании экземпляра виртуальной машины с хоста или с энтропийного сервера.

Плохо посеянные устройства являются широко распространенной проблемой на практике - исследование открытых ключей RSA показало, что многие серверы и устройства имели ключи, которые были сгенерированы с плохим ГСЧ, скорее всего, с хорошим ГСЧ, который был заполнен недостаточно. Как разработчик ОС, вы не можете решить эту проблему самостоятельно: задача субъекта, управляющего цепочкой развертывания, состоит в том, чтобы гарантировать, что RNG будет правильно посеян при первой загрузке. Ваша задача как разработчика ОС состоит в том, чтобы предоставить надлежащий RNG, включая интерфейс для обеспечения этого первого начального числа, и обеспечить надлежащую сигнализацию об ошибках, если RNG используется до того, как он будет правильно посеян.

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

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