Mendapatkan nomor acak di Arduino

Apa metode terbaik untuk mendapatkan nomor acak yang benar-benar (bukan pseudo) di Arduino, atau setidaknya perkiraan terbaik? Dari pemahaman saya, fungsi randomSeed (analogRead (x)) itu tidak cukup acak.

Jika memungkinkan, metode ini harus memanfaatkan pengaturan Arduino dasar saja (tidak ada sensor tambahan). Solusi dengan sensor eksternal dipersilakan jika mereka secara signifikan meningkatkan keacakan atas pengaturan dasar.

The Entropi perpustakaan menggunakan:

jitter alami pengawas waktu untuk menghasilkan aliran yang dapat diandalkan nomor acak benar

Saya suka solusi ini karena tidak menggunakan pin mikrokontroler Anda dan tidak memerlukan sirkuit eksternal. Ini juga membuatnya kurang tunduk pada kegagalan eksternal.

Selain perpustakaan, mereka juga menyediakan sketsa yang menunjukkan penggunaan teknik yang sama yang digunakan untuk menghasilkan benih acak untuk PRNG mikrokontroler tanpa perpustakaan: https://sites.google.com/site/astudyofentropy/project-definition / timer-jitter-entropy-sources / entropy-library / arduino-random-seed

randomSeed(analogRead(x))hanya akan menghasilkan 255 urutan angka, yang membuatnya sepele untuk mencoba semua kombo dan menghasilkan oracle yang dapat berpasangan dengan aliran output Anda, memprediksi semua output 100%. Namun Anda berada di jalur yang benar, ini hanya permainan angka, dan Anda membutuhkan BANYAK lebih banyak lagi. Misalnya, mengambil 100 analog dibaca dari 4 ADC, menjumlahkan semuanya, dan memberi makan itu randomSeedakan jauh lebih baik. Untuk keamanan maksimal, Anda membutuhkan input yang tidak dapat diprediksi dan pencampuran yang non-deterministik.

Saya bukan seorang cryptographer, tetapi saya telah menghabiskan ribuan jam untuk meneliti dan membangun perangkat keras dan perangkat lunak generator secara acak, jadi izinkan saya berbagi beberapa dari apa yang telah saya pelajari:

Input yang Tidak Dapat Diprediksi:

• analogRead () (pada floating pin)
• GetTemp ()

Input yang Mungkin Tidak Dapat Diprediksi:

• micros () (dengan periode sampel non-deterministik)
• clock jitter (bandwidth rendah, tetapi dapat digunakan)
• readVCC () (jika tidak bertenaga baterai)

Input Eksternal Tidak Dapat Diprediksi:

• temp, kelembaban, dan sensor tekanan
• mikrofon
• Pembagi tegangan LDR
• kebisingan transistor reverse-bias
• kompas / percepatan percepatan
• esp8266 wifi hotspot scan (ssid, db, dll)
• waktu esp8266 (tugas-tugas wifi latar belakang membuat micros dijadwalkan () mengambil tak tentu)
• esp8266 HWRNG - -sangat RANDOM_REG32cepat dan tidak dapat diprediksi, 1-stop

mengumpulkan Hal terakhir yang ingin Anda lakukan adalah memuntahkan entropi seperti yang terjadi. Lebih mudah untuk menebak flip koin daripada seember koin. Penjumlahan itu bagus. unsigned long bank;nanti bank+= thisSample;bagus; itu akan terguling. bank[32]bahkan lebih baik, baca terus. Anda ingin mengumpulkan setidaknya 8 sampel input untuk setiap potongan output, idealnya jauh lebih banyak.

Melindungi dari keracunan Jika memanaskan papan menyebabkan jitter jam maksimal, itu adalah vektor serangan. Sama dengan peledakan RFI ke input analogRead (). Serangan umum lainnya hanya mencabut unit sehingga membuang semua akumulasi entropi. Anda tidak boleh mengeluarkan angka sampai Anda tahu aman melakukannya, bahkan dengan mengorbankan kecepatan.

Inilah sebabnya mengapa Anda ingin menjaga beberapa entropi dalam jangka panjang, menggunakan EEPROM, SD, dll. Lihatlah ke dalam Fortuna PRNG , yang menggunakan 32 bank, masing-masing memperbarui setengah sesering yang sebelumnya. Itu membuatnya sulit untuk menyerang semua 32 bank dalam jumlah waktu yang wajar.

Memproses Setelah Anda mengumpulkan "entropi", Anda harus membersihkannya dan menceraikannya dari input dengan cara yang sulit untuk dibalik. SHA / 1/256 bagus untuk ini. Anda dapat menggunakan SHA1 (atau bahkan MD5) untuk kecepatan karena Anda tidak memiliki kerentanan plaintext. Untuk memanen, jangan pernah menggunakan bank entopy penuh, dan SELALU SELALU menambahkan "garam" ke output yang berbeda setiap kali untuk mencegah output identik tanpa perubahan bank entropi: output = sha1( String(micros()) + String(bank[0]) + [...] );Fungsi sha menyembunyikan input dan memutihkan output, melindungi terhadap benih lemah, akumulasi rendah, dan masalah umum lainnya.

Untuk menggunakan input penghitung waktu, Anda harus membuatnya tidak pasti. Ini sederhana seperti delayMicroseconds(lastSample % 255); yang menjeda jumlah waktu yang tidak dapat diprediksi, membuat jam "berturut-turut" membaca perbedaan yang tidak seragam. Lakukan itu secara semi-teratur, misalnya if(analogRead(A1)>200){...}, asalkan A1 berisik atau terhubung ke input dinamis. Membuat setiap garpu aliran Anda agak sulit untuk ditentukan akan mencegah cryptoanalysis pada hasil dekompilasi / robek.

Keamanan sebenarnya adalah ketika penyerang mengetahui seluruh sistem Anda dan masih tidak berdaya untuk mengatasinya.

Terakhir, periksa pekerjaan Anda. Jalankan output Anda melalui ENT.EXE (juga tersedia untuk nix / mac) dan lihat apakah ada gunanya. Yang paling penting adalah distribusi chi square, yang biasanya harus antara 33% dan 66%. Jika Anda mendapatkan 1,43% atau 99,999% atau sesuatu seperti itu, lebih dari satu tes berturut-turut, acak Anda adalah omong kosong. Anda juga ingin laporan ENT entropi sedekat mungkin dengan 8 bit per byte,> 7,9 pasti.

TLDR: Cara pembodohan yang paling sederhana adalah dengan menggunakan HWRNG ESP8266. Cepat, seragam, dan tidak dapat diprediksi. Jalankan sesuatu seperti ini pada ESP8266 yang menjalankan inti Ardunio, dan gunakan serial untuk berbicara dengan 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"
}

** sunting

di sini adalah sketsa HWRNG tanpa papan yang saya tulis beberapa waktu lalu, beroperasi bukan hanya sebagai kolektor, tetapi seluruh CSPRNG keluar dari port serial. Ini dibuat untuk pro-mini tetapi harus mudah disesuaikan dengan papan lainnya. Anda dapat menggunakan pin analog yang hanya mengambang, tetapi lebih baik menambahkannya, hal-hal yang lebih baik. Seperti mikrofon, LDR, termistor (dipangkas hingga maksimum yang menyebar di sekitar suhu kamar), dan bahkan kabel panjang. Itu cukup baik di THT jika Anda bahkan memiliki noise sedang.

Sketsa tersebut memadukan beberapa gagasan yang telah saya sebutkan dalam jawaban dan komentar tindak lanjut saya: akumulasi entropi, peregangan dengan pengambilan sampel entropi yang kurang ideal (von neumann mengatakan itu keren), dan berseragam. Ini melupakan estimasi kualitas entropi yang mendukung "beri aku sesuatu yang mungkin dinamis" dan pencampuran menggunakan primitif kriptografi.

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

Dari pengalaman saya, analogRead()pada pin mengambang memiliki entropi yang sangat rendah. Mungkin satu atau dua bit keacakan per panggilan. Anda pasti menginginkan sesuatu yang lebih baik. Jitter pengukur waktu pengawas, seperti yang diusulkan dalam jawaban per1234, adalah alternatif yang baik. Namun, itu menghasilkan entropi pada tingkat yang sangat lambat, yang dapat menjadi masalah jika Anda membutuhkannya saat program dimulai. Dandavis memiliki beberapa saran bagus, tetapi mereka umumnya membutuhkan ESP8266 atau perangkat keras eksternal.

Ada satu sumber entropi menarik yang belum disebutkan: isi RAM yang tidak diinisialisasi. Ketika MCU dinyalakan, beberapa bit RAM-nya (yang memiliki transistor paling simetris) mulai dalam keadaan acak. Seperti yang dibahas dalam artikel hackaday ini , ini dapat digunakan sebagai sumber entropi. Ini hanya tersedia pada boot dingin, sehingga Anda dapat menggunakannya untuk mengisi kumpulan entropi awal, yang kemudian akan Anda isi secara berkala dari sumber lain yang berpotensi lambat. Dengan cara ini, program Anda dapat memulai tugasnya tanpa harus menunggu kolam diisi secara perlahan.

Berikut adalah contoh bagaimana ini dapat dipanen pada Arduino berbasis AVR. Cuplikan kode di bawah XOR seluruh RAM untuk membangun sebuah benih yang kemudian diumpankan srandom(). Bagian yang sulit adalah bahwa pemanenan harus dilakukan sebelum runtime C menginisialisasi bagian .data dan .bss memori, dan kemudian benih harus disimpan di tempat runtime C tidak akan menimpa. Ini dilakukan dengan menggunakan bagian memori tertentu .

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

Perhatikan bahwa, pada reset hangat , SRAM dipertahankan, sehingga masih memiliki seluruh konten kumpulan entropi Anda. Kode yang sama ini kemudian dapat digunakan untuk menyimpan entropi yang dikumpulkan melalui reset.

Sunting : memperbaiki masalah dalam versi awal saya seed_from_ram()yang berfungsi di global random_seedalih-alih menggunakan lokal seed. Hal ini dapat menyebabkan benih menjadi XOR dengan dirinya sendiri, menghancurkan semua entropi yang dipanen sejauh ini.

Jika Anda tidak benar-benar membutuhkan entropi dan hanya ingin mendapatkan urutan angka pseudo-acak yang berbeda pada setiap startup, Anda dapat menggunakan EEPROM untuk beralih melalui seed berurutan. Secara teknis prosesnya akan sepenuhnya deterministik, tetapi secara praktis lebih baik daripada randomSeed(analogRead(0))pada pin yang tidak terhubung, yang sering membuat Anda mulai dengan seed yang sama 0 atau 1023. Menyimpan seed berikutnya di EEPROM akan menjamin Anda memulai dengan yang berbeda. benih setiap kali.

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

Jika Anda membutuhkan entropi nyata, Anda dapat mengumpulkannya baik dari penyimpangan jam, atau dengan memperkuat kebisingan eksternal. Dan jika Anda membutuhkan banyak entropi, noise eksternal adalah satu-satunya pilihan. Dioda Zener adalah pilihan yang populer, terutama jika Anda memiliki sumber tegangan di atas 5-6V (ini akan bekerja dengan 5V juga dengan dioda Zener yang sesuai, tetapi akan menghasilkan lebih sedikit entropi):

( sumber ).

Output amplifier harus dihubungkan ke pin analog, yang akan menghasilkan beberapa bit entropi dengan masing-masing analogRead()hingga puluhan MHz (lebih cepat daripada sampel Arduino).