id: Гость   вход   регистрация
текущее время 02:36 29/03/2024
Владелец: unknown (создано 28/01/2013 13:30), редакция от 26/04/2014 19:46 (автор: unknown) Печать
Категории: криптография, случайные числа, хард
https://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


 
На страницу: 1, 2, 3, 4 След.
Комментарии [скрыть комментарии/форму]
— SATtva (28/01/2013 14:02)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Спасибо, очень интересный и обстоятельный обзор.
— unknown (28/01/2013 14:07, исправлен 28/01/2013 14:08)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Хотел больше, но как всегда не всё успеваю. Может что-то скажу ещё подробнее, если возникнет дискуссия по теме. За многие новости спасибо пользователям форума, они вызывают интерес к изучению неожиданных тем.

— sentaus (28/01/2013 20:30)   профиль/связь   <#>
комментариев: 1060   документов: 16   редакций: 32
"Войны компиляторов" приводят к тому, что исходные коды для выполнения команд непосредственной работы с процессором могут быть скомпилированы не так, как задумывалось, из-за навязываемой компилятором оптимизации. Это может привести к фатальной ошибке и требует тестирования сборки после каждого обновления компилятора.


А у них есть список протестированных сборок? Не совсем понятно вот что. У них на сайте написано, что некорректная сборка может засегфолтиться. Но можно ли считать сборку безопасной на основании того, что она не сегфолтится? :)
— unknown (28/01/2013 21:23)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Это самое безопасное из того, что может быть. Идея HAVEGE сколь привлекательная, столь и рисковая с точки зрения незаметного фейла, наподобие ошибки в PRNG Debian OpenSSL.
— Гость (28/01/2013 21:38)   <#>
А windows'ы значится в пролете или же кто-то портировал?
— Гость (28/01/2013 22:08)   <#>
Виндэус всегда в пролёте :)
— unknown (28/01/2013 22:10, исправлен 28/01/2013 22:11)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Портировали ещё с версии 1.3:

Haveged has been reorganized to allow its collection mechanism to be better accessed directly through the file system. This reorganization includes the option to suppress the daemon interface in the build so that haveged can now be used in those circumstances where the use of /dev/random is unavailable or inappropriate. This also means that haveged can now be built and used on non-linux systems. For example, the current tarball builds unmodified in mingw on Windows.
— unknown (28/01/2013 22:29, исправлен 28/01/2013 23:56)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Народ в форумах пишет, что у них работает, быстрее, чем urandom для затирания винтов. У меня дебьяновская бэкпорт-версия ничего не пишет в файл на 64-битной системе с опцией havege -f test, хотя должна. Отчего тогда буфер энтропии растёт?
Или он собран принудительно как демон, а как утилита не запускается (висит фоном) и эти опции отключены во избежание, хотя в мане остались? Не понимаю.


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


Одним из критических замечаний к этой реализации было, что в отличие от CSPRNG, он не делает проверки статданных на лету и требует ручной проверки перед инсталляцией.


P.S. Прояснилось. В бэкпортах относительно старая версия и перенаправление в произвольный файл или пайп не работает. /usr/sbin/haveged -r 16 создаёт в текущем каталоге файл с именем sample размером 16384 байта, так что можно убедиться, что выглядит всё достаточно случайно. Опция -f для записи в произвольный файл и пайп не работает без опции -n, которой нет в этой версии, -r меняет только его размер. Так что есть надежда, что с /dev/urandom всё взаимодействует в полном порядке.


P.S.S. Даже в текущей старой дебьяновской версии можно перенаправлять с некоторым извратом /usr/sbin/havenger -f /dev/stdout -r 10000000000 | pv | cat – > /dev/null. Порядок опций имеет значение. Скорость 200 MB/s, загрузка проца небольшая. В конце помимо случайных данных пишется диагностический заголовок и номер версии, что непрактично, например, для затирания винтов. Да и максимальный размер ограничен примерно полутора гигами.
В текущей версии, надеюсь, это уже всё пофиксили.
Но радует, что потенциально аппаратный интеловый RNG во многих случаях не нужен.

— Гость (29/01/2013 01:54)   <#>
Сборка в window'ах под mingw – это же какими надо быть извращенцами?!
Нет чтобы сделать отчуждаемую либу, пригодную к встраиванию в продукты пусть даже хотя бы на уровне сорцов.
— unknown (29/01/2013 09:27)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

PolarSSL?
— Гость (29/01/2013 11:16)   <#>
Возможно также использование в Windows и других ОС.
кто знает как, подскажите plz
— unknown (29/01/2013 12:02)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
По ссылке же написано, что виндовая версия либы PolarSSL компилится не только в Mingw, но и в Visual Studio. Можете поискать ещё какие-нибудь достойные виндовые либы с реализацией алгоритма HAVEGE.
— Гость (29/01/2013 13:25)   <#>
Результат может подмешиваться в Linux устройство /dev/random.
Только после постобработки/хэширования/ещё чего-нибудь.

Так, проект OpenBSD отверг его использование даже не на основании известных недостатков этого генератора, а, похоже, только из-за непонимания и недоверия к его идеям и незнакомству с этой областью исследований, число достаточно серьёзных публикаций и проектов по которой растёт в последнее время.
По вашей ссылке вполне нормальные комменты OpenBSD'шников, которые сводятся примерно к следующему: это лишь ещё один источник энтропии, такой же псевдо, как и все остальные. А раз на производительность им наплевать (так всегда было), то одним источником больше, одним меньше — нет разницы.

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

сложная система выбора оптимальных решений с параллелизацией, конвейеризацией, ветвлением делает внутреннее состояние всех его регистров малопредсказуемым даже для пользователя системы)
Кое-кто тоже так думал. Может быть, лучше не делать громких заявлений до тех пор, пока не будет железобетнного доказательства безопасности? И так ведь понятно, что это всё та же security throw obscurity, на которой стоит почти всё классическое крипто.

Интересным свойством процессора, связывающим воедино его дискретную и аналоговую сущность, является факт того, что всякое измерение путём вычислений меняет его внутреннее состояние
Измерять можно и косвенно, по излучению, не вычисляя ничего дополнительно на процессоре, и что тогда? При сильных side-channel attacks как он себя поведёт?

Наиболее подробно сравнительный анализ различных генераторов, их сравнение с HAVEGE и его подробное описание представлены в дипломной работе Pseudorandom Number Generators for Cryptographic Applications.
Работа интересная, но собственно доказательство безопасности я там не увидел. Может быть, плохо смотрел? И обсуждение AES и всё такое — к чему там это всё?

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

Одним из критических замечаний к этой реализации было, что в отличие от CSPRNG, он не делает проверки статданных на лету и требует ручной проверки перед инсталляцией.
Скажу по большому секрету, что даже выход QRNG проходит постобработку. Несмотря на то, что физический эффект даёт истиную случайность, сам прибор всё равно будет немного неидеален, что приведёт к отклонениям от случайности. Далее, при распределении QRNG-энтропии по хостам всё равно используется её смешивание с локальной энтропией на хостах и постобработка. C'e la vie, даже QRNG не спасает от необходимости хэширования.
— unknown (29/01/2013 13:53, исправлен 29/01/2013 14:47)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Всё, что попадает в /dev/random само там хэшируется. Постобработка у них есть и в самом HAVENGE (без хэширования — перексоривание с отбрасыванием).



Претендует на не совсем псевдо. В других работах авторов проведены исследования, что при традиционном сборе энтропии на сервере практически единственным источником энтропии (до 99%) может быть винчестер (обращения к нему). Что даёт её ничтожно мало и делает предсказуемой. А с переходом на SSD неизвестно как это оценивать вообще. О какой производительности речь, если в /dev/random меньше 128 бит энтропии, а /dev/urandom в итоге стартует с предсказуемых значений?



Random jitter
Микроколебания температуры-проводимости, даже влияние проходящих потоков воздуха, в таком режиме из цифрового устройства извлекается тот же аналоговый шум на фоне цифрового. В HAVEGE немного другое — временнОй шум.



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



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


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



Да /dev/random хэширует свой пул уже сам. И постобработка перед помещением туда данных есть (перексоривание с отбрасыванием — вариант экстрактора энтропии). Кривые картинки энтропии с QRNG где-то видел (возможно даже в работе этих авторов). Вообще, по HAVENGE достаточно публикаций и цитирований.

— Гость (29/01/2013 15:05)   <#>
Хотя если можно так точно померить микротайминг произвольных операций, то можно снимать и тайминг всех криптоопераций и вообще обрабатываемых на процессоре данных.

Можно поступить хитрее: взять опытный образец, тщательно его промерить таким образом, а потом продать жертве. Это даже не будет являться встраиванием закладки.

Вообще, по HAVENGE достаточно публикаций и цитирований.

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

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

Скорость 200 MB/s

200 мегабайт в секунду? Слишком много, чтобы быть достаточно качественной энтропией, на мой взгляд.
На страницу: 1, 2, 3, 4 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3