Linux что такое entropy

Случайные числа в 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) — паравиртуальное устройство которое будет брать энтропию из пула хоста. Но, это уже совсем другая история…)

Источник

Entropy and randomness

Contents

Introduction

Entropy is described as ‘a numerical measure of the uncertainty of an outcome’ and is often associated with chaos or disorder however is often more simply called randomness.

It is important for a secure operating system to have sufficient quantities of entropy available for various crypotographic and non-cryptographic purposes, such as:

• Generation of cryptographic keys

• Address Space Layout Randomisation (ASLR) — used by default in Alpine of course 😉

• TCP port randomisation (NAT, outbound connection)

• TCP sequence number selection (see this too)

• Writing random files for testing network functionality and throughput

• Overwriting hard disks prior to reuse or resale or encryption

Entropy is contained within a pool, which draws its entropy from various sources. To view the current amount of entropy in the pool:

To view the maximum limit of entropy that the pool can hold:

On a standard system the limit is 4096 bits (512 bytes). The gr-sec patch used on Alpine increases this limit to 16384 bits (2048 bytes). Entropy is added to the pool in bits from various sources, «the relative number of unknown bits per event is roughly 8/keyboard, 12/mouse, 3/disk, 4/interrupt» source meaning that on a headless server (without mouse and keyboard attached), which ironically is often a system requiring the most entropy, entropy generation is somewhat limited.

The entropy from the pool can be accessed in two ways by default:

/dev/random — This is a blocking resource, so it will use available entropy from the pool. If more entropy is required than is available, the process will wait until more entropy is available in the pool. Due to this behaviour, /dev/random is best used where small amounts of high quality randomness are required, such as for cryptographic keys.

/dev/urandom — Is a non-blocking resource. It uses a seed value from the same entropy pool as /dev/random and therefore, if little entropy is available in the pool, it is recommended not to use /dev/urandom until more entropy is made available in the pool. It runs the seed value through an algorithm and so is a pseudo-random number generator, operating much faster than /dev/random. /dev/urandom is best used for non-cryptographic purposes such as overwriting disks.

Writing to /dev/random or /dev/urandom will update the entropy pool with the data written, but this will not result in a higher entropy count. This means that it will impact the contents read from both files, but it will not make reads from /dev/random faster. For more information see the random manpage

It is generally recommended wherever entropy is used heavily to supply additional entropy sources; some possibilities are below. Adding more sources of entropy to feed into the pool is a good idea. It makes an attackers job more difficult, because there will be more sources they have to gain control over (or at the very least observe at source), and adding more sources of entropy, even weak ones, can only result in higher entropy.

If you are desperate for more entropy and are working on a headless server with no internet connection, you could try generating some via disk activity. Just don’t expect any miracles! Here’s an example:

If your server is a ‘run-from-ram’ setup and so you have no disks to create churn but require more entropy, it is strongly recommended to add alternative entropy sources as discussed below.

Alternative/Additional entropy sources

Haveged

Haveged generates entropy based on CPU flutter. The entropy is buffered and fed into the entropy pool when write_wakeup_threshold is reached. Write a value (the number of bits) to it if you wish to change it:

echo «1024» > /proc/sys/kernel/random/write_wakeup_threshold

Or change it via haveged:

Install haveged, then start and set to autostart at boot:

apk -U add haveged && rc-service haveged start && rc-update add haveged

Further configuration is possible however the defaults should work fine out of the box.

Other possibilities

Some other possibilites for entropy generation are:

• timer entropy daemon — should provide on-demand entropy based on variances in timings of sleep command.

• video entropy daemon — requires a video4linux-device, gathers entropy by taking a couple of images and calculating the differences and then the entropy of that. Can be run on demand or as a cron job.

• audio entropy daemon — requires alsa development libraries and an audio device. Generates entropy by reading from audio device and de-baising data.

• GUChaos — «Give Us Chaos» provides on-demand entropy, by retrieving random blocks of bytes from the Random.org website, and transforms them with a polynumeric substitution cipher before adding them to /dev/random until the entropy pool is filled.

and hardware entropy generators such as:

It is also possible to replace /dev/random with EGD, the Entropy Gathering Daemon, or to use this on systems that are not able to support /dev/random. However, this is not required (or recommended) under normal circumstances.

Testing entropy with ENT

It is possible to test entropy to see how statistically random it is. Generally, such tests only reveal part of the picture, since some numbers can pass statistical entropy tests whilst they are not actually random. Failing a statistical randomness test is not a good indicator of course!

Make a folder for testing, and get hold of ENT:

Create some random data. In this example we read from /dev/urandom:

Run the ENT test against it:

Try the same test whilst treating the data as a stream of bits and printing an account of character occurrences:

./ent -b -c /tmp/test/urandomfile

Note any differences against the previous test.

I propose also generating larger streams of data (10’s or 100’s of MB) and testing against this too. Any repeating data or patterns (caused by a small/poor seed value for instance) will make spotting any weaknesses and a lack of randomness much easier across large amounts of data than across small amounts.

I also suggest running the test against known non-random files, so you may see that some tests show that such a file can have some characteristics of a random file, whilst completely failing other randomness tests.

Finally, once you are done testing with ENT, it’s good practice to delete the working folder:

Источник

Использование простого демона энтропии Haveged

Кратко об энтропии и случайных данных

Алгоритм Linux PRNG (Linux pseudo random number generator, генератор псевдослучайных чисел Linux, ГСЧ) разработан специально для генерирования случайностей из аппаратных прерываний. Аппаратные (или внешние) прерывания – это события, исходящие от внешних источников, – клавиатуры, мыши, I/O диска или сети, – в произвольный момент. Случайность, созданная PRNG, в основном необходима для функционирования механизмов шифрования (SSL/TLS), но этим сфера её применения не ограничивается. Даже простые программы (например, виртуальные карточные игры) зависят от энтропии.

В Linux есть два общих устройства: /dev/random и /dev/urandom. Случайность создаётся инструментом /dev/random (он предназначен для блокирования) и ожидает соответствующего уровня энтропии для своего вывода. Если энтропия находится на достаточном уровне, /dev/urandom произведёт такой же уровень случайности; однако /dev/urandom продолжит генерировать случайные данные (поскольку является неблокирующим устройством) даже если пул энтропии иссякает. Это может привести к снижению качества случайностей и увеличивает шансы повтора предыдущих данных. Снижение уровня энтропии очень опасно для производственного сервера, особенно если этот сервер выполняет криптографические функции. Для примера предположим, что существует облачный сервер, на котором запущены следующие демоны (все они используют SSL/TLS или блочные шифры):

• Веб-сервер
• Почтовый сервер входящих/исходящих сообщений
• SSH/SFTP

Если какому-либо из этих демонов понадобится случайность в тот момент, когда энтропия иссякла, он перейдёт в режим ожидания, что может вызвать чрезмерные задержки в работе приложения. И это ещё не всё: многие современные приложения в такой ситуации могут либо обратиться к собственным случайным данным, созданным при инициализации программы, либо использовать /dev/urandom, чтобы избежать блокирования, что станет причиной снижения надежности случайных данных. Это может отрицательно повлиять на безопасность соединений и увеличивает шансы криптографической атаки.

Пользовательское решение для заполнения пулов энтропии

Linux уже предоставляет довольно качественные случайные данные при помощи вышеописанного ПО, но поскольку автономные компьютеры обычно не имеют клавиатуры или мыши, генерируемая на них энтропия гораздо ниже, поскольку создаётся диском или I/O сети. Очень немногие автономные машины имеют специальное аппаратное обеспечение для ГСЧ, поэтому существует несколько пользовательских решений для создания дополнительной энтропии при помощи аппаратных прерываний, т.к. некоторые устройства (например, звуковые и видеокарты) создают больше так называемого «шума», чем жёсткий диск. К сожалению, даже это не решает проблему виртуальных серверов. Но тут на помощь приходит инструмент haveged. Основанный на алгоритме HAVEGE (а ранее – на его библиотеке), haveged позволяет генерировать случайные данные, руководствуясь изменениями во времени выполнения кода на процессоре. Так как обработать один и тот же блок кода в течение точно такого же времени почти невозможно (даже в той же среде на том же оборудовании), сроки выполнения одной или нескольких программ отлично подходят для генерации случайных данных. Инструмент haveged создаёт источник случайных данных с учетом различий в счётчика времени процессора (TSC) после неоднократного выполнения цикла. Сначала может показаться, что в конечном итоге он может создать предсказуемые данные; одна из целей данного руководства – опровергнуть это заблуждение.

Установка haveged в Debian/Ubuntu

Установить haveged в Debian или Ubuntu можно при помощи простой команды:

# apt-get install haveged

Примечание: Если этот пакет недоступен из репозитория, придётся скомпилировать его из исходников (об этом – в отдельном разделе руководства).

После установки пакета можно просто отредактировать конфигурационный файл, расположенный в /etc/default/haveged; установите следующие опции (если они не установлены по умолчанию):

В завершение настройте автоматический запуск программы:

# update-rc.d haveged defaults

Установка haveged в RHEL/CentOS/Fedora

Чтобы установить haveged в системы RHEL или CentOS, нужно добавить репозиторий EPEL, руководствуясь инструкциями официального сайта.

Примечание: Пользователям Fedora не нужно добавлять EPEL.

Установив и включив EPEL, установите haveged при помощи команды:

# yum install haveged

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

# chkconfig haveged on

Установка haveged из исходного кода

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

# tar zxvf /path/to/haveged-x.x.tar.gz

Теперь можно скомпилировать и установить его:

# cd /path/to/haveged-x.x
# ./configure
# make
# make install

По умолчанию haveged устанавливается с префиксом /usr/local, потому нужно добавить в /etc/rc.local (или аналог в вашей системе) следующее, чтобы настроить автоматический запуск программы при загрузке системы:

# Autostart haveged
/usr/local/sbin/haveged -w 1024

Примечание: В случае необходимости отредактируйте путь.

Запустите ту же команду вручную как root, чтобы запустить демон без перезагрузки системы (или же просто перезапустите систему, если вы используете Windows-подобную систему).

Тестирование энтропии и качества случайных данных

После установки haveged пул энтропии системы будет заполнен случайными данными. Однако невозможно достичь надежного уровня безопасности, если слепо доверять установке, потому следует протестировать сгенерированные случайные данные. В этой проверке применяется метод FIPS-140, используемый rngtest и доступный в большинстве основных дистрибутивов Linux под разными именами, одно из которых – rng-tools:

# cat /dev/random | rngtest -c 1000

На экране появится следующий вывод:

rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
rngtest: starting FIPS tests.
rngtest: bits received from input: 20000032
rngtest: FIPS 140-2 successes: 999
rngtest: FIPS 140-2 failures: 1
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 1
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=1.139; avg=22.274; max=19073.486)Mibits/s
rngtest: FIPS tests speed: (min=19.827; avg=110.859; max=115.597)Mibits/s
rngtest: Program run time: 1028784 microseconds

Небольшое количество неудачных результатов допускается в любом генераторе случайных чисел, но в среднем hovered выдаёт 998-1000 успешных чисел.

Чтобы протестировать доступную энтропию, запустите команду:

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

Источник