Uzyskanie naprawdę losowej liczby w Arduino

Jaka jest najlepsza metoda na uzyskanie prawdziwie (w przeciwieństwie do pseudo) losowej liczby w Arduino, lub przynajmniej najlepsze możliwe przybliżenie? Z mojego zrozumienia, funkcja randomSeed (analogRead (x)) nie jest wystarczająco losowa.

Jeśli to możliwe, metoda powinna wykorzystywać samą podstawową konfigurację Arduino (bez dodatkowych czujników). Rozwiązania z czujnikami zewnętrznymi są mile widziane, jeśli znacznie poprawią losowość w stosunku do podstawowej konfiguracji.

W Entropy bibliotecznych zastosowania:

naturalny jitter licznika czasu watchdoga, aby uzyskać niezawodny strumień prawdziwych liczb losowych

Podoba mi się to rozwiązanie, ponieważ nie zużywa żadnych styków twojego mikrokontrolera i nie wymaga żadnych zewnętrznych obwodów. Dzięki temu jest mniej podatny na awarie zewnętrzne.

Oprócz biblioteki udostępniają również szkic ilustrujący użycie tej samej techniki, która została użyta do wygenerowania losowego materiału siewnego dla PRNG mikrokontrolera bez biblioteki: https://sites.google.com/site/astudyofentropy/project-definition / timer-jitter-entropy-sources / entropy-library / arduino-random-seed

randomSeed(analogRead(x))wygeneruje tylko 255 ciągów liczb, co sprawia, że ​​wypróbowanie wszystkich kombinacji jest proste, a wyrocznia może łączyć się ze strumieniem wyjściowym, przewidując 100% wyniku. Jesteś na dobrej drodze, ale to tylko gra liczbowa i potrzebujesz dużo więcej. Na przykład pobranie 100 odczytów analogowych z 4 ADC, zsumowanie ich wszystkich i karmienie tego randomSeedbyłoby znacznie lepsze. Aby uzyskać maksymalne bezpieczeństwo, potrzebujesz zarówno nieprzewidywalnych danych wejściowych, jak i niedeterministycznego miksowania.

Nie jestem kryptografem, ale spędziłem tysiące godzin na badaniu i budowaniu losowych generatorów sprzętu i oprogramowania, więc pozwólcie, że podzielę się częścią mojej wiedzy:

Nieprzewidywalne dane wejściowe:

• analogRead () (na ruchomych pinach)
• GetTemp ()

Potencjalnie nieprzewidywalne dane wejściowe:

• micros () (z niedeterministycznym okresem próbkowania)
• jitter zegara (niska przepustowość, ale użyteczny)
• readVCC () (jeśli nie jest zasilany bateryjnie)

Zewnętrzne nieprzewidywalne dane wejściowe:

• czujniki temperatury, wilgotności i ciśnienia
• mikrofony
• Dzielniki napięcia LDR
• szum tranzystorowy z odwrotnym napięciem
• kompas / jitter przyspieszenia
• esp8266 skanowanie hotspotu Wi-Fi (ssid, db itp.)
• Czas esp8266 (zadania Wi-Fi w tle powodują, że zaplanowane pobieranie micros () jest nieokreślone)
• esp8266 HWRNG - RANDOM_REG32wyjątkowo szybki i nieprzewidywalny, 1 przystanek

zbieranie Ostatnią rzeczą, którą chcesz zrobić, jest wyplucie entropii, jak tylko się pojawi. Łatwiej zgadnąć rzut monetą niż wiadro monet. Podsumowanie jest dobre. unsigned long bank;potem bank+= thisSample;jest dobrze; przewróci się. bank[32]jest jeszcze lepszy, czytaj dalej. Chcesz zebrać co najmniej 8 próbek danych wejściowych dla każdego kawałka danych wyjściowych, najlepiej znacznie więcej.

Ochrona przed zatruciem Jeśli ogrzewanie planszy powoduje pewne maksymalne drgania zegara, jest to wektor ataku. To samo z odpalaniem RFI w kierunku wejść analogRead (). Kolejnym częstym atakiem jest po prostu odłączenie jednostki od zasilania, a więc zrzucenie całej nagromadzonej entropii. Nie powinieneś wypisywać liczb, dopóki nie będziesz wiedział, że jest to bezpieczne, nawet kosztem szybkości.

Dlatego chcesz zachować trochę entropii przez długi czas, używając EEPROM, SD itp. Spójrz na Fortuna PRNG , który wykorzystuje 32 banki, z których każdy aktualizuje się o połowę tak często, jak przed nim. Utrudnia to atakowanie wszystkich 32 banków w rozsądnym czasie.

Przetwarzanie Po zebraniu „entropii” musisz ją wyczyścić i oddzielić od danych wejściowych w trudny do odwrócenia sposób. SHA / 1/256 jest do tego dobry. Możesz użyć SHA1 (a nawet MD5 naprawdę) do prędkości, ponieważ nie masz luki w postaci zwykłego tekstu. Do zbioru nigdy nie używaj pełnego banku entopy, a ZAWSZE ZAWSZE dodawaj „sól” do wyjścia, które jest za każdym razem inne, aby zapobiec identycznym wyjściom, biorąc pod uwagę brak zmian banku entropii: output = sha1( String(micros()) + String(bank[0]) + [...] );funkcja sha zarówno ukrywa nakłady, jak i wybiela wyjście, chroniąc przed słabymi nasionami, niski poziom akumulacji entów i inne typowe problemy.

Aby korzystać z wejść timera, musisz uczynić je nieokreślonymi. To proste jak delayMicroseconds(lastSample % 255); która wstrzymuje nieprzewidywalny czas, powodując, że „kolejny” zegar odczytuje różnicę nierównomierną. Rób to co pół, regularnie, if(analogRead(A1)>200){...}pod warunkiem, że A1 jest głośny lub podłączony do wejścia dynamicznego. Sprawienie, że każdy rozwidlenie przepływu będzie trudny do ustalenia, zapobiegnie kryptoanalizie dekompilowanej / zgranej produkcji.

Prawdziwe bezpieczeństwo ma miejsce, gdy osoba atakująca zna cały system i nadal nie jest w stanie go pokonać.

Na koniec sprawdź swoją pracę. Uruchom swoje wyjście za pomocą ENT.EXE (dostępnego również dla nix / mac) i sprawdź, czy jest w porządku. Najważniejszy jest rozkład chi-kwadrat, który zwykle powinien wynosić od 33% do 66%. Jeśli dostaniesz 1,43% lub 99,999% lub coś w tym stylu, więcej niż jeden test z rzędu, twój los to bzdury. Chcesz także, aby raporty ENT z entropii były jak najbliższe 8 bitom na bajt, na pewno> 7,9.

TLDR: Najprostszym niezawodnym sposobem jest użycie HWRNG w ESP8266. Jest szybki, jednolity i nieprzewidywalny. Uruchom coś takiego na ESP8266 z rdzeniem Ardunio i użyj serial do rozmowy z 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"
}

** edytować

oto szkic HWRNG bez systemu operacyjnego, który napisałem jakiś czas temu, działając nie tylko jako kolektor, ale cały CSPRNG wypluwający z portu szeregowego. Jest zbudowany na pro-mini, ale powinien być łatwy do dostosowania do innych płyt. Możesz użyć tylko pływających pinów analogowych, ale lepiej jest do nich dodawać różne rzeczy, najlepiej różne. Jak mikrofony, LDR, termistory (przycięte do maks. Rozpiętości wokół temperatury pokojowej), a nawet długie przewody. W ENT robi to całkiem dobrze, jeśli masz nawet umiarkowany hałas.

Szkic obejmuje kilka pojęć, o których wspomniałem w mojej odpowiedzi i komentarzach uzupełniających: akumulację entropii, rozciąganie poprzez nadmierne próbkowanie entropii mniej niż idealnej (von neumann powiedział, że jest fajna) i mieszanie się do jednolitości. Rezygnuje z oceny jakości entropii na rzecz „daj mi wszystko, co możliwe, dynamiczne” i miksowania przy użyciu kryptograficznego elementu pierwotnego.

// 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()

Z mojego doświadczenia analogRead()wynika , że na pływającej szpilce ma bardzo niską entropię. Może jeden lub dwa bity losowości na połączenie. Na pewno chcesz czegoś lepszego. Jitter timera watchdoga, jak zaproponowano w odpowiedzi per1234, jest dobrą alternatywą. Jednak generuje entropię z dość małą szybkością, co może być problemem, jeśli potrzebujesz go w momencie uruchamiania programu. dandavis ma kilka dobrych sugestii, ale na ogół wymagają ESP8266 lub zewnętrznego sprzętu.

Jest jedno interesujące źródło entropii, o którym jeszcze nie wspomniano: zawartość niezainicjowanej pamięci RAM. Po włączeniu MCU niektóre bity RAM (te, które mają najbardziej symetryczne tranzystory) uruchamiają się w losowym stanie. Jak omówiono w tym artykule o hackaday , można go użyć jako źródła entropii. Jest dostępny tylko przy zimnym rozruchu, więc możesz go użyć do wypełnienia początkowej puli entropii, którą następnie okresowo uzupełniasz z innego, potencjalnie wolnego źródła. W ten sposób Twój program może rozpocząć pracę bez czekania, aż pula powoli się zapełni.

Oto przykład, w jaki sposób można to zrobić na Arduino opartym na AVR. Fragment kodu poniżej XOR zapełnia całą pamięć RAM, aby zbudować ziarno, do którego później będzie się karmił srandom(). Problem polega na tym, że zbieranie musi zostać wykonane, zanim środowisko wykonawcze C zainicjuje sekcje pamięci .data i .bss, a następnie nasiona muszą zostać zapisane w miejscu, w którym środowisko wykonawcze C nie nadpisze. Odbywa się to za pomocą określonych sekcji pamięci .

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);
}

Zauważ, że po ciepłym resecie pamięć SRAM zostaje zachowana, więc nadal ma całą zawartość twojej puli entropii. Ten sam kod można następnie wykorzystać do zachowania zgromadzonej entropii podczas resetowania.

Edycja : naprawiono problem w mojej początkowej wersji, seed_from_ram()który działał na globalnym random_seedzamiast używać lokalnego seed. Może to doprowadzić do tego, że ziarno zostanie XOR z samym sobą, niszcząc całą dotychczasową entropię.

Jeśli tak naprawdę nie potrzebujesz entropii i po prostu chcesz uzyskać inną sekwencję liczb pseudolosowych przy każdym uruchomieniu, możesz użyć EEPROM do iteracji przez kolejne nasiona. Technicznie proces będzie całkowicie deterministyczny, ale pod względem praktycznym jest znacznie lepszy niż randomSeed(analogRead(0))na niepodłączonym pinie, co często powoduje, że zaczynasz z tym samym początkiem 0 lub 1023. Zapisanie następnego początku w EEPROM zagwarantuje, że zaczniesz od innego ziarno za każdym razem.

#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);
}

Jeśli potrzebujesz prawdziwej entropii, możesz ją zebrać z dryftu zegara lub przez wzmocnienie zewnętrznego szumu. A jeśli potrzebujesz dużo entropii, hałas zewnętrzny jest jedyną realną opcją. Dioda Zenera jest popularnym wyborem, szczególnie jeśli masz źródło napięcia powyżej 5-6 V (będzie również działać z 5 V z odpowiednią diodą Zenera, ale spowoduje mniej entropii):

( źródło ).

Wyjście wzmacniacza musi być podłączone do pinu analogowego, który wytworzy kilka bitów entropii z każdym analogRead()do dziesiątek MHz (szybciej niż Arduino może próbkować).