Регистрация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 году.
Ещё в девяностые годы исследователи решали проблему точного вычисления времени исполнения алгоритмов на процессоре для решения задач реального времени. Как оказалось, меньше некоторого предела добиться точности по времени алгоритмически, технически и физически невозможно. Был открыт т.н. процессорный флаттер-эффект.
Флаттер можно представить как развевающийся на ветру флаг. Даже если в лабораторных условиях создать идеально постоянный ветровой поток, то из-за возникновения турбулентностей и неоднородностей в материале ткани флага, он будет развеваться хотя и периодически, но с существенными элементами непредсказуемости. То же самое происходит при выполнении вычислительных операций на процессорах.
При простом (но очень точном) измерении времени исполнения операции даже на малозагруженном процессоре он показывает значительную нестабильность, связанную с влиянием как физических параметров (температура, напряжение), так и алгоритмических (сложная система выбора оптимальных решений с параллелизацией, конвейеризацией, ветвлением делает внутреннее состояние всех его регистров малопредсказуемым даже для пользователя системы). Дополнительные возмущения вносит работа операционной системы, которые гораздо более многочисленны и труднопредсказуемы, чем просто сбор данных о системных событиях в обычных драйверах сбора энтропии. Реальной атакой на такой генератор была бы остановка процессорного времени и анализ процессора на лабораторном стенде, насчёт других атак авторы приводят аргументы об их неэффективности. Интересным свойством процессора, связывающим воедино его дискретную и аналоговую сущность, является факт того, что всякое измерение путём вычислений меняет его внутреннее состояние, что в какой-то мере делает его аналогом сложной статистической макросистемы или квантового объекта. По крайней мере, в презентационных 
слайдах исследователи проводят аналогию с принципом неопределённости Гейзенберга.
Наиболее подробно сравнительный анализ различных генераторов, их сравнение с HAVEGE и его подробное описание представлены в дипломной работе Pseudorandom Number Generators for Cryptographic Applications и диссертации Quantifying Studies of (Pseudo) Random Number Generation for Cryptography.
Пассивный алгоритм измерений скорости выполнения операций называется HAVEG. В начале 2000-х годов на десктопных процессорах того времени исследователям удалось генерировать поток энтропии 8-16 кбит/сек. Активный алгоритм генерации энтропии HAVEGE на тех же процессорах позволял собирать поток энтропии до 280 Мбит/сек.
Отличие HAVEGE от HAVEG состоит в том, что исходные данные по алгоритму HAVEG используются для затравки и заполнения большого пула внутреннего состояния. Этот пул перемешивается и используется для проведения в процессоре вычислений, рэндомизированных на основе предыдущих данных, что приводит сам процессор в ещё более хаотическое состояние. Для перемешивания используются относительно простые операция обхода, динамической табличной замены, сравнения, отбрасывания, циклического сдвига и XOR, но не используется никаких криптографических операций, которые затрудняли бы оценку стойкости.
В качестве преимуществ алгоритма HAVEGE можно отнести портируемость практически на любые процессоры, избыточно большой уровень генерируемой энтропии, отсутствие необходимости сохранять промежуточные данные, быстрое восстановление непредсказуемости последующей гаммы даже после гипотетического перехвата противником текущего внутреннего состояния, невозможность внезапной поломки без остановки работы остальной системы.
Но у алгоритма есть и существенные недостатки.
- Плохая теоретическая обоснованность качества получаемой энтропии. На практике она очень хорошо проходит все статтесты, но нельзя строго доказать, сколько в ней "истинной", а сколько "псевдослучайной", возможно даже предсказуемой и некриптостойкой энтропии. Из-за отсутствия знаний о полном устройстве процессора нельзя построить точную модель получения энтропии, можно лишь ввести нижний порог и опираться на избыточность. Иногда, в отличие от "псевдослучайного" (Pseudo Random Number Generator — PRNG) и "истинно случайного" (True Random Number Generator — TRNG), авторы и другие исследователи называют генератор на основе этого алгоритма "труднопредсказуемым" (Unpredictable Random Number Generator — URNG).
- Даже по экспериментальным данным оказалось, что разные процессоры дают разный уровень энтропии. С одной стороны, по мере роста сложности процессоров операции становятся в нём всё более хаотичными по временным характеристикам. С другой стороны, производители вносят оптимизацию с выравниванием отдельных операций в целях поддержки алгоритмов реального времени. В этом случае наблюдаются линейные корреляции временых интервалов, но и при этом остаётся достаточно материала для сбора энтропии. Для переносимости алгоритм желательно тестировать на каждом процессоре. Если же максимальная производительность не важна, то разработчики рекомендуют использовать минимальную производительность по умолчанию, приемлемую для всех типов процессоров.
- "Войны компиляторов" приводят к тому, что исходные коды для выполнения команд непосредственной работы с процессором могут быть скомпилированы не так, как задумывалось, из-за навязываемой компилятором оптимизации. Это может привести к фатальной ошибке и требует тестирования сборки после каждого обновления компилятора.
- Алгоритм не может безопасно работать на виртуальной машине. Некоторые виртуальные машины выдают округлённые, предсказуемые или занулённые значения процессорных таймеров.
- Теоретически возможно появление процессоров со случайными сбоями или преднамеренными "закладками" в процессорных таймерах, которые будут выдавать не слишком точные значения, хотя это и маловероятно, т.к. может привести к нарушению функциональности.
Тем не менее, пользователи серверов, роутеров, гаджетов и пр. устройств, работающих с криптографическими приложениями, могут начать применять этот алгоритм уже сейчас с достаточной степенью уверенности, что его применение лучше, чем недостаточный уровень энтропии в системе, приводящий к предсказуемости ключей и других секретных параметров.
Старая версия от создателей находится по адресу 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
комментариев: 9796 документов: 488 редакций: 5664
Так бы все неквантовые PRNG не имели прав на существование. Эти параметры непостоянные. Ну монетку вы померяете, узнаете, что она смещена в сторону выпадения решки на 0.0000001%, отдадите "жертве". А там её выход будут перексоривать с запасом для извлечения несмещённой энтропии.
В случаем с процом, конечно есть опасения, что противник может лучше его промоделировать. И то, что качество энтропии оценить крайне сложно, чем даже в сравнении с джитерром электронных осцилляторов или оцифровкой аналоговых шумов. И доказательств и хороших обоснований стойкости не дождаться. Но можно предположить, что это всё же лучше, чем запись системных прерываний.
Для поддержания пула /dev/random на уровне 4096 бит скорость на порядки ниже (килобиты), даже если его будут достаточно часто дёргать разные программы или тот же /dev/urandom будет с него переинициализироваться периодически.
Именно это я и имел в виду.
Это, конечно, да, но сводится к вышесказанному «ещё один источник энтропии для пополнения пула».
комментариев: 9796 документов: 488 редакций: 5664
А если он перед этим глюканет, забыв отписать текущий ключ затравки /dev/urandom на диск и стартанёт с предыдущим ключом, повторив гамму с большой предсказуемостью?
Можно ли после этого считать сеансы связи достаточно безопасными? Ну если там QRNG, да ещё собственноручно собранный без закладок, то конечно это лучше. Неслучайно же, что первыми HAVEGE заинтересовались именно в OpenVPN и его государственной голландской версией, сертифицированной для официальных дел (Dutch government's national communications security agency (NLNCSA)).
комментариев: 9796 документов: 488 редакций: 5664
HAVEGE использовали в симуляторе биосферы:
http://arxiv.org/abs/nlin/0604026
Вроде удалось вырастить более сложных виртуальных
монстроворганизмов, чем при помощи PRNG.комментариев: 9796 документов: 488 редакций: 5664
Spinore, вы что-нибудь про это в курсе?
[/offtop]
Во-первых, конечно же спасибо.
Во-вторых, конечно же оно нихера не собирается. Даже на чистой(не засраной) машине со всем необходимым. Весь этот ваш Open Source как был последние 15 лет вещью в себе и абы для кого, так оным и остался.
Сходу, да и то не полностью, собирается только один вариант из четырех — "Release Win32". Факт наличия в солюшене остальных трех вариантов следует игнорировать.
Да и "Release Win32" будет собираться только в том случае, если сборка идет через не через "Rebuild Solution".
Соберется не полностью, споткнется на "rsa_verify_pss" — надо дождаться пока соберутся остальные и после этого делаем "Build" персонально для "rsa_verify_pss". Ни в коем случае не "Rebuild".
Ну вы поняли — добро пожаловать в мир Open Source, как тронешь, так перемажешься :)
комментариев: 9796 документов: 488 редакций: 5664
Если я правильно понял намёки на несовершенство алгоритма по этому коду, то вот аналогичная критика. Вот ответ изобретателя алгоритма в первом коменте.
Сам изобретатель в исследовании процессоров как бы не последнее место занимает. Можете глянуть ещё работы других сотрудников этого института. Там есть лабораторное оборудование и исследования по моделям температурных микрораспределений в процессорах, к примеру.
А данный код скорее всего защищает от запуска алгоритма в виртуалках или когда нельзя полагаться на CPUINFO в определении параметров процессора. Нормальная перестраховка.
Некоторые виртуалки позволяли его использовать, пока не начали округлять тайминги. Не используйте его там вообще или смешивайте с другими источниками энтропии, что и рекомендовали в багрепорте PolarSSL.
Проблемы переносимости в неопенсорсные ОС часто действительно мало волнуют мир Open Source. Разрабатывалось под Debian, нормально перенесли под Arch и RedHat. Из модуля ядра переписали алгоритм под демон. В либу эту внесли, в другие проекты вносят. Как-то у всех всё получалось.
Ну перепишите версию под винду. Если кому-то было бы очень надо, то сделали бы. Скорее это проблемы виндопрограммеров, которым не хочется самим принимать участие в разработке Open Source под свою систему, а только заимствовать готовое.
[offtopic]
Это отчасти верно. А зачем ему стараться для других?
[/offtopic]
Элементарно решаемые проблемы со сборкой под windows'ом говорят о том, что люди держащие вожжи управления проектом не смогли привлечь в свои ряды никого из С/С++ разработчиков разбирающихся в создании ПО под windows'ы.
Идея у проекта неплохая, достойная — значит проблема или в адекватности держащих вожжи или же их неопытности в разработке ПО.
Даже если и не понимать или не знать о существующей системе поручительства и принципах опознавания свой-чужой у этого цехового братства, а просто по здравому смыслу посмотреть на ситуацию. Вот проект взялось посмотреть сотня человек и каждый 15 минут потратит на то, чтобы понять и устранить проблемы со сборкой, то в итоге это 25 человеко-часов. Больше половины рабочей сорока часовой недели.
Да и должно быть понимание, что поддержка windows'ов — это охват в двадцать раз больше, чем количество компов с linux/unix на борту.
[offtopic]
Хорошие идеи приходят в головы совершенно разным людям. Далеко не все из которых способны воплотить таковые в жизнь, ибо это требует и ума, и общей адекватности.
Разработка под windows'ы на С/С++ сложнее чем под юникс лайк семейство. Это некоторый порог сложности, взятие которого доступно далеко не всем. В том числе требуется пройти путь в несколько лет и несколько проектов. В итоге, получается, что сообщество С/С++ разработчиков под windows'ы это люди неглупые, с опытом поболее пяти лет, семейные. Им сложно выделить время и на сорок то часов работы в неделю. А уж как судьба проекта зависит от вменяемости и адекватности со стороны тех, кто им управляет они уже понасмотрелись.
Потому, если в проекте, типа PolarSSL, не видно признаков присутствия кого-то из их цехового братства, то автоматом делается вывод о степени вменяемости тех, кто на управляющих ролях. Это элемент той самой системы поручительства. Которая позволяет держаться подальше от основной массы людей того сорта, что тучами слетаются на Open Source проекты. Ибо чем ниже порог вхождения, тем выше процент людей глупых, невежественных, да и просто с психическими расстройствами. И вот зачем о них пачкаться, когда время на работу то приходится выделять чуть ли не в ущерб семье?
[/offtopic]
комментариев: 9796 документов: 488 редакций: 5664
Вот коммерческая компания, которая собрала VPN на PolarSSL в т.ч. и под Windows. Ну выковыряйте рабочую либу оттуда. Сделано по заказу и финансированию Dutch secret service AIVD, между прочим.
Сам HAVEGE и его первые реализации разрабатывался французским национальным исследовательским институтом. GnuPG и Tor, к примеру, тоже сидят на госфинансировании. Нормальный такой уровень у большинства серьёзных Open Source проектов. Даже государственный, а не коммерческий.
комментариев: 9796 документов: 488 редакций: 5664
Ещё простенький эксперимент после запуска демона haveged:
Поскольку в самом /dev/random также есть хэширование пула, то он даёт выход помедленнее, чем /dev/urandom и на порядки медленнее, чем прямой вывод из havenged через пайп. Но зато становится таким же неисчерпаемым. Можно генерировать 16384-битные OpenSSL-ключи :-)
Если кого-то вдруг заинтересовало посмотреть именно на тот пример реализации HAVEGE, который получил "добро" со стороны Dutch secret service, то смотреть надо PolarSSL-0.14.3, отнюдь не тот, который последний – 1.2.4
Единственная ценность этой либы(в контексте интереса к HAVEGE) — пример реализации, не более чем в статусе прототипа. Практика показывает, что быстрее всего изучение работы реализаций идет в том случае, когда есть возможность смотреть их работу в интерактивном отладчике.
Собственно скачал сорцы, собрал, посмотрел под отладчиком работу данной реализации(за счет уже наличествующих примеров, или набросав какие-то свои варианты использования).
Пошел рассказал об этом коллеге, ну или письмо написал. Он уже в свою очередь садится писать реализацию исходя из специфики и задач в вашем текущем проекте. И это будет не продакшен код, а всего лишь один из прототипов. На которых обкатываются различные идеи. За счет чего становятся понятны варианты решения изначальной задачи. Каждый из которых уже становится возможным обосновано/аргументированно прикинуть по срокам и ресурсам.
Тырить, словно гопники, чужой код из Open Source проектов не имеет никакого смысла. И вовсе не из-за высоких лицензионные рисков или там политики партии(конторы)т. А просто из-за того, что никто и никогда не поручится за то, как именно этот код будет себя вести в конкретно наших ситуациях. Пристально же изучать его на этот предмет — по времени тоже самое, что свой написать.
И дело не в куче пафоса, а в конкруренции среди производителей коммерческого ПО. За хорошие деньги продается и покупается лишь то ПО, на которое есть качественный и быстрый саппорт. И основная задача производителя коммерческого ПО сводится к организации процесса производства именно исходя из этого требования.
комментариев: 9796 документов: 488 редакций: 5664
Dutch — это Голландия (Нидерланды, NL). Бывает, что её путают с Данией американцы. В фильмах-комедиях собственного производства. И ещё Австрию с Австралией. Вроде даже президенты у них так оговаривались.
Может у них хороший саппорт по коммерческой лицензии, не знаю. Нет желания рекламировать конкретно эту реализацию.
Псевдокод, все теоретические выкладки, часть экспериментальных исследований у вас на руках.
У MS, HP, IBM, Sony есть свои research-отделы по прикладным и даже фундаментальным дисциплинам, весьма далёким от сиюминутной коммерции. И сотрудничество с исследовательскими учреждениями тоже налажено. В чём проблема заключить контракт с Computer Science исследователями, оплатить грант?
Всё логично — для бесплатного Open Source работает свой подход и он себя оправдывает, хотите вкладывать и зарабатывать деньги — ищите другой.
Удачи этой сотне писателей коммерческого ПО. Это и есть настоящие гопники в мире опен сорса.