Давно хотел попинать ГСЧ от Интела, но никак не мог свободную минутку найти. Пришлось себя заставить. Результат пинания — текст ниже.
Формат текста — стеб и критика, с уважением к оппоненту.
Не думаю, что пост будет интересен разработчикам этого ГСЧ (они уже давно премию за него получили), но вот кому-то другому, для общего развития, возможно будет интересен.
О чем же молчит ГСЧ от Интела? А молчит он о многое чем, но для начала надо определится с терминологией.
Есть общее название Генератор Случайных Чисел (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Гбит/с производительность, как и все данные в статье — это всего-то симуляция.
Ну да ладно, первая проба всегда симуляция, и с эти можно согласится, но никак нельзя согласится с тем, что
- Источник энтропии, по словам разработчиков — полностью цифровой.
В принципе, центральным элементом источника энтропии — бистабильная ячейка, которая по сути цифровая 
, но то, как ее обработали напильником уже выходит за рамки определения all-digital.
Вот пример использованного инвертора (всего 2), который имеет 8 специально подобранных отводов на питание и землю.
Включая/выключая их можно настроить уровень переключения инвертора (в реальном чипе транзисторы то буду все разные). Цель разработчиков была проста — добиться одинакового уровня переключения пары использованных инверторов в бистабильном элементе; цели то они наверное достигли (компенсировали технологический разброс), но называть это древнее решение (древнее меня) — all-digital — это просто кощунство, imho.
В придачу к «специально-цифровым инверторам», которых явно в стандартной цифровой библиотеке для дизайна нету, исследователи из Интела добавили ещё одно all-digital решение по компенсации паразитной ёмкости соединительных связей (delay element), которое работает по тому-же принципу настройки/колмпенсации. В результате, получили такое-вот «all-digital»
где 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Гбит/с
- тот-же неполноценный набор статистических тестов, источник энтропии и т.д;
- добавлен механизм самокалибровки, который надо рассмотреть детальнее;
Функционирует система самокалибровки следующим образом: система проверяет сгенерированный бит и в зависимости от его значения, перестраивает источник энтропии, что-бы в следующий раз получить на выходе инверсное значение. Например, если текущее (сгенерированное) значение '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 этих самых «почти рандомных» данных с источника энтропии.
Такая-же картинка (только деталей больше) и на IDF 2012.
Хочется отметить в этой статье фразу «It starts by collecting the mostly random output of the two inverters 512 bits at a time.». У меня не получилось однозначно представить реализацию этого решения. Ну да ладно.
К чему это все было?
В любом случае, разработчики Интела молодцы, смогли выпустить такое «цифровое решение» на 22нм технологи и это очень даже круто.
P.S. Если кому-то показалось сумбурным изложение материала или возникли вопросы — с удовольствием уточню или отвечу.
Автор: kDaniu
