Как можно генерировать случайные биты? Некоторые люди думают, что это непросто, другие скажут вам, что это чертовски сложно, а есть и те, кто задается вопросом, возможно ли это вообще. Конечно, очень легко создать очень длинную псевдослучайную последовательность в программном обеспечении, но даже самый лучший PRNG (генератор псевдослучайных чисел) нуждается в хорошем случайном начальном числе, так как мы не хотим получать одну и ту же последовательность каждый раз, когда мы включаем устройство., не так ли? Вот почему нам нужен TRNG (истинный генератор случайных чисел), но для этого требуется специальное оборудование.
Некоторые high-end микропроцессоры оснащены внутренним аппаратным TRNG, но, к сожалению, это не так для большинства недорогих микроконтроллеров. Есть несколько уловок, которые хакеры используют для компенсации. Обычно они запускают внутренний свободный счетчик и извлекают его содержимое, когда происходит какое-то внешнее событие (пользователь нажимает кнопку или что-то в этом роде). Это работает, но не без недостатков. Во-первых, существует опасность «блокировки» этих двух событий, поскольку период таймера может быть производным от времени процедуры сканирования ввода. Во-вторых, свободное время работы (между включением и моментом, когда устройство запрашивает случайное число) часто бывает слишком коротким, в результате чего начальное число находится слишком близко к началу последовательности и, следовательно, предсказуемо. В некоторых случаях даже нет внешнего ввода до того, как блоку потребуется случайное начальное число!
Несмотря на то, что уже обсуждалось, внутри микроконтроллеров действительно есть источник истинной случайности. Хотя этого может быть недостаточно для криптографических приложений, он по-прежнему генерирует достаточно высокую энтропию для развлекательных игр, симуляций, художественных гаджетов и т. д.
Неинициализированная оперативная память
Хакеры часто используют аппаратные ресурсы сверх своих первоначальных возможностей. Здесь мы будем использовать энергозависимую оперативную память не как блок памяти, а как источник энтропии.
При подаче питания на MCU его внутренняя энергозависимая память имеет неизвестное содержимое. Каждый триггер будет предварительно установлен в состояние 0 или 1 - следствие несовершенства внутренних цепей, сбоев в подаче питания, протекания окружающего тока или теплового (или даже квантового) шума. Вот почему содержимое ОЗУ меняется при каждом включении питания.
Несколько лет назад Intel придумала новый способ генерации истинно случайных битов, используя настроенный триггер, который переводился в метастабильное состояние, а затем возвращался в стабильное состояние 0 или 1 на частоте 3 МГц. оценивать. Объявили, что он будет встроен в процессоры нового поколения.
У нас нет настроенных триггеров в MCU, но у нас есть много триггеров, и мы можем ожидать, что некоторые из них будут работать как настроенные. Сколько триггеров нам действительно нужно, чтобы создать хорошее случайное число, используя энергозависимое содержимое ОЗУ? Это, безусловно, зависит от производительности ОЗУ микроконтроллера, поэтому мы должны провести несколько экспериментов, чтобы увидеть, сколько битов непредсказуемо после включения микроконтроллера. Эта нестабильность возникает только в высокосимметричных триггерах с хорошо сбалансированными транзисторами. Нам нужны эти непредсказуемые биты для сбора энтропии, поэтому мы должны использовать столько данных, сколько у нас есть - всю память данных, прежде чем она будет инициализирована некоторыми известными значениями. У нас нет линий управления, которые могли бы переводить триггеры ОЗУ в метастабильное состояние, поэтому мы можем использовать его только один раз - после включения питания и перед инициализацией ОЗУ.
Эксперименты
Давайте посмотрим содержимое типичного неинициализированного ОЗУ микроконтроллера. На следующем рисунке показано начальное состояние одной части (20480 бит) памяти данных в микроконтроллере PIC18F2525. В каждой строке 256 бит (32 байта). Единицы красные, а нули желтые.
Очевидно, что в этой памяти микроконтроллера меньше единиц, чем нулей, но это не имеет большого значения. Здесь есть еще два интересных вопроса: во-первых, будет ли этот шаблон отличаться, если мы будем использовать другие микроконтроллеры (даже с той же производственной линии), и сколько битов будет изменено после следующего включения питания с тем же микроконтроллером?
Вы, наверное, догадались об ответе на первый вопрос - да, у каждого MCU совершенно разный начальный рисунок ОЗУ. Второй вопрос более важен, и ответ заключается в том, что не так много битов меняется (непредсказуемо) после каждого включения питания. Тем не менее, их достаточно, чтобы сгенерировать несколько случайных байтов.
Вот экспериментальный результат двойного выключения и включения PIC18F2525. Серые пиксели оба раза читаются как 1, белые - как 0, красные - «0, затем 1», а синие - «1, затем 0».
Поэкспериментировав, вы смогли увидеть, что в общем случае одни и те же биты в одном MCU непредсказуемы после включения. Они произошли от «хороших» триггеров и представляют собой наш источник энтропии. Я протестировал только микроконтроллеры Microchip PIC18 и PIC24E (результаты приведены ниже), но любой другой микроконтроллер должен вести себя аналогичным образом. Показанные здесь примеры генерируются с коротким временем нарастания Vdd (высокая скорость нарастания), поскольку переключатель включения-выключения находился между источником постоянного тока и микроконтроллером. Если вы переключите первичную сторону источника питания с низкой скоростью нарастания, вы заметите некоторые закономерности в содержимом памяти, но каким-то образом количество нестабильных битов фактически увеличится.
Программное обеспечение
Итак, если вам нужно несколько случайных байтов (для начального числа PRNG или некоторого магического числа), вы можете использовать неинициализированное содержимое ОЗУ для их генерации. Вы должны создать специальную процедуру, которая будет выполнять операцию XOR (или ADD MOD 256) над каждым байтом в некотором блоке неинициализированного ОЗУ, чтобы сгенерировать первый случайный байт, затем следующий блок для следующего байта и так далее. Например, если ваш MCU содержит 4 КБ ОЗУ (например, PIC18F2525, если вы включаете область SFR) и вам нужно 32-битное начальное число, вы можете разделить ОЗУ на четыре блока по 1024 байта и использовать их для генерации четырех случайных байтов. Даже если небольшие части некоторых блоков уже инициализированы (SFR или переменные для рутинного цикла), это не должно существенно влиять на глобальную энтропию. Я использовал эту технику около десяти лет назад для светодиодных штор, которые имитировали водопад в казино. Для этого проекта я построил много однокристальных микроконтроллеров, и каждый из них регулировал яркость 256 адресуемых светодиодов. Трюк со случайным начальным числом RAM и 32-битным PRNG создал красивый хаос с минимумом оборудования.
Вы также можете добавить больше скремблирования позже, например, вы можете вызвать свою процедуру PRNG из существующего цикла синхронизации (вместо цикла NOP), поэтому она будет вызываться, предположительно, случайное количество раз, пока ваша программа не спросит для вывода PRNG. Этот принцип не создаст хорошую последовательность случайных чисел, если использовать его отдельно, но он не может привести к снижению производительности TRNG, так как энтропия может только расти.
Основным ограничением этого подхода является то, что его нельзя использовать, если есть резервная батарея или если вместо переключателя ON-OFF используется режим SLEEP. Однако для некоторых менее чувствительных приложений (таких как цифровое искусство или развлекательные игры) у вас все еще есть длинная последовательность PRNG, покрывающая период до замены батареи и нового сброса, когда начальное число будет рандомизировано. Вы также можете позволить периферийному счетчику работать в спящем режиме и использовать его позже в скремблировании начального числа PRNG, предполагая, что дополнительный ток в спящем режиме не влияет существенно на срок службы батареи.
Мы должны помнить, что содержимое ОЗУ должно быть деинициализировано и использоваться как есть сразу после включения питания. Также рекомендуется избегать развязки Vdd большой емкости, так как напряжение удержания CMOS RAM может быть довольно низким. Наихудший сценарий - если вы выключите устройство на очень короткий период времени, так что напряжение на развязывающих конденсаторах упадет достаточно, чтобы активировать сброс при отключении питания, но не зашифровать содержимое ОЗУ. К счастью, очень маловероятно, что содержимое ОЗУ когда-либо будет точно таким же, поскольку всегда есть какая-то «служебная» часть ОЗУ (или, по крайней мере, регистры микроконтроллера), на которую будет влиять поток программы. Дополнительную безопасность может обеспечить многобайтовый автономный двоичный счетчик в оперативной памяти, даже если он не нужен программе и никогда не считывает его состояние.
Есть несколько подходов к проектированию, которые можно использовать для повышения качества случайных чисел, получаемых из энергозависимой оперативной памяти. Никогда не инициализируйте всю оперативную память нулями или любым другим содержимым, а только необходимую часть. Если вы не используете спящий режим (а вместо этого отключаете Vdd), то не используйте слишком большую развязывающую способность или, по крайней мере, используйте дополнительный резистор параллельно с питанием MCU. Это увеличит ток питания, но не слишком сильно. Даже 5% от общего тока питания MCU через этот резистор будет достаточно, чтобы предотвратить блокировку напряжения, когда Vdd падает так, что Idd становится близким к нулю, или даже когда какие-то внешние компоненты подают ток на MCU (красивый пример описан в The Mystery). О статье Zombie Ram). Этот резистор гарантирует, что ОЗУ ничего не вспомнит из своих предыдущих «реинкарнаций», даже если MCU перед выключением питания находился в спящем режиме.
Искал в Интернете похожие идеи и опыт, я наткнулся на дискуссию на тему «Почему бы нам не использовать использование ЦП/ОЗУ для «настоящей» случайной генерации. Автор идеи подвергся резкой критике, в основном за то, что он предложил использовать инициализированную оперативную память для криптоприложений. Я также нашел патент US5214423, который основан на аналогичной идее (используется для уменьшения вероятности повторных коллизий доступа к шине). Такие патентные заявки пугают каждого инженера-конструктора, потому что они делают процесс проектирования похожим на прогулку по минному полю - никогда не знаешь, когда на тебя могут подать в суд за твои идеи. Хорошая новость заключается в том, что юридический статус этого патента «истек в связи с неуплатой пошлины за обслуживание», так что, надеюсь, мне не о чем беспокоиться - по крайней мере, на этот раз.
Экспериментальные установки
Первые экспериментальные результаты вдохновили меня на создание некоторых модулей, которые используют неинициализированное содержимое ОЗУ для создания постоянного случайного потока данных. Поэтому я назвал описанную идею (использование неинициализированного содержимого ОЗУ для создания семян) «нулевой концепцией», а затем построил три устройства для тестирования трех новых концепций.
- Два PIC18F2525 с 8-битной односторонней параллельной связью, поддерживаемой простым квитированием. Ведомый MCU генерирует 16 случайных байтов, каждый из которых основан на 248 байтах неинициализированного внутреннего ОЗУ данных. Главный MCU (показан в середине выше) получает эти байты и отправляет их на настольный ПК через порт RS232. После получения 16-байтной строки ведущий ЦП с помощью PNP-транзистора отключает ведомый MCU на 200 мс, что предположительно создаст новое случайное содержимое ОЗУ (по моим экспериментам эффект «Зомби-баран» в 8-битных PIC MCU имеет место, если устройство было выключено менее чем на 85 мс). Затем весь процесс повторяется 625 000 раз, что в сумме дает 10 МБ двоичных данных, необходимых для тестов на случайность. Это занимает около 50 часов (средняя скорость 56 байт/сек).
- Для второго теста используется тот же главный MCU, но на этот раз ведомым является 16-битный MCU 24EP512GP202. Все микроконтроллеры находятся на одной макетной плате (поэтому они и на одной принципиальной схеме), и программа в ведущем микроконтроллере решает, какой подчиненный микроконтроллер будет использоваться. Левый значительно быстрее (70 MIPS против 4 MIPS) и имеет гораздо больше внутренней памяти данных (48 КБ вместо 4 КБ). Одна строка случайных данных содержит 192 байта, поэтому файл размером 10 Мбайт был создан за 5,5 часов.
- И, наконец, используется только один MCU (24EP256GP710A) с 4 Мбайт внешней SRAM (CY62177EV30). У меня были аппаратные остатки от какого-то старого проекта, иначе я бы использовал недорогую I2C SRAM и небольшой MCU. SRAM выключается и снова включается, а затем считывается аналогичным образом. Единственным преимуществом является большой объем оперативной памяти, что привело к высокой скорости, поэтому для файла размером 10 Мбайт потребовалось всего 19 минут. Это могло бы быть намного быстрее, но порт RS232 слишком медленный, чтобы не отставать от быстрого создания потока случайных данных.
Тесты случайности
Были использованы две батареи тестов, Diehard и ENT. Первая концепция (с двумя 18F2525) показала отличный результат - все 15 Diehard и 6 ENT тестов прошли! Остальные две концепции прошли все тесты Дихарда, но не прошли один тест ЛОР, который является наиболее чувствительным индикатором случайности, грубо определяемым как «скорость, при которой распределение хи-квадрат будет случайным образом превышено». Требуемая скорость составляет от 10% до 90% (в идеале 50%), но большинство TRNG и PRNG не проходят этот тест, показывая менее 0,01% или более 99,99%. Fourmilab опубликовал пример хорошо зарекомендовавшего себя коммерческого TRNG, в котором используются события радиоактивного распада - на странице ENT, указанной выше, это оборудование оценивается в 40,98%.
Я не математик, но в ходе экспериментов у меня сложилось ощущение, что пройти все тесты Дихарда должно быть довольно легко (не знаю, почему инженеры-конструкторы этого боятся), а также получить хорошие значения на почти все ЛОР-тесты - но этот просто кошмар! Он значительно колеблется во время роста файла и имеет тенденцию стабилизироваться по мере того, как файл становится достаточно большим, но даже с файлами размером 10 Мбайт он все еще недостаточно стабилен. Этот тест настолько чувствителен, что чрезвычайно трудно получить значения, которые не были бы насыщены ниже 0,01% или выше 99,99%, поэтому, даже если он колеблется где-то между ними, это хорошая новость.
Первый тестовый прогон моего первого концепта дал на удивление хороший рейтинг 47,47%! Две другие концепции потерпели неудачу (<0,01%), но у меня все еще было секретное оружие, называемое отбеливающей трансформацией. В каждом аппаратном TRNG есть какой-то экстрактор случайности (в основном реализованный в программном обеспечении), чтобы минимизировать смещение и повысить равномерность распределения данных. Самый простой способ сделать это - объединить каким-либо образом (например, XOR) необработанные случайные данные из аппаратного TRNG с программным PRNG. Поэтому я добавил простую 32-битную процедуру линейного конгруэнтного ГПСЧ в прошивку MCU (только для концепций 2 и 3) - хотя это может показаться не самой лучшей идеей, она выполнила свою работу, так как все результаты были в пределах допустимого диапазона.. Вот результаты ЛОР-тестов:
| Источник энтропии | 1. (8-битные необработанные данные MCU) | 2. (16-битный MCU с поддержкой PRNG) | 3. (дополнительная оперативная память с поддержкой PRNG) |
| Энтропия (бит/байт) | 7.999982 | 7.999982 | 7.999982 |
| Сжатие уменьшило размер на | 0% | 0% | 0% |
| Распределение хи-квадрат случайным образом будет превышено при | 47.47% | 34.29% | 42.24% |
| Среднее арифметическое значение (127,5=случайное) | 127.4936 | 127.5478 | 127.4937 |
| Ошибка для значения Монте-Карло Пи | 0.03 | 0.05 | 0.00 |
| Последовательный коэффициент корреляции (0,0=некоррелированный) | 0.000206 | 0.000434 | 0.000104 |
Результаты твердотельных испытаний требуют гораздо большего пространства для представления, вы можете найти их на www.voja.rs/rndtests.htm вместе с бинарными файлами, созданными в этом эксперименте, и всеми исходными файлами на языке ассемблера PIC.
Вывод
В итоге все протестированные проекты прошли все тесты Diehard и ENT. Даже коммерческие TRNG (включая очень дорогие модели) иногда не проходят тесты, а эти 10-долларовые самодельные устройства прошли их все!
Важно иметь в виду, что этот принцип основан на недокументированных характеристиках микроконтроллеров, и невозможно достичь степени безопасности, необходимой для криптографических приложений. Итак, как насчет нашего высокого балла? Ну, по крайней мере, мы доказали, что неинициализированная оперативная память может предлагать высококачественные случайные числа и что мы можем использовать ее для генерации начальных значений во многих приложениях MCU. Это просто, бесплатно, не занимает лишнего места на печатной плате и не потребляет лишнего тока.
Для тех, кто хочет получить случайное начальное число без создания собственного оборудования, ознакомьтесь со статьей [Эллиота] о NIST Randomness Beacon.
[Иллюстрация Боба Живковича]
Воя Антонич работает внештатным инженером по микроконтроллерам в Белграде. Его первые микропроцессорные проекты на базе Z80 относятся к 1977 году, всего через несколько лет после появления первого интеловского 4004. Прошивку он собирал вручную, с помощью ручки и бумаги. В 1983 году он опубликовал свой оригинальный проект микрокомпьютера DIY под названием Galaksija, который был создан примерно 8000 энтузиастами в бывшей Югославии. На сегодняшний день он опубликовал более 50 проектов, в основном основанных на микроконтроллерах, и все они выложены в открытый доступ.