Скрыть объявление
На нашем форуме недоступен просмотр изображений для неавторизованных пользователей. Если Вы уже зарегистрированы на нашем форуме, то можете войти. Если у Вас еще нет аккаунта, мы будем рады, если Вы к нам присоединитесь. Зарегистрироваться Вы можете здесь.

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

Тема в разделе "Идеи", создана пользователем Юрий Ботов, 8 янв 2019.

Метки:
  1. Юрий Ботов

    Юрий Ботов Moderator Команда форума

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

    Итак mytrng.h
    Код (C):
    1. #ifndef _mytrng_h_
    2. #define _mytrng_h_
    3.  
    4. class TRNG {
    5.   public:
    6.     inline TRNG(void) { buf = 0; }
    7.     inline ~TRNG(void){}
    8.     inline void Init( u16 p){ port = p; for (u8 i = 0; i < 12; i++) { buf = buf << 1 | Bit();} }
    9.     inline u8 Bit(void){ delay(1); buf = buf << 1 | (analogRead(port) & 1); return (buf&1)^(buf>>1&1)^(buf>>2&1)^(buf>>10&1); }
    10.     inline u8 Byte(void){ u8 r = 0; for (u8 i = 0; i < 8; i++) { r = r << 1 | Bit();} return r;}
    11.     inline u8 Byte(u8 max) { return Byte()*max/0xff; }
    12.     inline u16 Word(void){ u16 r = 0; for (u8 i = 0; i < 2; i++) { r = r << 8 | Byte();} return r;}
    13.     inline u16 Word(u16 max) { return Word()*max/0xffff; }
    14.     inline u32 Dword(void){ u32 r = 0; for (u8 i = 0; i < 2; i++) { r = r << 16 | Word();} return r;}
    15.     inline u32 Dword(u32 max) { return Dword()*max/0xffffffff; }
    16.   private:
    17.     u16 buf;
    18.     u16 port;
    19. };
    20.  
    21. #endif
    Код в Arduino esp8266 для тестирования:
    Код (C):
    1. //#include "d:/include/mytypes.h"
    2. #include "d:/include/mytrng.h"
    3.  
    4. TRNG Random;
    5.  
    6. void setup() {
    7.   Serial.begin(115200);
    8.   Random.Init(A0);
    9. }
    10.  
    11. void loop() {
    12.   Serial.println(Random.Byte());
    13. }
    Не забудьте исправить пути до инклюд-файлов на свои.
    Первый "инклюд" не нужен под esp, там и так это объявлено, только под stm.
    Если кому надо - вот он:
    Код (C):
    1. #ifndef _mytypes_h_
    2. #define _mytypes_h_
    3.  
    4. typedef unsigned char u8;
    5. typedef signed char i8;
    6. typedef unsigned short u16;
    7. typedef signed short i16;
    8. typedef unsigned long u32;
    9. typedef signed long i32;
    10.  
    11. #endif
    А это результат - таблица частот выпадения значений:
    Код (Text):
    1.     1705    1682    1725    1718    1691    1739    1799    1714    1657    1637    1739    1648    1756    1673    1637    1693
    2.  
    3.     1657    1637    1739    1648    1756    1673    1637    1693    1712    1720    1687    1697    1717    1660    1720    1729
    4.  
    5.     1712    1720    1687    1697    1717    1660    1720    1729    1634    1736    1727    1697    1744    1665    1728    1649
    6.  
    7.     1634    1736    1727    1697    1744    1665    1728    1649    1715    1696    1715    1737    1762    1690    1723    1704
    8.  
    9.     1715    1696    1715    1737    1762    1690    1723    1704    1694    1660    1749    1649    1744    1661    1694    1736
    10.  
    11.     1694    1660    1749    1649    1744    1661    1694    1736    1602    1768    1799    1644    1673    1661    1711    1712
    12.  
    13.     1602    1768    1799    1644    1673    1661    1711    1712    1717    1739    1677    1741    1687    1753    1730    1684
    14.  
    15.     1717    1739    1677    1741    1687    1753    1730    1684    1733    1727    1723    1726    1668    1723    1687    1662
    16.  
    17.     1733    1727    1723    1726    1668    1723    1687    1662    1745    1738    1765    1702    1666    1734    1679    1719
    18.  
    19.     1745    1738    1765    1702    1666    1734    1679    1719    1682    1713    1757    1723    1686    1691    1653    1749
    20.  
    21.     1682    1713    1757    1723    1686    1691    1653    1749    1693    1757    1717    1774    1620    1727    1718    1776
    22.  
    23.     1693    1757    1717    1774    1620    1727    1718    1776    1674    1701    1740    1704    1740    1724    1704    1700
    24.  
    25.     1674    1701    1740    1704    1740    1724    1704    1700    1629    1680    1688    1672    1805    1615    1713    1643
    26.  
    27.     1629    1680    1688    1672    1805    1615    1713    1643    1799    1687    1690    1674    1632    1698    1726    1688
    28.  
    29.     1799    1687    1690    1674    1632    1698    1726    1688    1710    1753    1722    1711    1728    1625    1760    1764
    30.  
    31.     1710    1753    1722    1711    1728    1625    1760    1764    1646    1728    1744    1707    1762    1697    1757    1713
    32.  
    33.  
    34. обработано байт: 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 на бит - там внутри есть миллисекундная задержка между запросами к АЦП - если ее убрать, равномерность резко ухудшается)

    Кому как а мне для моей задачи - хватило.
     
    Последнее редактирование: 8 янв 2019
    Сергей_Ф нравится это.
  2. enjoynering

    enjoynering Авторитетный участник сообщества

    Сообщения:
    444
    Симпатии:
    48
    а вы не боитесь что специально обученная наводка на контакты ацп превратит ваши шумы в тыкву?
     
  3. Юрий Ботов

    Юрий Ботов Moderator Команда форума

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

    view24 Читатель

    Сообщения:
    150
    Симпатии:
    5
    Гениально!
     
  5. Юрий Ботов

    Юрий Ботов Moderator Команда форума

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

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

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

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

    Юрий Ботов Moderator Команда форума

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

    Не могу не согласиться :)
    Просто руки не дошли еще до полноценного анализа последовательности, прежде чем вбрасывать это "в мир" - разумеется сделаю.
    Если кому то интересно, могу выслать файл часового "потока случайных чисел" (это около 500кБ в zip) в формате:
    Код (Text):
    1. 79
    2. 97
    3. 170
    4. 11
    5. 26
    6. 90
    7. 31
    8. 148
    9. 205
    10. 45
    11. 48
    12. 113
    13. 43
    14. 24
    15. 172
    16. 109
    17. 173
    18. 78
    19. 118
    20. 142
    21. 220
    22. 19
    23. 234
    24. 239
    25. 123
    26. 36
    27. 11
    28. 191
    29. 251
    То есть цифры в текстовом формате разделенные CR/LF
    (специально выбрал отрезок в котором есть неподалеку два одинаковых значения - 11, что бы было видно что не с предыдущими ни с последующими значениями они не связаны)
     
    Последнее редактирование: 14 янв 2019
  7. Юрий Ботов

    Юрий Ботов Moderator Команда форума

    Сообщения:
    1.023
    Симпатии:
    172
    Учитывая, что к данному форуму, да и к теме это имеет ооочень отдаленное отношение :) я на днях опишу это в личке.
     
  8. Сергей_Ф

    Сергей_Ф Moderator Команда форума

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

    Юрий Ботов Moderator Команда форума

    Сообщения:
    1.023
    Симпатии:
    172
    :) немного терпения, просто сейчас очень занят - напишу про свою задачу в личке.
    Лично этот "классический" уже генератор я "взломал" на своем компе за 8 часов - 3 часа на поиск "точки старта" и 5 часов на генерацию 40 Гб полной последовательности (основное время на обращение к диску). По моему, это слишком быстро.
     
  10. enjoynering

    enjoynering Авторитетный участник сообщества

    Сообщения:
    444
    Симпатии:
    48
    по это я автору намекал

     
  11. Юрий Ботов

    Юрий Ботов Moderator Команда форума

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

    Прообраз токена.. узнаете? DSC01015 (2).JPG
     
    Последнее редактирование: 15 янв 2019
  12. Юрий Ботов

    Юрий Ботов Moderator Команда форума

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

    view24 Читатель

    Сообщения:
    150
    Симпатии:
    5
     
  14. view24

    view24 Читатель

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

    view24 Читатель

    Сообщения:
    150
    Симпатии:
    5
    Оговорился не проблема, а свойство.
     
  16. view24

    view24 Читатель

    Сообщения:
    150
    Симпатии:
    5
    По поводу непредсказуемости: 10 умножить на 15 по модулю 100 равно 50. Программный ДСЧ это датчик псевдо-случайных чисел. И он должен всегда проверятся, ибо зацикливание может произойти на первых шагах. Если пользуемся методом Монте-Карло для исследования, то либо до моделирования ДСЧ проверяем, либо в процессе моделирования. Если датчик зациклится, эксперимент повторяем.
     
  17. Vladimir555

    Vladimir555 Читатель

    Сообщения:
    264
    Симпатии:
    5
    Привет!
    Применяю STM32F103 (для авторизации) c SHA256 USB HID клавиатура.
    Все держится на защите STM32F103.
    Все взломано, но за деньги. Microcontroller reverse engineer - Mikatech
    Где теперь хранить приватные ключи?
     
    Последнее редактирование: 28 янв 2019
  18. Юрий Ботов

    Юрий Ботов Moderator Команда форума

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

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

Поделиться этой страницей