Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com — новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.
К сожалению, ваша первая покупка в интернете была скомпрометирована с самого начала: вскоре обнаружится, что якобы безопасный протокол, по которому браузер установил соединение, на самом деле не очень защищён.
Проблема в том, что секретные ключи, которые использовал Netscape, были недостаточно случайными. Их длина составляла всего 40 бит, что означает около триллиона возможных комбинаций. Это кажется большим числом, но хакерам удалось взломать эти коды, даже на компьютерах 1990-х годов, примерно за 30 часов. Якобы случайное число, которое Netscape использовал для генерации секретного ключа, базировалось всего на трёх значениях: времени суток, идентификационном номере процесса и идентификационном номере материнского процесса — все они являются предсказуемыми. Из-за этого злоумышленник имел возможность сократить количество вариантов для перебора и найти нужный ключ гораздо раньше, чем предполагали в Netscape.
Программисты Netscape с радостью бы использовали полностью случайные числа для генерации ключа, но не знали, как их получить. Причина в том, что цифровые компьютеры всегда находятся в точно определённом состоянии, которое меняется только при поступлении определённой команды от программы. Самое лучшее, что вы можете сделать — эмулировать случайность, генерируя так называемые псевдослучайные числа с помощью специальной математической функции. Набор таких чисел на первый взгляд выглядит полностью случайным, но кто-нибудь другой с помощью такой же процедуры может легко сгенерировать в точности такие же числа, так что обычно они плохо подходят для шифрования.
Исследователям удалось изобрести генераторы псевдослучайных чисел, которые признаны криптографически надёжными. Но их нужно запускать с качественного случайного начального значения (random seed), иначе они всегда сгенерируют один и тот же набор чисел. И для этого начального значения вам нужно нечто такое, что действительно невозможно подобрать или предсказать.
К счастью, несложно получить действительно непредсказумые значения, используя хаотическую вселенную, которая со всех сторон окружает строго детерминированный мир компьютерных битов. Но как именно это сделать?
В течение последних лет в онлайне работает источник случайных чисел под названием Lavarand. Он был создан в 1996 году для автоматической генерации случайных значений путём обработки фотографий декоративного светильника — лавовой лампы, которая непредсказуемым образом меняет облик каждую секунду. С тех пор случайными значениями из этого источника воспользовались более миллиона раз. Есть и более изощрённые аппаратные генераторы случайных чисел, которые регистрируют квантовые эффекты, например, удары фотонов в зеркало. Вы можете на самом обычном компьютере получить случайные числа путём регистрации непредсказуемых событий, таких как точное время нажатия на кнопки клавиатуры. Но чтобы получить большое количество таких случайных значений, придётся нажать немало кнопок.
Мы с коллегами в компании Intel решили, что нужно сделать более простой способ. Вот почему уже более десяти лет многие из чипсетов нашего производства содержат аналоговый аппаратный генератор случайных чисел. Проблема в том, что его аналоговый контур впустую расходует энергию. Вдобавок, трудно сохранить работоспособность этой аналоговой схемы по мере совершенствования техпроцесса по производству микросхем и их миниатюризации. Поэтому сейчас мы разработали новую и полностью цифровую систему, которая позволяет микропроцессору генерировать обильный поток случайных значений без этих проблем. Скоро этот новый цифровой генератор случайных чисел придёт к вам вместе с новым процессором.
Первая попытка Intel сделать лучший генератор случайных чисел на обычных ПК датируется 1999-м годом, когда компания Intel представила компонент Firmware Hub для чипсетов. Генератор случайных чисел в этом чипе (PDF) представляет собой аналоговый дизайн на базе кольцевого осциллятора, который регистрирует тепловой шум с резисторов, усиливает его и использует результирующий сигнал для изменения периода относительно медленного генератора тактовых импульсов. На каждый непредсказуемый «тик» этого медленного генератора микросхема накладывала частоту колебаний второго, быстрого генератора, который регулярно меняет своё значение между двумя бинарными состояниями: 0 и 1. В результате получается непредсказуемая последовательность нулей и единиц.
Проблема в том, что кольцевой осциллятор, который занимается усилением теплового сигнала, потребляет слишком много энергии — и он работает постоянно, независимо от того, нужны или нет компьютеру случайные числа в данный момент. Эти аналоговые компоненты также доставляют неудобства каждый раз, когда компания меняет техпроцесс производства микросхем. Каждые несколько лет компания модернизирует производственные линии, чтобы делать микросхемы в более миниатюрном масштабе. И каждый раз этот аналоговый фрагмент нужно по-новому калибровать и тестировать — эта сложная и кропотливая работа стала настоящей головной болью.
Вот почему в 2008 году Intel принялась за разработку генератора случайных чисел, который работает исключительно на цифровой основе. Исследователи компании в Хиллсборо (Орегон, США), совместно с инженерами Design Lab в Бангалоре (Индия) начали изучать ключевую проблему — как получить случайный поток битов без использования аналоговых схем.
Забавно, но предложенное ими решение нарушает основное правило цифрового дизайна, что схема должна всегда быть в определённом положении и возвращать либо логический 0, либо 1. Конечно, цифровой элемент может проводить краткосрочные промежутки времени в неопределённом положении, переключаясь между этими двумя значениями. Однако, он должен работать предельно чётко и никогда не должен колебаться между ними, иначе это вызовет задержки или даже сбой в системе. В нашем же генераторе случайных битов колебания являются фичей, а не багом.
НЕОПРЕДЕЛЁННЫЕ СХЕМЫ: Когда транзистор 1 и транзистор 2 включаются, пара инвертеров поворачивают узлы Node A и Node B в одинаковое положение [налево]. Если возрастает тактовая частота [жёлтый график справа], эти транзисторы отключаются. Первоначально оба инвертера обращаются в неопределённое положение, но случайный тепловой шум в инвертерах скоро поворачивает один узел в логическое положение 1, а другой узел — в логическое положение 0.
Дизайн состоит из пары инвертеров — элементов цепи, у которых значение на выходе является обратным значению на входе. Мы соединили выход одного инвертера со входом другого инвертера. Если на выходе у первого инвертера 0, то второй инвертер получает это на входе и, соответственно, выдаёт 1. Или если первый инвертер выдаёт 1, то второй инвертер будет выдавать 0.
Дополнительно в цепь к двум инверторам добавлены два транзистора с довольно странным местоположеием. Включение этих транзисторов даёт на входе и на выходе обоих инвертеров логическую 1. Конечно, инвертеры пришлось слегка модифицировать, чтобы такой фокус стал возможным, но это довольно просто сделать.
Самое интересное начинается, когда транзисторы отключают. Двум инвертерам не нравится, что у них на выходах одинаковое состояние, и они стремятся принять противоположное положение, то есть одно из двух устойчивых состояний. Но какой инвертер поменяется на 0? Это неизвестно.
Есть две вероятности, и цепь выбирает между ними. В идеальном мире статус-кво может сохраняться вечно, но в реальности даже минимальное воздействие теплового шума — случайных атомных вибраций — сталкивает цепь в одно из двух возможных устойчивых состояний.
В данном случае, наша простая цифровая схема с лёгкостью получает частичку вездесущной случайности природы. Всё что нам остаётся — подключить генератор тактовых импульсов, который будет регулярно включать и выключать транзисторы. На каждый такт генерируется один случайный бит.
Этот цифровой подход к генерации случайных битов работал бы хорошо, если бы инвертеры были абсолютно одинаковыми. Но из-за несовершенства физического мира так никогда не бывает. В реальности, два инвертера никогда не бывают абсолютно одинаковыми. Отличия в их характеристиках могут казаться чрезвычайно маленькими, но в данном применении эти отличия способны легко скомпрометировать случайный поток битов, который мы пытаемся извлечь из цепи.
Чтобы соблюсти сбалансированность инвертеров, мы встроили механизм обратной связи, чтобы схема соответствовала одному из правил статистической случайности, в соответствии с которым в длинной последовательности должно быть одинаковое количество всех возможных чисел. Таким образом, мы можем бороться с предсказуемостью, которая внушает такой ужас любому криптологу.
Одновременно с разработкой надёжного цифрового источника случайных чисел, другие инженеры Intel начали разработку дополнительных логических элементов, чтобы эффективно обрабатывать и использовать эти биты. Вы могли бы подумать, что процессор способен просто принимать сырой поток битов из генерирующего контура и вставлять их в программу. Но на самом деле эти биты не настолько случайны, как хотелось бы. Сырой поток из контура, независимо от качества оборудования, в любом случае может иметь какие-то перекосы в ту или иную сторону.
Нашей целью было создать систему, которая выдаёт поток случайных чисел, соответствующий признанным криптографическим критериям, таким как стандарты Национального института стандартов и технологий США. Чтобы гарантировать качество наших случайных чисел, мы разработали трёхступенчатый процесс, в котором задействованы первоначальная цифровая схема, «нормализатор» (conditioner) и генератор псевдослучайных чисел — теперь известный под кодовым названием Bull Mountain.
Наш предыдущий аналоговый генератор был способен выдавать только пару сотен килобит случайных чисел в секунду, в то время как новый генерирует их потоком около 3 Гб/с. Он начинает работу, собирая практически случайные значения двух инвертеров блоками по 512 бит. В дальнейшем эти блоки разбиваются на пары 256-битных чисел. Конечно, если оригинальные 512 бит не полностью случайны, эти 256-битные числа тоже не будут полностью случайными. Но их можно математически скомбинировать таким образом, чтобы получить 256-битное число, близкое к идеальному.
ТРИ УРОВНЯ ЧИСЕЛ: Генератор случайных чисел Intel Bull Mountain предотвращает любые варианты предсказуемости с помощью трёхступенчатого процесса. Сначала цифровой контур генерирует поток случайных битов. Потом «нормализатор» (conditioner) генерирует на основе этого потока хорошие случайные начальные значения (random seeds). На третьем этапе генератор псевдослучайных чисел выдаёт поток цифр для использования в программном обеспечении.
Всё это лучше показано на простой иллюстрации. Предположите на секунду, что генератор случайных битов выдаёт 8-битные комбинации, то есть как бы числа в диапазоне от 0 до 255. Предположите также, что эти 8-битные числа не полностью случайны. Теперь представьте, что, к примеру, какой-то неуловимый изъян в цепи смещает выдаваемые значения в нижнюю часть диапазона. На первый взгляд, поток случайных чисел кажется хорошим, но если вы обработаете миллионы значений, то заметите, что числа из верхней части диапазона встречаются немножко реже, чем числа из нижней части.
Одно из возможных решений этой проблемы простое: всегда берите пару 8-битных чисел, перемножайте их, а потом отбрасывайте верхние восемь бит из получившегося 16-битного числа. Такая процедура устранит перекос практически целиком.
Bull Mountain не работает с 8-битными числами: он работает, как уже было сказано, с 256-битными числами. И он их не перемножает, а производит более сложные криптографические операции. Но основная идея та же самая. Вы можете представить этот этап как «нормализацию» по устранению тех отклонений от случайного распределения чисел, которое может возникнуть в схеме с двумя инвертерами.
Нам действительно хочется хорошо спать по ночам, так что спроектировали дополнительную схему, которая проводит тестирование потоков 256-битных чисел, которые поступают в «нормализатор», чтобы они не были слишком смещёнными в какую-то сторону. Если такое обнаруживается, мы помечаем его как бракованный и не соответствующий стандартам. Таким образом, операции производятся только с качественными парами чисел.
Гарантированной случайности недостаточно, если случайные значения не выдаются достаточно быстро, чтобы соответствовать стандартам. Хотя аппаратный контур генерирует поток значительно быстрее, чем его предшественники, этого всё ещё недостаточно для некоторых современных задач. Чтобы Bull Mountain мог выдавать случайные числа так же быстро, как выдают поток программные генераторы псевдослучайных чисел, но при этом сохранять высокое качество случайных чисел, мы добавили ещё один уровень в схему. Здесь 256-битные случайные числа используются как криптографически надёжные начальные значения (random seeds) для генерации большого количества псевдослучайных 128-битных чисел. Поскольку 256-битные числа поступают с частотой 3 ГГц, то гарантируется достаточное количество материала для быстрой генерации криптографических ключей.
Новая инструкция под названием RdRand даёт возможность программе, которой нужны случайные числа, обратиться с запросом к аппаратному обеспечению, которое их производит. Созданная для 64-битных процессоров Intel, инструкция RdRand — это ключ к генератору Bull Mountain. Она извлекает 16-, 32- или 64-битные случайные значения и помещает их в регистр, доступный для программы. Инструкция RdRand была открыта для публики около года назад, и первым процессором Intel, который будет поддерживать её, станет Ivy Bridge. Новый чипсет работает на 37% быстрее, чем его предшественник, а размер его минимальных элементов уменьшен с 32 до 22 нанометров. Общее увеличение производительности хорошо сочетается с потребностями нашего генератора случайных чисел.
Хотя лавовые лампы выглядят круто, они впишутся не в каждый интерьер. Мы думаем, что наш подход к генерации случайных чисел, напротив, найдёт самое универсальное применение.
Как уже было упомянуто, регистрация точного времени нажатия на клавиши использовалась как удобный источник случайных стартовых значений для генераторов в прошлом. Для тех же целей использовали передвижения мыши и даже скорость поиска секторов на жёстком диске. Но такие события не всегда дают вам достаточное количество случайных битов, и при определённом времени измерений эти биты становятся предсказуемыми. Хуже того, поскольку мы теперь живём в мире серверов с SSD и виртуализацией, эти физические источники случайностей просто недоступны на многих компьютерах. На этих машинах требуется получать случайные числа каким-то другим способом, а не событиями на периферийных устройствах. Bull Mountain предлагает решение.
Так что если вы программист, будьте готовы к появлению обильного источника случайности прямо под рукой. И даже если вы не хотите отказываться от любимого генератора псевдослучайных чисел, который привыкли использовать для криптографии, научных вычислений или даже в играх — у вас теперь есть Bull Mountain для получения начальных значений к нему. Мы ожидаем, что такое применение Bull Mountain будет весьма популярным, в результате чего вырастут и расцветут разные виды замечательного софта.
