Хорошо, когда под рукой есть аппаратный генератор случайных чисел или хотя бы /dev/urandom. Но что делать, если их нет, а чуть-чуть случайности привнести в прошивку своего умного устройства все-таки хочется? В такой ситуации стоит внимательней присмотреться к самым обычным вещам: например, шумам в аналогово-цифровом преобразователе.

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

INFO

Если ты читал «Криптономикон» Нила Стивенсона, то наверняка помнишь, как главный герой романа собирал энтропию для шифрования сообщений программой «Ордо», хаотично нажимая клавиши на клавиатуре ноутбука. Тот редкий случай, когда описание технических подробностей в художественной литературе соответствует реальности и не заставляет специалистов тяжело вздыхать.

Кроме того, я постараюсь рассказать, что еще можно использовать в качестве источника для генерации случайных чисел. Аппаратные ГСЧ в современных микроконтроллерах на архитектуре ARM — вещь не сказать чтобы редкая, но и не самая распространенная.

Узнать, присутствует ли TRNG в твоем МК, можно по этой таблице. Модельный ряд Н7 почему-то еще не добавили
Узнать, присутствует ли TRNG в твоем МК, можно по этой таблице. Модельный ряд Н7 почему-то еще не добавили

Увы, даже внутри одного семейства далеко не у всех микросхем одинаковая периферия. Например, микроконтроллер F746NG имеет модуль TRNG, но не CRYP или HASH (их получили более старшие товарищи, которые мощнее и, разумеется, дороже). Порой бывает, что «камень» подходит по всем параметрам и по периферии, за исключением одной-двух мелочей. В таком случае можно попробовать реализовать недостающую функциональность своими силами.

WARNING

Следует помнить, что, если речь идет об особо важных данных, экономить нельзя ни в коем случае! Нужно использовать только проверенные генераторы (желательно накапливать энтропию сразу с нескольких) и комплексно подходить к проблеме безопасности.

 

Инструменты

Старые знакомые…

Из железа нам потребуется оценочная плата F746G Discovery. Не буду повторяться и вновь останавливаться на ее характеристиках. Замечу только, что в этот раз из периферии мы будем использовать ГСЧ, АЦП и еще слот для microSD. С помощью замечательной библиотеки FatFs полученные данные будут записываться на карту памяти для дальнейшей обработки и анализа на компьютере.

Настроить плату для работы с карточками формата SD можно по примерам в документации STMicroelectronics (пункт STM32F7 Series Device Support & Drivers) либо в дополнительных библиотеках к проекту STM32duino.

Обрати внимание, что интерфейсом для общения с микроконтроллером тут служит четырехбитный SDIO, а не обычный SPI, и это гораздо быстрее (карточки SD поддерживают SPI в режиме обратной совместимости). Кроме того, ST во всех своих примерах использует старую версию библиотеки FatFs. Ты можешь взять драйверы от ST, а за актуальной версией обратиться на сайт автора, чтобы потом уже собрать все самостоятельно.

Прежней осталась и IDE — это Arduino с установленным пакетом STM32duino. Кстати, с момента выхода прошлой статьи у них появилась версия 1.5.0, не забудь обновиться!

...и новые лица

Появление комплекта статистических тестов в статье об энтропии сложно назвать неожиданным. Случайность слишком важна, чтобы взять первый попавшийся набор чисел (например, из ячеек RAM или значение системного таймера) и скормить программе. Если ты интересовался темой ГСЧ, то наверняка встречал в интернете несколько пакетов тестов — DIEHARD(ER), CRYPT-X, TestU01 и прочие. Примечательно, что сам Дональд Кнут уделил внимание этой проблеме, и во втором томе его монументального (и несколько занудного) труда по алгоритмам ты можешь найти перечень тестов и много другой полезной информации.

Впрочем, я решил остановить свой выбор на пакете от NIST (The National Institute of Standards and Technology) преимущественно по двум причинам. Во-первых, этот набор тестов хорошо и исчерпывающе документирован (PDF) за исключением одного важного момента, о котором я расскажу ниже. Во-вторых, его использовали в ST для оценки ГСЧ на собственных микроконтроллерах, поэтому мне было любопытно сравнить, насколько сойдутся наши результаты. Подробнее об их тестировании ты можешь прочитать в соответствующем аппноуте (PDF). Если тебе больше интересен практический аспект применения STS (Statistical Test Suite), то рекомендую начать именно с последнего документа.

Что касается установки и использования самого пакета, то тут все тривиально. Просто разархивируй папку, укажи свой компилятор в makefile и собери программу assess из исходников. В зависимости от настроек сообщений твоего компилятора ты можешь увидеть на экране несколько предупреждений — игнорируй их, на результат они не повлияют.

А вот здесь уже интересней, и это то, о чем я говорил ранее. Кажется, что логично проверить работу готовой программы на тех данных, результат которых заранее известен, правда? Специально для этой цели в приложении Б документации (с. 107) указаны расчетные значения для примеров из папки data. Там лежат тестовые файлы, предназначенные для тестирования нашего комплекта тестов (как звучит-то, м-м-м). Если ты сейчас запустишь программу assess и укажешь путь, например, к data → data.pi, то увидишь значения как будто похожие, но все-таки другие. Спокойно, так и должно быть!

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

Так что самое главное — это чтобы итоги первого теста у тебя выглядели как на скриншоте.

Вывод для числа π
Вывод для числа π

INFO

Возможно, тебе будет любопытно узнать, что некоторые свойства числа π не изучены до сих пор. Например, совершенно непонятно, почему цифры в представлении числа π встречаются примерно с одинаковой вероятностью. Впрочем, так как сама эта последовательность весьма популярна (OEIS:A000796) и известны триллионы ее знаков, использовать число π для практических применений в качестве ключа не стоит ни в каком виде.

Пару слов об интерпретации результатов из отчета (experiments → AlgorithmTesting → finalAnalysisReport.txt). В самом низу документа есть краткая справка, и при первичном изучении последовательностей случайных чисел ее бывает достаточно. Программа сама помечает звездочкой проваленные тесты (критерии можно задавать в файле настроек include → defs.h или использовать значения по умолчанию).

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

Чтобы понять, насколько успешно был пройден тот или иной тест, обращай внимание на критерий P-value. Его смысл формулируется довольно академично: «вероятность того, что идеальный ГСЧ сформировал бы последовательность менее случайную относительно заданной». Если коротко, то чем ближе число к единице, тем лучше. И наоборот, значения около 0.1 свидетельствуют о том, что мы были близки к провалу. Впрочем, даже результат в диапазоне [0.4, 0.6] можно считать хорошим (при условии, что данных для анализа было достаточно).

Думаю, на этом можно наконец завершить знакомство с инструментами и перейти к основной теме статьи — тестированию наших генераторов.

Продолжение доступно только участникам

Вариант 1. Присоединись к сообществу «Xakep.ru», чтобы читать все материалы на сайте

Членство в сообществе в течение указанного срока откроет тебе доступ ко ВСЕМ материалам «Хакера», позволит скачивать выпуски в PDF, отключит рекламу на сайте и увеличит личную накопительную скидку! Подробнее

Вариант 2. Открой один материал

Заинтересовала статья, но нет возможности стать членом клуба «Xakep.ru»? Тогда этот вариант для тебя! Обрати внимание: этот способ подходит только для статей, опубликованных более двух месяцев назад.


  • Подпишись на наc в Telegram!

    Только важные новости и лучшие статьи

    Подписаться

  • Подписаться
    Уведомить о
    4 комментариев
    Старые
    Новые Популярные
    Межтекстовые Отзывы
    Посмотреть все комментарии