Test di un generatore di numeri casuali dell'hardware

13

Il Raspberry Pi ha un generatore di numeri casuali hardware incorporato ma non sembra esserci alcuna documentazione pubblica sull'hardware, e anche se ci fosse sarebbe discutibile (quale compagnia ammettere pubblicamente che potrebbe esserci problemi con il proprio hardware se possono farla franca?)

Quindi la domanda, qual è il metodo migliore per testare un generatore di numeri casuali dell'hardware? Se ho riempito un file da 10 GB con numeri casuali generati con il generatore di numeri casuali dell'hardware ci sono strumenti sul mio computer principale che posso usare per vedere se ci sono dei modelli nei numeri prodotti?

Trovo difficile credere che non ci sia alcun modo per verificare se un generatore di numeri casuali (sia esso software o hardware) sia sicuro da usare. Altrimenti perché qualcuno dovrebbe mai fidarsi di un generatore di numeri casuali che non era open source e che non poteva essere verificato in modo indipendente?

Mi piacerebbe usare il Raspberry Pi per generare alcune chiavi private ma il normale generatore di numeri casuali del software non ottiene abbastanza entropia per renderlo praticabile (impiega anni per generare) ma con il generatore di numeri casuali dell'hardware è molto più fattibile. Non so se posso fidarmi del generatore di numeri casuali dell'hardware o no.

    
posta Cromulent 22.12.2013 - 01:59
fonte

7 risposte

11

Ci sono diversi fattori in gioco qui:

  • Il meccanismo fisico HRNG utilizzato all'interno del microprocessore ARM.
  • La logica di supporto sul silicio all'interno del microprocessore.
  • Il microcodice distribuito sul microprocessore.
  • L'implementazione del RNG in Linux.

Secondo il produttore, quel particolare chip utilizza il rumore di un transistor di polarizzazione inversa, in un progetto HRNG a collettore aperto. Questo è precisamente l'hardware che sto usando nel mio attuale progetto HRNG, ma molto più piccolo. È uno dei modi più economici per implementare un HRNG direttamente nel silicio; mentre io sto usando transistor discreti, il processore ARM si riduce semplicemente a qualche puntina di silicio sul chip die.

Sappiamo che questo meccanismo è una strong fonte di casualità, perché si basa su un fenomeno chiamato tunneling quantico , che è noto per essere probabilistico e casuale. L'idea di base è che gli elettroni "saltano" casualmente sopra la banda proibita all'interno del transistor, portando a un segnale fluttuante in modo casuale. Possiamo quindi amplificare questo (un semplice amplificatore a transistor PNP lo farà) e interpretare l'uscita come 1 o 0 campionando il risultato ad una frequenza fissa - se supera una certa soglia è un 1, altrimenti è uno 0.

Un leggero deficit di questo meccanismo è che qualsiasi dispersione DC porterà ad una inclinazione verso 1s che appare più spesso di 0 secondi. Per ovviare a questo, possiamo usare un semplice trucco chiamato decorrelazione di von Neumann, che essenzialmente consiste nel codificare le coppie di bit 01 e 10 su 0 e 1 rispettivamente, ignorando tutte le coppie 00 e 11. Ciò produce un flusso statisticamente non distorto.

Posso quasi certamente garantire che questo è il meccanismo con cui produce numeri casuali. C'è un'alternativa principale (due porte NOT polarizzate inverse in parallelo) ma è coperta da un brevetto Intel, quindi dubito che ARM stia usando quello. Sfortunatamente, l'unico modo per sapere con certezza è di prendere un po 'di acido e decapare un chip, quindi prendere un microscopio e iniziare il reverse engineering del silicio. Non ho l'attrezzatura di riserva disponibile per questo.

La potenziale vulnerabilità che potresti trovare in tale esplorazione è che i segnali di clock ad alta frequenza o altre linee di dati HF sono instradati molto vicino all'RGNG o alla sua logica di supporto, portando a potenziali interferenze. Questo di solito è improbabile nei circuiti integrati, ma stiamo parlando di applicazioni ad alta sensibilità qui, quindi vale la pena cercarlo. Anche se fosse il caso, però, non vedo che fornisca un utile disallineamento da una prospettiva crittanalitica.

Il prossimo potenziale di sfruttamento è il microcodice. Recentemente, un ricercatore ha dimostrato che era possibile applicare patch al microcode per i processori Intel per cercare modelli unici nel buffer delle istruzioni e rilevare quando l'istruzione RDRAND veniva utilizzata per riempire il pool /dev/random . Identificherebbe quindi la posizione di quel buffer del pool nella cache del processore e lo azzererebbe effettivamente, causando la copia del pool zero nella memoria del sistema. Ciò significava che /dev/random avrebbe costantemente prodotto lo stesso valore controllato dagli attaccanti, con risultati ovviamente devastanti. Se è stato utilizzato un trucco simile ma più sottile nel microcode ARM, potrebbe essere possibile ridurre in modo massiccio l'entropia dell'HRNG in un modo che è noto solo al creatore del cerotto. Rilevare questi trucchi sarebbe difficile, ma potrebbe essere fatto estraendo il microcodice e analizzandolo.

Infine, l'ultimo problema è il design RNG all'interno del kernel di Linux. Il pool /dev/random viene in genere alimentato da una serie di fonti basate sullo stato, utilizzando un algoritmo di missaggio basato su una funzione crittografica. Tuttavia, quando sono disponibili istruzioni RDRAND o simili, il motore semplicemente svela i dati sul pool. Questa non è esattamente una buona idea, perché rende facile avvitare i dati del pool in modo significativo producendo determinati valori. Se fosse usata la funzione di missaggio più strong, l'attaccante avrebbe bisogno di romperlo (o fare qualcosa di più evidente) al fine di ottenere un controllo significativo sul pool.

Non c'è una risposta ovvia alla tua domanda. I generatori di numeri casuali dell'hardware possono essere di altissima qualità, ma è difficile analizzarne l'implementazione solo con un dispositivo consumer. Detto questo, se hai intenzione di diffidare del tuo hardware, non puoi davvero fare alcuna garanzia in primo luogo. Se si desidera limitare interamente la portata della sfiducia alla qualità dei numeri casuali prodotti, quindi progettare il sistema di supporto in base a tale circostanza.

    
risposta data 22.12.2013 - 04:29
fonte
6

Ho avuto lo stesso problema in passato. L'Istituto nazionale degli standard e della tecnologia degli Stati Uniti (NIST) ha effettivamente preparato una suite piena di un intero gruppo di test . Contiene tutti i tipi di test statistici e riporta un valore p per ogni test. Include test semplici come il conteggio degli zeri e quelli per vedere se sono vicini al 50% e test sofisticati come l'analisi dello spettro. C'è un manuale molto ampio di facile lettura e comprensione che spiega tutta la teoria e come utilizzare correttamente i test e interpretare i loro risultati.

    
risposta data 22.12.2013 - 10:30
fonte
5

I find it hard to believe that there is no third party way to verify whether a random number generator (be it software or hardware) is safe to use.

Purtroppo, questo è il caso. A meno che l'RNG sia terribilmente negativo che ci sia un bias visibile nell'output, è molto difficile rilevare se un RNG contiene debolezze sottili che possono essere considerate backdoor senza guardare alla fonte.

    
risposta data 22.12.2013 - 03:32
fonte
3

Per quanto riguarda gli strumenti da utilizzare per testare la prevedibilità dei dati casuali - lo standard del settore è la suite dieharder, da trovare qui .
Esempio specifico di RaspberryPi, da lanciare dopo installazione del modulo del kernel e rng-tools :

apt-get install dieharder
cat /dev/hwrng | dieharder -d 0 -vv  

# Verbose is now 0
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name|rands/second|   Seed   |
    mt19937|  1.34e+06  |2497347415|
#=============================================================================#
    test_name       |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.79423698|  PASSED  
    
risposta data 08.03.2014 - 12:09
fonte
2

Bene, ci sono alcune cose che puoi provare. Ti indicherò questa pagina: link

Controlla il tuo livello di casualità

Puoi verificare il livello di entropia / casualità nel tuo file di uscita usando ent. "Ent può essere usato contro qualsiasi file contenente dati e testerà la casualità di quei dati"

Aumenta la tua enthropy

Aumenta l'entropia. C'è un demone chiamato "rngd" che puoi usare. Funziona in background e aumenta significativamente la quantità di entropia sul sistema. La qualità dei dati è all'incirca uguale a quella che / dev / random produrrebbe, quindi è sufficiente fare di più al secondo.

Vale la pena ricordare il seguente articolo: link

The main change this has forced is the viewing of hardware random number generators as psudo-random number generators. Treating them as that means that precautions can be taken to make the generated numbers more random (such as passing it through as a seed to a second random number generator).

Potresti creare il tuo generatore di numeri casuali. Ci sono molti progetti interessanti là fuori che ti mostreranno come.

    
risposta data 22.12.2013 - 06:07
fonte
1

Un computer è una macchina deterministica e deve sempre eseguire i passaggi sani nello stesso ordine. Un generatore di numeri pseudo-casuali è un algoritmo software che produce numeri "imprevedibili" in determinate condizioni: conoscere qualsiasi output del generatore non ti aiuterà a determinare i numeri che sono stati generati prima della sequenza che conosci e sapere che l'output non ti aiuterà a determinare il futuro produzione. Naturalmente conoscere lo stato interno consente di prevedere l'output futuro. Lo stato iniziale è chiamato seme.

Per produrre numeri veramente imprevedibili, lo stato dell'algoritmo deve essere seminato con un valore inconoscibile. Ma un algoritmo matematico non può produrne uno. Quindi i progettisti di hardware creano hardware che offre una misura di imprevedibilità.

Se non ti fidi dell'hardware, puoi comunque raccogliere il maggior numero possibile di informazioni sconosciute e combinarle insieme. Se una fonte è distorta, contribuirà semplicemente meno allo stato generale sconosciuto. Questi algoritmi sono noti come raccoglitori di entropia. L'output viene eseguito tramite una funzione di spugna crittografica, che assorbe i dati sconosciuti a qualunque velocità arrivi, quindi emette byte pseudocasuali su richiesta.

    
risposta data 22.12.2013 - 04:13
fonte
1

Il test di un generatore di numeri casuali è simile a test di generatori di numeri casuali pseduo di buona qualità (funzioni matematiche) e può utilizzare gli stessi strumenti sviluppati per loro; FIPS 140, STS 1.2.1, irriducibile, dieharder, Test U01, ecc.

Interpretare i risultati di questi test è un po 'diverso quando si ha a che fare con un vero generatore di numeri casuali. Quando si verifica un generatore basato su una funzione matematica, un errore di test rivela un difetto nella progettazione del generatore di base; tuttavia, con un generatore basato su fisica ci aspettiamo che i test falliscano occasionalmente su un dato campione. E fintanto che questi test falliti non si ripetono frequentemente con diversi campioni il generatore sta ancora producendo quello che ci aspettiamo dovrebbe.

Un'altra differenza è che quando si verifica un generatore basato su matematica, è necessario testarlo solo una volta per determinarne la validità; tuttavia, un generatore basato fisico dovrebbe essere testato regolarmente poiché i cambiamenti nelle proprietà fisiche dell'hardware che raccoglie la casualità (entropia) possono influire sulla validità del suo output.

Ho creato un sito web che descrive in dettaglio le mie esplorazioni in corso relative alla progettazione, all'implementazione, all'utilizzo e al collaudo di questi generatori fisici che contiene più informazioni se il vostro interesse, compresi quattro set di test eseguiti su quattro diversi campioni di quattro gigabyte raccolti dal generatore di numeri casuali dell'hardware interno di Pi:

Visualizzazione dei generatori di numeri casuali veri

test Raspberry Pi

    
risposta data 19.04.2014 - 14:43
fonte

Leggi altre domande sui tag