Регистрация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
Самое близкое к криптографии:
Картинка на закуску.
1Вообще, у него, как и у Ааронсона, интересный блог, можно порыться в заметках.
2Quantum Proofs of Knowledge
Abstract: When (re)analysing the security of classical cryptographic protocols in a quantum setting, one finds that many classical proof techniques break down. [в ту же копилку] Proofs of knowledge are a typical example of this: Their proofs usually involve rewinding, which is challenging in the quantum setting due to the no-cloning theorem. We present known solutions for proving the quantum security of proofs of knowledge, with a particular focus on what is not solved.
3How to Encrypt a Functionality
Abstract: The goal of secure program obfuscation is to make a program "unintelligible" while preserving its functionality. For decades, program obfuscation for general programs has remained an art, with all public general-purpose obfuscation methods known to be broken. In this talk, we will describe new developments that for the first time provide a mathematical approach to the problem of general-purpose program obfuscation, where extracting secrets from the obfuscated program requires solving mathematical problems that we believe to be intractable. We will also discuss the implications of these developments.
4Quantum Obfuscation of Classical Circuits
Abstract: We consider the usual problem of circuit obfuscation: given some classical circuit C, can we prepare an obfuscated version which allows a user to simulate black-box access to C without learning anything else? Classically this problem is known to be impossible, even for relatively weak formulations. But it may still be possible to produce a quantum state which obfuscates C, even in the very strong sense that any measurement of that state can be simulated (up to computational indistinguishability) using black-box access to C. I will describe a protocol for quantum obfuscation of classical circuits, whose security is open. Time permitting I will discuss some of the technical issues that come up in the analysis.
5Quantum and Classical Coin-flipping Protocols Based on Bit-commitment and their Point Games
Abstract: We examine a cryptographic primitive known as (quantum) coin-flipping where two parties generate a random bit over a (quantum) communication channel. Using semidefinite programming, we formulate optimal cheating strategies and use duality theory to construct their point games. Using linear programming, we formulate optimal cheating strategies for the classical protocol counterpart. We also investigate their point games, discuss how they are connected to the quantum point games, and show that they are useful in the security analysis.
6Verification of BosonSampling Devices
Abstract: BosonSampling, which Alex Arkhipov and I proposed several years ago, is a rudimentary, non-universal form of linear-optical quantum computing that nevertheless seems to be intractable to simulate using a classical computer. Unfortunately, verifying that a claimed BosonSampling device is working might itself be an intractable computational problem, and BosonSampling has come in for some criticism on that ground. In this talk, after introducing BosonSampling, I will explain recent polynomial-time classical protocols that distinguish a BosonSampling device from several important "null hypotheses." I will also discuss the possibility of an interactive protocol to verify post-classical computational power in a BosonSampling device.
комментариев: 9796 документов: 488 редакций: 5664
ФотошопGIMP?Тему продолжают развивать с разных сторон:
Знакомьтесь: квантовый t-дизайн. Он бывает сферическим и унитарным. Суть:
Т.е. усреднение чего-то по континууму t-инстэнсовых состояний не может быть отличено от усреднения по конечному набору t-инстэнсовых состояний. Звучит контринтуитивно, но факт. Штука имеет применения в жизни:
комментариев: 9796 документов: 488 редакций: 5664
Поскольку по HAVEGE могут вновь начать исследования и найти в самой концепции или конкретных реализациях конкретные уязвимости, следует присматривать за этой темой.
Чисто квантовые заморочки тоже интересны, но они далеки от рядового доверяемого практического использования и наработки по ним лучше складывать в отдельные темы, чтобы не терялись на общем фоне.