Cosa rende i generatori di numeri casuali così fragili?

Question

view on stackexchange narkive permalink

Mi sembra che un componente hardware che genera numeri casuali sia estremamente semplice: basta misurare piccole vibrazioni nell'hardware con un sensore, giusto? Forse mi sbaglio ma sembra che se misurassi le vibrazioni con una precisione molto elevata, potresti facilmente generare numeri casuali indovinabili.

Tuttavia, sono un noob della crittografia e ne so poco. Quindi sto leggendo e un articolo dice:

e non è necessario essere così sofisticati per indebolire un generatore di numeri casuali. Questi generatori sono già sorprendentemente fragili ed è terribilmente difficile rilevare quando uno è rotto. I manutentori di Debian hanno sottolineato questo punto in modo meraviglioso nel 2008, quando un'errata pulizia del codice ha ridotto l'entropia effettiva di OpenSSL a soli 16 bit. In effetti, gli RNG sono così vulnerabili che la sfida qui non è indebolire l'RNG - qualsiasi idiota con una tastiera può farlo - lo fa senza rendere l'implementazione banalmente vulnerabile a tutti gli altri.

Sicuramente mi mancano alcuni dettagli critici su come la generazione di numeri casuali sia "fragile". Qualcuno può spiegare?

Answer 1

view on stackexchange narkive permalink

RNG hardware e software

La prima cosa che dici è una fonte di rumore hardware. La misurazione ad alta precisione di alcuni fenomeni metastabili è sufficiente per generare dati imprevedibili. Questo può essere fatto con un diodo zener a polarizzazione inversa, con oscillatori ad anello, con un ADC o anche con un contatore Geiger. Si può anche misurare i ritardi a livello di nanosecondi nei tempi tra le sequenze di tasti. Queste sorgenti di rumore possono non funzionare se l'hardware stesso inizia a guastarsi. Ad esempio, un transistor può rompersi se non è specificamente progettato per funzionare al contrario ad alte tensioni. Sebbene queste tecniche abbiano diversi livelli di fragilità, non è ciò che viene discusso nel testo che hai citato.

Il secondo tipo di RNG che hai menzionato è un software RNG chiamato generatore di numeri pseudocasuali (PRNG ^* ). Questo è un algoritmo che prende un seed , che è come una chiave di crittografia, e lo espande in un flusso infinito di dati. Tenta di garantire che i dati non possano essere previsti o separati dalla pura casualità, senza la conoscenza del seme casuale segreto con cui l'algoritmo è iniziato. In questo caso, il PRNG è implementato in software puro, quindi per romperlo è sufficiente introdurre un bug nel codice, che è ciò di cui parla il testo che hai citato. È semplicemente codice che è fragile , rischiando il completo fallimento se vengono apportate modifiche al codice che deviano dal comportamento previsto dall'algoritmo.

Un PRNG può essere considerato come un algoritmo di crittografia proposto. In effetti, puoi creare un PRNG crittograficamente sicuro utilizzando un codice come AES per crittografare un contatore. Finché la chiave di crittografia (seed) è segreta, l'output non può essere previsto e il seed non può essere scoperto. Quando ci si pensa in questo modo, diventa più facile capire come un piccolo, insignificante cambiamento nel codice possa rompere completamente la sicurezza dell'algoritmo.

Raccolta della casualità

Quindi, in che modo i dispositivi moderni raccolgono effettivamente la casualità? Prendiamo un server in esecuzione silenziosamente in un datacenter da qualche parte. Per supportare cose come TLS, ha bisogno di una grande quantità di dati completamente imprevedibili che non possono essere distinti da un flusso veramente casuale. Senza una sorgente di rumore hardware dedicata, la casualità deve provenire dall'interno. I computer si sforzano di essere completamente deterministici, ma ricevono molti input da dispositivi non deterministici. Inserisci ... interrupt!

Nell'hardware moderno, un interrupt è un segnale emesso dall'hardware per avvisare la CPU di un cambiamento di stato. Consente alla CPU di evitare di eseguire rapidamente il polling di ogni dispositivo hardware per gli aggiornamenti e invece di fidarsi che il dispositivo lo avviserà in modo asincrono quando sarà il momento. Quando si verifica un interrupt, viene chiamato un gestore di interrupt per elaborare il segnale. Si scopre che questo gestore è il posto perfetto per ottenere casualità! Quando misuri la temporizzazione a livello di nanosecondi degli interrupt, puoi ottenere rapidamente un bel po 'di casualità. Questo perché gli interrupt vengono attivati ​​per ogni genere di cose, dai pacchetti in arrivo sulla scheda NIC ai dati letti da un disco rigido. Alcune di queste sorgenti di interrupt sono altamente non deterministiche, come un disco rigido che si basa sul movimento fisico di un attuatore.

Una volta che sufficienti bit casuali sono stati raccolti dal sistema operativo, un piccolo seme di almeno 128 bit possono essere inseriti in un PRNG crittograficamente sicuro per generare un flusso illimitato di dati pseudocasuali. A meno che qualcuno non sia in grado di prevedere esattamente quando si è verificato ogni interruzione passata, con una precisione al nanosecondo, non sarà in grado di derivare il seme e non sarà in grado di prevedere la futura produzione di PRNG. Questo rende l'output completamente adatto per le chiavi TLS.

_{* Un PRNG orientato alla sicurezza è chiamato PRNG crittograficamente sicuro o CSPRNG. L'utilizzo di un normale PRNG quando un'applicazione richiede un CSPRNG può causare vulnerabilità di sicurezza.}

Answer 2

view on stackexchange narkive permalink

Storicamente, gli RNG hardware adatti per la crittografia non erano comunemente disponibili su PC: ad esempio, secondo questa domanda AMD ha aggiunto il supporto solo pochi anni fa, quindi anche oggi un fornitore di software può " t semplicemente presumere che sarà disponibile. Questo è presumibilmente il motivo per cui OpenSSL (come discusso nella tua citazione) utilizzava un software RNG, rendendolo vulnerabile al bug trovato nel codice.

(Come ampiamente discusso nei commenti, un PC standard contiene una serie di "fonti di entropia" che un software RNG può utilizzare - e credo che OpenSSL lo faccia, anche se non sono molto familiare con esso - ma ovviamente in quello scenario un bug nel software può portare a numeri casuali errati, come in effetti è successo.)

Ci sono anche preoccupazioni che gli RNG hardware potrebbero essere stati backdoor , portando le persone a combinare RNG hardware con altre fonti di entropia piuttosto che utilizzarli così come sono. (L'hardware con backdoor è menzionato anche nel tuo articolo collegato, a pochi paragrafi dal bit che hai citato.)

Va ​​anche detto che gli RNG hardware non sono così semplici da implementare come la tua domanda suggerisce ... per prima cosa, le implementazioni ingenue potrebbero essere vulnerabili a vari attacchi fisici, ad esempio, se stai generando bit casuali basati su vibrazioni, cosa succede se qualcuno punta un'ecografia su di esso? Anche in condizioni ideali, è probabile che ci sia una sorta di bias nei risultati che potrebbe rendere i bit generati non sicuri per l'uso crittografico.

Ecco perché le implementazioni del mondo reale usano il rumore hardware ma anche lo elaborano crittograficamente. Ma a quel punto sei tornato alla domanda se l'algoritmo (o la sua implementazione) è stato deliberatamente sabotato, o forse semplicemente non è robusto come si credeva.

Answer 3

view on stackexchange narkive permalink

Perché sono difficili da testare

Sebbene sia facile verificare che un generatore di numeri casuali produca output con il formato corretto, determinare se è statisticamente casuale è molto più complicato e improbabile che venga incluso in una suite di test automatizzata. Un sacco di altro codice sarà molto più ovvio se lo si rompe.

Crypto deve essere corretto

In generale, assicurarsi che il codice sia corretto è difficile. Una grazia salvifica per molto codice è che solo una piccola percentuale di errori di correttezza provoca vulnerabilità di sicurezza. Ma con il codice crittografico, inclusi i generatori di numeri casuali, molti errori di correttezza si tradurranno in vulnerabilità. Il codice crittografico deve essere corretto, per essere sicuro e assicurarsi che sia corretto è difficile.

Il manutentore Debian ha commesso un grave errore

Il codice non lo è in realtà così fragile. Affinché fosse reso insicuro, sono stati necessari gravi errori da parte del manutentore. tagliare righe che producono avvisi con solo controlli superficiali che non sia rotto nulla, è piuttosto scadente.

Modifica: non era solo il colpa del manutentore, vedi il commento di Angel

Answer 4

view on stackexchange narkive permalink

Uno degli aspetti più importanti di qualsiasi generatore casuale è che il valore di ogni bit casuale non solo deve essere completamente indipendente dai valori di tutti gli altri bit che genera, ma deve anche essere completamente indipendente da tutto il resto nell'universo un avversario potrebbe osservare o influenzare . Sfortunatamente, quella proprietà è spesso una delle più difficili da garantire. Il meglio che si può fare in genere è generare bit in un modo che è improbabile che abbia una relazione sfruttabile con qualsiasi altra cosa nell'universo.

A titolo di semplice esempio, se un avversario con un trasmettitore RF altamente focalizzato avesse una capacità di influenzare il tuo generatore di numeri casuali in modo che alcuni campioni di sua scelta abbiano una probabilità del 95% di produrne uno, mentre il resto avrebbe solo una probabilità del 5% di farlo. Se si dovessero semplicemente leggere 128 bit da un tale generatore e incorporarli in una chiave a 128 bit, un attaccante che ha concentrato un attacco di forza bruta su schemi di bit vicini a quello usato per influenzare il generatore avrebbe una probabilità molto maggiore di successo rapido che se il generatore fosse stato imparziale. Supponiamo, tuttavia, che invece di selezionare i bit uno alla volta, si selezionino gruppi di 7 bit e li xo insieme. Ciò aumenterebbe di sette volte il tempo per generare una chiave a 128 bit, ma l'influenza di un utente malintenzionato verrebbe ridotta da 95/5 a 74/26, riducendo notevolmente la probabilità che la chiave finisca per essere vicina al modello di bit dell'aggressore cercando di forzare.

In alternativa, si supponga di generare 128 bit casuali, di eseguirne l'hashing in qualche modo e quindi di xorarli con altri 128 bit casuali. Ciò richiederebbe solo la generazione di 256 bit anziché 896, ma renderebbe molto difficile per un attaccante sfruttare qualsiasi bias nel generatore. Anche se enumerare i pattern più probabili a 95.000.000.000 di bit a 128 bit avrebbe circa il 50% di possibilità di abbinare un gruppo di 128 bit utilizzato prima dell'hash, o quello con cui il valore di hash è stato xor'ed, la distribuzione finale dopo xor sarebbe improbabile che abbiano pregiudizi o fughe di informazioni sfruttabili .

Answer 5

view on stackexchange narkive permalink

Gli RNG sicuri comunemente usati come / dev / random di Linux, ChaCha20 o RdRand funzionano bene per molti casi convenzionali. Tuttavia, sono tutt'altro che a prova di idiota. Supponiamo che tu faccia qualcosa di divertente come non impostare il tuo orologio in tempo reale quando generi numeri casuali all'avvio. Se non capisci come questo influenzerà il tuo RNG, qualcuno che lo fa potrebbe andarsene con la tua chiave privata. C'è poco spazio per errori qui perché una piccola quantità di non casualità può compromettere un intero protocollo crittografico come la generazione di chiavi.

Sebbene i problemi con implementazioni personalizzate di generatori di numeri casuali o interferenze fisiche nel tuo hardware ingenui siano fonte di buone discussioni, la maggior parte delle vulnerabilità nelle notizie con generatori di numeri casuali, come il problema Debian che hai citato, non è dovuto a questi problemi. I problemi più grandi che ho riscontrato ripetutamente sono gli sviluppatori che pensano di avere una buona fonte di entropia per seminare il generatore di numeri casuali quando in realtà non lo fanno, consentendo erroneamente di scoprire e sfruttare lo stato del generatore casuale, o la mancanza di test rigorosi del generatore di numeri casuali stesso. L'NSA non ha bisogno di backdoor per la generazione delle chiavi se sei uno dello 0,75% dei client TLS che utilizza chiavi a bassa entropia. In sintesi, gli sviluppatori ignorano i pochi avvertimenti e presumono che il loro RNG funzionerà in qualsiasi applicazione.

Cos'è l'entropia e dove la trovo?

Poiché tutti i programmi per computer producono gli stessi output dati gli stessi input, devono essere letti da una fonte di entropia (o dati imprevedibili) nel sistema operativo o hardware. Oggigiorno abbiamo cose come il comando RdRand che può generare decine o centinaia di MB di entropia ogni secondo. Tuttavia, i dispositivi con generatori di numeri casuali hardware come Ferranti Mark 1 nel 1951 o Intel 82802 Firmware Hub nel 1999 rappresentavano l'eccezione piuttosto che la regola fino al 2010.

Quindi, i generatori di numeri storicamente casuali si basano su fonti di entropia relativamente lente come l'input umano o i tempi del computer, ei sistemi legacy potrebbero non avere quasi nessuna funzione incorporata con buone fonti di entropia disponibili. / Dev / random di Linux, ad esempio, può utilizzare l'ora di avvio, la temporizzazione dei dispositivi di input umani, le temporizzazioni del disco, le temporizzazioni IRQ e persino la modifica del pool di entropia da parte di altri thread

In molti modi generatori di numeri casuali sono fragili perché questi metodi standard per ottenere l'entropia non sono infallibili. Tutto ciò che rende queste fonti di entropia prevedibili o limitate comprometterà il tuo RNG, ad esempio:

• Il bug Debian che hai notato utilizzava solo l'ID del processo per l'entropia.
• Se si utilizza un sistema operativo headless e preconfigurato che genera chiavi all'avvio, molte delle fonti di entropia di Linux potrebbero essere prevedibili. fonte
• Java Cryptography Architecture di Android è risultato richiedere un'inizializzazione esplicita da una buona fonte di entropia su alcuni dispositivi.
• La generazione di numeri casuali troppo rapidamente in Linux esaurirà il pool di entropia più velocemente di quanto possa essere reintegrato, portando a numeri meno casuali.

Capire lo stato e la mancanza di reseeding

Spesso gli RNG non ottengono nuova entropia con ogni chiamata di funzione come fa / dev / random. A volte non puoi ottenere abbastanza entropia abbastanza velocemente, o non ti fidi completamente della fonte di entropia. Quindi, invece, l'RNG viene seminato con una fonte nota di entropia, quindi produce valori indipendenti da quel seme. Tuttavia, quando qualcuno capisce lo stato interno del generatore le cose vanno male, portando a tutto, dalla clonazione delle smart card al imbroglio di una slot machine a Las Vegas.

Un attacco di overflow del buffer o un attacco simile può rivelare lo stato del generatore di numeri casuali. L'apprendimento dello stato può anche essere possibile con un attacco di forza bruta, soprattutto se l'algoritmo è noto ed è reversibile, può essere calcolato rapidamente o è noto un testo in chiaro. Questo era il caso dei problemi con Windows XP, libreria SSH Dropbear, XorShift128 + in Chrome e algoritmo di messerne twister, tra molti altri.

La richiesta di mitigazione avanzata per questi attacchi a stati noti rende fragile l'RNG. Il modo migliore per mitigare gli attacchi a stati noti è non utilizzare un algoritmo vulnerabile (come la maggior parte dei CSRNG). Questa domanda spiega anche in modo più dettagliato esattamente cosa rende sicuro un buon RNG. Tuttavia, anche i CSRNG a volte hanno anche dei punti deboli (per esempio, la vulnerabilità RNG nel kernel Linux 2.6.10). Quindi la difesa in profondità richiede attenuazioni come l'utilizzo di stati separati per generatori di numeri casuali (forse uno per utente), l'aggiornamento frequente del seed e attraverso protezioni da attacchi di canale laterale e buffer overflow.

Passare la colpa tra sviluppatori e utenti

Spesso questi RNG sono fragili a causa della comunicazione errata delle limitazioni tra sviluppatori di librerie o creatori di sistemi operativi che non possono progettare un sistema infallibile e utenti che si aspettano uno. Linux, ad esempio, costringe gli utenti a scegliere tra alta latenza / dev / random e potenzialmente bassa entropia / dev / urandom. Come altro esempio, PHP prima della 5.3 non supportava i PRNG potenti in Windows tramite interfacce come mcrypt_create_iv () e prima della 7.0 non aveva un buon CSPRNG integrato.

Difficoltà nel rilevamento

C'è un punto di discussione popolare quando si discute di numeri casuali che, per un numero veramente casuale, ogni possibilità è ugualmente probabile e ci sono un numero infinito di schemi potenziali. Allora come puoi veramente guardare una sequenza e dire che non è casuale? (pertinente Dilbert)

In realtà, la rilevazione di pattern in numeri casuali è un campo maturo, sebbene imperfetto, e la questione se possa essere rilevata la non casualità è stata affrontata da quando M.G. L'articolo del 1938 di Kendall e B. Babington-Smith. puoi dimostrare che non è molto più probabile che appaiano tipi specifici di modelli rispetto al caso casuale. Ad esempio, posso verificare se la cifra 1 è più comune di altre cifre, con soglie determinate da un test del chi quadrato. Finché questi modelli testati sono almeno remotamente probabili e controlli un insieme sufficientemente lungo di numeri generati, le probabilità di un falso positivo sono basse. Sebbene alcuni problemi nascosti con alcuni generatori di numeri casuali possano passare inosservati per anni, se hai eseguito una crittoanalisi di base e poi applicato test di livello industriale come spiegato in questa domanda, allora non si può sbagliare.

Tuttavia, i progettisti potrebbero anche sottovalutare i loro aggressori (come si poteva prevedere che le persone effettuerebbero il reverse engineering e il tempo della tua slot machine?). Peggio ancora, a volte il generatore di numeri casuali o la generazione di entropia non vengono mai ispezionati da un esperto e viene esaminato solo il risultato dell'utilizzo dell'RNG, come quando le firme del firmware PS3 erano firmate con un output "casuale" costante.

Alla fine della giornata, il problema qui è simile a quello in gran parte della sicurezza informatica: hai un insieme molto complesso di protocolli, requisiti e dispositivi per numeri casuali. Come sempre, se non capisci la complessità, sei vulnerabile a un aggressore che lo fa.