О чем молчит Генератор Случайных Чисел от Интела?

Давно хотел попинать ГСЧ от Интела, но никак не мог свободную минутку найти. Пришлось себя заставить. Результат пинания — текст ниже.
Формат текста — стеб и критика, с уважением к оппоненту.
Не думаю, что пост будет интересен разработчикам этого ГСЧ (они уже давно премию за него получили), но вот кому-то другому, для общего развития, возможно будет интересен.

О чем же молчит ГСЧ от Интела? А молчит он о многое чем, но для начала надо определится с терминологией.
Есть общее название Генератор Случайных Чисел (Random Number Generator — RNG). Их делят на PRNG (Pseudo Random Number Generator) и TRNG – True RNG. Каждая уважающая себя контора, которая выпускает крипто IP, ну просто обязана иметь в своем арсенале True RNG.
Ещё лучше, если свой True RNG компактный, быстрый и самое главное — цифровой (ну без аналоговых заморочек, типа диодов Шоттки, шумящих резисторов и т.д. экзотической живности, ибо ее сложно «поддерживать»).
Одним словом, без True RNG никак, поскольку реальная энтропия в криптографии нужна и точка.

Если кто интересовался True RNG, должен быть в курсе материала, где впервые описан первый Интеловский RNG.
У них там как источник энтропии используется «шумящий резистор» в комбинации с парой осцилляторов. Это первый True RNG от Интела и до последнего времени (до выхода продуктов Ivy Bridge) был единственным. В принципе, первый интеловский True RNG работал исправно (хоть и не шустрый был), но на переносимость (между технологиями производства) у него была аллергия (личное предположение), требовал специального питания и т.д. ограничений. Поэтому, его «держали» на задворках чипсета, который, с разных причин, отставал (по технологии производства) от процессоров на год-два.
Решили в Интеле этот мазохизм прекратить и в 2008ом дали задачу двум группам разработчиков сделать новый True RNG. Чтобы был цифровой, да быстрый, и что-бы энергию ценную не кушал попусту, да сертификации разные прошёл.

По ходу разработки, было 2 публикации на эту тему, и я просто должен на них остановится детально. К сожалению, их нету в открытом доступе (только IEEE), но ищущий — всегда найдёт.
Первая, «A 4Gbps 0.57pJ/bit Process-Voltage-Temperature Variation Tolerant All-Digital True Random Number Generator in 45nm CMOS»
Из названия и абстракта к материалу сразу стало понятно, что в Интеле шутить не любят, и «рвут всех», даже не спрашивая фамилии. Но когда почитал до конца — долго смеялся. Основные моменты, вызывающие смех:
  • Мы все оттестировали набором тестов NIST STS, и наш RNG проходит все тесты.
На самом деле, исследователи Интела использовали только 5 тестов из 16ти (в новой редакции пакета их 15 (сами тесты и документация к ним лежат открыто тут). В дополнение, один тест использован неправильно, поскольку для Discrete Fourier Transform надо значительно больше данных для анализа, нежели предложенные 500 бит, но ведь исследователей можно простить, поскольку полученная 4Гбит/с производительность, как и все данные в статье — это всего-то симуляция.
Ну да ладно, первая проба всегда симуляция, и с эти можно согласится, но никак нельзя согласится с тем, что
  • Источник энтропии, по словам разработчиков — полностью цифровой.

В принципе, центральным элементом источника энтропии — бистабильная ячейка, которая по сути цифровая image, но то, как ее обработали напильником уже выходит за рамки определения all-digital.
Вот пример использованного инвертора (всего 2), который имеет 8 специально подобранных отводов на питание и землю.
image
Включая/выключая их можно настроить уровень переключения инвертора (в реальном чипе транзисторы то буду все разные). Цель разработчиков была проста — добиться одинакового уровня переключения пары использованных инверторов в бистабильном элементе; цели то они наверное достигли (компенсировали технологический разброс), но называть это древнее решение (древнее меня) — all-digital — это просто кощунство, imho.
В придачу к «специально-цифровым инверторам», которых явно в стандартной цифровой библиотеке для дизайна нету, исследователи из Интела добавили ещё одно all-digital решение по компенсации паразитной ёмкости соединительных связей (delay element), которое работает по тому-же принципу настройки/компенсации. В результате, получили такое-вот «all-digital»
image
где CONF0-1 это 8ми битные регистры для подстройки уровней переключения инверторов, а CONF2-3 это 4ех битные регистры для компенсации паразитной ёмкости соединительных линий (настройки задержки). В общем, CONF0-3 используют для балансирования системы, поскольку без этого — как повезёт (чип от чипа будет отличатся): либо работать не будет, если шум меньше разницы переключения инверторов, либо работать будет но плохо — распределение нулей и единиц будет не равномерным, хотя возможные и рабочие варианты (все по Гауссу).
Там ещё много к чему можно придраться (как симулировали технологический разброс, оценивали результаты прохождения статистических тестов, о «мало-потребляющем» энергию решении и т.д), но лучше перейти ко второй публикации.

Вторая, «2.4GHz 7mW All-Digital PVT-Variation Tolerant True Random Number Generator in 45nm CMOS», по всем основным моментам повторяет первую, даже добавляет некоторые «спорные моменты оценки», и только в производительности поумерили аппетит — с 4Гбит/с до 2.4Гбит/с
  • тот-же неполноценный набор статистических тестов, источник энтропии и т.д;
  • добавлен механизм самокалибровки, который надо рассмотреть детальнее;

image

Функционирует система самокалибровки следующим образом: система проверяет сгенерированный бит и в зависимости от его значения, перестраивает источник энтропии, что-бы в следующий раз получить на выходе инверсное значение. Например, если текущее (сгенерированное) значение '0', то источник энтропии (с помощью новой комбинации нагрузок на части инверторов и соединительные линии) будут «подталкивать» в противоположную сторону, чтобы сгенерировать '1' с большей вероятностью.
Да, приведённый выше пример достаточно упрощён, поскольку, по словам разработчиков, система самокалибровки оценивает 1, 2 и 4 последовательных бита при принятии решения (деталей не приведено). В общей сложности я могу согласиться, что это решение позволит достичь на выходе Uniformity (равномерного распределения значений типа '1' и '0'), но как же быть с Unpredictability и Independence? А ведь даже мистер Джесси Волкер упомянул о таких важных параметрах как Unpredictability и Independence для Генераторов Случайных Чисел.
Ещё возникает резонный вопрос по тестах — какой длины и сколько семплов протестировано?
Как результат есть таблица с прохождением 5ти тестов (Frequency, Block Frequency, Runs, Cumulative Sums и FFT), притом что в пакете их 15. Если в первой статье они получали данные с аналоговой симуляции, то во второй, они чётко оглашают что RNG реализован аппаратно (fabricated), а из этого следует, что не должно быть обоснованных причин для неполноценной проверки (в смысле — сложно генерить).
На этом наукообразный поход закончился и осталась практически только реклама.
На IDF 2011 вскользь было анонсирован RNG в Ivy Bridge, но детальнее только в IEEE Spectrum публикации на эту тему.
Перевод этой статьи уже давно на Хабре тут, где в комментариях хорошенько постебались над двойным отбеливанием с помощью AES этих самых «почти рандомных» данных с источника энтропии.

image

Такая-же картинка (только деталей больше) и на IDF 2012.
Хочется отметить в этой статье фразу «It starts by collecting the mostly random output of the two inverters 512 bits at a time.». У меня не получилось однозначно представить реализацию этого решения. Ну да ладно.

К чему это все было?
В любом случае, разработчики Интела молодцы, смогли выпустить такое «цифровое решение» на 22нм технологи и это очень даже круто.

P.S. Если кому-то показалось сумбурным изложение материала или возникли вопросы — с удовольствием уточню или отвечу.

P.S. 2. спасибо за правки
Share post

Similar posts

Comments 36

  • UFO just landed and posted this here
      0
      более чем уверен что пройдёт («отбеливание» алгоритмом AES скроет все)
      +7
      Раз вы такой умный и образованный, то почему не провели недостающие тесты и не выложили результаты?

      У вас в статье сплошная субъективная критика, а в конце — Интел молодцы. Итог не соответствует повествованию.
        0
        Я, конечно, не автор, но Ivy Bridge еще не поставляется конечным пользователям. Так что прогнать реально тесты могут только большие конторы типа IBM, Dell и т.д., которым не больше месяца назад начали поставки для сборки компьютеров и нотбуков.
          +16
          Ivy Bridge уже давно лежит у нас в магазинах города.
          +7
          >Раз вы такой умный и образованный, то почему не провели недостающие тесты и не выложили результаты?
          Предлагаю вам, такому умному, предоставить оборудование для тестов.
            0
            Не вижу смысла тестировать данные RdRand (после двойного AES), поскольку, источнику энтропии достаточно чихнуть, и Вы получите на выходе последовательность, которая пройдёт NIST STS

            То, что они заставили это работать на технологии 22нм (3Д) — уже большое достижение (как с точки зрения технологии, так и с точки зрения достаточной точности балансировки системы)
              0
              3D транзисторы там используются только в кеше, насколько я знаю.
                0
                можете дать линк на информацию? (когда я говорил с технологами — они это не вспоминали)
                  +1
                  Забираю слова обратно, сейчас нашел опровержение.
            +5
            > Раз вы такой умный и образованный, то почему не провели недостающие тесты и не выложили результаты?
            Ну нужно еще железку найти.
            То есть найти-то не проблема, насколько я вижу ГСЧ встроен в процессор, но придётся его нужно купить как минимум. А то и полностью менять платформу (мать + память).
              +12
              Как-то сумбурно написано, нет вывода.

              Задача ГСЧ — генерировать случайную последовательность чисел, которая должна отвечать набору определённых требований. ГСЧ от Интела справляется с этой задачей или нет? Или «справляется, но недостаточно хорошо»? Для каких классов задач следует использовать ГСЧ от Интел, а для каких следует использовать другие ГСЧ?

              Выводов нет и это печалит.
                0
                ответ тут habrahabr.ru/post/145188/#comment_4880755

                + учитывая то, что это не Smart Card, где деньги лежат, Вы разницу не почувствуете
                  +6
                  Я не понимаю, что значит «чувствовать разницу», когда речь заходит о технологии.

                  Есть некая технология, например, сверление, которое используется во многих областях человеческой жизни, начиная от сверления дерева, и заканчивая стоматологией и бурением скважин. Технология одна и та же, но только назначение разное. Из вашей статьи непонятно, о чём вы вообще хотели сказать — о том, чем отличается ГСЧ Интел от иных ГСЧ, реализованных аппаратно? Или вы хотели рассказать о том, как он физически реализован? Или вы хотели описать классы задач, в которых использование этого ГСЧ оправданно, а в каких нет? Из вашей статьи непонятно, о чём она. В ней написано обо всём и ни о чём конкретно.

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

                  Если человек хочет написать другой обзор дрелей (читай, ГСЧ), то он берёт три или сколько хочет штук, развинчивает их и рассказывает читателям о том, как они устроены, с фотографиями, и заключениями о том, чем хорошо или плохо использование того или иного патрона, электромотора, подводящего кабеля, подшипников, щёток и т.п. вещей, из которых состоит дрель. Читатель понимает, о чём хотел сказать автор и принимает решение, какая дрель ему подходит.

                  В вашей статье этого нет. В ней намешано про технологии, какие-то тесты, дано суждение того, что Интел «схитрил» с тестами и т.п. Нет выводов о том, хорош или плох ГСЧ Интел, где его стоит использовать, а где надо купить отдельную железку.

                  Однако, если вы говорите о том, что «учитывая то, что это не Smart Card, где деньги лежат, Вы разницу не почувствуете», то я делаю вывод, что он годится, ну, чтобы придумать псевдослучайный номер варианта для задачки и негоден для серьёзных задач. Для такого рода баловства меня устроит функция, random() входящая в любую библиотеку разработки.
                    0
                    я имел ввиду тип задач, которые обычно решаются на даном устройстве, и возможностях атак на них
                    для примера, в Smart Card (где деньги лежат), требования к источнику энтропии значительно выше; если интересует вопрос, копните стандарт AIS31
                    общая презентация мистера Шиндлера
                    детальнее
                      +3
                      А почему вы не пишете об этом в статье? Почему вы не рассказываете про «типы задач, которые обычно решаются на даном устройстве, и возможностях атак на них». Почему вы не приводите требования к источникам энтропии и т.п.?

                      Из вашей статьи мог бы получиться интересный обзор ГСЧ с погружением в теорию и практическими выводами, а получилась статья… непонятно о чём.

                      Прочитав сей опус, лично я не могу сказать, что обогатился знаниями о ГСЧ, о том, какие они бывают, как работают, в чём преимущества и недостатки того или иного ГСЧ, какие бывают требования к ГСЧ, какие бывают требования к случайным последовательностям, какие бывают атаки на ГСЧ и т.п.

                      Ничего существенного в статье, увы, нет. Зачем вы её вообще писали? Чтобы сообщить миру что-то новое? Нового не видать. Рассказать по опыт решения какого-либо класса задач на разных ГСЧ? В статье нет описания опыта. Описать теорию, о том, как строятся разные ГСЧ? И этого нет. Нет, вру. Есть слова «диод Шоттки» и «шумящие резисторы», из чего можно сделать вывод, что такие штуки используют для создания ГСЧ.

                      Я прошу прощения за то, что мои высказывания могут показаться вам резкими, возможно даже, они могут быть расценены, как «выпады», просто меня не покидает неприятное чувство пустоты. Обычно так случается, когда ждёшь чего-то, по твоему мнению интересного, приходишь на лекцию (или в кино, или читаешь статью), а там… ничего. Пустота. Ни о чём. Лектор пришёл, написал на доске ключевые слова для поиска в Гугле и ушёл со словами: «дальше вы сами». Как-то… жидковато.

                      ГСЧ — это прекрасная тема, тем паче, что приложений СЧ в реальной жизни не счесть! Но у нас есть громкий, почти детективный заголовок, и пустое содержание. Увы и ах.
                        0
                        задачи, в которых нужны True RNG, подходы к дизайну, атаки на них и т.д. — темы возможно будущих публикаций
                        в даной я попытался приуменьшить некоторые «громкие слова» сказанные разработчиками в ходе дизайна
                          0
                          Хочу уточнить свой ответ:
                          — почему нету (в статье) информации о известных подходах к дизайну источника энтропии?
                          — Как оценивать True RNG (Startup test, online test, statistical evaluation)?
                          — Почему не рассмотрены задачи где True RNG необходимы?
                          — Где собственный опыт?
                          По объёму работ — «тянет» на диссертацию, что меня не интересует
                          Этой информации полно в интернете, и если Вам надо «в собранном виде», можете поискать Koc — Cryptographic Engineering (Springer, 2009); 3 главы посвящены True RNG
                          если у Вас есть более конкретные вопросы, а у меня ответы, то нет проблем поделиться опытом

                          лично меня интересуют атаки (на реализацию), но пока нечего рассказать

                          а насчёт пустого заголовка — разве не показана несостоятельность заявлений о прохождении всех тестов NIST STS? Полностью цифрового решения? Возможные проблемы с Independence?
                          0
                          И что, так легко взломать рандом нагенеренный TRND-чипом внутри этой смарт-карты?

                          Ощущение, что эти повышенные требования от безделия.
                            0
                            уверен, что возможно
                            не секрет, что некоторые True RNG (которые используют jitter в Ring Oscillator) довольно чувствительные к синхронным шумам на питании и земле
                            если есть возможность уменьшить таким образом энтропию то это, возможно, уже большой шаг ко взлому системы в целом
                    +2
                    Кстати, картинки из статьи были замечены в другой статье на Хабре: тык!

                    Да и текст там поинтереснее…
                      0
                      картинка в рекламе должна красиво выглядеть
                      +1
                      По поводу all-digital: имеется в виду использование стандартного КМОП-процесса для цифровых схем, т.е. для данного RNG используются те же «цифровые» транзисторы, что и для стандартной логики. В аналоговых схемах используется специальный техпроцесс и живут они на островах, отделенных от цифровой логики.
                        0
                        иногда ещё имеют ввиду стандартную цифровую библиотеку, где нету таких специальных инверторов и именно таких элементов задержки
                          0
                          Вы о SOC слышали? там аналоговая и цифровая часть на одном чипе, с использованием одного техпроцесса и т.д,
                            0
                            Если вы про минус, то он был не мой. Профиксил его :)
                            В любой микросхеме есть аналоговая часть: i/o ячейки с согласованным импедансом и защитой от электростатики. Но интеграция аналоговых компонентов: моп-транзисторв нестандартной геометрии, биполярных транзисторов, диодов и.т.д потребует усложнения техпроцесса, изготовления дополнительных масок. В добавок, аналоговые схемы плохо масштабируются и на 45/32/22 нм часто занимают ту же площадь что и на 130nm.
                            Думаю что у Intel аналоговая часть ограничеена I/O ring и фапч. Хотя наверняка после покупки infineon wireless они начали биться над тем, как бы запилить радиочастотную комппоненту gsm-модемов на своих фабриках.
                              0
                              Ок, рассмотрим этот пример с другой стороны:
                              — Вы можете описать на Verilog этот RNG и синтезировать так, чтобы был похожий инвертор (с настройкой ёмкости на питании и земле), а также элемент задержки?
                              — Или приведите пример стандартной цифровой библиотеки синтеза, где-бы эти элементы были?

                              Товарищам из статьи, для реализации этого источника энтропии, нужен custom layout (серия низкоуровневой разводки и post-layout симуляции, что-бы достичь нужной точности балансировки); причём, чем меньше нанометров техпроцес, тем точность моделей, аналоговой симуляции, падает (т. е. что Вы видите в симуляции не обязательно будет в железе)

                              ОК, получился у них продукт который работает (я за них искренне рад).
                              А если поменяли фабрику или техпроцес? — Начинай сначала, поскольку, новые передаточные характеристики, коэффициент усиления у инвертора, разброс технологических параметров (уровни переключения сигнала), паразитные ёмкости и т. п.
                              И это совсем не похоже на «all digital approach»
                              с этим Daffodil согласен?
                                0
                                Ну они же не сказали что схема синтезируемая :) Да, можно открыть Virtuoso, подключить drc для «цифрового» процесса, нарисовать схему и сделать layout руками. Как меня учили в универе, для timing-critical цепей в процессорах с миллионными тиражами это не фокус.
                                  0
                                  да, это не фокус и это реальность
                                  но только не надо называть эту реальность красивыми словами «all digital»
                          0
                          За статью в любом случае спасибо. Если у вас есть практический интерес к теме «генераторов», то я знаю человека, который с удовольствием ответит на поставленные вопросы. У него (точнее — у нее) даже блог свой есть. Не стесняйтесь, обращайтесь! Готов поработать переводчиком, если что ;)
                            0
                            спасибо за предложение, но должен отказаться
                            переводчик мне не нужен, тема мне знакома, задачи стоят у нас разные
                            да и коллеги могут меня неправильно понять, если я буду обсуждать эту тему с мисс Gael Holmes Hofemeier
                            0
                            Вы несколько раз упомянули, про какие-то тесты, например FFT. А как проверять, что сгенерированное число случайное?
                              0
                              одно число проверить на рандомность сложно (ошибка большая)
                              проверяют не число, а выходную последовательность генератора и чем длиннее — тем лучше
                              например, результатом каждого теста в пакете NIST STS — значение вероятности — рандомная или нет анализированная последовательность
                              чем больше данных на входе теста, тем выше вероятность, что пакет тестов лучше определит — на сколько анализированная последовательность похожа на случайную
                              причем, тестируется не только равномерное распределение (uniformity), но и зависимостеи между частями последовательности (independency)
                              пакет NIST STS, на сколько мне известно, наиболее полно предоставляет
                              документацию и исходники
                                0
                                Случайна ли последовательность 111111111110000000000000000000000011111111111111111111111111111111111111111100011111111111111111111111111111101000000000000000000000001000000000000000001000011111111110000000000000?
                              0
                              Вчера был пост про TRNG-генератор на основе атмосферных шумов RANDOM.ORG. У них есть статистика по выходным данным, но я сходу не смог разобраться, что означает какой тест.
                              Может кто-нибудь из коллег «в теме» посмотреть и оценить, можно ли «доверять» этому TRNG?
                                0
                                Имел удовольствие ознакомится с диссертацией разработки аппаратного генератора случайных чисел на базе двух диодов и микроконтроллера, и понял что это весьма нетривиальная задача. И прохождение всех тестов — это весьма и весьма сложная задача.

                                Only users with full accounts can post comments. Log in, please.