Знай себе числа генерируй на основе непредсказуемых данных физического мира — немудреная мысль эта преследует человека на протяжении всего пути современной криптографии. Псевдослучайные генераторы чисел (PRNG), основанные на одних лишь математических алгоритмах, предсказуемы или подвержены внешнему влиянию, поэтому аппаратные генераторы, использующие различные источники энтропии, считаются золотым стандартом безопасности.
Однако даже генераторы реальных случайных чисел (RNG), собирающие непредсказуемые данные физических явлений, имеют недостатки: они могут быть громоздкими, медленными и дорогостоящими в производстве. Нет никакой гарантии, что проприетарная система не открыта для спецслужб — поэтому разработчики FreeBSD, отказались от непосредственного использования аппаратных генераторов, встроенных в чипы Intel.
Эволюция методов шифрования повлекла за собой необходимость создать более совершенные генераторы — о них и пойдет сегодня речь.
100 лет назад для получения случайных чисел бросали игральные кубики, раздавали карты, собирали номера из шляпы. В 1927 году статистик Леонард Генри Калеб Типпетт опубликовал первую в мире «таблицу случайности» — 41 600 чисел — полученную путем сбора данных о площади английских церквей.
В 1955 году корпорация RAND опубликовала книгу, которая на долгие годы стала одним из главных источников данных о рандоме — «Миллион случайных цифр со стандартным отклонением 100 000». Возможно, книгу до сих пор никто не прочитал от корки до корки — почти весь ее текст состоит из пятизначных чисел.
С развитием компьютерной эры для RNG стали использовать осмысленные и неосмысленные действия пользователя: нажатия клавиш на клавиатуре, клики мышью и др. Впрочем, такой подход дает небольшую скорость получения случайных бит. Проблема и в том, что все происходящее внутри компьютера нельзя считать истинно случайным. Компьютеры с самого начала создавались так, чтобы быть предсказуемыми. Источники из окружающей среды — например, действия пользователя — тоже имеют свои пределы, хотя бы во времени.
Высокие требования к безопасности дали жизнь сразу нескольким новым взаимодополняющим подходам к генерации случайных чисел.
«Игрушечный» генератор
Фонд Electronic Frontier Foundation (EFF), занимающийся борьбой за общечеловеческие права в вопросах, связанных с новыми технологиями связи, предложил простой способ создания безопасных паролей, основанный на использовании физического генератора случайных чисел.
Способ действительно простой — в его основе игральные кости.
Бросаем пять игральных кубиков одновременно, и записываем получившиеся цифры. Допустим, кубики расположились слева направо так: 4, 3, 4, 6, 3. Открываем список EFF's Long Wordlist, чтобы найти соответствующее слово рядом с 43463. Это слово «panoramic».
Процедура повторяется пять раз. В результате у нас получается что-то вроде panoramic nectar precut smith banana handclap — парольная фраза, которая имеет около 221 073 919 720 733 357 899 776 вариаций.
С помощью мнемоники фразу легко запомнить. С учетом наличия 2⁷⁷ альтернатив брутфорсом подобрать ваш пароль будет крайне сложно.
ChaosKey
Кейт Паккард, активный разработчик Debian, лидер проекта X.Org, создатель XRender, XComposite и XRandR, совместно с известным сторонником открытых данных, главой направления Linux-проектов Hewlett-Packard Бдейлом Гарби разработали недорогой, но надежный генератор случайных чисел ChaosKey.
Устройство с открытым исходным кодом ChaosKey 1.0 было представлено на конференции DeConf16 Debian. Цель разработки — добавить реальную энтропию генератору случайных чисел, обеспечить высокий уровень безопасности и снизить цену до минимума.
К ChaosKey невозможно получить удаленный доступ и нельзя перезаписать прошивку, даже когда устройство подключено по USB к компьютеру. Для этого вам необходимо получить физический доступ, вскрыть гаджет и соединить два контакта внутри.
Сам полнофункциональный RNG похож на маленькую флешку и занимает один USB-разъем. Конструкция платы минималистична — на ней фактически имеется только процессор и транзисторы для генерации шума. Скорость передачи случайных значений — около мегабайта в секунду.
И по поводу цены. Устройство можно заказать, но все схемы и прошивка выложены в открытый доступ — разработчики сами рекомендуют каждому создавать и совершенствовать ChaosKey.
Z1FFER
Еще один недорогой генератор случайных чисел с открытым исходным кодом, который придется по душе всем любителям DIY. Каждый может собрать и разобрать устройство, а также удостовериться, что в нем нет встроенных бэкдоров.
Z1FFER не является законченным продуктом и не поставляется с каким-либо ПО (авторы делятся лишь несколькими сценариями и инструкцией для начала работы). Он предназначен для работы на платформе arduino, однако не имеет подтвержденной надежности от взлома извне. Устройство в первую очередь для тех, кто хочет лично «пощупать» технологию генерации чисел с помощью железа.
Z1FFER использует тепловой шум от резистора, удваивая сигнал, что приводит к экспоненциальному росту сложности предсказания последовательности бит.
QRBG121
Грешно было бы не упомянуть в этой теме генератор случайных чисел QRBG121, который по неизвестной причине однажды стал маскотом одной из имиджборд рунета. QRBG121 (Quantum Random Bit Generator), возможно, действительно, у кого-то вызывает умиление, но самое интересное скрывается внутри коробочки.
Эффект случайности в устройстве зависит от квантового физического процесса фотонного излучения в полупроводниках и последующего обнаружения отдельных фотонов с помощью фотоэлектронного умножителя. В этом процессе фотоны обнаруживаются случайным образом, независимо друг от друга. Информация о синхронизации обнаруженных фотонов используется для генерации бит. Уникальной особенностью этого метода является то, что он использует только один детектор фотонов для получения как нулей, так и единиц.
Лава-лампы в Cloudflare
Компания CloudFlare, которая сама заявляет, что через ее сеть проходит «около 10 % мирового трафика», защищает интернет-проекты от DDoS-атак, но и ей самой нужна защита. Трафик, который проходит через сети CloudFlare, шифруется — и в этом помогает сотня разноцветных лава-ламп на «Стене Энтропии».
Лавовая лампа представляет собой стеклянную емкость, заполненную прозрачным маслом и полупрозрачным парафином. Расположенная в нижней части емкости лампочка накаливания нагревает и подсвечивает содержимое цилиндра, при этом происходит «лавообразное» перемещение парафина в масле. Парафин немного тяжелее масла, но при небольшом нагреве становится легче и всплывает.
За движением жидкостей наблюдают несколько камер, делающих моментальные фотоснимки. Снимки преобразовываются в числа, из которых потом генерируются ключи шифрования. За один кадр получается 16 384 бит энтропии.
В двух других офисах CloudFlare используются иные способы получать случайные значения. В Лондоне камера снимает движения трех хаотических маятников, а в Сингапуре поставили счетчик Гейгера, замеряющий показатели радиоактивного распада небольшого кусочка урана. В последнем случае уран используется в качестве «источника данных», поскольку для радиоактивного излучения характерна случайность каждого отдельного акта распада.
Все эти способы работы с данными привлекают внимание к деятельности компании, чья работа часто остается невидимой для обычных клиентов.
HotBits
HotBits — сайт, который предоставляет всем желающим истинные случайные числа, генерируемые с помощью счетчика Гейгера, регистрирующего ионизирующее излучение. Вы заполняете на сайте форму запроса с указанием количества случайных байт и выбираете предпочтительный способ получения данных. Предварительная заявка необходима, поскольку аппаратное обеспечение HotBits позволяет создавать данные со скромной скоростью около 100 байт в секунду.
После того, как случайные числа предоставляются клиенту, они немедленно удаляются из системы — одни и те же данные никогда не будут отправлены разным пользователям (если, конечно, вы доверяете HotBits).
Для получения еще большей надежности данных существует ресурс EntropyPool, который собирает и «миксует» случайные биты из разных источников, включая HotBits и random.org (этот ресурс, в свою очередь, «добывает» энтропию атмосферного радиошума). Люди, которые переживают за квантовую безопасность в максимальной степени, к вышеназванным ресурсам могут добавить онлайн-сервис Quantum Random Bit Generator.
Квантовые флуктуации вакуума
Схематическое представление пространственно-временных отклонений от уровня невозмущенных вакуумных флуктуаций электрического поля
Источник
Вакуум, вопреки названию («vacuus» — пустой), истинно пустым считать нельзя, поскольку в нем в силу принципа неопределенности Гейзенберга беспрестанно рождаются и умирают виртуальные частицы — происходят так называемые квантовые флуктуации, колебания уровня энергии в единице объема пространства-времени.
Канадские физики сконструировали быстрый и конструктивно простой генератор случайных чисел на базе вакуумных флуктуаций. Генератор состоит из импульсного лазера с высокой частотой излучения, среды с высоким коэффициентом преломления (алмаз) и детектора. Проходя через алмаз, каждый импульс на детекторе показывает разные характеристики, в зависимости от вакуумных флуктуаций поля, которые встретились на пути фотонов. В спектре рассеянного излучения на выходе появляются спектральные линии, которых нет в спектре первичного света, а из-за непредсказуемости вакуумных флуктуаций эти линии каждый раз отличаются непредсказуемым образом.
Физики говорят, что не существует даже концепции того, как теоретически можно было бы разработать устройство для предсказаний колебаний энергии появления и аннигиляции виртуальных частиц — это одно из самых случайных событий, которое мы наблюдаем во Вселенной.
Осталось сделать этот генератор достаточно компактным и дешевым, чтобы начать его массовое использование.
Сервер случайных чисел ANU Quantum
Альтернативный вариант, основанный на измерении квантовой флуктуации вакуума, предлагает сайт ANU Quantum. Случайные числа, выложенные в открытый доступ, генерируются в реальном времени в лаборатории Центра квантовых вычислений и коммуникационных технологий Университета Нового Южного Уэльса (Сидней, Австралия).
Измеряя колебания электромагнитного поля вакуума, ANU Quantum позволяет всем видеть, слушать или загружать случайные квантовые числа и оценивать в реальном времени качество генерируемых чисел.
Серийная квантовая случайность
Существует не так много компаний, создающих устройства QRNG (Quantum Random Number Generator). Лидером в этом направлении сейчас называют швейцарский стартап ID Quantique (IDQ), с 2001 года создающий коммерческие генераторы квантовых случайных чисел. IDQ предлагает множество форматов QRNG, как показано на изображении выше. Одно из самых популярных устройств компании — USB Quantum, генерирующее больше случайных чисел, чем вам, вероятно, может понадобиться в этой жизни.
Другая известная в этой области компания — QuintessenceLabs. В компании утверждают, что их версия QRNG-устройства настолько мощная, что эквивалентна 60 устройствам IDQ.
Компания ComScire на рынке QRNG-устройств представлена с 1994 года. На изображении выше представлен топовый источник случайных чисел, дающий поток данных из смешения различных типов транзисторных шумов со скоростью 128 Мбит/сек.
Генератор из углеродных нанотрубок
Существующие решения аппаратных и программных генераторов не особенно подходят для носимых устройств. В Northwestern предложили другой подход, сочетающий компактность с генерируемым тепловым шумом.
Исследователи построили генератор случайных чисел из статической ячейки памяти с произвольным доступом (SRAM), напечатанной специальными чернилами, содержащими полупроводниковые углеродные нанотрубки. Ячейка памяти использует флуктуации теплового шума для генерации случайных бит.
Генератор из углеродных нанотрубок можно напечатать на гибких пластиковых подложках, что позволяет интегрировать его в крошечные устройства гибкой электроники — носимые датчики, одноразовые этикетки, элементы умной одежды. Печать ячеек SRAM с нанотрубками относительно недорогой процесс, что позволяет использовать их в производстве бытовой электроники.
Генератор квантовых случайных чисел из смартфона
В 2014 году Женевский университет отметился устройством QRNG, которое использует восьмимегапиксельную камеру смартфона Nokia N9.
Камера смартфона подсчитывает количество фотонов, попадающих на каждый отдельный пиксель. Источником света выступает обычный светодиод. Работа камеры и светодиода регулируется так, чтобы каждый пиксель в 8 МП камере обнаруживал около 400 фотонов за короткое время. Число фотонов на всех пикселях преобразуется в последовательность случайных чисел со скоростью 1,25 Гбит/сек.
Такая скорость — не рекорд. Еще в 2011 году Intel показал, что их процессорный генератор создает поток случайных чисел со скоростью около 3 Гбит/сек. Однако все компоненты QRNG могут быть интегрированы на чипе стоимостью в несколько долларов и легко добавлены в любые портативные электронные устройства, включая смартфоны.
Истинная случайность
Имея так много источников данных, логично задаться вопросом: а как в действительности проверить случайность бит?
Национальный институт стандартов и технологий США предложил «Пакет статистических тестов для случайных и псевдослучайных генераторов чисел для криптографических приложений». В его состав входят 15 статистических тестов, целью которых является определение меры случайности бит, порожденных либо аппаратными, либо программными генераторами.
Одни из самых строгих статистических тестов предложил профессор Джордж Марсалья из Университета штата Флорида. «Тесты diehard» включают 17 различных проверок, некоторые из них требуют очень длинных последовательностей: минимум 268 мегабайт.
Случайность можно проверить с помощью библиотеки TestU01, представленной Пьером Л`Экуйе и Ричардом Симардом из Монреальского университета, включающей классические тесты и некоторые оригинальные, а также посредством общедоступной библиотеки SPRNG.
Еще один полезный сервис для количественного измерения случайности — http://www.fourmilab.ch/random.
И не будем забывать про самый главный критерий — каждый следующий бит в последовательности случайных данных должен быть предсказан с вероятностью, не превышающей вероятность встретить динозавра на улице ;)
