Мы продолжаем рассказывать о проектах Зимней школы RISC-V, организованной YADRO. Возможно ли создать программный генератор на базе открытой архитектуры, используя физически неклонируемые функции (PUF) динамической памяти? Команда из БГУИР — Никита Малявко, Ксения Трубач, Михаил Кулик, Павел Шлык — в своем проекте проверила гипотезу о наличии PUF в динамической памяти и создала модель одноканального источника шума. Затем реализовала постобработку и тестирование, измерила производительность генератора и оптимизировала код.

Как устроена динамическая память? Каждая ячейка DRAM складывается из транзистора и конденсатора. Конденсаторы разряжаются, поэтому без периодической подзарядки данные памяти будут потеряны. Так же, как и в результате чтения данных из памяти.

Как получить случайные данные из DRAM? Нужно ее полностью выключить, подождать, пока конденсаторы разрядятся, и включить снова. Новые состояния ячеек памяти можно будет анализировать и исследовать в качестве случайных данных.

Устройство генератора случайных числовых последовательностей

На основе DRAM мы создали модель одноканального источника шума, который возвращает один случайный бит за один условный такт. Память разбита на два региона, которые не пересекаются. Первый отвечает за инициализацию одноканального сигнатурного анализатора (ОСА), который инициализирует второй подобный анализатор. Затем мы сможем взять другой регион памяти и заново инициализировать первый ОСА, что абсолютно случайным образом изменит выход второго ОСА. Такая схема позволит не перезагружать память после каждой генерации числовой последовательности — ведь в реальных проектах это, как правило, невозможно. 

Далее мы направляем данные из DRAM PUF в два подмодуля — постобработки, а также тестирования, анализа и оценки качества данных. Первый частично запускается на «железе», второй — на собранных данных на машине хоста.

Для постобработки мы протестировали шесть комбинаций. Последняя нам кажется наиболее перспективной:

• сырые данные,

• чистый корректор фон Неймана,

• одноканальный сигнатурный анализатор,

• чистый корректор фон Неймана + одноканальный сигнатурный анализатор,

• одноканальный сигнатурный анализатор + чистый корректор фон Неймана,

• многоканальный сигнатурный анализатор (МСА).

Как работает наш сигнатурный анализатор? Мы отводим на генерацию 32-разрядного слова 32 такта: забираем по биту из памяти, прогоняем его через анализатор 32 раза и получаем на выходе 32-разрядное слово:

fn made_shift(&mut self, bit: u32){
  let new_bit = (self.state & self.taps).count_ones() & 1;
  let xored bit = (bit & 1) ^ newbit;
  self.state = (self.state « 1) | xored_bit;
}

Прототип мы делали на x64, поэтому в код включена небольшая оптимизация count_once, которая раскрывается в инструкцию popcount. На некоторых RISC-V-процессорах она тоже имеется, но мы работали с AMD MicroBlaze, где ее не было. Чтобы реализовать многоканальный сигнатурный анализатор, мы взяли 32 сигнатурных анализатора и отвели на генерацию один такт.

Наш тестовый стенд основан на плате Digilent Zybo Z7-10 с процессором Cortex и гигабайтом отделяемой памяти. На программируемой логике развернут процессор Microblaze R15, на нем запущен рантайм на C. Логика написана на Rust и слинкована с кодом на C. Для работы с ПЛИС мы использовали тулчейн Xilinx, а для сбора сырых данных — Jupyter.

Почему мы использовали Rust, а не C или C++? Не только потому, что мы очень любим его. Rust позволяет писать безопасно с точки зрения доступа к памяти, арифметических операций и т. д. Можно проверить многие ошибки еще на этапе компиляции. Если программа на Rust скомпилировалась, то она точно запустится, а затем с очень большой вероятностью будет нормально работать и на RISC-V, и на x64. К тому же Rust имеет удобную и развитую экосистему.

Портирование прототипа под RISC-V заняло менее часа. Из 128 МБ разделяемой памяти мы заняли 112 МБ, из них:

• 4 Б для команд сигнатурного анализатора,

• 8 Б для записи времени,

• 256 Б для инициализирующей области, откуда мы берем шум, чтобы инициализировать другой сигнатурный анализатор,

• около 7 МБ для области шумящих данных второго сигнатурного анализатора,

• около 102 МБ для датасетов с результатами работы генератора.

Во время генерации случайных чисел создается буфер размером 128 Б, где каждый такт запускаются health-тесты NIST — Adaptive Proportion и Repetition Count. Если они завершаются ошибкой, то мы ожидаем перезапуск.

Теперь о том, как все работает на верхнем уровне. На Cortex запущен дистрибутив Linux, к которому мы через ssh подключаем хост-машину. Затем с помощью python-скрипта через memory I/O мы обращаемся к распределяемой памяти. MicroBlaze считывает запрос и пишет ответ в регион памяти, который выделен для обмена.

В python-скрипте мы реализовали упомянутый выше корректор фон Неймана, энтропию по Шеннону, health-тесты NIST, которые являются обязательными согласно рекомендации 800-90B от NIST. Они проверяют, что в нашей последовательности нет непрерывных рядов нолей или единиц длиннее, чем некоторое значение C, и что нули и единицы не превалируют друг над другом больше, чем на некоторое значение C.

Также в скрипт входит модуль построения гистограммы, которая отражает частоту появления 8-битных слов, тепловая карта, метрики уникальности, тесты «распределения плоскости» и random walk. Качество данных оценивали несколько раз в зависимости от того, какая постобработка к ним применялась. Забегая вперед, скажем, что в нашем генераторе впоследствии были использованы корректор фон Неймана и health-тесты NIST. Все остальное применяли только на хостовой машине для анализа уже впоследствии.

Оцениваем случайность итоговых данных

С помощью Python и окружения PYNQ, запущенного на PS-части Zynq-7010, мы собрали 768к*8 бит данных. Прочитали итоговый файл как последовательности восьмибитных слов, посчитали относительную частоту появления каждого символа и построили гистограмму распределения случайных чисел:

В идеале все значения должны приближаться к единице, но на сырых данных это далеко не так: превалируют крайние значения, 0 и 255. Энтропия по Шеннону — 7,3914 бит (в идеале мы стремимся к восьми). Теперь добавим в схему корректор фон Неймана:

Разница очевидна: энтропия по Шеннону составила уже 7,9979 бит. Но еще явно есть к чему стремиться. Корректор фон Неймана просто рассматривает входящие последовательности битов. Если он видит две единицы или два ноля подряд, то пропускает значение. Если видит 0 и 1 — выдает 1, если 1 и 0 — выдает 0. 

Далее мы построили тепловую карту, где отражена частота встречаемости каждого бита. По оси y — номер бита, по оси x — номер слова. Здесь мы хотим увидеть отсутствие каких-либо явных паттернов:

Сгенерировали random walk’и на нескольких наборах данных:

Эффект «лесенки» вызван тем, что при включении платы в значениях были в основном ноли (FFFF). Но на наш генератор это не сильно повлияло — с учетом постобработки получилось в целом неплохо. В random walk 1D мы смотрим на один бит: если он равен 1, мы увеличиваем x, если 0 — то y. В 2D смотрим на два бита и, в зависимости от их порядка, уменьшаем или увеличиваем x или y.

Теперь проведем тест распределения на плоскости:

Мы сдвинули на один элемент массив данных восьмибитных слов. Значения, которые получились на пересечении, взяли как x и y. Здесь уже можно заметить некоторые паттерны — значит, DRAM не является достаточно качественным источником шума. Так что мы добавим постобработку.

Производительность генератора случайных чисел

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

1. Фиксируем время старта t1.

2. Генерируем N случайных бит.

3. Фиксируем время финиша t2.

4. Определяем производительность как (t2 – t1) / N.

Для доступа к системному времени мы обратились к специальным регистрам:

asm! {
  "csrr t0, 0xC01",
  "csrr t1, 0xC81",
  out( "t0" ) "t0",
  out( "t1" ) "t1",
  options(nostack)
}

Всего мы произвели около 20 замеров:

Оценка случайности после обработки OCA и MCA

Вернемся к оценке случайности и снова приведем результаты после корректора фон Неймана. Здесь мы получаем энтропию по Шеннону 7,9979 бит. Распределение на плоскости тоже не имеет заметных паттернов:

Далее мы измерили энтропию по Шеннону после обработки OCA и MCA. В первом случае получили 7.99999059 бит, во втором — 7.9999908969 бит. Разница невелика, однако МСА в наших условиях более сложен и менее производителен, поэтому мы остановились на ОСА. МСА, однако, находит место в аппаратной реализации. Вот тесты после OCA:

А это — random walk’и:

Мы видим, что на разных запусках генератора они расходятся — именно к этому мы и стремимся. Нет «лестниц» и никаких других явных паттернов. Запускали на 2048 бит — если взять больший размер, карта будет разрастаться слишком быстро и результат будет недостаточно нагляден.

При перестановке корректора фон Неймана и ОСА в модуле постобработки разница в энтропии совсем ничтожна: 7,999922838 бит, когда первым идет корректор, и 7,9999499403 — когда OCA. Учитывая энтропию в схеме с одним ОСА (7.99999059 бит), корректор в реализацию можно не включать.

К сожалению, из набора NIST-тестов наша итоговая реализация прошла только Linear Complexity. Есть над чем работать дальше.

Подведем итоги

С помощью физически неклонируемых функций в динамической памяти вполне можно сделать хороший генератор случайных чисел (TRNG). В ходе проекта мы создали его программную модель на основе одноканального и многоканального источников шума. Для программной реализации больше подойдет одноканальный источник шума, тогда как многоканальный найдет применение в реализации аппаратной.

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

Увы, мы не прошли достаточно NIST-тестов, чтобы наш генератор можно было использовать для криптографии, но он вполне подойдет, например, для геймдева. Наконец, мы вновь убедились, что язык Rust хорошо подходит для разработки под bare metal: итоговый код заработает куда с большей вероятностью, чем на C или C++.

Артём Шамына

куратор проекта, старший преподаватель кафедры ПОИТ БГУИР

Проект студентов БГУИР имеет практическую и научную значимость в области генерации случайных числовых последовательностей с использованием физически неклонируемых функций на основе DRAM-памяти. Эта тема напрямую соотносится с направлением физической криптографии, исследуемым в совместной лаборатории БГУИР-YADRO.

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

Особый интерес вызывает применение DRAM в качестве источника энтропии — это перспективное направление, поскольку такие PUF позволяют получать качественные случайные последовательности. Проект имеет практическую значимость для защиты данных в IoT-устройствах, встроенных системах (embedded) и защищенных вычислительных платформах, где требуется генерация случайных числовых последовательностей.

Участники Зимней Школы RISC-V в БГУИР работали с soft-процессорным ядром RISC-V, реализованным на отладочной FPGA-плате. Это позволило им не только изучить архитектуру RISC-V, но и получить практический опыт работы с мультипроцессорной асимметричной вычислительной системой, а также с экспериментальной реализацией RISC-V процессора, что особенно ценно для подготовки специалистов в области современных аппаратно-программных решений.

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