id: Гость   вход   регистрация
текущее время 16:09 29/03/2024
Владелец: unknown (создано 28/01/2013 13:30), редакция от 26/04/2014 19:46 (автор: unknown) Печать
Категории: криптография, случайные числа, хард
http://www.pgpru.com/Новости/2013/HAVEGEАльтернативныйСпособПолученияКриптостойкойЭнтропииИзПроцессоров
создать
просмотр
редакции
ссылки

28.01 // HAVEGE: альтернативный способ получения криптостойкой энтропии из процессоров


В середине января 2013 года вышла очередная реструктурированная стабильная версия 1.7 генератора энтропии haveged. Это демон, который эффективно "вычисляет" энтропию на основе нестабильности работы практически любого процессора, в котором не требуется наличия никакого встроенного аппаратного генератора случайных чисел. Результат может подмешиваться в Linux устройство /dev/random. Возможно также использование в Windows и других ОС.


Идея этого проекта и его аналогов уходит корнями в ряд научных исследований конца девяностых — начала двухтысячных годов, но многими так до сих пор остаётся непонятой и недооценённой. Так, проект OpenBSD отверг его использование даже не на основании известных недостатков этого генератора, а, похоже, только из-за непонимания и недоверия к его идеям и незнакомству с этой областью исследований, число достаточно серьёзных публикаций и проектов по которой растёт в последнее время.


Генерация случайных чисел для криптографических приложений была долгой проблемой на обычных компьютерах. Компьютер всегда воспринимался как строго детерминированное устройство, из которого было трудно извлечь какую-либо энтропию. С появлением первых криптографических программ для шифрования дисков, файлов, электронной почты, к ним поставлялся драйвер, который собирал случайные данные, считывая и обрабатывая интервалы между нажатиями клавиш и изменениями координат курсора мыши. Этот метод впоследствии перенесли в драйвера операционных систем, дополнив его сбором данных о программных прерываниях, обращении к дискам и др. системным событиям. Проблема заключается в том, что таким способом генерируется крайне малый поток энтропии, который быстро исчерпывается. Дело обстоит гораздо хуже на серверах, роутерах, виртуальных машинах, бездисковых станциях, Live-CD-дистрибутивах, гаджетах. Малое значение энтропии не может быть быстро восполнено при отсутствии активной работы пользователя, а использование малого значения энтропии в качестве ключа для последующего псевдогенератора приводит к проблеме возможной утраты, повторения или предсказуемости этого ключа при невозможности его записи на диск при перезагрузках или при восстановлении системы из бэкапов. Это, в свою очередь, приводит к предсказуемости псевдослучайной гаммы и краху многих криптопротоколов, см. также здесь.


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


Но, как оказалось, чисто цифровые устройства, при работе в определённом режиме, также способны вырабатывать энтропию. При пропускании сигналов через множество одинаковых цифровых устройств, можно добиться режима осцилляции, который будет вырождаться в процесс с элементами хаотичности (джиттер-эффект), что можно использовать для извлечения энтропии. Любительский проект такого уровня известен как Whirlygig, на схожем принципе работает генератор случайных чисел, встроенный в процессоры Intel, начиная с Ivy Bridge. Аналогичные схемы из-за компактности удобно использовать в миниатюрных устройствах, наподобие смарт-карт.


Но что, если у пользователя нет встроенного генератора, он не хочет или не может подключать внешний и не доверяет готовым аппаратным решениям, которые нельзя проверить? Здесь как раз есть возможность компромиссных решений на основе HAVEGE-алгоритмов (HArdware Volatile Entropy Gathering and Expansion), с упоминания которых начался этот небольшой обзор. Первоначально этот алгоритм был открыт в государственном институте исследований в области информатики и автоматики INRIA во Франции исследователями N. Sendrier и A. Seznec в 2002 году.


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


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


При простом (но очень точном) измерении времени исполнения операции даже на малозагруженном процессоре он показывает значительную нестабильность, связанную с влиянием как физических параметров (температура, напряжение), так и алгоритмических (сложная система выбора оптимальных решений с параллелизацией, конвейеризацией, ветвлением делает внутреннее состояние всех его регистров малопредсказуемым даже для пользователя системы). Дополнительные возмущения вносит работа операционной системы, которые гораздо более многочисленны и труднопредсказуемы, чем просто сбор данных о системных событиях в обычных драйверах сбора энтропии. Реальной атакой на такой генератор была бы остановка процессорного времени и анализ процессора на лабораторном стенде, насчёт других атак авторы приводят аргументы об их неэффективности. Интересным свойством процессора, связывающим воедино его дискретную и аналоговую сущность, является факт того, что всякое измерение путём вычислений меняет его внутреннее состояние, что в какой-то мере делает его аналогом сложной статистической макросистемы или квантового объекта. По крайней мере, в презентационных fileслайдах исследователи проводят аналогию с принципом неопределённости Гейзенберга.


Наиболее подробно сравнительный анализ различных генераторов, их сравнение с HAVEGE и его подробное описание представлены в дипломной работе filePseudorandom Number Generators for Cryptographic Applications и диссертации fileQuantifying Studies of (Pseudo) Random Number Generation for Cryptography.


Пассивный алгоритм измерений скорости выполнения операций называется HAVEG. В начале 2000-х годов на десктопных процессорах того времени исследователям удалось генерировать поток энтропии 8-16 кбит/сек. Активный алгоритм генерации энтропии HAVEGE на тех же процессорах позволял собирать поток энтропии до 280 Мбит/сек.


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


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


Но у алгоритма есть и существенные недостатки.


  1. Плохая теоретическая обоснованность качества получаемой энтропии. На практике она очень хорошо проходит все статтесты, но нельзя строго доказать, сколько в ней "истинной", а сколько "псевдослучайной", возможно даже предсказуемой и некриптостойкой энтропии. Из-за отсутствия знаний о полном устройстве процессора нельзя построить точную модель получения энтропии, можно лишь ввести нижний порог и опираться на избыточность. Иногда, в отличие от "псевдослучайного" (Pseudo Random Number Generator — PRNG) и "истинно случайного" (True Random Number Generator — TRNG), авторы и другие исследователи называют генератор на основе этого алгоритма "труднопредсказуемым" (Unpredictable Random Number Generator — URNG).
  2. Даже по экспериментальным данным оказалось, что разные процессоры дают разный уровень энтропии. С одной стороны, по мере роста сложности процессоров операции становятся в нём всё более хаотичными по временным характеристикам. С другой стороны, производители вносят оптимизацию с выравниванием отдельных операций в целях поддержки алгоритмов реального времени. В этом случае наблюдаются линейные корреляции временых интервалов, но и при этом остаётся достаточно материала для сбора энтропии. Для переносимости алгоритм желательно тестировать на каждом процессоре. Если же максимальная производительность не важна, то разработчики рекомендуют использовать минимальную производительность по умолчанию, приемлемую для всех типов процессоров.
  3. "Войны компиляторов" приводят к тому, что исходные коды для выполнения команд непосредственной работы с процессором могут быть скомпилированы не так, как задумывалось, из-за навязываемой компилятором оптимизации. Это может привести к фатальной ошибке и требует тестирования сборки после каждого обновления компилятора.
  4. Алгоритм не может безопасно работать на виртуальной машине. Некоторые виртуальные машины выдают округлённые, предсказуемые или занулённые значения процессорных таймеров.
  5. Теоретически возможно появление процессоров со случайными сбоями или преднамеренными "закладками" в процессорных таймерах, которые будут выдавать не слишком точные значения, хотя это и маловероятно, т.к. может привести к нарушению функциональности.

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


Старая версия от создателей находится по адресу http://www.irisa.fr/caps/projects/hipsor/, однако их проект нацеливался на включение в ядро и требовал сравнительно сложной процедуры сборки модуля. Актуальная версия от продолжателей работает как пользовательский демон или системный процесс и не требует никаких модификаций системы. Готовая версия пакета есть в Debian, начиная со squeeze-backports и будет включена в последующие релизы в стандартную поставку.

После установки пакета, он прописывает в системе все нужные стартовые скрипты и запускает процесс накачки устройства /dev/random дополнительной энтропией по алгоритму HAVEGE. Наблюдать за этим процессом можно посредством команды watch cat /proc/sys/kernel/random/entropy_avail. Если в обычном случае количество энтропии быстро расходуется и держится на низком уровне, то после старта демона haveged наблюдается непрерывный процесс подкачки до максимума (по умолчанию примерно до 4096), затем чуть более медленное расходование с падением до 1024 и очередной цикл быстрой подкачки. Посмотреть список потребителей энтропии в системе можно командой fuser -v /dev/{,u}random.


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


Известный проект OpenVPN использует библиотеку PolarSSL, в которой реализован алгоритм HAVEGE, однако, из-за проблем на виртуальных хостингах в нём может быть использовано смешанное решение из многих RNG-алгоритмов. Одним из примеров такого решения стал проект CSPRNG, который смешивает энтропию от множества разных алгоритмов, включая HAVEGE и встроенный генератор Intel. Этот проект развивается в составе Archlinux.


Несмотря на появление встроенного аппаратного генератора Intel, проекты на основе сбора энтропии обычных процессоров продолжают развиваться. Хотя изначальные работы исследователей были в значительной части свёрнуты в середине 2000-х годов, их последователи изучают новые версии HAVEGE-алгоритмов. В частности, в 2009 году на конференции по параллельным вычислениям и прикладной математике были представлены возможности параллелизации HAVEGE на современных процессорах для повышения количества и качества вырабатываемой энтропии. Другой алгоритм URNG был создан в 2012 году на основе публикации Unpredictable Random Number Generator Based on Hardware Performance Counters.


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


Источник: haveged – A simple entropy daemon


 
Много комментариев (50) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3