Uzyskanie naprawdę losowej liczby w Arduino


13

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.


Jaka jest aplikacja? Czy musi być kryptograficznie bezpieczny? Co zatem robisz z przypadkowością? Zatem bez zewnętrznego układu implementującego TRNG z fizycznego źródła entropii nie masz szczęścia. Możesz także zaimplementować deterministyczny RNG, taki jak HMAC DRBG, i zainicjować go z czegoś statycznego oraz niskiej jakości źródła entropii, ale nadal nie będzie to kryptograficznie bezpieczne.
Maximilian Gerhardt

Tak, potrzebuję liczb losowych dla aplikacji bezpiecznych kryptograficznie.
Rexcirus

Odpowiedzi:


10

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


8

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

(Przepraszam, brakuje mi postaci). Dobry przegląd! Sugerowałbym użyć licznika soli; micros () to strata bitów, ponieważ może przeskakiwać o kilka kroków między wywołaniami. Unikaj wysokich bitów na wejściach analogowych, ogranicz do najniższego jednego lub dwóch bitów. Nawet przy ukierunkowanym ataku są trudne do przypięcia (chyba, że ​​możesz umieścić drut na wejściu). „Niedeterministyczne mieszanie” nie jest czymś, co można zrobić w oprogramowaniu. Mieszanie SHA-1 jest znormalizowane: crypto.stackexchange.com/a/6232 . Indet. zaproponowany przez Ciebie zegar jest tak losowy, jak źródło, które już masz. Nie ma tu wielkiego zysku.
Jonas Schäfer

sha upraszcza i chroni, dzięki czemu nie musisz się martwić, na przykład, ile bitów można pobrać z wejścia analogowego. kilka cali drutu podłączonego do analogu (lub serpentynowego śladu płytki drukowanej) przesunie go o więcej niż kilka bitów. mieszanie jest niedeterministyczne z powodu niezapisanej i nieznanej soli podawanej do mieszania z podpróbką skumulowanych wartości. micros () jest trudniejszy do odtworzenia niż licznik, szczególnie gdy jest uruchamiany w nieokreślonych odstępach czasu.
dandavis

1
Mam pytanie. Powiedziałeś, że podjęcie 100 kroków jest lepsze. Ale czy podejmowanie wielu działań nie jest rodzajem „średniej”, która ogranicza skuteczność pobierania tych „losowych” danych? Chodzi mi o to, że zwykle uzyskuje się mniej hałaśliwych (a więc mniej „losowych”) pomiarów ...
frarugi87 14.03.18

cóż, zalecam stałe próbkowanie, mówiłem tylko, że 100 jest lepsze niż 1, ponieważ oferuje więcej kombinacji. Model akumulacji, taki jak Yarrow / Fortuna, jest wciąż znacznie lepszy. Rozważ połączenie (bez sumowania) tych 100 próbek analogowych przed mieszaniem; silniejszy, ponieważ sprawia, że ​​kolejność próbek jest ważna, a bycie jednym charakterem daje zupełnie inny skrót. Tak więc, chociaż można uśrednić próbki, aby uzyskać mniej hałasu, atakujący musiałby dosłownie recytować wszystkie wartości lub nie pasować do siebie ... Moim głównym celem jest „gromadzenie, miksowanie i weryfikacja” bardziej niż zalecanie określonego źródła hałasu.
dandavis

4

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ę.


Dobra robota! czy mogę ukraść? re: piny: wystarczy jeden lub dwa bity nieznanego, jeśli są właściwie wykorzystane; ograniczyłoby to tylko szybkość wyjściową idealnej tajemnicy (fuj), ale nie tajemnicę obliczeniową, której potrzebujemy ...
dandavis

1
@dandavis: Tak, możesz ponownie użyć, jasne. Masz rację co analogRead()do użyteczności, jeśli wiesz, co robisz. Musisz tylko uważać, aby nie przecenić jego losowości podczas aktualizacji oszacowania entropii puli. Chodzi mi o analogRead()to głównie pomyślany jako krytykę ubogiej jeszcze często powtarzane „przepis” : randomSeed(analogRead(0)) tylko raz w setup()i zakładamy, że to wystarczy.
Edgar Bonet

Jeśli analogRead(0)ma 1 bit entropii na wywołanie, to wywołanie go wielokrotnie da 10000/8 = 1,25 KB / s entropii, 150 razy więcej niż biblioteka Entropy.
Dmitrij Grigoriew

0

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):

wprowadź opis zdjęcia tutaj

( ź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ć).

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.