Аппаратные ГСЧ в ЦПУ от Intel
Судя по white papers (веб[link1] и pdf, 457Kb[link2]) в 3-ем поколении ЦПУ i5 и i7 реализованы аппаратные ГСЧ/ГПСЧ соответствующие криптографическим критериям, расширенно множество инструкций – Intel Secure Key(codenamed Bull Mountain).
Так же приведен пример про простоту и легкость прикручивания их к OpenSSL[link3] с последующими кое-какими тестами производительности.
Есть уже у кого-нибудь опыт практического использования?
Ссылки
[link1] http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide
[link2] http://software.intel.com/sites/default/files/m/d/4/1/d/8/441_Intel_R__DRNG_Software_Implementation_Guide_final_Aug7.pdf
[link3] http://software.intel.com/en-us/articles/performance-impact-of-intel-secure-key-on-openssl
[link4] http://lists.randombit.net/pipermail/cryptography/2012-June/thread.html#2995
[link5] http://software.intel.com/sites/default/files/m/d/4/1/d/8/drng-figure-1.jpg
[link6] http://www.theregister.co.uk/2013/12/09/freebsd_abandoning_hardware_randomness/
[link7] http://www.pgpru.com/novosti/2013/havegealjternativnyjjsposobpoluchenijakriptostojjkojjentropiiizprocessorov
[link8] http://www.pgpru.com/comment70439
[link9] http://www.pgpru.com/comment68174
[link10] http://www.securitylab.ru/news/448404.php
[link11] https://blog.torproject.org/blog/tor-weekly-news-—-december-25th-2013
[link12] https://lists.torproject.org/pipermail/tor-talk/2013-December/031483.html
[link13] https://www.torproject.org/projects/torbrowser.html.en
[link14] http://eprint.iacr.org/2014/504
Да.
Там ещё и аппаратный AES есть.
Никто из признанных авторитетов в области криптографии ещё не публиковал свои оценки качества работы этого Intel'овского ГСЧ?
Источник энтропии в нем конечно честный и сомнений не вызывает, вот только обратная связь и нормализации делают солюшен в целом чем-то средним между аппаратным ГСЧ и ГПСЧ.
Понятно, что рано или поздно въедливые ребята докопаются до аппаратных уязвимостей позволяющих влиять на распределение вероятностей. Например, та команда, где публичным лицом является Рутковская. Поскольку приблуда довольно новая, то выявление уязвимостей дело будущего. На текущий момент, скорее всего, могли успеть появиться лишь публикации по анализу качества работы в "штатном режиме".
Тысячи их.
http://lists.randombit.net/pip.....une/thread.html#2995[link4]
© Цитата из закромов в амбаре.
Отнюдь, это легко проверяется через специальный флаг:
Изложено в Section 7.3.18 документа "Intel® 64 and IA-32 Architectures Software Developer Manuals"
Имелась в виду проверка RNG на бэкдоры или недостаточную рандомность.
Лучше бы sha аппаратный реализовали...
Интересно, как эту штуку вообще возможно проанализировать? У кого кроме Intel есть лаборатории и специалисты для реверса современного CPU?
Источник энтропии неизвестный, особенности реализации неизвестны, наличие бекдоров неизвестно. Или вы верите пресс-релизам производителя?
Если там скрытый бекдор, либо некачественный аппаратный ГСЧ блок, это может быть никогда не выявлено ввиду того что после отбеливания через AES поток ничем не отличим от рандомного для того кто не знает скрытый в железе секрет.
ИМХО использовать любой аппаратный ГСЧ как единственный источник энтропии – несусветная глупость. Используйте какой-нибудь ГПСЧ типа Fortuna в который постоянно подмешивается энтропия из множества источников (на вход можно пихать вообще всё что в голову взбредет, чем больше всякого разного – тем лучше).
Золотые слова.
Читал ваш пост и даже призадумался – неужели на пгпгру вернулись толковые специалисты...
Или показалось...
Они никуда и не уходили.
Первый, второй, третий, все их режимы и разновидности?
Взять тэйп и писать всю последовательность пока период не появится.
Вместо того чтобы с видио компаниями DRM-ы хардварные встраивать и новое кабельное телевидение с порнухой открывать через процессоры, могли бы весь гражданский стандарт криптографии аппаратно реализовать в камне и открыть технологию.
Кто вам сказал, что закладка в ГСЧ всегда приводит к периоду?
К утечке по радио каналу приводит закладка.
Кто вам сказал, что в ГСЧ имеет смысл встраивать закладку, дающую утечку по какому-то каналу?
Это к вопросу о том, что чисто алгоритмическая закладка может не иметь обнаружимого периода или вообще какого-либо различителя от случайного потока без знания секретного ключа.
Мне одному кажется, что на сайте интела опечатка в схеме? В тексте[link1] везде CSPRNG, а на картинке[link5] какой-то CSPRING?
Pseudo Random Intel Number Generator? :)
C-SPRING? Американцы любят аббревиатуры, складывающиеся в слова.
Приходят в голову два варианта тривиальной закладки в любой TRNG.
В генераторе есть схема, предназначенная для сбора энтропии (например из осцилляторов), но она там только для отвода глаз (на каких-нибудь рентгеновских или тепловых снимках будет видно, что она якобы есть и даже работает). Но её выход не будет ни к чему подключен. В генератор ставится замаскированный 256-битный счётчик. Основное его свойство: сколь угодно долго сохранять последнее значение своего состояния после выключения питания или любых воздействий (радиация, замораживание и т.д.) и никогда не сбоить. Это, кстати, инженерно сложная задача. Кроме того в процессор встраивается уникальный ключ шифрования значений счётчика.
Первый вариант. На производстве проца счётчик ставится в уникальное случайное значение C, оно нигде больше не запоминается. А вот уникальный прошитый ключ K запоминается в секретной базе производителя. В процессе имитации честной работы TRNG, счётчик делает цикл C+1 до 2256 и затем от 0 до C (сколько успеет за свой срок службы). Выход счётчика шифруется криптостойким алгоритмом с ключом K. При конфискации процессора на нём запускают этот FakeRNG и снимают два блока гаммы G 256+256 бит. К ним подбирают ключи из известных производителю K, которые расшифруют гамму с соблюдением условия Decrypt ( G1, G2 ) = ( C1, C1 + 1 mod 2256 ). Даже если был выпущен миллион процов, быстро перебрать миллион ключей несложно. Можно упростить задачу, привязав ключи к серийному номеру генератора (проца). И восстановить всё, что на нём когда-либо шифровалось, если использовался только этот RNG.
Второй вариант. Потенциально более "палевный" для производителя. Счётчик всем ставится в одинаковое (нулевое) состояние. Поскольку ключи у всех всё равно разные, то и гаммы будут всё равно вырабатываться разные. Тогда их можно будет подбирать удалённо, без доступа к процу. Например расшифровывать весь трафик, вычислять закрытые ключи по открытым и т.д.
Могут быть и более хитроумные варианты. Без раскурочивания железа или взлома стойкого криптоалгоритма, доказать неслучайность чисел будет практически невозможно.
Будет очень смешно, если кто-то, имещюий доступ к этим секретам, потом сольёт эту информацию с мельчайшими подробностями, раструбит на весь мир и попросит политического убежища в Великой России. :) Пожалуй, это единственное, что не даёт кое-кому встраивать закладки на уровне железа.
Имхо, закладка с персистентным счетчиком нереализуема из-за крайней сложности реализации персистентности счетчика — просто поставить десяток флэш-транзисторов там не получится. Более того, такую закладку можно легко обнаружить: достаточно создать набор условий для сбоя персистентного счетчика и смотреть корреляции между сессиями рандома. Для этого можно манипулировать питанием, облучать процессор рентгеном и т.д.
Я предлагаю другой вариант бэкдора:
Конечная архитектура бэкдора такова:
Пояснения:
1Естественно, псевдорандомным алгоритмом, известным только атакующему.
2Один процессор будет генерить всю последовательность 2905 лет — получить гамму быстрее, чем ее выдает процессор, не получится, т.к. для обнаружения периода придется ждать его проявления.
3Тем более, все сгенерированные данные за 11 лет надо хранить и как-то обрабатывать.
4Собственно, для того функция f и предназначена, чтобы была такая возможность.
5Подмешиваем зашифрованные эллиптикой seed и serial.
Такой вариант имеет право на существование, но содержит много obscurity. В идеале, алгоритм бэкдора должен быть даже опубликован или разгадан, только без ключа это всё равно не давало бы его возможность обнаружить.
"Размазать" гамму тоже просто — сгенерировать один случайный 256-битный блок, и каждый его бит вставить в последующие 255 блоков, которые являются функцией от этого первого случайного блока. Тогда и сохранять ничего не надо и при утере небольшой части блоков, можно подобрать недостающие биты. А можно использовать т.н. cryptcoding: криптостойкое и неотличимое от случайного "размазывание" меньшего в большее, основанное на смеси шифрования с кодированием избыточности или на разделении секрета. Но это не самый лучший способ восстановления.
Также не стоит завязываться на серийник процессора, тем более держать его в секрете и извлекать по какой-то секретной команде. Серийник может облегчать выбор ключа из базы, но поскольку число изделий ограничено, то можно просто перебрать из базы все их ключи. Это займёт мало времени: минуты, часы, максимум дни.
Можно вернуться к первому варианту, только использовать незаписываемый счётчик. При старте проца туда записывается настоящий рэндом и он инкрементируется с шифрованием выхода. И так до выключения питания, после чего стирается. При каждой перезагрузке всё повторяется заново. Это даже очень похоже на штатный алгоритм работы TRNG: в схеме практически ничего не надо менять, только слегка попортить — ключ с шифрованием якобы используются для отбеливания.
Даже это даст противнику значительную утечку с сохранением неразличимости. Допустим, пользователь создал криптоконтейнер, заполнив его рэндомом из дефектного TRNG, а затем (не перезагружая компьютер) с помощью этого же TRNG создал ключ к этому контейнеру, который зашифровал своим паролем. Перебрав все блоки контейнера (среди которых найдутся незаполненные, т.е. чистая гамма) на попытку расшифровать известными ключами из них восстанавливается значение счётчика и искомый ключ. И это можно сделать даже не имея доступа к процу, не зная его серийника, а просто найдя неизвестно кем шифрованный контейнер на каком-нибудь файлхостинге.
Через утечку дефектной энтропии из векторов инициализации, согласованиях параметров трафика в DH, можно будет много чего расшифровать. Не обязательно даже получать два подряд идущих чистых блока гаммы. Достаточно собирать все попадающиеся в пределах сеанса до предполагаемой перезагрузки и пытаться их расшифровывать известными ключами в (ECB-Counter)-режиме. При угадывании подходящего ключа из предопределённого набора между ними будет небольшое расстояние по счётчику (расстояния Хэмминга) в отличие от случайного распределения при неправильном ключе. Отсюда легко вычисляется счётчик сеанса.
Для распознавания разных сеансов составляются карты распределений блоков, к ним по быстрому подбирается своё значение счётчика и т.д.
Прикручивание асимметрики (эллиптики) не очень критично. Если сам факт бэкдора вскроется, то не так важно, смогут ли им воспользоваться посторонние. Данные всё равно будут считаться скомпрометированными обеими сторонами. К тому же, асимметрика, тем более эллиптика, требует кучу специальных заголовков, которые надо передать в определённом месте. И возможно, есть проблема распознаваемости. Так, например, протокол DH в эллиптике распознаваем от случайного значения (не является случайным оракулом), а стойкость достигается за счёт избыточности (не знаю подробностей ECC-Эль-Гамаля). Ну может его как-то ещё отбеливать можно, тожно не знаю эти тонкости, но ясно, что это всё ведёт к усложнению.
В то время как в симметричном шифровании случайного счётчика никаких векторов инициализации и заголовоков при данной задаче не обязательно. Каждый блок просто шифруется простой заменой без лишних вставок. И легко распознаётся простым перебором известных производителю ключей.
Ваш последний варинт тоже жизнеспособный. Вообще, для бекдора в ГСЧ существует не одна единственная рабочая схема, можно много чего придумать.
Ещё подумалось, что короткий счетчик можно попытаться обнаружить через парадокс дней рождения: если счетчик имеет длину 64 бита и при старте заполняется случайно, вероятность получить коллизию имеется при 232 стартах. Способ проверки на этот бэкдор такой: собираем стенд, который дергает питание на процессоре и генерирует по одному блоку случайных чисел за раз; повторяем это 232 (или 233) раз, ищем коллизии.
…Поэтому противник скорее всего будет использовать 256-битный счётчик и шифровать его, к примеру, 256-RIJNDAEL (который имеет 256-битовый блок, поэтому не вошёл в стандарт AES).
От такого бекдора мало толку, ведь для его вскрытия нужно получить как минимум 1 блок рандома в неизменном виде, а это далеко не всюду возможно. Ну а короткий счетчик можно брутить повторяя алгоритм опирающийся на рандом, и таким образом вскрывать ssl сессии, pgp ключи, и вообще все что угодно. Поэтому я бы делал короткий счетчик, не длинее 64 бит (а лучше 56 бит чтобы не запариться брутить), и дополнил бы бекдор схемой которая вводит его в действие с задержкой в секунду (до этого на выход идет реальный рандом или псевдорандом). Таким образом сохраниться высокая универсальность бекдора, и проверка через парадокс дней рождения станет невозможной.
http://habrahabr.ru/post/168607/ Извиняюсь что не в той теме. Важно.
У меня было такое, раз или два за 5 лет, что во время работы ноутбук сам выключился во время работы за ним без каких бы то ни было видимых причин, и дело не в батарее было. Мог ли быть глюк в самой ОС — не знаю.
Странно, что по теме бэкдоров никто так и не вспомнил вариант с конечным множеством псевдослучайных последовательностей вообще не имеющих периода. Примерно такой же как и у спутников GPS. Вот только идентифицировать "вещающего" по совпадению с предварительно рассчитанным последовательностям будет отнюдь не маломощных чип за пятнадцать центов.
Так киньте ссылку на статьи, где это обсуждается, а мы почитаем, спасибо скажем.
P.S. И при чём тут период? В варианте с шифрованным счётчиком он тоже не обязан быть. Такое впечатление, что некоторые рассуждают так: нет периода ⇒ ГСЧ безопасен. Другие идут ещё дальше: нет периода в генерации гаммы для одноразового блокнота ⇒ шифр безопасен. У последовательности, не имеющей периода, всё равно могут быть легко детектируемые отклонения от случайного распределения, здесь же пытались придумать такую закладку, чтобы она была незаметной по статистике (а наличие периода — это совсем провал и предельный случай).
FreeBSD abandoning hardware randomness[link6].
Вроде бы, решение команды FreeBSD не соответствует тому, что описано в статье по ссылке. Они просто решили не подавать выход с аппаратных генераторов энтропии напрямую в /dev/random, а прокручивать через сборщик системной энтропии в качестве одного из источников. Опять же, Линус Торвальдс принял такое же решение, для Linux соответственно.
А что, раньше они так делали?! Хардварный пул не смешивался с той энтропией, что набирается софтварно? В Linux вроде всегда смешивалась.
«Hardware randomness» — не очень удачный термин, думаю. Есть ли чисто программная рандомность? BBS какой-нибудь если только? Остальное всё равно сводится к чему-то хардварному, просто в «TRNG» случайность черпается с самого нижнего уровня, а в программных RNG та же случайность собирается из её влияния на программные вещи более высокого уровня.
Возможно, в BSD так и не делали, но просто собирались рассмотреть такой вариант.
Торвальдс жаловался, что инженеры Intel предлагали ему замещать энтропию в пуле при определении их ГСЧ, а не подмешивать в качестве одного из входов.
В принципе, если отбросить вероятность злого умысла, в этом есть и рациональное зерно: на примере HAVEGE[link7], если снимать с него энтропию напрямую, то скорость будет 200 MB/s; если собирать её и пропускать через /dev/random и снимать уже оттуда (как делает демон haveged), то скорость на этой же системе будет 4 MB/s. Вопрос об оценках качества этой энтропии пока не рассматриваем, но то, что /dev/random сильно тормозной за счёт постобработки — очевидно.
Если бы HW-TRNG можно было считать идеальным и доверяемым, то постобработка ему была бы не нужна — она и так в него встроена, вместе с тестами и проверками на сбои. А внешняя софтварная постобаботка, реализованная в /dev/random, сильно тормозит его работу (почти на два порядка).
Нельзя доверять одному источнику энтропии, каким бы он ни был. Просто нужно придумать быструю и программную постобработку.
Совершенно верно.
Но, помимо всех своих прочих недостатков, существующие реализации /dev/random не были рассчитаны на сбор больших количеств энтропии с быстрых источников, поэтому скорость работы на такой случай в них никак не была оптимизирована.
/comment70439[link8]
Вспомнилось, что разработчики QRNG на это тоже жаловались[link9] (на скорость /dev/random):
А жёлтая пресса уже пишет[link10]: "В FreeBSD 10 аппаратные ГСЧ RDRAND и Padlock использоваться не будут".
Да, заголовок откровенно жёлтый, хотя внутри всё же правильно расписано:
В новостях[link11] и рассылке[link12] недавно было, но тут прошло незамеченым:
Всё настолько серьёзно? Непонятно, это касается всех, у кого выполнен хотя бы один из перечисленных пунктов, или требуется выполнение всех из них вместе? Звучит так, как будто у всех с означенными Intel-процессорами можно постфактум расшифровать трафик из-за слабого RNG.
OpenSSL целиком полагался на интеловский RDRAND и блокировал подмешивание свежей энтропии? Tor целиком черпал энтропию только из одного АНБ-источника под названием «Intel ГСЧ»?!
В последних downloads[link13] стоит версия 3.5 для TBB, в ней в Docs/ChangeLog.txt написано, что
Это что получается, текущая версия stable-связки не имеет защиты от вышеуказанной дыры с RNG?
Второе.
Могу ошибаться, но проблема вроде бы не в OpenSSL, а конкретно в Tor и в том, как он использовал RDRAND при его наличии.
Опция
вроде бы не включена в стандартном TBB по умолчанию, поэтому, получается, всех, кто сидел на стандартных сборках, это не касается безотносительно выполнения всех остальных условий.
Для клиентов эта опция бессмысленна, вычислительная нагрузка от криптоопераций по сравнению с релеями у них ничтожна.
Ну, вдруг кто-то держит высоконагруженный HS у себя дома, будучи всего лишь Tor-клиентом. :)
Предположим, что ГПСЧ Intel абсолютно честный, не содержит никаких закладок и полностью соответствует своим заявленным спецификациям. Даже в этом случае, по мнению исследователей, его умудрились криво спроектировать. Использование неаккуратно подобраных криптопримитивов и некорректно составленного криптопротокола для извлечения случайности из шума приводит к снижению стойкости как в теоретических атаках, так и в надуманно практических — тех, где противник может считывать поток данных из этого генератора и пытаться предсказать, какие биты случайного потока получают в это время другие пользователи этого же генератора в этой же аппаратной системе.
В некоторых, узких и слегка надуманных сценариях, авторы нашли различитель от идеального случайного генератора. В этих случаях стойкость интелового генератора по различимости и непредсказуемости составляет всего 220 … 240.
A Provable Security Analysis of Intel's Secure Key RNG[link14].