Источник энтропии (Nvmkcunt zumjkhnn)

Источники энтропии используются для накопления энтропии, с последующим получением из неё начального значения (англ. initial value, seed), необходимого генераторам истинно случайных чисел (ГСЧ) для формирования случайных чисел.

Отличие от генератора псевдослучайных чисел (ГПСЧ) в том, что ГПСЧ использует единственное начальное значение, откуда и получается его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии.

Случайные числа имеют много применений в криптографии, например, для создания криптографических ключей, паролей.

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

Информационная энтропия — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита.

Энтропия — это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения. Источники энтропии, как оказывается, очень зависят от реализации. Как только накоплено достаточное количество энтропии, её можно использовать как начальное значение (seed) для создания необходимой величины криптографически стойкой хаотичности. Существует надежда, что в будущем появится подлинный и портативный источник хаотичности. Всё, что нужно — физический источник непредсказуемых чисел. Тепловой шум (или шум Джонсона), источник радиоактивного распада, генератор свободных колебаний могут быть источниками энтропии. Эти обычные аппаратные средства могут легко стать частью стандартной архитектуры компьютеров. Также источниками может служить большинство видео- и аудиоустройств, кольцевой генератор, любая система с вращающимся диском, устойчивые точные часы, специализированные аппаратные генераторы псевдослучайных чисел, встроенные в материнскую плату персонального компьютера или его процессора (например Intel i82802 RNG, встроенный генератор микропроцессора VIA C3).

Необходимый объём энтропии

«Непредсказуемости» нужно не так много. Например, в AES (Advanced Encryption Standard) длина ключа 128 бит и даже очень защищённые системы редко используют материал свыше 200 бит. Если нужен набор ключей, они могут быть сгенерированы криптографически сильной последовательностью, используя хорошее случайное начальное значение (seed). Нескольких сотен случайных бит, получаемых при запуске компьютера раз в день, достаточно, если используются подобные последовательности.

Аппаратные источники энтропии

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

Видео- и аудиовходы

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

Дисковые накопители

Дисковые накопители (жёсткие диски) имеют небольшие случайные колебания скорости вращения из-за хаотической турбулентности воздуха. Если к этому добавить инструмент поиска данных на дисках, время которого очень мало, можно получить серии измерений, содержащих в себе нужную хаотичность. Такие данные, как правило, сильно взаимозависимы, поэтому необходима значительная обработка. Тем не менее, эксперименты, проводившиеся в своё время, показали, что с надлежащей обработкой даже медленные дисковые накопители на медленных компьютерах тех дней могли без проблем производить 100 или более бит превосходных случайных данных в минуту. Лет 5 назад на современном оборудовании получали степень генерации случайных бит свыше 10 тыс. в секунду. Эта техника используется в генераторах случайных чисел, имеющихся во многих библиотеках операционных систем. Использование кеша в этой технике не представляет проблем из-за того, что обращение в кеш выполняется в течение короткого времени и таким образом может быть проигнорировано.

Часы и серийные номера

Компьютерные часы и подобные величины, относящиеся к операционной системе и оборудованию, обеспечивают гораздо меньшее число необходимых случайных, непредсказуемых бит, нежели ожидается от их спецификации. Были проведены тесты часов огромного числа систем и было обнаружено, что поведение часов может сильно меняться, причём непредсказуемым образом. Одна версия операционной системы, запущенная на одном наборе оборудования, может предоставить разрешение часов в микросекунды, в то время как другая конфигурация этой же операционной системы может выдавать одни и те же младшие биты (то есть давать меньшее разрешение часов). Это значит, что последовательные считывания с часов могут выдать одинаковые значения, даже если прошло достаточное время, за которое величина должна была бы измениться, основываясь на номинальном разрешении часов. Также существуют случаи, когда быстрые считывания с часов могут произвести искусственные последовательные величины, потому что дополнительный код проверяет часы, которые, в свою очередь, не изменились между двумя считываниями, и увеличивает их на 1. Разработка портативных приложений, использующих системные часы для генерации непредсказуемых случайных величин — всегда особенно сложная задача, потому что разработчик приложения не всегда знает свойства системных часов.

Использование серийного номера оборудования (вроде MAC-адреса) также обеспечивает меньшее число непредсказуемых бит, нежели можно ожидать. Такие величины, как правило, хорошо структурированы, и их сегменты поля могут иметь лишь ограниченный набор возможных значений либо эти значения могут быть легко угаданы, основываясь на примерной дате выпуска или на других данных. Например, если компания производит как компьютеры, так и Ethernet-адаптеры, она, скорее всего (по крайней мере, внутри компании), будет использовать свои собственные адаптеры, что сильно ограничивает набор встроенных адресов.

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

Время и величины внешних событий

Вполне возможно измерить время и величину движения мыши, удара по клавише и подобных внешних событий, связанных с пользователем, статистику выделения памяти внутри операционной системы и сетевой активности, счётчики аппаратных и программных прерываний, показания имеющихся в системе датчиков окружающей среды (температура, напряжение, скорость вентиляторов системы охлаждения). Это разумные источники качественных непредсказуемых данных. На некоторых компьютерных системах такие входные данные, как нажатия клавиш, буферизуются, то есть записываются и накапливаются. Хотя времена нажатия на клавиши пользователем и имеют достаточные изменение и непредсказуемость, может не быть лёгкого способа получить доступ к этим изменениям. Другая проблема заключается в том, что не существует стандартного метода выделения (выборки) этого времени нажатия. Всё это усложняет использование этого метода для создания стандартного программного обеспечения, направленного на распространение на большой набор разнообразных компьютерных систем.

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

Также могут быть использованы некоторые другие внешние источники случайных данных, такие как время прибытия сетевого пакета и его длина, но лишь при аккуратном использовании. Почти любой внешний приемник может быть хорошим источником энтропии, например, грубый радиоприёмник, термометр в хорошо оборудованной компьютерной системе. Однако, в каждом конкретном случае данные должны быть проверены, сколько в действительности энтропии они могут предоставить.

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

Неаппаратные источники и некоторые выводы

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

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

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

Ссылки

• RFC 4086 — Randomness Requirements for Security
• Pseudo Random Number Generators  (неопр.). Cryptography. OpenBSD (11 мая 2009). — Источники энтропии и применение случайных чисел в OpenBSD. Дата обращения: 8 апреля 2010. Архивировано 13 апреля 2012 года.