9.6. $RANDOM: генерация псевдослучайных целых чисел
$RANDOM — внутренняя функция Bash (не константа), которая возвращает псевдослучайные целые числа в диапазоне 0 — 32767. Функция $RANDOM не должна использоваться для генераци ключей шифрования.
Пример 9-23. Генерация случайных чисел
Пример 9-24. Выбор случайной карты из колоды
Jipe подсказал еще один способ генерации случайных чисел из заданного диапазона.
Насколько случайны числа, возвращаемые функцией $RANDOM? Лучший способ оценить «случайность» генерируемых чисел — это написать сценарий, который будет имитировать бросание игрального кубика достаточно большое число раз, а затем выведет количество выпадений каждой из граней.
Пример 9-25. Имитация бросания кубика с помощью RANDOM
Как видно из последнего примера, неплохо было бы производить переустановку начального числа генератора случайных чисел RANDOM перед тем, как начать работу с ним. Если используется одно и то же начальное число, то генератор RANDOM будет выдавать одну и ту же последовательность чисел. (Это совпадает с поведением функции random() в языке C.)
Пример 9-26. Переустановка RANDOM
Системный генератор /dev/urandom дает последовательность псевдослучайных чисел с более равномерным распределением, чем $RANDOM. Команда dd if=/dev/urandom of=targetfile bs=1 count=XX создает файл, содержащий последовательность псевдослучайных чисел. Однако, эти числа требуют дополнительной обработки, например с помощью команды od (этот прием используется в примере выше) или dd (см. Пример 12-42).
Есть и другие способы генерации псевдослучайных последовательностей в сценариях. Awk имеет для этого достаточно удобные средства.
Пример 9-27. Получение псевдослучайных чисел с помощью awk
Случайные числа в Linux(RNG) или как «наполнить» /dev/random и /dev/urandom
Пожалуй всем пользователям Linux известны такие файлы псевдо-устройств как /dev/random и /dev/urandom. Эти устройства являются интерфейсом к генератору случайных чисел ядра(RNG, random number generator).
Случайные числа(они же — непредсказуемый набор битов) очень важны в криптографии. Они являются базовыми кирпичиками для криптографических протоколов. От качества (неповторимости, непредсказуемости) этих чисел зависит стойкость всевозможных TLS-сертификатов, SSH и GPG ключей, сессионных симметричных TLS-ключей и т.д. Так же случайные числа являются основой для генерации UUID’ов, PID’ов, TCP sequence numbers и многого другого.
RNG генерит случайные числа на основе данных из пула энтропии(entropy pool) в ядре Linux. Наполнением этого пула так же занимается RNG и делается это на основе случайных событий в системе таких как: тайминги клавиатуры и дисков, движения мыши, прерывания(interrupts), сетевой трафик.
Пул энтропии имеет фиксированный объем 4096 bits:
Размер пула нельзя изменить, это захардкожено в ядре.
Посмотреть текущий объем данных в пуле:
Доступный объем энтропии постоянно меняется, в зависимости от скорости пополнения и потребления соответственно.
Собственно через /dev/random и /dev/urandom приложения в user space получают эти самые случайные числа\данные.
/dev/random является источником случайных данных наивысшего качества которые может предоставить ядро. Но при этом он блокирующийся, что означает, что приложение читающее из /dev/random повиснет в ожидании данных если пул энтропии окажется пустым.
/dev/urandom — unlimited random, не блокирующийся и приложения могут читать из него бесконечно. Предоставляет случайные данные такого же высокого качества что и /dev/random но до тех пор пока пул энтропии не опустеет. Когда пул будет пустым, /dev/urandom продолжит выдавать случайные данные но теоретически сильно меньшего качества.
Настоятельно рекомендуется для любых долго-живущих ключей, например для TLS-сертификатов использовать /dev/random т.к. только он гарантирует качество случайных чисел. Но, большинство приложений таких как Apache, Nginx, sshd и о Боже ssh-keygen, openssl используют /dev/urandom. Тут в принципе понятно Apache, Nginx, sshd не хотят блокироваться при генерации сессионных ключей. Но то, что ssh-keygen и openssl используют по умолчанию /dev/urandom меня поразило. Причем для openssl можно задать устройство при генерации ключей(ниже пример) а вот для ssh-keygen я возможности переопределить поведение не нашел.
В общем не важно откуда читают ваши приложения, нельзя допускать опустошение этого самого пула энтропии и тогда счастье будет и с /dev/urandom.
Прежде чем начать “майнить” энтропию, пара слов о ее корректном использовании из man /dev/random:
The amount of seed material required to generate a cryptographic key equals the effective key size of the key. For example, a 3072-bit RSA or Diffie-Hellman private key has an effective key size of 128 bits (it requires about 2^128 operations to break) so a key generator only needs 128 bits (16 bytes) of seed material from /dev/random.
Например openssl для генерации RSA ключа длиной 10240 bit использует всего 2048 исходного материала из /dev/random:
Как заполнить пул энтропии?
Лучшее решение это использование специальных аппаратных средств(TPM, Trusted Platform Module) или инструкций процессора типа RDRAND(есть в Intel IvyBridge и Haswell процессорах).
Проверить наличие подобных устройств на сервере поможет утилита rngd из пакета rng-tools
Если rngd обнаружит поддерживаемые средства то вам повезло и вы можете запустить сервис rngd. В моем случае их нет)
Собственно задача rngd читать энтропию из аппаратных средств и наполнять ей пул энтропии ядра. Делается это через специальный ioctl вызов(RNDADDENTROPY) интерфейса /dev/random.
Если нет аппаратной поддержки
В интернете можно встретить рекомендации, где предлагают указывать /dev/urandom как источник энтропии для rngd. То есть источником энтропии для ядра по сути будет само ядро). Это довольно сомнительная идея, и я бы не стал так делать и вам не советую. Но ради эксперимента я провел тесты и результаты(которые ниже) тоже довольно не плохие.
Havegd
В основе лежит алгоритм HAVAGE который генерирует энтропию на основе счётчиков и состояний процессора. В силу сложного, многоуровневого устройства процессоров, один и тот же код всегда выполняется за разное время и это не постоянство является основой для алгоритма HAVAGE.
На практике, это user space демон который как и rngd наполняет пул энтропии ядра через ioctl интерфейс /dev/random. при этом не нуждается в источнике энтропии как rngd.
Для centos пакет доступен из epel.
После установки нужно просто запустить сервис. С параметрами по умолчанию haveged будет стараться держать пул энтропии ядра на уровне не ниже 1024.
Тестирование
Без rngd и haveged, команда(ниже будет понятно, что она делает):
Не завершилась за сутки!
rngd с /dev/urandom в качестве источника энтропии
(то, что я вам не рекомендовал)
Тест(худший из 3-х результат):
Тут нужно смотреть на successes, failures, и на input channel speed.
При этом утилизация CPU процессом rngd: 57%
haveged
Тест(худший из 3-х результат):
При этом утилизация CPU процессом haveged:12%
Виртуальные машины
Не рекомендуется использовать haveged внутри ВМ, т.к. там вроде как счетчики CPU не такие точные(типа округляются) и это сказывается на качестве энтропии. Тру путь это использовать virt-ioRNG(qemu-kvm) — паравиртуальное устройство которое будет брать энтропию из пула хоста. Но, это уже совсем другая история…)
Заметил, что в линуксе сей процесс происходит намного медленне, чем в винде и это не зависит от используемого языка программирования. Причём, винда стоит под виртуальной машиной, но один и тот же код с генерацией этих чисел выполняется там в среднем в 2 раза быстрее, чем под линуксом.
Где-то в интернете нашёл, что в линуксе по-умолчанию используется криптостойкий генератор случайных чисел, в то время как в винде — обыкновенный.
Собственно, кто-нибудь знает точно в чём причина такого поведения?
Re: Генерация случайных чисел в Linux и Windows
А вы там, часом /dev/random читаете? Тогда попробуйте /dev/urandom, если, конечно, важна именно скорость.
/dev/random конечно медленнее, но оттуда имеет смысл брать только один из seed для генерации ключей и прочего. А на тривиальную генерацию хватает urandom
Re: Генерация случайных чисел в Linux и Windows
> Заметил, что в линуксе сей процесс происходит намного медленне, чем в винде
Что вообще подразумевается под «генератором случайных чисел ОСи»? «генератора случайных чисел независимо от языка программирования»? Какие конкретно генераторы сравнивались? И каким образом происходило сравнение? А-то заявление выглядит бредово. Код в студию.
Re: Генерация случайных чисел в Linux и Windows
Да я понимаю, что первое сообщение немного странное получилось. 🙂 Просто дело в том, что несколько раз приходилось писать небольшие программки, в которых производительность очень сильно зависила от генерации случайных чисел. В итоге получалось, что под виртуальной машиной с виндой они работали примерно в 2 раза быстрее, чем на основной системе с линуксом. Опытным путём установил, что всё дело в собственно генерации. Подобное наблюдалось со стандартным C’шным rand(), с Qt’шным потоко-безопасным qrand() и с D’шным собственным движком. Стало любопытно, в чём же дело. 🙂
Конкретный код пока, к сожалению, привести не могу, ибо там будет очень много мусора, не касающегося темы. Сейчас как раз пытаюсь создать минимально-воспроизводимый пример.
