Тропинки к «Бычьей горе»

Начиная с чипов нового семейства Ivy Bridge, компания Intel будет аппаратно встраивать в свои микропроцессоры цифровой криптогенератор на основе подлинно случайных чисел. Новая криптографическая технология получила кодовое наименование Bull Mountain («Бычья гора», по названию населенного пункта в штате Орегон, расположенного неподалеку от исследовательского центра Intel's Circuit Research Lab в г. Хиллсборо, где и была проделана основная часть работы над Bull Mountain). Для того чтобы стало понятнее не только происхождение странноватого названия, но и то, почему появление новой криптотехнологии можно назвать действительным событием, предлагаю взглянуть на предмет в более широком историческом, теоретическом и прикладном контексте.

⇡#Немного истории

Случилось так, что развитие теории информации и научной криптографии с самого начала шли бок о бок. То есть четкое представление о том, что любую информацию — тексты, картинки, речь, музыку и прочее — можно передавать в двоичном виде как последовательность нулей и единиц, пришло к человечеству практически одновременно с пониманием того, как должны быть устроены шифры для абсолютно надежного засекречивания такого рода передач.

Более того, и отцом обеих великих идей стал один и тот же человек — Клод Элвуд Шеннон. Работая в годы Второй мировой войны над задачами обеспечения надежной связи, Шеннон сумел строго математически показать, что защита сигнала от шумовых помех и шифрование информации — это, по сути дела, две стороны одной и той же проблемы.

Клод Шеннон в годы открытий

То есть в любом сигнале электросвязи всегда присутствуют две компоненты — полезная информация и хаотический шум электростатических помех, искажающих эту информацию. Для связистов главная задача, конечно же, заключается в эффективной очистке сигнала от шума. А криптографы, которые, по сути дела, накладывают на сигнал искусственный шум с помощью шифрования, заинтересованы в том, чтобы никто, кроме законного получателя, не мог восстановить информацию из-под наложенных шифром помех.

Математическое обоснование этой концепции позволило Шеннону доказать, что существует совершенно стойкий шифр, который в принципе невозможно вскрыть аналитически — даже при наличии у противника любых вычислительных и временных ресурсов. Причем шифр этот устроен довольно тривиально (хотя и не очень удобно для практического применения): при каждом засекречивании сообщения длина ключа — или шифрующей последовательности — должна быть точно такой же, как у открытого текста. И если биты этого ключа были сгенерированы на основе чисто случайного хаотического процесса (вроде подбрасывания монеты или сигналов от датчика теплового шума), а побитное наложение этой последовательности для шифрования сеанса происходило строго один раз, то у противника нет никаких шансов вскрыть такую систему без ключа.

В годы Второй мировой серийные шифровальные машины были довольно громоздкими, а уровень защиты оставлял желать лучшего даже по меркам докомпьютерной эпохи

Пример с тепловым шумом здесь далеко не случаен, поскольку уже само рождение научной теории информации и криптографии происходило под влиянием физико-математического аппарата для описания термодинамических процессов. Шеннон по совету видного научного светила Джона фон Неймана привлек в свою теорию понятие «энтропии» — математической меры, применяемой в термодинамике и статистической физике для характеристики степени хаотичности или разупорядоченности систем. У Шеннона энтропия стала мерой хаотичности сигнала, а количество информации, соответственно, было определено как величина, обратная энтропии.

Вспоминая впоследствии этот эпизод, Шеннон не без юмора рассказывал, что вообще-то фон Нейман обосновывал свой совет сугубо прагматичными соображениями: в те времена среди математиков и инженеров мало кто был наслышан об энтропии, а потому автор получил бы огромное преимущество в неизбежных грядущих спорах вокруг новой теории. Вместо споров и критики, однако, произошло очень быстрое и повсеместное признание теории информации научно-техническим сообществом — вполне сравнимое со всеобщим признанием компьютерной архитектуры фон Неймана, реализованной ныне в абсолютном большинстве вычислительных устройств.

Ну а в криптографии, как показывает жизнь, несмотря на все грандиозные достижения цифровых технологий, физические источники хаотического шума по-прежнему являются наиболее качественными источниками энтропии для генераторов криптоключей. Или, как их чаще называют из-за востребованности во множестве других областей, для генераторов случайных чисел.

⇡#Немного теории

Теперь давайте вкратце разберемся с тем, что принято называть генераторами случайных чисел или кратко 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, где случайные биты генерировались на основе хаотичного поведения форм из расплавленного парафина, порождаемых в «лавовой лампе»... Генераторы типа TRNG обычно очень хороши своей недетерминированностью, однако среди их главных минусов обычно выступает недостаточно высокая производительность и не слишком гладкие «от природы» статистические свойства, желательные в криптографии.

Право же, непросто догадаться — когда оторвется очередная гигантская капля, и какой формы она будет

• Генераторы каскадной конструкции или CCRNG (Cascade Construction RNG). Можно сказать, оптимальная на сегодняшний день схема криптогенератора для реальных высокоскоростных приложений. Этот тип нашел широкое применение в современных операционных системах и криптографических программных библиотеках. Здесь вход берется от физического источника энтропии, чтобы обеспечить буфер, или «пул энтропии». После чего этот энтропийный пул используется для выдачи недетерминированных случайных чисел, которые в качестве «зерен» периодически засевают криптографически безопасный псевдослучайный генератор (CSPRNG).
  
  Помимо хороших статистических характеристик, одно из важнейших достоинств каскадной конструкции — это высокая производительность. Взятие образцов от источников энтропии зачастую может быть медленным, поскольку обычно подразумевает участие входа/выхода устройства того или иного типа, а также некоторое время на то, чтобы произошло собственно событие взятия образца в реальном времени. Но если придумать такую схему, чтобы пул энтропии пополнялся подлинно случайными числами достаточно быстро, каскадный генератор CCNRG можно сделать одновременно и чрезвычайно быстродействующим (на основе аппаратно реализованного PRNG), и криптографически высокостойким, благодаря очень частому засеву алгоритма подлинно случайными зернами.

Исследования в области криптографии ведутся инженерами Intel уже много лет, и нынешняя итерация — это не робкие шаги к успеху, а, скорее, венец творения

Именно такую конструкцию и сумели реализовать разработчики Intel в своем новом криптогенераторе Bull Moutain, который планируется массово встраивать в процессоры, начиная с поколения Ivy Bridge.

⇡#Бочка меда

Вообще говоря, встраиванием в микропроцессоры генераторов чисто случайных чисел на основе природной энтропии разработчики корпорации Intel начали заниматься довольно давно. Первые такие модули стали появляться в интеловских чипах еще с 1999 года. Там в качестве TRNG выступала компактная аналоговая конструкция, работавшая на основе теплового шума, который имеется во всех резисторах электрических схем.

После усиления этого хаотического шума формируемый из него дрожащий сигнал изменял период цикла в относительно медленно «тикающих» часах. Для каждого из тактов этих беспорядочно «тикающих» медленных часов схема чипа брала выход от вторых, быстро «тикающих» часов, которые поочередно выдавали бинарные значения 0 и 1. В результате беспорядочной выборки битов с этого выхода и получалась подлинно случайная последовательность из нулей и единиц генератора.

Один из главных минусов этой аналоговой конструкции был в том, что для усиления теплового шума потреблялось немало энергии. Хуже того, данная схема работала в чипе постоянно и независимо от того, нужны ли приложениям в данный момент случайные числа или нет.

Другой существенный минус аналоговых компонентов внутри чипа — это серьезные проблемы в ситуациях, когда в очередной раз приходит время менять производственные технологии в сторону более совершенных техпроцессов. Для цифровых элементов схем КМОП-технологии этот регулярный переход осуществляется относительно просто, а вот для каждого нового поколения ужатых аналоговых схем все оказывается гораздо сложнее. Потому что аналоговые компоненты всякий раз требуют дополнительной конструкторской доработки и тестирований, чтобы обеспечивать нужное соотношение сигнал-шум.

Это только на многократно увеличенной фотографии 22-нанометровые 3D-транзисторы выглядят достаточно солидно. На практике же сохранить в них работающую аналоговую часть, мягко говоря, непросто

Принимая во внимание все эти проблемы, к 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.

Вы ведь тоже помните время, когда защита лицензионных DVD казалась непреодолимой?

Известно, что подобная участь не обошла стороной и некоторые из прошлых криптосхем Intel. Например, бесспорно квалифицированные специалисты именно этой компании разрабатывали одиозно известную систему CSS DVD для защиты от копирования контента на видеодисках. В итоге этой разработки получилась криптосхема, защиту которой современные программы копирования снимают столь легко, что многие пользователи подобных программ даже не осознают, что взламывают систему, некогда полагавшуюся очень сильной. Почему так вышло, официально никто не объяснял. Однако в кулуарах Сети давно гуляют анонимные признания сотрудников фирмы, согласно которым Intel просто «попросили» реализовать слабую криптозащиту, понадеявшись на сохранение схемы в тайне.

В случае с грядущей массовой доступностью мощного криптогенератора в новых процессорах Intel Ivy Bridge все обстоит гораздо серьезнее, чем с защитой фильмов на DVD. Фактически благодаря системе Bull Mountain кто угодно — террористы, бандиты и, конечно же, чертовы педофилы (стандартный набор параметров в доводах за ослабленное крипто) — получают возможность быстро и дешево создавать совершенно стойкие шифры почти по Шеннону, гарантированно противостоящие взлому. Все, что для этого надо, — просто вызвать новую инструкцию процессора RdRand и на огромной скорости сгенерировать сотни гигабайт случайной шифрпоследовательности, разбитой на странички по 1000, скажем, знаков для удобства употребления одноразового шифра в переписке. Создать копированием второй экземпляр массива — и все...

Возможно, конечно, что в АНБ подобные угрозы уже никого вдруг ныне не волнуют. Вот только верится в это как-то с трудом.