Почему случайные числа (RN)?

В этом десятилетии наблюдается экспоненциальный рост устройств Интернета вещей и атак на них. Устройства Интернета вещей часто ставят под угрозу безопасность из-за нехватки места, времени и памяти. Одним из таких очевидных компромиссов является использование не «настоящих» генераторов случайных чисел (ГСЧ). Современные механизмы безопасной связи в значительной степени зависят от наличия истинных генераторов случайных чисел (TRNG). Например, вот как TLS полагается на ГСЧ для установления защищенной связи:

  1. Клиент отправляет на сервер информацию о том, какую версию TLS он хочет использовать, и другую информацию.
  2. Сервер отвечает аналогичной информацией о версиях TLS и его сертификате SSL.
  3. Клиент проверяет действительность сертификата. Если это так, он генерирует случайный «предварительный секрет», который будет использоваться для защиты соединения.

Дальнейшее общение в канале происходит на основе предварительного мастер-ключа. Чтобы соединение было безопасным, ключ должен быть непредсказуемым (на основе RN) (подробнее см. Здесь).

Действительно ли RN не могут быть созданы компьютерами, удивительно? Они могут быть вызваны только физическими процессами (например, атмосферным шумом, шумом часов, броском кубика, радиоактивным распадом и т. Д.). Это означает, что специальное оборудование для генерации случайных чисел неизбежно . Это неправда, эта заметка посвящена механизму генерации действительно случайных чисел из ячеек статической произвольной памяти (SRAM). Поскольку SRAM де-факто являются типом RAM в микроконтроллерах, этот метод является масштабируемым.

Подбросим монетку - случайность в SRAM

Простым ГСЧ будет событие по подбрасыванию монеты. Это событие является случайным, потому что предыдущие броски не влияют на текущий бросок (не причинно). Также вероятность получить голову и хвост равна. Каждый бросок монеты генерирует 1-битный RN. Если нам нужен 4-битный RN, мы можем подбросить 4 монеты одновременно. Каждая ячейка SRAM похожа на монету. Начальное значение бита в ячейке SRAM является случайным. Давайте углубимся и попробуем изложить 6-ти транзисторную ячейку SRAM.

После подачи питания (Vdd высокий) существует только два стабильных состояния, в которых может находиться ячейка: либо (Q = 0 & Q ’= 1), либо (Q = 1 & Q’ = 0). Состояние является функцией изменения процесса и случайного шума. Например, конструктивный случайный шум в точке «Q» во время запуска может подтолкнуть ячейку к состоянию (Q = 1 & Q ’= 0). Этот фактор является более случайным и может быть вызван шумом от источника питания, схемами синхронизации или переходными процессами переключения. Этот фактор вносит случайность в исходное состояние ячейки.

С другой стороны, емкость затвора (Cgs) каждого полевого МОП-транзистора нельзя точно контролировать в процессе изготовления (можно только гарантировать, что она находится в определенном диапазоне). Если Cgs M1 ниже, чем M3, M1 включится быстрее, чем M3, переводя ячейку в состояние (Q = 1 & Q ’= 0). Эффекты, обусловленные изменениями процесса, уменьшают случайность исходного состояния ячейки, поскольку состояние ячейки становится более предсказуемым, вы можете представить, что это эквивалентно смещенной монете, где голова более вероятна. Ясно, что начальное состояние ячейки представляет собой сочетание неслучайных и случайных процессов.

Извлечение случайности из SRAM

В идеале 1 ячейка должна быть равна 1-битной случайной величине. Но из-за факторов, уменьшающих случайность, количество ячеек SRAM, необходимых для генерации 1 бита случайности, больше. Ученые Массачусетского университета в Амхерсте (см. Здесь) эмпирически рассчитали, что для получения 1-битного RN необходимо 20 ячеек. Захват случайности из ячеек может быть выполнен путем передачи их через хеш-функцию, это также гарантирует, что o / p имеет фиксированную длину. Например, мы можем использовать 3200 бит SRAM в качестве входных данных для безопасного алгоритма хеширования (SHA1), чтобы получить 160-битное случайное число.

Пример приложения

Пример приложения был создан с использованием STM 32 Nucleo F030R8 (см. Здесь) для создания RN. При включении питания приложение выполняет следующие действия:

  1. Захватывает начальные биты SRAM.
  2. Хеширует биты SRAM для получения 160-битного случайного числа.
  3. Отправляет случайное число через последовательный порт на ПК (для реальных приложений этот шаг можно игнорировать).

В качестве среды разработки использовалась Atollic true studio, а пакет поддержки плат (BSP) был автоматически сгенерирован с использованием Cube MX. В качестве компилятора использовался arm-gcc. Компоновщик arm-gcc по умолчанию помещает неинициализированные переменные в секцию .bss, и секция инициализируется нулевым значением кодом запуска. Как следствие, мы теряем стартовые значения SRAM. К счастью, мы можем обойти это поведение, определив новый неинициализированный раздел в конце RAM и поместив переменную в этот раздел RAM. Вот как мы это делаем:

В командном файле компоновщика:

Https://gist.github.com/dheeptuck/df3aa84790f01ded33badbe7066129f8

Поместите переменную в неинициализированный раздел:

Https://gist.github.com/dheeptuck/21f9a8145e71115ed34ee393fbedea8c

Массив au8Arr содержит неинициализированные байты (или биты) SRAM. Затем этот массив передается в функцию SHA1 для генерации 160-битного RN. Библиотеку SHA1, используемую в этом приложении, можно найти здесь. au8Arr можно использовать для других целей после создания RN. 160-битный RN отправляется через последовательный порт для сценария python на ПК для его записи. Скрипт выгружает сгенерированные случайные числа в двоичный файл, чтобы его можно было использовать для оценки. Пример приложения находится в этом репозитории Github.

Насколько хороша наша ГПСЧ?

SP800–22 Revision 1a от Национального института стандартов и технологий (Министерство торговли США) является одним из широко распространенных тестов для RN. Тестовый комплект содержит тесты, которые статистически оценивают выходные данные, генерируемые ГСЧ. Подробности каждого теста выходят за рамки данной статьи и уже хорошо описаны здесь.

Для набора тестов SP800 необходимо, чтобы генератор случайных чисел сгенерировал как минимум ~ 1100000 случайных битов, чтобы оценить его силу. Поскольку разработанная нами SRAM TRNG может генерировать 160 случайных битов при одном включении питания, плата STM 32 Nucleo была присоединена к установке для цикла включения питания. Эта установка будет постоянно включать и выключать плату Nucleo (с частотой ~ 1 Гц), позволяя генерировать 160 случайных битов при каждом включении.

Данные, генерируемые платой Nucleo при каждом запуске, добавлялись в двоичный файл (с помощью скрипта Python, собирающего данные из последовательного порта). Я запустил тестовую установку, чтобы собрать 2431872 случайных бита (скачать). Данные были проанализированы с использованием этой Python-реализации тестов NIST SP800. Результаты многообещающие:

P-Value - это показатель того, насколько близок ГСЧ к идеальному ГСЧ. Если P-значение для теста определено равным 1, то последовательность кажется абсолютно случайной. Нулевое значение P указывает на то, что последовательность кажется полностью неслучайной. Категорически P-значения больше 0,01 отлично подходят для криптографических целей.

Предостережения в отношении случайного числа SRAM

  1. Скорость генерации случайных чисел SRAM TRNG составляет 1 последовательность / включение. Поскольку большинству криптографических приложений требуется генерирование нескольких случайных чисел с более высокой скоростью, это неудобно. Это ограничение можно преодолеть, используя генератор псевдослучайных чисел (PRNG) вместе с SRAM TRNG. RN из TRNG может использоваться для заполнения PRNG, последующие RN могут быть сгенерированы из PRNG. Подходящим ГПСЧ для этого приложения будет твистер Мерсенн.

2. Основным источником случайности в SRAM является тепловой шум. Противник может уменьшить случайность, снизив температуру. Это можно преодолеть, используя больше битов SRAM (чем ранее обсуждавшиеся 20 бит) для генерации 1 случайного бита.

Резюме

TRNG на основе SRAM потенциально могут быть бесплатной заменой TRNG для многих криптографических приложений. Усилия по добавлению SRAM TRNG в ваше приложение минимальны (~ 150 строк кода). Поскольку этот вид ГПСЧ мало изучается, необходимо осознавать потенциал скрытых угроз безопасности.

Я хотел бы услышать ваши мысли, поделиться своими комментариями, аплодировать, если вы найдете эту заметку полезной.

📝 Прочтите этот рассказ позже в Журнале.

👩‍💻 Просыпайтесь каждое воскресное утро и слушайте самые интересные истории недели в области технологий, которые ждут вас в вашем почтовом ящике. Прочтите информационный бюллетень« Примечательно в технологиях .