Введение
Файл генератора псевдослучайных чисел в Unix-подобных операционных системах
В Unix-подобных операционных системах `/dev/random` и `/dev/urandom` являются специальными файлами, которые служат в качестве криптографически безопасных генераторов псевдослучайных чисел (CSPRNG). Они обеспечивают доступ к CSPRNG, который инициализируется энтропией, полученной из шума окружающей среды, собираемой драйверами устройств и другими источниками. Ранее `/dev/random` обычно блокировался, если доступной энтропии было меньше, чем запрошено; в последнее время (см. ниже различия между операционными системами) он обычно блокируется при запуске, пока не будет собрано достаточно энтропии, а затем разблокируется навсегда. Устройство `/dev/urandom` обычно никогда не было блокирующим, даже если семя генератора псевдослучайных чисел не было полностью инициализировано энтропией с момента загрузки. Не все операционные системы реализуют одинаковые методы для `/dev/random` и `/dev/urandom`.
Этот специальный файл впервые появился в Linux в 1994 году. Он был быстро принят другими Unix-подобными операционными системами. В октябре 2016 года, с выпуском ядра Linux версии 4.8, реализация `/dev/random` в ядре была переключена на криптографический генератор псевдослучайных чисел (CPRNG) на основе ChaCha20, разработанный Теодор Цо на основе хорошо зарекомендовавшего себя потокового шифра ChaCha20 Бернштейна. Начиная с версии 5.17 ядра Linux, генератор случайных чисел перешел с использования криптографической хеш-функции SHA-1 в сборщике энтропии на BLAKE2s – более новую, быструю и безопасную хеш-функцию.
In Unix like operating systems, and are special files that serve as cryptographically secure pseudorandom number generators (CSPRNGs). They allow access to a CSPRNG that is seeded with entropy from environmental noise, collected from device drivers and other sources. typically blocked if there was less entropy available than requested; more recently (see below for the differences between operating systems) it usually blocks at startup until sufficient entropy has been gathered, then unblocks permanently. The device typically was never a blocking device, even if the pseudorandom number generator seed was not fully initialized with entropy since boot. Not all operating systems implement the same methods for and
This special file originated in Linux in 1994. It was quickly adopted by other Unix like operating systems. In October 2016, with the release of Linux kernel version 4.8, the kernel's was switched over to a ChaCha20 based cryptographic pseudorandom number generator (CPRNG) implementation by Theodore Ts'o, based on Bernstein's well regarded stream cipher ChaCha20. Since version 5.17 of the Linux kernel, the random number generator switched from using the SHA 1 cryptographic hash function in the entropy collector to BLAKE2s, a newer, faster and more secure hash function.
Первоначальная реализация
Впервые генерация случайных чисел в пространстве ядра была реализована для Linux в 1994 году Теодором Цо. Реализация использовала криптографические хеш-функции, а не шифры, чтобы избежать ограничений на экспорт криптографии, действовавших на момент первоначальной разработки генератора. Реализация также была спроектирована с учетом того, что любая конкретная хеш-функция или шифр со временем может оказаться уязвимой, поэтому конструкция обеспечивает устойчивость к подобным слабостям. Быстрое восстановление после компрометации пула не рассматривается как требование, поскольку условия, необходимые для компрометации пула, достаточны для гораздо более простых и прямых атак на другие части операционной системы. В реализации Цо генератор поддерживает оценку количества бит энтропии в пуле энтропии. Из этого пула энтропии генерируются случайные числа. При чтении устройство возвращает только случайные байты в пределах предполагаемого количества бит энтропии в пуле. Если пул энтропии пуст, чтение блокируется до тех пор, пока не будет собрано дополнительное случайное воздействие из окружающей среды. Цель состоит в том, чтобы служить криптографически безопасным генератором псевдослучайных чисел, обеспечивающим максимально возможную энтропию выходных данных. Авторы рекомендуют использовать его для генерации криптографических ключей для защиты ценной информации или на длительный срок./ Неблокирующий источник случайных чисел
Также можно записывать данные в этот файл. Это позволяет любому пользователю добавлять случайные данные в пул. Неслучайные данные безвредны, поскольку только привилегированный пользователь может выполнить ioctl-вызов, необходимый для увеличения оценки энтропии. Текущее количество энтропии и размер пула энтропии ядра Linux, измеряемые в битах, доступны в файлах и могут быть отображены командами и соответственно.
Инъекция энтропии
Гаттерман, Пинкас и Рейнман в марте 2006 года опубликовали подробный криптографический анализ генератора случайных чисел Linux, в котором они описывают несколько уязвимостей. Наиболее серьезной проблемой, о которой они сообщают, является использование во встроенных или Live CD системах, таких как маршрутизаторы и бездисковые клиенты, где состояние загрузки предсказуемо, а доступный запас энтропии из окружающей среды может быть ограничен. Для системы с энергонезависимой памятью они рекомендуют сохранять часть состояния генератора случайных чисел при выключении, чтобы оно могло быть включено в состояние генератора при следующей перезагрузке. В случае маршрутизатора, для которого сетевой трафик является основным доступным источником энтропии, они отмечают, что сохранение состояния между перезагрузками "потребует от потенциальных злоумышленников либо перехвата всего сетевого трафика" с момента ввода маршрутизатора в эксплуатацию, либо получения прямого доступа к внутреннему состоянию маршрутизатора. Эта проблема, по их мнению, особенно критична для беспроводных маршрутизаторов, чей сетевой трафик можно перехватить на расстоянии, и которые могут использовать генератор случайных чисел для генерации ключей для шифрования данных. Ядро Linux поддерживает несколько аппаратных генераторов случайных чисел, при условии их установки. Необработанные данные с такого устройства можно получить из.
With Linux kernel 3.16 and newer, the kernel itself mixes data from hardware random number generators into on a sliding scale based on the definable entropy estimation quality of the HWRNG. This means that no userspace daemon, such as from , is needed to do that job. With Linux kernel 3.17+, the VirtIO RNG was modified to have a default quality defined above 0, and as such, is currently the only HWRNG mixed into by default. The entropy pool can be improved by programs like , , etc. With , hardware random number generators like Entropy Key, etc. can write to The diehard tests programs , and can test these random number generators.
Начиная с ядра Linux 3.16 и более поздних версий, само ядро смешивает данные от аппаратных генераторов случайных чисел в , используя скользящую шкалу, основанную на определяемом качестве оценки энтропии HWRNG. Это означает, что для выполнения этой задачи не требуется демон пользовательского пространства, такой как from. Начиная с ядра Linux 3.17+, VirtIO RNG был модифицирован для установки качества по умолчанию выше 0 и, следовательно, в настоящее время является единственным HWRNG, смешиваемым в по умолчанию. Пуль энтропии можно улучшить с помощью программ, таких как , , и т.д. С помощью аппаратных генераторов случайных чисел, таких как Entropy Key и т.д., можно записывать в. Программы тестирования, такие как , и , могут тестировать эти генераторы случайных чисел.
With Linux kernel 3.16 and newer, the kernel itself mixes data from hardware random number generators into on a sliding scale based on the definable entropy estimation quality of the HWRNG. This means that no userspace daemon, such as from , is needed to do that job. With Linux kernel 3.17+, the VirtIO RNG was modified to have a default quality defined above 0, and as such, is currently the only HWRNG mixed into by default. The entropy pool can be improved by programs like , , etc. With , hardware random number generators like Entropy Key, etc. can write to The diehard tests programs , and can test these random number generators.
Критика введения энтропии
В январе 2014 года Дэниел Бернштейн опубликовал критику подхода Linux к смешиванию различных источников энтропии. Он описывает атаку, в которой один источник энтропии, способный отслеживать другие источники энтропии, может изменять свой выход, чтобы нейтрализовать случайность остальных источников энтропии. Рассмотрим функцию H(x, y, z), где H – хеш-функция, а x, y и z – источники энтропии, причем z является результатом работы вредоносного HRNG Z: Z генерирует случайное значение r. Z вычисляет H(x, y, r). Если результат вычисления H(x, y, r) соответствует желаемому значению, то r выводится как z. В противном случае, повторить процесс с шага 1. Бернштейн оценил, что злоумышленнику потребуется повторить вычисление H(x, y, r) 16 раз, чтобы скомпрометировать DSA и ECDSA, заставив первые четыре бита выходных данных ГСЧ быть равными 0. Это возможно, поскольку Linux постоянно обновляет начальное значение H, вместо использования одного высококачественного начального значения.
Z generates a random value of r.
Z computes H(x,y,r). If the output of H(x,y,r) is equal to the desired value, output r as z. Else, repeat starting at 1. Bernstein estimated that an attacker would need to repeat H(x,y,r) 16 times to compromise DSA and ECDSA, by causing the first four bits of the RNG output to be 0. This is possible because Linux reseeds H on an ongoing basis instead of using a single high quality seed.
Системы BSD
Операционная система FreeBSD предоставляет связь с блоком Both только до момента его надлежащей инициализации. PRNG (Fortuna) FreeBSD регулярно переинициализируется и не пытается оценить энтропию. На системе с небольшим объемом сетевой и дисковой активности переинициализация происходит в течение доли секунды. Начиная с OpenBSD 5.1 (1 мая 2012 года) используется arc4random, функция CSPRNG, основанная на RC4. Функция была изменена на использование более надежного ChaCha20 с OpenBSD 5.5 (1 мая 2014 года). Система автоматически использует аппаратные генераторы случайных чисел (например, те, что предоставляются на некоторых шинах Intel PCI), если они доступны, через криптографический фреймворк OpenBSD. Был удален в OpenBSD 6.3 (15 апреля 2018 года). Реализация NetBSD устаревшего API также была переведена на ChaCha20.
macOS, iOS и другие операционные системы Apple
Все операционные системы Apple используют Fortuna как минимум с декабря 2019 года, возможно, и раньше. Алгоритм основан на SHA 256. В качестве источников энтропии используются различные параметры, такие как генератор случайных чисел защищенного анклава, джиттер времени фазы загрузки и аппаратные прерывания (предполагается временная составляющая). На компьютерах Mac на базе Intel, поддерживающих соответствующие инструкции, используются RDSEED/RDRAND. Данные начального значения (энтропии) также сохраняются для последующих перезагрузок. До перехода на Fortuna, macOS и iOS использовали 160-битный Yarrow, основанный на SHA 1. Между и нет никакой разницы; оба работают идентично.