 |
Цифровой ГСЧ и Большой Брат
|
|
|
|
Сначала сделаем небольшое, но важное отступление. Внимательный Читатель, пересматривая предыдущие обзоры процессорных микроархитектур и технологий, наверняка заметит, что мы как-то обошли такую популярную тему как мировые заговоры. Непорядок-с:) Ну, многие помнят, как в 1999 г. при выпуске Pentium III мировая конспирологическая общественность обратила внимание на уникальный серийный номер (PSN), которым Intel собиралась помечать каждый ЦП, и так громко завопила «Ага, попались!», что в уже ноябре Оценочная комиссия по наукам и технологиям (STOA) при Европарламенте всерьёз стала обсуждать запрет на импорт новых «Пней» в Европу, опасаясь цифровой слежки. Так что Intel пришлось через 2 года убрать PSN в чипах Tualatin. Точнее, так нам сказали;)
Но главные компьютерные заговоры, разумеется, лежат в логовах штаб-квартирах коварных спецслужб (например, американского Агентства Национальной Безопасности, АНБ) и охмуряемых ими фирм-гигантов (например, ненавистной многим Microsoft). Причиной охмурения стало то, что «с появлением быстрых компьютеров, с бесконтрольным распространением сильных криптографических алгоритмов […] у всех желающих появились возможности для надёжного засекречивания не только текстовых, но и речевых коммуникаций». Поэтому ещё со времён Windows NT, как утверждают аналитики, АНБ пыталось внедрить чёрный вход в самую популярную серию ОС. Если бы это удалось, то «граждане, фирмы, организации и государственные ведомства в случае засекречивания своих коммуникаций должны использовать лишь такие криптосредства, которые без проблем могут быть расшифрованы правоохранительными органами».
Естественно, АНБ в этом не одинока — в 2006 г. обнаружилось, что «Британские власти ведут переговоры с представителями Microsoft по поводу умышленного создания уязвимостей всистеме защиты новой операционной системы Windows Vista, чтобы сотрудники спецслужб могли проникать в компьютеры злоумышленников […] — это “поможет предотвратить террористические акты”» (ну разумеется, куда же мы без борьбы с мировым тараканизмом…). MS быстро заверила, что «в Windows Vista не будет “чёрных ходов” для спецслужб», но через год появилось продолжение — «В работе над Vista принимало участие АНБ, …[чтобы] убедиться в том, что новая ОС Microsoft соответствует всем необходимым требованиям Пентагона… Правозащитники полагают, что при участии АНБ в состав ОС могли быть включены средства […] доступа к конфиденциальным данным.»
|
|
|
В общем, Мировая Закулиса не дремлет. Ну, кто бы сомневался, но причём же тут случайные числа? А вот тут и начинается самое интересное. Дело в том, что крипто в Windows и др. ОСможет быть взломано «плохим» ГСЧ (реализованным в ОС программно) или случайной ошибкой в процессоре. (Да простят читатели автора за столь обильное цитирование, но в выжимке ниже сказана вся суть.)
«Примером тому может служить случайное открытие в середине 1990-х глубоко спрятавшегося “бага деления” в процессорах Pentium… Если какая-нибудь спецслужба […] обнаружит (или тайно встроит) хотя бы лишь пару таких целых чисел, произведение которых микропроцессор вычисляет некорректно, то […] любой ключ в любой криптопрограмме на основе RSA, работающей на любом из миллионов компьютеров с этим процессором, может быть взломан… Если взломан ГСЧ, то в большинстве случаев можно считать взломанной и всю систему безопасности…
В новый спецвыпуск Национального института стандартов США, […] описывающий 4 одобренных к использованию схемы RNG, включен генератор Dual_EC_DRBG, разработанный в недрах американского АНБ… Выяснилось, что …[константы шифрования] связаны со вторым, секретным набором чисел… Если вы знаете эти секретные числа, то всего по 32 байтам выхода можно предсказывать всю генерируемую “случайным генератором” последовательность… [Dual_EC_DRBG] используется во всех приложениях [Windows 2000]… Функция запускается в режиме пользователя, […] что делает очень лёгким доступ к состояниям генератора… Никто толком не знает, как устроен ГСЧ в XP, но есть веские основания полагать, что он не слишком отличается от Windows 2000.»
|
|
|
Наконец, «Dual_EC_DRBG вошёл как опция в пакет обновления Service Pack 1 ОС Windows Vista».
Таким образом, начиная с 1995 г., история шифрования в Windows и пакета Office показывает систематически кочующие из версии в версию уязвимости, объяснить которые можно тольконамеренным ухудшением защиты по приказу Большого Брата. А чтобы пингвинофилам не стало обидно за обделение вниманием — в прошлом году всплыла история о том, «как ФБР и АНБ США встраивали закладки-бэкдоры в криптографию операционной системы с открытыми исходными кодами»:
«В 2003 г. программисты-разработчики, занимавшиеся созданием […] ядра ОС Linux, […] обнаружили и ликвидировали в открытых исходных кодах системы тайный бэкдор. Причём реализован этот бэкдор был настолько хитро и искусно, что […] разговоры о неуловимых троянах в открытом ПО перестали звучать как бред… Человек, знавший […] экзотическое сочетание управляющих флагов плюс место, где их следует применить, получал бы благодаря этим двум строчкам полный, с максимальными привилегиями Root, контроль… В сообществе OpenBSD начались аудиторские проверки криптоподсистем этой ОС. Первые же дни пристрастных перепроверок позволили выявить в кодах пару существенных и прежде незамеченных багов.»
Итак, мы уже трепещем: Большой Брат достал своими щупальцами до каждого ПК (кто-нибудь сомневается, что и продукция Apple не обойдена стороной?). Более того, по требованию АНБ и производители невычислительных устройств могут укоротить фактически используемую длину ключа, заполняя часть битов константой. Так это сделано в телефонах стандарта GSM и противоугонных автомобильных системах: в применявшихся до этого года чипах радиочастотной идентификации (RFID) фирмы Texas Instruments фактическая длина ключа составляла лишь 40 бит из 64, а в системах на основе KeeLoq фирмы Microchip — 28 из 64. Впрочем, взлом телефонов и угон авто — это совсем не наша тема, а вот как насчёт компьютеров?
|
|
|
И тут все в белом выходят маркетологи Intel и как-бы говорят: Аллилуйя! Свершилось! Повальная интеграция всего и вся в процессор достигла и случайных чисел! Тем более, что ускорение шифрования, где они так нужны, тоже давно добавлено в виде AES-NI и некоторых отдельных команд. Что говорите? Аппаратный ГСЧ ещё с 2003 г. как есть в процессорах VIA (в составе PadLock), начиная с C3 и заканчивая последними Nano? Да кто эти Нано видел-то? Вот то-то же, а вот мы — великая Intel! Поэтому с нашими Ivy Bridge ваши, граждане, случайные числа будут на 146% случайней обычных. Аминь! Ура, товарищи!
Технология аппаратного ГСЧ получила кодовое имя Bull Mountain («Бычья гора») в честь селения в штате Орегон рядом с городом Хиллсборо, где расположился исследовательский центр Intel’s Circuit Research Lab, в недрах которого технология и родилась. Перед тем как описать её суть, следует сделать теоретический экскурс, поясняющий суть задачи. Ещё Клод Шеннон показал, что лучший способ сделать так, чтобы никто, кроме целевого получателя, не мог восстановить дискретную информацию — максимально исказить её шифрованием. Более того, существует абсолютно стойкий шифр, принципиально невскрываемый аналитически — даже при наличии бесконечных петафлопсов и времени. Для этого надо всего лишь для каждого шифрования генерировать идеально случайный ключ длиной с весь шифруемый текст, причём использоваться он должен только раз.
Шеннон позаимствовал для своей теории понятие энтропии — математической меры хаотичности термодинамической системы. Энтропия по Шеннону стала мерой хаоса сигнала. И до сих пор наиболее качественными источниками хаоса являются физические явления, а не алгоритмы ГСЧ. Но т. к. программный генератор есть вещь нематериальная, то именно такой вид и применяется чаще всего, ибо он наиболее прост. И т. к. числа в нём на самом деле не очень-то случайные, то вернее его называть генератором псевдослучайных чисел (ГПСЧ, PRNG). Помимо простоты «конструкции» ещё одно важное преимущество перед аппаратными генераторами истинно случайных чисел (ГИСЧ, TRNG) — программная сущность позволяет им куда быстрее работать, что очень важно, когда шифровать надо много (для сетевых служб и устройств это особенно востребовано). Однако результат ГПСЧ должен быть криптографически стойким на случай атак и взломов, суть которых проста: следует наблюдать выходные числа или менять стартовое состояние ГСЧ, чтобы предсказывать следующие его значения, либо как-то ещё вмешиваться в его работу. И чаще всего это получается.
|
|
|
Дело в том, что обычные ГПСЧ, как и любая другая программа для машины с конечным числом состояний (а таков любой цифровой компьютер), основаны на детерминированном алгоритме, потому их числа лишь притворяются случайными. Для начала генерации им требуется посевное число или затравка (seed), из которого конкретный ГПСЧ всегда выдаст одну и ту же последовательность чисел, которые к тому же ещё и неизбежно начнут повторяться (хоть и с очень большим периодом — для 32-битного ГПСЧ Mersenne Twister MT19937 период равен 219937−1). Такие псевдослучайные числа подойдут для управления ИИ-соперниками в играх или в приближённых моделях в прикладной науке. Но для криптографии ГПСЧ неприменимы. Поэтому появился подвид «криптографически безопасных» ГПСЧ (КБ-ГПСЧ, CSPRNG). Он значительно лучше удовлетворяет основным требованиям к случайным числам для шифрования:
· последовательность должна быть статистически неотличима от случайной;
· восстановление прошлых или будущих состояний алгоритма по текущему должно быть максимально затруднено, а в идеале — невозможно. (Для вышеупомянутого MT19937 достаточно протестировать всего 624 числа для точного предсказания всех следующих.)
Лучший способ превратить обычный ГПСЧ в криптографически безопасный — обеспечить ему периодическую «рандомизацию», подмешивая настоящие случайные числа, полученные извне, т. е. от ГИСЧ. Таким образом можно получить много чисел, которые будут куда случайнее, чем от ГПСЧ, но при этом на единицу времени их будет куда больше, чем от медленного ГИСЧ. Но почему же медленного? А потому, что эти генераторы ничего сами не считают, а выделяют энтропию из некоего физического источника и оцифровывают её. Таким источником могут быть тепловые шумы в усилителе или специальном шумовом диоде, случайные распады радиоактивного вещества (с поправкой на темп полураспада согласно известному периоду), колебания атмосферы, хаотичное поведение микро- или макрообъектов в жидкости, и пр. Датчики, преобразующие это в последовательность нулей и единиц, работают не очень быстро.
|
|
|
Более того, не смотря на «природность» источника энтропии, и его статистические свойства бывают неидеальны. Например, тепловые шумы, очевидно, зависят от температуры, а броуновское движение — ещё и от внешних толчков и колебаний (даже малейших). Поэтому самые крутые ГСЧ имеют составную или «каскадную конструкцию» (КГСЧ, CCRNG): числа от встроенного ГИСЧ попадают в буфер, названный «бассейном (пулом) энтропии». Оттуда они периодически читаются в качестве недетерминированных «затравок» для КБ-ГПСЧ. Таким образом получаются и качественный хаос на выходе, и высокий темп его генерации.
Так что же нового сделала Intel? Она попыталась уместить на кристалле (причём дешёвом и массовом) все компоненты КГСЧ, чтобы любой пользователь мог иметь настоящие случайные числа, не покупая за большие деньги приставку к ПК, считающую колебания луча лазера от пролетающего за окном комара. Если не вспоминать про других производителей (тем более, что об их решениях не так уж и много известно), то конкретно Intel впервые сделала такую интеграцию ещё в 1999 г., встроив в микросхему БИОСа ГИСЧ, фиксирующий тепловой шум в виде разности сопротивлений близко расположенных резисторов. Шум усиливался и подключался к кольцевому генератору, постоянно меняя его период. Выход генератора оцифровывался через равные промежутки, фильтровался от псевдослучайных влияний (внешние электромагнитные наводки, температура и колебания шины питания) и подавался в буфер, откуда его можно было читать спецкомандой.
Часть этой схемы является аналоговой и потребляла довольно много энергии, особенно на стадии усиления — причём постоянно, пока подано питание. 13 лет назад на лишние милливатты никто внимание не обращал, но сегодня это катастрофично. Другой минус аналоговых схем — крайне трудное моделирование, которое требуется проводить не только при проектировании первого образца, но и каждый раз при переводе чипа с этой схемой на новый техпроцесс. Разумеется, цифровые схемы также моделируются, но для них это проще благодаря детерминированности. Аналоговые же компоненты всякий раз требуют ещё и коррекции для обеспечения нужного качества сигнала, причём начиная с 45 нм это оказывается крайне трудно. Так что помимо ваттов хорошо бы сэкономить и человеко-часы инженеров. Да и 75 Кбит/с на выходе этого ГСЧ сегодня кажутся смешными — профессиональные ГИСЧ выдают 10–20 Мбит/с.
Поэтому в 2008 г. конструкторы Intel занялись созданием полностью цифрового ГИСЧ, отвечающего американским государственным стандартам на такие приборы (NIST SP800-90, FIPS-140-2 и ANSI X9.82). Спустя 4 года именно его мы и получили в IB в составе встроенного каскадного ГСЧ. Этот генератор формально нарушает одну из аксиом построения цифровой схемы: она должна находиться в точно определённом и предсказуемом состоянии. Очевидно, новый ГИСЧ должен делать прямо противоположное, но теми же транзисторами, что и обычные вентили. Для этого генератор стал метастабильным, что для обычной логики является дефектом.
 Упрощённая схема кольцевого инвертора и график одного из двух вариантов его срабатывания (второй — очевидно, инвертированное состояние первого).
|
Состоит он из обычного кольцевого инвертора, который применяется в любой ячейке СОЗУ для хранения бита. Сигналом сброса оба вывода (прямой и инверсный) на очень короткое время подключаются к шине питания (т. е. логической «1»), образуя короткое замыкание. Чтобы не закоротить весь чип до снятия сброса, к питанию подключаются изолированные диодами буферные конденсаторы, которые и запитывают выводы генератора до снятия сброса. После этого каждый инвертор генерируют на выходе «0», которая смешивается с «1» и попадает на вход другого инвертора. Срединное значение на входах приводит к неустойчивому равновесию, когда малейшее отклонение из-за теплового шума сдвигает баланс к случайному из крайних состояний. Достаточно одному из инверторов хоть немного перетянуть вольтаж от центра, как его выход «убедит» напарника сдвигать своё значение в противоположном направлении — в результате через короткое время с любого инвертора можно читать бит. Момент фиксации также генерирует импульс для местного тактирования, нужный для схемы сброса и 1-й стадии обрабатывающей случайные биты логики.
|
Расположенный во внеядре ГСЧ Bull Mountain оформлен как частично асинхронный 4-стадийный конвейер (см. схему-таблицу). Стадия №2 срабатывает только после заполнения буфера перед ней. А стадии №3 и №4 имеют внешнее тактирование; причём, являясь по сути одной схемой, они не могут работать одновременно. 1-я стадия — метастабильный кольцевой инвертор, генерирующий хаос с энтропией >80%. Далее каждый бит потока смешивается с предыдущим, а результат подаётся в 512-битный регистр сдвига. Формируемые на выходе порции подаются на статистический тестер (стадия №2), который проверяет фактическую случайность порции — побитным сравнением с результатом математической модели кольцевого генератора и плавающим окном на 64 Кбит. Если энтропия недостаточна, то такую порцию отбрасывают. Т. о. после тестера темп потока качественных порций непредсказуем.
Проверенные порции подаются в очиститель (стадия №3), где делятся на половинки, которые проходят через сложные взаимные преобразования, чтобы сделать 256-битное слово-результат ещё случайней. Причина такой обработки — те самые псевдослучайные влияния, от которых пришлось защищаться ещё в 1999 г. К вышеописанному списку сегодня добавляется ещё как минимум разброс параметров транзисторов, который сильно мешает жить и дизайнерам обычных цифровых схем. На выходе очистителя стоит КБ-ГПСЧ (стадия №4), представляющий чуть изменённый аппаратный шифратор по алгоритму AES. 256-битные слова-затравки подмешиваются в поток генерируемых им 128-битных векторов псевдослучайных чисел, которые буферизуются и становятся доступными командой RDRAND. Также присутствуют схемы стартовой самопроверки и отладочные блоки. Когда все буферы заполнены, вся логика, включая кольцевой генератор, отключается от питания для сохранения энергии.
Производительность самосинхронизированного генератора энтропии — 2,5–3 Гбит/с, что зависит от параметров конкретной пары инверторов. Поэтому он сильно подвержен джиттеру (уходу частоты), с которым обычно нещадно борются. Тестер имеет собственный источник тактирования, который, как нетрудно подсчитать, считывает 512-битные порции с частотой не более 5–6 МГц. А вот очиститель и ГПСЧ тактируются твёрдыми 800 МГц (непонятно только, с какого умножителя частоты их подают — неужели с отдельного?). Очиститель, судя по всему, срабатывает за такт, а вот ГПСЧ требует 11 тактов для каждого 128-битного вектора, генерируя 0,8/11×128≈9,3 Гбит/с. Впрочем, на одной из иллюстраций указано, что верная цифра — ≈6 Гбит/с… Как только новая порция готова и протестирована, из неё тут же вычислят очередную затравку, которая сначала попадает в буфер, а в ГПСЧ будет использована через некий определяемый им самим интервал. Согласно теории (делим 800 МГц на пиковую частоту подачи порций), затравки в среднем хватит на 12–15 векторов, но документ Intel говорит, что максимум из неё можно сделать аж 511 векторов, из чего можно сделать вывод, что тестер, видимо, пропускает в среднем примерно каждую 20-ю порцию.
Аргумент RDRAND — 16-, 32- или 64-битный РОН, причём если в момент обращения буфер пуст, то вместо числа будет выставлен флаг переноса. Происходит это, когда ядра слишком часто читают буфер, быстро его опустошая. С ядрами ГСЧ связан через ту же кольцевую шину, что и остальные компоненты чипа, а потому её частота (равная частоте ядер) теоретически тоже может оказаться ограничивающим фактором. Например, если от внеядра к любому запросившему ядру передаётся только 2/4/8 байт(а)/такт (а не 32, на что способна шина), то именно эта скорость — 8 байт/такт на все ядра — и является пиковой в этом месте. Но буфер всё равно можно опустошить, т. к. темп его заполнения ещё меньше — например, для частоты ядер в 3,5 ГГц это ≈24 такта на 8-байтовое число (или даже ≈37, если цифра ≈6 Гбит/с верна). Более того, в реальных тестах время задержки при непрерывном чтении оказалось и вовсе 104 такта, что всего вдвое меньше чтения из ОЗУ. Почему — неясно.
В официальном учебнике по оптимизации для x86-ЦП Intel написано: «the total bandwidth to deliver random numbers via RDRAND by the uncore is about 500 MBytes/sec». При этом даже 2-ядерный ЦП с частотой 3 ГГц при задержке ГСЧ в 100 тактов будет читать 480 МБ/с. А если он 4-ядерный?… Другие, не менее официальные источники пишут о 800 МБ/с (т. е. 4 Гбит/с) или «70 million RDRAND invocations per second» (т. е. 560 МБ/с, если читать 8-байтовые числа), и даже «RDRAND Response Time and Reseeding Frequency — ≈150 clocks per invocation» (т. е. аж 150 тактов задержки). Все эти цитаты с детальным анализом цифр каждой из них собраны вэтом обсуждении, вывод из которого простой: какая бы цифра ни была верной, темп генерации всё равно оказывается недостаточным для удовлетворения вала запросов от всех ядер, а потому уже придумана схема возможной атаки — повесить на два ядра потоки-паразиты, постоянно запрашивающие случайные числа, чтобы из вечно пустого буфера остальным программам ничего не досталось…
Тем не менее, несмотря на некоторые странности, можно заключить, что благодаря стараниям инженеров Intel мир впервые получил массовый, дешёвый и качественный источник случайных чисел. Вроде бы всё хорошо, если бы не ложка дёгтя: некоторые из прошлых криптоидей Intel также описывались как абсолютно надёжные, например — система CSS для защиты DVD. Сегодня программы копирования дисков так легко её «ломают», что большинство их пользователей и не подозревают о само́м факте взлома шифра, некогда отрекламированного как очень сильный. Почему так получилось — официально никто не объяснял. Однако в сетевых дебрях гуляют анонимные признания сотрудников, согласно которым Intel, наряду с Microsoft и другими фирмами, попала в список «охмуряемых» — некто «попросил» её реализовать слабую защиту, понадеясь на сохранение решения в тайне.
Ныне же всё может измениться. Благодаря компьютерам с процессорами IB кто угодно, включая террористов, хакеров и педофилов (любимый контингент жупелов в доводах государства за ослабление шифров…), получает возможность быстро и дёшево создавать шифры, абсолютно невзламываемые даже для самого АНБ! Неужели нам следует поверить, что на этот раз в таинственной спецслужбе внезапно перестали пробивать внедрение очередной лазейки? Или же мы всё-таки чего-то не знаем? Пока…
Внеядро и ГП
Помимо добавления ГСЧ, остальные блоки внеядра («системного агента») изменились немного.ИКП для памяти DDR3 поддерживает штатные частоты до 1600 МГц, а разогнанные — до 2800 (SB — до 2133). Причём теперь их можно задавать не только с шагом 266,(6) МГц, но и 200 — в частности, 2800 это не 266,(6)×10,5 (в отличие от большинства остальных, этот множитель не может быть полуцелым), а 200×14. Мобильные ЦП смогут поддерживать экономную LP-DDR3 (с неизвестной пока частотой — тем более, что ни один ноутбук или планшет с такой памятью пока не вышел), причём у модуля памяти теперь может быть своё значение TDP для защиты от перегрева. Контроллер PCIe дорос до версии 3.0. (У Xeon на базе SB такой уже есть, но серверный чипсет X79 почему-то позволяет ЦП включать только режим 2.0…) 16 полос PCIe могут использоваться как 16, 8+8 и 8+4+4 — но не всем моделям доступны все комбинации. Шина DMI (по сути — та же PCIe на 4 полосы) осталась версии 2.0 и обеспечивает пропуск в 20 Гбит/с.
|
|
|
