Делюсь опытом Генератор случайной последовательности

Юрий Ботов

Moderator
Команда форума
Недавно для железки на stm32 мне понадобился генератор случайной последовательности байтов.
L4x2 (и более дорогие) - имеют внутренний TRNG (True Random Numbers Generanor) - но дороговаты, а младшие модели (412-432) реально недоступны лично мне на рынке, есть только в виде Nucleo... Пришлось экспериментировать:
- шум транзисторов и стабилитронов - легко создать, хорошо воспроизводится, но требуется 9+ вольт питания, да и уровень маловат (десятки микровольт) - нужно городить усилители, а прикосновение рукой к донглу полностью подменяет шум меандром 50Гц...
- шум стабилизаторов (а ля lm317) - гораздо интереснее (единицы милливольт), но под осциллографом раскрылось, что на самом деле это периодическая пила случайной амплитуды. Для тестирования радио-устройств - нормально, а вот для генератора действительно случайных чисел - сомнительно.
- в конце концов решил использовать реально дешевый f103c8t6 - и попытаться что то вытянуть из шума АЦП... Вернее из его самого младшего разряда. Поток с младшего бита имеет примерно такой вид: "000000000101110000000000100010000000011001000", то есть, что-то похожее на случайные числа перемежающиеся блоками нулей случайной длины. Пробовал проредить нули - бяка. Решил поиграться с XOR - и даже первый результат (a[0]^a[10]) превзошел ожидания. Далее долгие эксперименты по разному сочетанию битов. Результат прилагаю. (Результат уже на esp8266, оно превосходно работает и на ней).

Итак mytrng.h
Код:
#ifndef _mytrng_h_
#define _mytrng_h_

class TRNG {
  public:
    inline TRNG(void) { buf = 0; }
    inline ~TRNG(void){}
    inline void Init( u16 p){ port = p; for (u8 i = 0; i < 12; i++) { buf = buf << 1 | Bit();} }
    inline u8 Bit(void){ delay(1); buf = buf << 1 | (analogRead(port) & 1); return (buf&1)^(buf>>1&1)^(buf>>2&1)^(buf>>10&1); }
    inline u8 Byte(void){ u8 r = 0; for (u8 i = 0; i < 8; i++) { r = r << 1 | Bit();} return r;}
    inline u8 Byte(u8 max) { return Byte()*max/0xff; }
    inline u16 Word(void){ u16 r = 0; for (u8 i = 0; i < 2; i++) { r = r << 8 | Byte();} return r;}
    inline u16 Word(u16 max) { return Word()*max/0xffff; }
    inline u32 Dword(void){ u32 r = 0; for (u8 i = 0; i < 2; i++) { r = r << 16 | Word();} return r;}
    inline u32 Dword(u32 max) { return Dword()*max/0xffffffff; }
  private:
    u16 buf;
    u16 port;
};

#endif
Код в Arduino esp8266 для тестирования:
Код:
//#include "d:/include/mytypes.h"
#include "d:/include/mytrng.h"

TRNG Random;

void setup() {
  Serial.begin(115200);
  Random.Init(A0);
}

void loop() {
  Serial.println(Random.Byte());
}
Не забудьте исправить пути до инклюд-файлов на свои.
Первый "инклюд" не нужен под esp, там и так это объявлено, только под stm.
Если кому надо - вот он:
Код:
#ifndef _mytypes_h_
#define _mytypes_h_

typedef unsigned char u8;
typedef signed char i8;
typedef unsigned short u16;
typedef signed short i16;
typedef unsigned long u32;
typedef signed long i32;

#endif
А это результат - таблица частот выпадения значений:
Код:
    1705    1682    1725    1718    1691    1739    1799    1714    1657    1637    1739    1648    1756    1673    1637    1693

    1657    1637    1739    1648    1756    1673    1637    1693    1712    1720    1687    1697    1717    1660    1720    1729

    1712    1720    1687    1697    1717    1660    1720    1729    1634    1736    1727    1697    1744    1665    1728    1649

    1634    1736    1727    1697    1744    1665    1728    1649    1715    1696    1715    1737    1762    1690    1723    1704

    1715    1696    1715    1737    1762    1690    1723    1704    1694    1660    1749    1649    1744    1661    1694    1736

    1694    1660    1749    1649    1744    1661    1694    1736    1602    1768    1799    1644    1673    1661    1711    1712

    1602    1768    1799    1644    1673    1661    1711    1712    1717    1739    1677    1741    1687    1753    1730    1684

    1717    1739    1677    1741    1687    1753    1730    1684    1733    1727    1723    1726    1668    1723    1687    1662

    1733    1727    1723    1726    1668    1723    1687    1662    1745    1738    1765    1702    1666    1734    1679    1719

    1745    1738    1765    1702    1666    1734    1679    1719    1682    1713    1757    1723    1686    1691    1653    1749

    1682    1713    1757    1723    1686    1691    1653    1749    1693    1757    1717    1774    1620    1727    1718    1776

    1693    1757    1717    1774    1620    1727    1718    1776    1674    1701    1740    1704    1740    1724    1704    1700

    1674    1701    1740    1704    1740    1724    1704    1700    1629    1680    1688    1672    1805    1615    1713    1643

    1629    1680    1688    1672    1805    1615    1713    1643    1799    1687    1690    1674    1632    1698    1726    1688

    1799    1687    1690    1674    1632    1698    1726    1688    1710    1753    1722    1711    1728    1625    1760    1764

    1710    1753    1722    1711    1728    1625    1760    1764    1646    1728    1744    1707    1762    1697    1757    1713


обработано байт: 436698, min: 1602, max: 1805, avg: 1705, разброс: 11 %
разброс = 100* (max-min)/avg
Учтите, что разброс уменьшается при увеличении размера выборки, так у меня на выборке около 70000 он был 33%, а тут на выборке примерно 400000 уже 11%, что радует глаз в гораздо большей степени :)

Верхнее левое число таблицы - количество 0-байтов, потом 1... справа верх 15 ну и право низ соответственно 255.
Баланс 0 и 1 терпимый - разница менее 1%.

ВАЖНО:
- увы нельзя использовать один и тот же вывод и для генерации случайных чисел и как просто АЦП
- вывод АЦП должен "висеть в воздухе"! То есть на NodeMCU вы получите вместо случайных чисел пачку нулей (проверил :) ). Впрочем никто не запрещает аккуратно перерезать дорожку.
- это не быстрый генератор (около 1ms на бит - там внутри есть миллисекундная задержка между запросами к АЦП - если ее убрать, равномерность резко ухудшается)

Кому как а мне для моей задачи - хватило.
 
Последнее редактирование:

enjoynering

Active member
а вы не боитесь что специально обученная наводка на контакты ацп превратит ваши шумы в тыкву?
 

Юрий Ботов

Moderator
Команда форума
enjoynering, да, работу в микроволновке, открытом космосе и последствий ядерных взрывов я не предусмотрел :) Просто встроенный в более дорогие чипы TRNG падет под специально обученной наводкой с тем же успехом. Я не предлагаю данное решение как коммерческий продукт или для управления технологическими процессами. А для DIY - вполне. К слову для превращения моих шумов в тыкву достаточно обычного молотка. Обучать наводку - это перебор.
 

Юрий Ботов

Moderator
Команда форума
чем не устраивает программная реализация
Прошу вспомнить, что изначально это было устройство на stm32 - токен с единственным интерфейсом наружу: USB HID keyboard. Устройство по определению работает только "на вывод" и никакой информации от компьютера получать не имеет права.
Так вот. На программной проверке идеи я разумеется использовал программный генератор и мне его недостатки были даже удобны :)
По большому счету, есть два основных вида программной реализации (известные мне): "сдвиговый регистр с обратной связью" и криптографический (на основе эллиптических кривых).
У первого есть два недостатка: неизменное начало последовательности - с этим можно было бы как то бороться если получить случайное число для начала каким-то другим, не программным, способом и ... полная предсказуемость последовательности выдаваемых значений (это вообще "машина состояний") - это не лечится никак. Основной плюс - высокая "равномерность" и удобство при отладке :) - знаешь что получишь.
Второй тоже грешит неизменностью начального значения - лечится аналогично. Последовательность предсказать труднее. Но самая большая беда второго алгоритма - он очень прожорлив по отношению к памяти, и чем он качественнее, тем прожорливей. В общем, у меня, в 20кБ ОЗУ он просто не влез, и при тестировании использовался первый вариант с длиной регистра 32 бита.

Итак ответ на собственно вопрос: не устроила полная предсказуемость генерируемой последовательности (с неизменным началом я вполне мог справиться)

какие характеристики данного генератора ( спектральная плотность или корреляционная функция ) иначе какой это шум - белый, розовый Иначе это "кот в мешке"
Там вверху есть "таблица частот выпадения значений" - это и есть распределение. Распределение практически равномерное в диапазоне 0-255 с разбросом в среднем 7% и максимальным выбросом 11%. Это на полмиллиона "испытаний" - около часа работы генератора. Зависимость от количества испытаний прослеживается правильная: чем больше испытаний тем меньше разброс (то есть в пределе сходится к равномерному закону распределения).
Терминами "белый и розовый" шум - не пользуюсь тут принципиально ввиду принципиальной ограниченности возможных значений результата, а белый шум подразумевает дельта функцию и бесконечный спектр...

чем лучше первого варианта?
Да ничем не лучше. Просто они для разных задач. Просто в варианте с использованием АЦП заранее не известны не первое, не каждое следующее значение. Недостатки тоже есть - нельзя гарантировать равномерность соотношения 0 и 1 на коротких последовательностях - для классической криптографии это придется корректировать.
 

Юрий Ботов

Moderator
Команда форума
Есть существенно лучшие алгоритмы генерации случайных кодов
Немного порассуждаю:
- я априори полагаю что код известен "злоумышленику". "защита кода" stm32 10x серии давно взломана и расчитывать на нее нельзя, у esp она отсутствует как класс. Потому свой код в случае успешного окончанию работы я скорее всего опубликую - нет смысла его прятать.
- то что не достижимо сегодня на компе, легко достижимо способом "аренды вычислительной мощности" крипто-фермы. Мода на криптовалюты пошла на спад и владельцы ферм с удовольствием продают "время" за "живые" деньги - причем сравнительно небольшие.
Учитывая сказанное, алгоритм ЛЭкюера болен теми же болезнями, что и предыдущие: как только будут известны начальные условия двух последовательностей (а алгоритм известен по определению) - вся последовательность становится на 100% предсказуемой... Да, сломать его дороже, но тому кто готов платить - взлом вполне доступен, причем в обозримое время.

2) закон распределения значений и спектральная плотность - это две большие разницы
У Вас приведены данные по оценке первого .
Но это распределение ничего не знает и нам не говорит о независимости (коррелированности) значений во времени т е предсказуемости процесса - а это и есть мера случайности.
Не могу не согласиться :)
Просто руки не дошли еще до полноценного анализа последовательности, прежде чем вбрасывать это "в мир" - разумеется сделаю.
Если кому то интересно, могу выслать файл часового "потока случайных чисел" (это около 500кБ в zip) в формате:
Код:
79
97
170
11
26
90
31
148
205
45
48
113
43
24
172
109
173
78
118
142
220
19
234
239
123
36
11
191
251
То есть цифры в текстовом формате разделенные CR/LF
(специально выбрал отрезок в котором есть неподалеку два одинаковых значения - 11, что бы было видно что не с предыдущими ни с последующими значениями они не связаны)
 
Последнее редактирование:

Юрий Ботов

Moderator
Команда форума
Но главное - что Вы хотите так тщательно шифровать? И зачем нужен генератор псевдослучайной последовательности ?
Учитывая, что к данному форуму, да и к теме это имеет ооочень отдаленное отношение :) я на днях опишу это в личке.
 

Сергей_Ф

Moderator
Команда форума
Юрий Ботов, а в условиях помех не проверяли? Мне кажется, даже обычный коллекторный двигатель на 4В рядом с этим esp способен в этот генератор внести устойчивую последовательность.
Тем не менее, это отличный способ получить первое случайное число.
 

Юрий Ботов

Moderator
Команда форума
:) немного терпения, просто сейчас очень занят - напишу про свою задачу в личке.
Вам не понравилось что простейший генератор кода на 32 битах имеет период 100 000 000 и 2^31 вариантов
Лично этот "классический" уже генератор я "взломал" на своем компе за 8 часов - 3 часа на поиск "точки старта" и 5 часов на генерацию 40 Гб полной последовательности (основное время на обращение к диску). По моему, это слишком быстро.
 

enjoynering

Active member
@Юрий Ботов, а в условиях помех не проверяли? Мне кажется, даже обычный коллекторный двигатель на 4В рядом с этим esp способен в этот генератор внести устойчивую последовательность.
Тем не менее, это отличный способ получить первое случайное число.
по это я автору намекал

а вы не боитесь что специально обученная наводка на контакты ацп превратит ваши шумы в тыкву?
 

Юрий Ботов

Moderator
Команда форума
enjoynering, Не спорю :) ! Повторю, изначально это токен на stm32, никаких моторов, помехи - только наводка от руки владельца (я их отсеиваю на другом этапе авторизации - все вам рассказывать? Не маленькие же :) ). А иные виды использования - на усмотрение Homo Sapiens.

Прообраз токена.. узнаете?DSC01015 (2).JPG
 
Последнее редактирование:

Юрий Ботов

Moderator
Команда форума
Уффф... я же просил потерпеть чуть чуть.... я делаю "АВТОРИЗАЦИЮ без крипто-алгритмов".
 

view24

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

view24

Member
Понимаю Вашу иронию. Я дсч занимался с 70х годов. Вы уже жили тогда? Проблема программных датчиков в зацикливании. Но поскольку состоят они они из операций умножения и сдвига, то выход - это просто увеличение разрядности. Ферма!
Оговорился не проблема, а свойство.
 

view24

Member
По поводу непредсказуемости: 10 умножить на 15 по модулю 100 равно 50. Программный ДСЧ это датчик псевдо-случайных чисел. И он должен всегда проверятся, ибо зацикливание может произойти на первых шагах. Если пользуемся методом Монте-Карло для исследования, то либо до моделирования ДСЧ проверяем, либо в процессе моделирования. Если датчик зациклится, эксперимент повторяем.
 
"защита кода" stm32 10x серии давно взломана и расчитывать на нее нельзя
Привет!
Применяю STM32F103 (для авторизации) c SHA256 USB HID клавиатура.
Все держится на защите STM32F103.
Все взломано, но за деньги. Microcontroller reverse engineer - Mikatech
Где теперь хранить приватные ключи?
 
Последнее редактирование:

Юрий Ботов

Moderator
Команда форума
не зная конкретной задачи трудно советовать...
1. берите новые stm32 - l7xx, l4xx, l0xx - их пока не взломали... да, они дороже, но в некоторых даже есть встроенный TRNG
2. переходите на идентификацию с обратной связью (для броузера не подходит)
3. если браузер Chrome реализуйте u2f
4. используйте вспомогательные проверки, например "почерк" токена - искусственно добавленные задержки между передаваемыми "нажатиями на клавиши"
5. сделайте токен читающий отпечатки пальцев или транспондер NFC

И да, должно соблюдаться: "стоимость скрываемых данных+стоимость защиты < стоимость взлома". Иногда для какой-то фигни городят несравнимо крутую защиту, которая больше защищает себя чем фигню.
 

wilex

New member
Спешу поделиться благой вестью. После месяца мучений с analogRead() случайно узнал, что в esp8266 есть встроенный, но официально недокументированный аппаратный генератор случайных чисел, аж 32 битный.
Находится он по адресу 0x3FF20E44, при обращении к этому регистру каждый раз считываются случайное 32 битное число. Лично я его еще не тестировал, но в англоязычных интернетах пишут, что он успешно проходит стандартные статистические тесты. Поскольку он не документирован, о нем мало информации и ничего не известно о том, как он устроен - существует вероятность, что к числам могут подмешиваться псевдослучайные последовательности или применяться какие-нибудь алгоритмические фильтры для выравнивания (но, лично я в этом сомневаюсь, уж больно шустро он работает для генератора, в котором что-то фильтруется программно).

Источники:
Any details of the esp8266 hardware random number generator?
Twitter

Ссылка на первоисточник, куда все ссылаются давно недоступна, но страница сохранилась в web-архиве: Random Number Generator - ESP8266-RE Wiki

Пользоваться им можно примерно так:

Код:
#define TRND_UINT8_T  ( *(volatile uint8_t *) 0x3FF20E44 )
#define TRND_UINT16_T ( *(volatile uint16_t *) 0x3FF20E44 )
#define TRND_UINT32_T ( *(volatile uint32_t *) 0x3FF20E44 )
#define TRND_CHAR ( *(volatile char *) 0x3FF20E44 )
#define TRND_BIT0 ( ~ ( *(volatile uint8_t *) 0x3FF20E44 ) & (1 << 0) )

<.........>

for(uint8_t i = 0; i<100; ++i)
        Serial.println(TRND_UINT8_T);
P.S. К сожалению, для моих целей ни похоже этот генератор, ни analogRead() не подходят... Мне нужен какой-нибудь природный источник шума. Задача не связанна с криптографией, поэтому допускается неравномерность распределения и периодические компоненты в разумных пределах = я все это могу учесть при статобработке. Но критически важно, чтобы при воспроизведении устройства на другом оборудовании другими людьми или, например, при включении пылесоса / микроволновки соседями за стеной - статистические характеристики распределения не менялись. И важно, чтобы шум был природный такой, какой есть, без применения каких-либо программных фильтров. Пробовал играться с шумом звуковой карты, шумом транзисторов, шумом радиоприемника между станциями, датчиками света/температуры, и даже с солнечной батареей, но пока результат меня не устраивает, либо по скорости, либо по качеству. Может быть кто посоветует в каком направлении копать?
 
Сверху Снизу