Поиск энтропии на микросхеме для повышения стойкости шифра

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

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

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

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

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

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

Инструменты

Старые инструменты

Из железа нам потребуется оценочная плата 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, то увидите значения как будто похожие, но все-таки другие. Спокойно, так и должно быть!

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

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

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

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

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

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

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

Аппаратно — это надежно?

Предлагаю начать со встроенного в микросхему F746NG TRNG-генератора и попытаться повторить результаты ST. К слову, некоторые аспекты проведенного ими тестирования лично у меня вызывают вопросы. Напомню, они анализировали десять подпоследовательностей примерно по 500 тысяч бит каждая (в сумме больше 5 миллионов бит).

Во-первых, авторы STS в своей работе прямо указывают (на с. 91), что для получения статистически значимых результатов (чтобы была возможность их дальнейшей интерпретации) нужно выделять и анализировать не менее 55 подпоследовательностей из общего пула энтропии. Во-вторых, можно ли получить достоверные значения при объеме в 5 миллионов бит?

Приведу простой пример: можно ли считать последовательность 01010 случайной? А последовательность 01010101010? Думаю, вы согласитесь, что во втором случае у нас гораздо больше оснований полагать, что мы имеем дело с некоторым паттерном, как раз из-за того, что мы увеличили объем выборки для наших статистических тестов.

Если вы все еще сомневаетесь, предлагаю рассмотреть другой пример — хорошо известные функции rand и srand. На самом деле это неплохие функции, если нужно, например, заменить игральный кубик в вашей любимой настолке. Наверное, излишне говорить о том, что они совершенно не подходят для сколько-нибудь серьезных применений, — вы и так об этом слышали. Впрочем, слышать — одно дело, а проверить самостоятельно на практике — совсем другое.

Для наглядности на компьютере с помощью этих функций был сформирован файл с 1 миллиардом случайных бит. Так как было выбрано ASCII-представление нулей и единиц, каждый бит потока занимал один байт в файле (итого ровно гигабайт). Сначала в STS были проанализированы первые 10 миллионов бит из этой последовательности.

Интересный нюанс: функция rand возвращает целое число со знаком, но в стандарте языка нигде не оговорен диапазон принимаемых значений (упоминается, что должно быть не меньше 16 бит). Мой компилятор (GCC) выдает результат в диапазоне [0, 2147483647], то есть только положительную половину из всех возможных. А отрицательные числа? Их нет.

В результате старший 31-й бит, который и хранит в себе информацию о знаке числа, оказывается всегда равным нулю. Если пытаться генерировать энтропию таким способом, результат будет крайне детерминированным. Поэтому даже в примере выше я использовал на каждой итерации только младшие 25 бит числа.

Вернемся к результатам. Надеюсь, они вас хотя бы чуть-чуть удивили. Действительно, судя по отчету, наша последовательность успешно прошла через все тесты. Неужели все ругают замечательную функцию rand совершенно напрасно? Предлагаю не спешить с выводами и проверить целиком весь файл.

Обработка больших массивов входных данных — однозначно не самая сильная сторона STS. На i9-8950HK прогон полного комплекта тестов для последовательности в 1 миллиард бит занимает больше часа. Это связано с тем, что все вычисления в программе однопоточные. Так что, если будете повторять, запаситесь терпением.

Тест FFT (Fast Fourier Transform, или быстрое преобразование Фурье) ищет периодичности в распределении данных в нашем наборе (более детально можете ознакомиться на с. 68). Вполне естественно, что в такой примитивной реализации псевдослучайности период проявляет себя гораздо раньше полного цикла (напомню, что для 1 миллиарда битов потребовалось взять 40 миллионов последовательных значений — это примерно 2% от всего диапазона). Однако надо отдать должное функции rand: остальные тесты (на частоту, распределение и подпоследовательности) подвоха не заметили.

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

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

Подробнее об устройстве TRNG

Если верить документации ST, TRNG — это генератор кольцевого типа. В его основе лежит джиттер — фазовое дрожание сигнала. Так как длительность периода в цепочках инверторов не является идеальной (всегда чуть-чуть разная) и тесно связана с физическими характеристиками каждого элемента на конкретной микросхеме, последовательность на выходе вполне можно считать случайной.

Другая сторона АЦП

Если вы когда-нибудь пытались провести точные измерения аналоговой величины и конвертировать ее в цифровой формат, то не могли не заметить, что даже в идеальных условиях значение всегда дрейфует в районе какого-либо значения. Ничего удивительного, ведь сам АЦП не идеален, да и преобразование из непрерывной функции в дискретную без потерь невозможно (в общем случае). На эту тему у ST для разработчиков припасен специальный аппноут (PDF). Он помогает, во-первых, смириться с неизбежным, во-вторых, минимизировать хотя бы часть шумов, которые ухудшают качество преобразований.

В данном случае шумы играют нам только на руку. Чем их больше, тем менее предсказуемый результат получится на выходе и тем сложнее будет выделить постоянную составляющую. Но что выбрать в качестве входного сигнала (без него шумы в АЦП сами собой не появятся)? На плате доступно шесть аналоговых входов разъема Arduino, однако их использовать я не рекомендую. Выводы нужно экономить, да и есть вероятность, что кто-то подаст на него заранее известный сигнал и попытается испортить наш генератор.

К счастью, современные микроконтроллеры оснащены массой полезных мелочей — почти как хороший швейцарский армейский нож. На борту у микросхемы F746NG — аналоговые датчики температуры и напряжения с регулятора 1,2 В. Помимо шестнадцати внешних входов, у первого АЦП есть два дополнительных канала для соответствующих измерений. Всего же у нас целых три АЦП и контакты А0 — А5 используются совместно с третьим. Все это можно узнать из документации (PDF, с. 413) и исходников проекта STM32duino. Таким образом, мы будем использовать ADC1, не мешая работе остальной части программы.

О датчиках стоит рассказать подробнее. Даже инженеры ST указывают в даташите (PDF, с. 43 и 151), что точность измерений у них оставляет желать лучшего и что они предназначены скорее «для качественного, нежели количественного измерения характеристик». Конечно, есть возможность улучшить точность, используя параметры заводской калибровки (для каждой микросхемы они свои), но в целом картину это мало меняет. Прекрасно!

Возможно, вы задумались, зачем на микроконтроллере, который работает от 3,3 В, нужно напряжение 1,2 В. На самом деле это напряжение питания самого ядра (Cortex-M7), а также памяти (ОЗУ и ПЗУ). Это сделано в первую очередь, чтобы снизить энергопотребление и тепловыделение кристалла. С периферией ввода-вывода эта часть соединяется через преобразователи логических уровней (подобно тому как схемы с уровнем 3,3 В иногда соединяют со старыми — с 5 В).

Генерация случайных чисел (наивный подход)

Теперь остается только написать функции инициализации АЦП и чтения соответствующих значений. Это чуть сложнее, чем запустить TRNG: регистров тут больше, несколько режимов работы, и вроде бы совершенно непонятно, какие настройки указывать. Но после вдумчивого чтения мануала почти все вопросы должны исчезнуть. Единственный тонкий момент, который может вызвать затруднения, — это как именно задать нужный канал для измерений.

Дело в том, что блоки АЦП на таких продвинутых микроконтроллерах рассчитаны на пакетную обработку данных. Предполагается, что ЦПУ занят слишком важными вещами, чтобы отвлекаться и ждать значения из АЦП. Правильный сценарий по умолчанию заключается в том, чтобы по срабатыванию какого-либо прерывания (например, от таймера) запустить сразу цепочку преобразований на самых разных каналах из регистра SQRX. Параллельно задействуется прямой доступ (DMA), чтобы перебрасывать результат куда-то в память (где их потом заберет ЦПУ).

Но это менее наглядно и в случае со всего двумя каналами даже излишне. Поэтому мы попытаемся сохранить понятный интерфейс вызовов Arduino, используя при этом CMSIS для максимальной скорости.

Обратите внимание, что используется двенадцатибитная точность измерений, чтобы регистрировать даже небольшие шумы в сигнале. Кроме того, на каждое преобразование отводится 28 тактов, хотя минимальное значение для 12 бит составляет 15 тактов (можно найти в мануале). От этого напрямую зависит точность (чем медленнее — тем точнее) и количество преобразований за единицу времени. Изначально я предполагал, что лучше всего энтропию набирать при максимальной скорости, но опытным путем было выяснено, что это не так и 28 тактов — оптимальное значение.

Разумеется, полностью брать результат для наших нужд нельзя. Старшие разряды вряд ли будут существенно меняться, сколько бы мы ни пытались. Более-менее случайны как раз младшие биты нашего числа. Я беру наименее предсказуемый правый бит. Таким образом, алгоритм очень простой: поочередно читаем значения с датчиков температуры и напряжения и добавляем два бита в нашу выходную последовательность. Что же, что же получится в результате?

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

Генерация случайных чисел (вторая попытка)

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

Во-первых, наш метод может быть сколь угодно случайным, но это еще не означает, что распределение в нем равномерное. Классический пример — «неправильная» монетка, вероятность выпадения орла на которой больше 0,5 (скажем, 0,9). Очевидно, что в серии бросков орлов будет гораздо больше, чем решек, но при этом гарантированно угадать каждый следующий результат все еще невозможно.

Аналогично обстоит дело и с АЦП. В идеальной ситуации в выходной последовательности должно быть примерно поровну нулей и единиц. Чтобы этого добиться, можно использовать алгоритм фильтрации фон Неймана. Если коротко, то в каждой паре битов во входном потоке мы сравниваем оба значения между собой и используем только первый или второй бит в парах с переходом (вида 01 или 10). При этом пары не накладываются друг на друга, а следуют одна за другой.

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

Подробней обо всем этом (а также о многом другом) вы можете прочитать в RFC 4086. Несмотря на то что это довольно старый документ, в нем доступно изложены базовые концепции и он по-прежнему актуален. Как правило, выход с аппаратного генератора почти всегда рекомендуется фильтровать перед обработкой (в англоязычной литературе употребляется термин whitening — побелка). Существуют и другие алгоритмы, но, учитывая скромные ресурсы микроконтроллеров, в первую очередь желательно пробовать именно те, что я описал.

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

С учетом всех дополнений код принимает такой вид:

Наконец, после долгого ожидания, накопления и проверки энтропии результат тестов выглядит следующим образом.

Выводы

Конечно же, генерировать весь пул энтропии средствами АЦП вряд ли целесообразно (разве что у вас в запасе целая куча времени). А вот проинициализировать начальным значением программный генератор вполне разумно. Кроме того, если у вас есть сомнения относительно вашего текущего ГСЧ, подмешивание второго потока может придать дополнительной уверенности.

Если вас заинтересовала тема аппаратной генерации случайных чисел, рекомендую заглянуть в «Искусство схемотехники» (Хоровиц, Хилл). В девятой главе есть подробное описание некоторых любопытных схем. Там же можно прочитать про структуру и принцип действия АЦП. Правда, материал не самый простой и требует знания как аналоговой, так и цифровой электроники. Но оно того стоит!