(Сентябрь 2011)
Начиная с чипов нового семейства Ivy Bridge, компания Intel стала аппаратно встраивать в свои микропроцессоры цифровой криптогенератор на основе подлинно случайных чисел… Проблема в том, что декларируемая фирмой сильная криптография не вписывается в современную политическую обстановку.
Новая криптографическая технология получила кодовое наименование Bull Mountain (то есть «Бычья гора», по названию населенного пункта в штате Орегон, неподалеку от исследовательского центра Intel’s Circuit Research Lab в г. Хиллсборо, где была разработана система).
Для того, чтобы стало понятнее не только происхождение странноватого названия, но и то, почему появление новой криптотехнологии – это действительно примечательное событие, и как вообще все это хозяйство в чипе реализовано, имеет смысл взглянуть на предмет в более широком историческом, теоретическом и прикладном контекстах.
Немного истории
Случилось так, что развитие теории информации и научной криптографии с самого начала всегда шли бок о бок. То есть четкое представление о том, что любую информацию – тексты, картинки, речь, музыку и прочее – можно передавать в двоичном виде как последовательность нулей и единиц, пришло к человечеству практически одновременно с пониманием того, как должны быть устроены шифры для абсолютно надежного засекречивания такого рода передач.
Более того, и отцом обеих этих великих идей был один и тот же человек – Клод Элвуд Шеннон. Работая в годы второй мировой войны над задачами обеспечения надежной связи, Шеннон сумел строго математически показать, что защита сигнала от шумовых помех и шифрование информации – это, по сути дела, две стороны одной и той же проблемы.
То есть в любом сигнале электросвязи всегда присутствуют две компоненты – полезная информация и хаотический шум электростатических помех, эту информацию искажающих. Для связистов главная задача, конечно же, заключается в эффективной очистке сигнала от шума. А для криптографов, которые, по сути дела, накладывают на сигнал искусственный шум с помощью шифрования, задача в том, чтобы никто, кроме законного получателя, не мог восстановить информацию из-под наложенных шифром помех.
Математическое обоснование этой концепции позволило Шеннону строго доказать, что существует совершенно стойкий шифр, который в принципе невозможно вскрыть аналитически – даже при наличии у противника любых вычислительных и временных ресурсов. Причем шифр этот устроен довольно тривиально (хотя и не очень удобно для практического использования): при каждом засекречивании сообщения длина ключа – или шифрующей последовательности – должна быть точно такой же как у открытого текста.
И если биты этого ключа были сгенерированы на основе чисто случайного хаотического процесса (вроде подбрасывания монеты или сигналов от датчика теплового шума), а побитовое наложение этой последовательности для шифрования сеанса происходило строго один раз, то шансов вскрыть такую систему без ключа у противника нет никаких.
Пример с тепловым шумом здесь далеко не случаен, поскольку уже само рождение научной теории информации и криптографии происходило под влиянием физико-математического аппарата для описания термодинамических процессов.
По совету видного научного светила Джона фон Неймана, в свою теорию Шеннон привлек понятие «энтропии» – математической меры, в термодинамике и статистической физике применяемой для характеристики степени хаотичности или разупорядоченности систем. У Шеннона энтропия стала мерой хаотичности сигнала, а количество информации, соответственно, было определено как величина, обратная энтропии…
Вспоминая впоследствии этот эпизод, Шеннон не без юмора рассказывал, что вообще-то фон Нейман обосновывал свой совет сугубо прагматичными соображениями: среди математиков и инженеров в те времена мало кто был наслышан об энтропии, а потому автор получил бы огромное преимущество в неизбежных грядущих спорах вокруг новой теории.
Вместо споров и критики, однако, произошло очень быстрое и повсеместное признание теории информации научно-техническим сообществом – вполне сравнимое со всеобщим признанием компьютерной архитектуры фон Неймана, реализованной ныне в абсолютном большинстве вычислительных устройств.
Ну а в криптографии, как показывает жизнь, несмотря на все грандиозные достижения цифровых технологий, физические источники хаотического шума по-прежнему являются наиболее качественными источниками энтропии для генераторов криптоключей. Или, как их чаще называют из-за востребованности во множестве других областей, для генераторов случайных чисел.
Немного теории
Теперь хотя бы по минимуму надо разобраться с тем, что принято называть генераторами случайных чисел или кратко RNG (от Random Number Generator), и какие их разновидности сегодня чаще всего используются.
Под термином RNG понимается подпрограмма или аппаратное устройство, где на выходе порождается такая последовательность чисел из некоторого интервала, что ее значения выглядят непредсказуемыми.
Если пояснять непредсказуемость более формально, то каждое значение числа на выходе должно быть статистически независимым от предыдущих значений; общее распределение чисел, выбираемых из интервала, является равномерным; а в последовательности их появления не видно закономерности.
В дополнение к этому от современного RNG обычно хотят, чтобы он был достаточно быстрым в выдаче чисел и был способен к масштабированию (то есть при необходимости мог бы порождать нужный выход в ответ на большое число запросов за короткий интервал времени).
Кроме того, криптографический RNG должен быть стойким против атак злоумышленников, которые могут наблюдать числа на выходе или менять стартовое состояние генератора – дабы затем предсказывать следующие выходные значения, влиять на выход или как-то еще вмешиваться в работу функций генератора.
Если подразделять генераторы случайных чисел на классы, то несколько базовых разновидностей выглядят следующим образом.
Генераторы псевдослучайных чисел или PRNG. Самый распространенный ныне тип RNG, использующий детерминированный алгоритм, в типичных случаях реализованный в программном виде и вычисляющий последовательность чисел, которые «выглядят как случайные». В начале процесса генерации требуется число – «зерно для засева», на основе которого PRNG будет всегда выдавать в точности ту же самую последовательность «случайных чисел». Понятно, что на самом деле генерируемые таким образом числа далеко не случайны. Поэтому в большинстве своем PRNG или ПСЧ-генераторы считаются криптографически небезопасными.
Криптографически безопасные ПСЧ-генераторы или CSPRNG (Cryptographicaly Secure PRNG). Качественный с точки зрения криптографии генератор псевдослучайных чисел должен отвечать трем главным требованиям: (1) выдавать последовательность, статистически неотличимую от случайной равновероятной; (2) противостоять восстановлению прошлых состояний по известному; (3) противостоять восстановлению будущих состояний по текущему состоянию алгоритма. На сегодняшний день у разработчиков имеется хорошее понимание, каким образом должен быть в принципе устроен алгоритм, отвечающий всем этим трем требованиям. Но для того, чтобы все тут работало как надо, необходимо обеспечивать дополнительную «рандомизацию», то есть постоянное подмешивание в алгоритм случайные числа извне. По этой причине особую ценность у криптографов имеют генераторы следующего типа, TRNG.
Генераторы подлинно случайных чисел или TRNG (True RNG). Эти устройства не используют никаких математических моделей для детерминированного порождения чисел, «похожих на случайные». Вместо этого TRNG выделяют энтропию (элемент случайности) из работы физического источника того или иного типа, а затем используют ее для генерации случайных чисел. Физическим источником энтропии могут быть самые разные процессы – вроде нажатия кнопок на клавиатуре или беспорядочных движений манипулятора-мышки, к примеру.
Другой известный пример – на протяжении многих лет одним из популярных TRNG в интернете был веб-проект Lavarand (http://en.wikipedia.org/wiki/Lavarand), где случайные биты генерировались на основе хаотичного поведения форм из расплавленного парафина, порождаемых в «лавовой лампе»… Генераторы типа TRNG обычно очень хороши своей недетерминированностью, однако среди их главных минусов обычно выступает недостаточно высокая производительность и не слишком гладкие «от природы» статистические свойства, желательные в криптографии.
Генераторы каскадной конструкции или CCRNG (Cascade Construction RNG). Можно сказать, оптимальная на сегодняшний день схема криптогенератора для реальных высокоскоростных приложений. Этот тип нашел широкое применение в современных операционных системах и криптографических программных библиотеках. Здесь вход берется от физического источника энтропии, чтобы обеспечить буфер или «пул энтропии». После чего этот энтропийный пул используется для выдачи недетерминированных случайных чисел, которые в качестве «зерен» периодически засевают криптографически безопасный псевдослучайный генератор (CSPRNG).
Помимо хороших статистических характеристик, одно из важнейших достоинств каскадной конструкции – это высокая производительность. Взятие образцов от источников энтропии зачастую может быть медленным, поскольку обычно подразумевает участие входа/выхода устройства того или иного типа, а также некоторое время на то, чтобы произошло собственно событие взятия образца в реальном времени. Но если придумать такую схему, чтобы пул энтропии пополнялся подлинно случайными числами достаточно быстро, то каскадный генератор CCNRG можно сделать одновременно и чрезвычайно быстродействующим (на основе аппаратно реализованного PRNG), и криптографически высокостойким благодаря очень частому засеву алгоритма подлинно случайными зернами.
Именно такую конструкцию и сумели реализовать разработчики Intel в своем новом криптогенераторе Bull Moutain, который планируется массово встраивать в процессоры, начиная с поколения Ivy Bridge.
Бочка меда
Вообще говоря, встраиванием в микропроцессоры генераторов чисто случайных чисел на основе природной энтропии разработчики корпорации Intel начали заниматься довольно давно.
Первые такие модули стали появляться в интеловских чипах еще с 1999 года. Там в качестве TRNG выступала компактная аналоговая конструкция, работавшая на основе теплового шума, который имеется во всех резисторах электрических схем.
После усиления этого хаотического шума, формируемый из него дрожащий сигнал изменял период цикла в относительно медленно тикающих часах. Для каждого из тактов этих беспорядочно тикающих медленных часов схема чипа брала выход от вторых, быстро тикающих часов, которые поочередно выдавали бинарные значения 0 и 1. В результате беспорядочной выборки битов с этого выхода и получалась подлинно случайная последовательность из нулей и единиц генератора.
Один из главных минусов этой аналоговой конструкции был в том, что для усиления теплового шума потреблялось немало энергии. Хуже того, данная схема работала в чипе постоянно и независимо от того, нужны ли приложениям в данный момент случайные числа или нет.
Другой существенный минус аналоговых компонентов внутри чипа – это серьезные проблемы в ситуациях, когда в очередной раз приходит время менять производственные технологии из-за перехода к более мелким масштабам упаковки транзисторов.
Для цифровых элементов схем КМОП-технологии этот регулярный переход осуществляется довольно просто, а вот для каждого нового поколения ужатых аналоговых схем все оказывается гораздо сложнее. Потому что аналоговые компоненты всякий раз требуют дополнительной конструкторской доработки и тестирований, чтобы обеспечивать нужное соотношение сигнал-шум.
Принимая во внимание все эти проблемы, к 2008 году конструкторы Intel всерьез озаботились задачей по созданию такого генератора подлинно случайных чисел, который использовал бы в своей работе исключительно цифровые элементы схемы.
Согласно приведенной выше таксономии, архитектура нового генератора соответствует модели Каскадной конструкции. То есть высокоскоростной (3 миллиарда битов в секунду) источник энтропии, резидентно находящийся в процессоре, используется для часто повторяемого засевания случайными зернами алгоритма, аппаратно реализующего CSPRNG.
Чтобы гарантировать высокое криптографическое качество случайных чисел, с огромной скоростью порождаемых на выходе схемы, в Intel разработали специальный трехэтапный процесс генерации. Помимо базовой аппаратной схемы цифрового TRNG (первый этап), данный процесс также предусматривает «кондиционер» для концентрации случайностей в битах от физического источника (второй этап) и псевдослучайный генератор чисел для повышения производительности (заключительный третий этап). В совокупности же вся эта конструкция и получила кодовое наименование Bull Mountain.
Как подчеркивают разработчики, Bull Mountain изначально создан в соответствии со множеством криптографических стандартов, чтобы была гарантирована надежность и прозрачность реализации новой схемы. Эти стандарты включают в себя NIST SP800-90, FIPS-140-2 и ANSI X9.82.
Самой же интересной частью схемы, конечно, является конструкция цифрового TRNG. Решение, которое удалось найти разработчикам, по праву можно называть парадоксальным, потому что с формальной точки зрения оно нарушает одну из главных заповедей для конструкторов цифровых схем: модули схемы должны находиться в хорошо определенном состоянии, давая на выходе только логические 0 и 1.
В конструкции нового RNG, однако, этот принцип, по сути, поставлен с ног на голову. Данная схема построена на основе известного феномена «метастабильности» – обычно крайне нежелательного эффекта в логических схемах, использующих больше одной тактовой частоты. Под действием нескольких управляющих сигналов элементы такой схемы могут «подвисать» в нечетко определенном состоянии между 0 и 1, а выход из этого состояния зависит от случайностей – типа тепловых микровозбуждений в молекулярной структуре схемы. Цифровой же генератор, созданный командой разработчиков Intel, устроен таким образом, что здесь хаотическим результатом метастабильности является в буквальном смысле каждый бит на выходе модуля.
Более того, эта случайность результата еще и усиливается дополнительно с помощью петли обратной связи, настраивая метастабильность таким образом, чтобы бит падал в состояние 1 или 0 с примерно равной вероятностью. По сути дела, это «превращает данный процесс в электронный эквивалент подбрасывания монеты» – как прокомментировал конструкцию Грег Тэйлор (Greg Taylor), директор Circuit Research Lab и руководитель проекта «Бычья гора».
Еще немного истории
На этом месте самое время еще раз вспомнить о делах отца научной криптографии Клода Шеннона. Сегодня мало кто вспоминает, что все свои великие открытия и работы Шеннон сделал в возрасте до 40 лет, работая в стенах знаменитого исследовательского центра Bell Research Labs.
А затем по никому неведомой причине Шеннон вдруг резко охладел к передовым разработкам, в 1958 году подчистую уволился из Bell Research и занялся тихой преподавательской деятельностью в стенах Массачусетского технологического института. Не выдав с той поры ни одной работы, по своему масштабу хоть как-то соизмеримой с его прошлыми теоретическими достижениями.
Но это вовсе не означает, что большой ученый предавался безделью. Совсем наоборот, помимо безусловного теоретического дара, Шеннону были присущи таланты рукастого и изобретательного инженера-конструктора, благодаря которым он постоянно и очень увлеченно занимался созданием самых разных механизмов и гаджетов – от лыж для хождения по воде до роботов, жонглирующих мячиками.
Люди, бывавшие в большом доме Шеннона, похожем на гибрид музея и мастерской, впоследствии рассказывали о множестве удивительных вещей, изготовленных ученым. Например, было там развлекавшее посетителей механическое устройство, которое работало как подбрасыватель монеты.
Устройство было настроено Шенноном настолько точно, что он мог заранее задавать количество оборотов монеты в воздухе, абсолютно точно программируя таким образом исход как будто бы чисто случайного эксперимента с выпадением орла или решки.
Интерес ученого к тонким взаимосвязям между случайными и детерминированными процессами в 1960-е годы дал и еще один занятный результат: миниатюрный, размером с пачку сигарет аналоговый компьютер, позволявший предсказывать наиболее вероятный сектор-осьмушку для шарика рулетки, запускаемого крупье в казино (расчет по скорости вращения колеса и начальной скорости шарика).
Другой участник этого «строго засекреченного» проекта, известный математик Эдвард Торп, тридцать с лишним лет спустя рассказал на одной из научных конференций, что данное устройство действительно работало, и они с Шенноном даже специально ездили в Лас-Вегас для его практического использования в деле… (подробности см. в материале «Мы не будем полагаться на случай»)
Ложка дегтя
Набор упомянутых фактов из биографии великого ученого понадобился здесь для того, чтобы наглядно продемонстрировать, сколь эффективно оперируют совершенно случайными, казалось бы, процессами те люди, которые глубоко понимают их подлинную, «не совсем случайную» природу.
В области защиты информации такую позицию глубоко понимающего наблюдателя занимают криптографические спецслужбы, и в первую очередь, самая крупная и мощная из них – АНБ США. По давно сложившейся традиции в АНБ очень ревниво относятся к появлению на рынке сильной криптографии, не поддающейся быстрому аналитическому вскрытию, а потому используют все доступные им рычаги для внешне незаметного ослабления шифров и генераторов криптоключей (см. материалы «Объяснимые слабости» и «Неслучайные случайности»).
В самой примитивной форме эту стратегию контроля реализуют элементарным укорачиванием ключа, оставляя рабочими лишь бит 40 или около того, а остальные принудительно забивая нулями или оставляя постоянными. Как это сделано, к примеру, в телефонах GSM (см. «Что показало вскрытие«) или в крипточипах противоугонных автомобильных систем. В частности, в применявшихся вплоть до последнего времени системах на основе RFID-чипов DST фирмы Texas Instruments длина ключа составляла всего 40 бит, а в системах на основе KeeLoq фирмы Microchip, где общая длина ключа 64 бита, реально работают и изменяются при каждом сеансе лишь 28 бит.
В несколько более изощренной форме эта же стратегия может принимать форму криптоалгоритмов с любой, в принципе, рабочей длиной ключа, но функционирующих таким образом, что для грамотного вскрытия этот (или эквивалентный ему) ключ подбирается очень просто или вообще известен заранее. Нечто подобное, в частности, было реализовано в единой схеме генератора криптоключей всех версий ОС Windows вплоть до Win XP (см. «Хитрости крипторемесла«).
Известно, что подобная участь не обошла стороной и некоторые из прошлых криптосхем Intel. Например, бесспорно квалифицированные специалисты именно этой компании разрабатывали одиозно известную систему CSS DVD для защиты от копирования контента на видеодисках. В итоге же этой разработки получилась криптосхема, защиту которой современные программы копирования снимают столь легко, что многие пользователи подобных программ даже не осознают, что взламывают систему, некогда предполагавшуюся очень сильной.
Почему так вышло, официально никто не объяснял. Однако в кулуарах Сети давно гуляют анонимные признания сотрудников фирмы, согласно которым Intel просто «вынудили» реализовать слабую криптозащиту, понадеявшись на сохранение схемы в тайне.
В случае с грядущей массовой доступностью мощного криптогенератора в новых процессорах Intel Ivy Bridge все обстоит гораздо серьезнее, чем с защитой фильмов на DVD.
Фактически, благодаря системе Bull Mountain кто угодно – террористы, бандиты и конечно же чертовы педофилы (стандартный набор параметров в доводах за ослабленное крипто) – получают возможность быстро и дешево создавать совершенно стойкие шифры почти по Шеннону, гарантированно противостоящие взлому.
Все, что для этого надо – просто вызвать новую инструкцию процессора RdRand и на огромной скорости сгенерировать сотни или тысячи гигабайт случайной шифрпоследовательности, разбитой на странички по 1000, скажем, знаков для удобства употребления одноразового шифра в секретной переписке. Далее создать копированием второй экземпляр того же массива – для использования второй стороной – и, считай, готова практически невскрываемая криптосистема…
Возможно, конечно, что в АНБ подобные угрозы уже никого вдруг ныне не колышут. Вот только верится в это как-то с трудом.
kiwi arXiv 