Получение действительно случайного числа в Arduino

Каков наилучший способ получить действительно (в отличие от псевдо) случайное число в Arduino или, по крайней мере, наилучшее из возможных приближений? Насколько я понимаю, функция randomSeed (analogRead (x)) недостаточно случайна.

Если возможно, метод должен использовать только базовую настройку Arduino (без дополнительных датчиков). Решения с внешними датчиками приветствуются, если они значительно улучшают случайность по сравнению с базовой настройкой.

Библиотека Entropy использует:

естественный джиттер сторожевого таймера для создания надежного потока истинных случайных чисел

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

В дополнение к библиотеке они также предоставляют эскиз, демонстрирующий использование того же метода, который использовался для генерации случайного начального числа для PRNG микроконтроллера без библиотеки: https://sites.google.com/site/astudyofentropy/project-definition / таймер-джиттер-энтропия-источники / энтропия-библиотека / Arduino-случайные семена

randomSeed(analogRead(x))будет производить только 255 последовательностей чисел, что делает тривиальным пробовать все комбинации и создает оракула, который может соединиться с вашим выходным потоком, прогнозируя все выходные 100%. Вы на правильном пути, однако, это просто игра чисел, и вам нужно гораздо больше из них. Например, взяв 100 аналоговых считываний с 4 АЦП, суммируя их все, и подайте это, randomSeedбыло бы намного лучше. Для максимальной безопасности вам нужен как непредсказуемый ввод, так и недетерминированное микширование.

Я не криптограф, но я потратил тысячи часов на исследование и создание аппаратных и программных генераторов случайных чисел, поэтому позвольте мне поделиться с тем, что я узнал:

Непредсказуемый ввод:

• analogRead () (на плавающих выводах)
• GetTemp ()

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

• micros () (с недетерминированным периодом выборки)
• джиттер часов (низкая пропускная способность, но может использоваться)
• readVCC () (если не на батарейках)

Внешний непредсказуемый ввод:

• датчики температуры, влажности и давления
• микрофоны
• Делители напряжения LDR
• транзисторный шум с обратным смещением
• компас / ускорение джиттер
• esp8266 сканирование точки доступа wifi (ssid, db и т. д.)
• Время esp8266 (фоновые задачи Wi-Fi делают запланированные выборки micros () неопределенными)
• esp8266 HWRNG - RANDOM_REG32чрезвычайно быстрый и непредсказуемый, с 1 остановкой

сбор Последнее, что вы хотите сделать, это выплеснуть энтропию, как она есть. Легче угадать бросок монеты, чем ведро монет. Подведение итогов это хорошо. unsigned long bank;потом bank+= thisSample;будет хорошо; это перевернется. bank[32]еще лучше, читайте дальше. Вы хотите собрать как минимум 8 выборок ввода для каждого блока вывода, в идеале гораздо больше.

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

Вот почему вы хотите сохранить некоторую энтропию в долгосрочной перспективе, используя EEPROM, SD и т. Д. Посмотрите на Fortuna PRNG , который использует 32 банка, каждый из которых обновляется наполовину так же часто, как и предыдущий. Это затрудняет атаку на все 32 банка в разумные сроки.

Обработка Как только вы соберете «энтропию», вы должны очистить ее и отделить от входных данных в трудном обратном порядке. SHA / 1/256 хорош для этого. Вы можете использовать SHA1 (или даже MD5 на самом деле) для скорости, поскольку у вас нет уязвимости открытого текста. Для сбора урожая никогда не используйте полный банк энтопий, и ВСЕГДА всегда добавляйте «соль» к выходу, отличающемуся каждый раз, чтобы предотвратить идентичные выходные данные без изменений в банке энтропии: output = sha1( String(micros()) + String(bank[0]) + [...] );функция sha скрывает входные данные и отбеливает выходные данные, защищая от слабых семян, низкий накопленный энт и другие общие проблемы.

Чтобы использовать входы таймера, вы должны сделать их недетерминированными. Это просто как delayMicroseconds(lastSample % 255); что приостанавливает непредсказуемое количество времени, делая "последовательные" часы считывания неоднородными по разнице. Делайте это регулярно, например if(analogRead(A1)>200){...}, при условии, что А1 зашумлен или подключен к динамическому входу. Трудно определить каждую ветвь вашего потока, что предотвратит криптоанализ на декомпилированном / разорванном выходе.

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

Наконец, проверьте свою работу. Запустите вывод через ENT.EXE (также доступен для nix / mac) и посмотрите, хорош ли он. Наиболее важным является распределение хи-квадрат, которое обычно должно составлять от 33% до 66%. Если вы получаете 1,43% или 99,999% или что-то в этом роде, более чем один тест подряд, то ваш случай - дерьмо. Вы также хотите, чтобы отчеты ENT об энтропии были как можно ближе к 8 битам на байт, наверняка> 7,9.

TLDR: Самый простой и надежный способ - использовать HWRNG для ESP8266. Это быстро, равномерно и непредсказуемо. Запустите что-то вроде этого на ESP8266 с ядром Ardunio и используйте serial для связи с AVR:

// ESP8266 Arduino core code:
void setup(){
 Serial.begin(9600); // or whatever
}

void loop() {
  // Serial.write((char)(RANDOM_REG32 % 256)); // "bin"
  Serial.print( String(RANDOM_REG32, HEX).substring(1)); // "hex"
}

** редактировать

Вот набросок HWRNG, который я написал некоторое время назад и работающий как не просто коллектор, а целый CSPRNG, выплевывающий из последовательного порта. Он создан для про-мини, но должен легко адаптироваться к другим платам. Вы можете использовать только плавающие аналоговые выводы, но лучше добавить к ним что-нибудь, предпочтительно разные вещи. Как микрофоны, LDR, термисторы (подрезанные до максимального разброса по комнатной температуре) и даже длинные провода. Это хорошо работает в ЛОР, если у вас даже умеренный шум.

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

// AVR (ardunio) HWRNG by dandavis. released to public domain by author.
#include <Hash.h> 

unsigned long read[8] = {0, 0, 0, 0, 0, 0, 0, 0};
const int pincount = 9; // adjust down for non pro-mini boards
int pins[9] = {A0, A1, A2, A3, A4, A5, A6, A7, A0}; // adjust for board, name analog inputs to be sampled
unsigned int ticks = 0;
String buff = ""; // holds one round of derivation tokens to be hashed.
String cache; // the last read hash



void harvest() { // String() slows down the processing, making micros() calls harder to recreate
  unsigned long tot = 0; // the total of all analog reads
  buff = String(random(2147483647)) + String(millis() % 999);
  int seed =  random(256) + (micros() % 32);
  int offset =  random(2147483647) % 256;

  for (int i = 0; i < 8; i++) {
    buff += String( seed + read[i] + i + (ticks % 65), HEX );
    buff += String(random(2147483647), HEX);
    tot += read[i];
  }//next i

  buff += String( (micros() + ticks + offset) % 99999, HEX);
  if (random(10) < 3) randomSeed(tot + random(2147483647) + micros()); 
  buff = sha1( String(random(2147483647)) + buff + (micros()%64) + cache); // used hash to uniform output and waste time
  Serial.print( buff ); // output the hash
  cache = buff;
  spin();
}//end harvest()


void spin() { // add entropy and mix
  ticks++;
  int sample = 128;
  for (int i = 0; i < 8; i++) { // update ~6/8 banks 8 times
    read[ read[i] % 8] += (micros() % 128);
    sample = analogRead(  pins[i] ); // a read from each analog pin
    read[ micros() % 8] += ( read[i] % 64 ); // mix timing and 6LSBs from read
    read[i] += sample; // mix whole raw sample
    read[(i + 1) % 8] += random(2147483647) % 1024; // mix prng
    read[ticks % 8] += sample % 16; // mix the best nibble of the read
    read[sample % 8] += read[ticks % 8] % 2147483647; // intra-mix banks
  }

}//end spin()



void setup() {
  Serial.begin(9600);
  delay(222);
  int mx = 2028 + ((analogRead(A0)  + analogRead(A1) + analogRead(A2)  + analogRead(A3)) % 256);  
  while (ticks < mx) {
    spin();
    delay(1);
    randomSeed(read[2] + read[1] + read[0] + micros() + random(4096) + ticks);
  }// wend
}// end setup()



void loop() {
  spin();
  delayMicroseconds((read[ micros() % 8] %  2048) + 333  );
  delay(random(10));
  //if (millis() < 500) return;
  if ((ticks % 16) == (millis() % 16) ) harvest();
}// end loop()

Из моего опыта analogRead()на плавающей булавке очень низкая энтропия. Возможно один или два бита случайности за вызов. Вы определенно хотите чего-то лучшего. Джиттер сторожевого таймера, как предлагается в ответе per1234, является хорошей альтернативой. Тем не менее, он генерирует энтропию с довольно медленной скоростью, что может быть проблемой, если вам это нужно прямо при запуске программы. У dandavis есть несколько хороших предложений, но они обычно требуют либо ESP8266, либо внешнего оборудования.

Существует один интересный источник энтропии, который еще не был упомянут: содержимое неинициализированной оперативной памяти. Когда MCU включен, некоторые из его битов ОЗУ (те, которые имеют наибольшее количество симметричных транзисторов) запускаются в случайном состоянии. Как обсуждалось в этой статье , это можно использовать как источник энтропии. Он доступен только при холодной загрузке, поэтому вы можете использовать его для заполнения начального энтропийного пула, который вы затем периодически будете пополнять из другого, потенциально медленного источника. Таким образом, ваша программа может начать свою работу, не дожидаясь медленного заполнения пула.

Вот пример того, как это можно собрать на Arduino на базе AVR. Фрагмент кода ниже XOR заполняет всю оперативную память, чтобы создать начальное число, к которому она позже будет добавлена srandom(). Сложность в том, что сбор должен быть выполнен до того, как среда выполнения C инициализирует разделы памяти .data и .bss, а затем начальное число должно быть сохранено в месте, которое среда выполнения C не будет перезаписывать. Это делается с помощью определенных разделов памяти .

uint32_t __attribute__((section(".noinit"))) random_seed;

void __attribute__((naked, section(".init3"))) seed_from_ram()
{
    const uint32_t * const ramstart = (uint32_t *) RAMSTART;
    const uint32_t * const ramend   = (uint32_t *) RAMEND;
    uint32_t seed = 0;
    for (const uint32_t *p = ramstart; p <= ramend; p++)
        seed ^= *p;
    random_seed = seed;
}

void setup()
{
    srandom(random_seed);
}

Обратите внимание, что при « горячем» сбросе SRAM сохраняется, поэтому он по-прежнему содержит все содержимое вашего энтропийного пула. Этот же код можно затем использовать для сохранения собранной энтропии при сбросе.

Редактировать : исправил проблему в моей первоначальной версии, seed_from_ram()которая работала на глобальном, random_seedа не на локальном seed. Это может привести к тому, что семя будет подвергнуто XOR-обработке с самим собой, разрушая всю энтропию, собранную до сих пор.

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

#include <EEPROM.h>

const int seed_addr = 0;
unsigned long seed;

void setup() {
    seed = EEPROM.read(seed_addr);
    EEPROM.write(seed_addr, seed+1);
    randomSeed(seed);
}

Если вам нужна настоящая энтропия, вы можете получить ее либо по смещению тактовой частоты, либо за счет усиления внешнего шума. И если вам нужно много энтропии, внешний шум является единственным приемлемым вариантом. Стабилитрон является популярным выбором, особенно если у вас источник напряжения выше 5-6 В (он будет работать и при 5 В с соответствующим стабилитроном, но будет производить меньше энтропии):

( источник ).

Выход усилителя должен быть подключен к аналоговому выводу, который будет генерировать несколько битов энтропии с каждым analogRead()до десятков МГц (быстрее, чем Arduino может сэмплировать).