it-swarm-eu.dev

Cosa rende i generatori di numeri casuali così fragili?

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

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

e non devi essere così sofisticato da indebolire un generatore di numeri casuali. Questi generatori sono già sorprendentemente fragili ed è terribilmente difficile rilevare quando si è rotti. I manutentori di Debian hanno chiarito questo punto 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 sta indebolendo l'RNG - qualsiasi idiota con una tastiera può farlo - lo sta facendo senza rendere l'implementazione banalmente vulnerabile a tutti gli altri.

Mi mancano sicuramente alcuni dettagli critici su come la generazione casuale di numeri sia "fragile". Qualcuno può spiegare?

71
john doe

RNG hardware vs software

La prima cosa che citi è 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 polarizzato al contrario, con oscillatori ad anello, con un ADC o persino con un contatore Geiger. Si può anche fare la mia misurazione dei ritardi a livello di nanosecondi nei tempi tra i tasti premuti. Queste fonti di rumore possono fallire se l'hardware stesso inizia a guastarsi. Ad esempio, un transistor può guastarsi se non è progettato specificamente per funzionare al contrario ad alta tensione. Mentre queste tecniche hanno vari livelli di fragilità, non è ciò che viene discusso nel testo che hai citato.

Il secondo tipo di RNG menzionato è un RNG software chiamato generatore di numeri pseudocasuali (PRNG*). Questo è un algoritmo che accetta 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 divulgati a parte la pura casualità, senza la conoscenza del seme casuale segreto con cui è iniziato l'algoritmo. In questo caso, il PRNG è implementato nel software puro, quindi la sua rottura richiede solo l'introduzione di un bug nel codice, che è ciò di cui parla il testo che hai citato. È semplicemente il codice che è fragile, rischiando il completo fallimento se vengono apportate modifiche al codice che si discostano dal comportamento previsto dell'algoritmo.

A PRNG può essere pensato come un algoritmo di crittografia riproposto. In effetti, è possibile creare un crittograficamente sicuro PRNG utilizzando un codice come AES per crittografare un contatore. Fintanto che 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 può una piccola modifica non significativa del codice rompere completamente la sicurezza dell'algoritmo.

Collezionando 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 fonte di rumore hardware dedicata, la casualità deve provenire dall'interno. I computer si sforzano di essere completamente deterministici, ma hanno un sacco di input da dispositivi non deterministici. Enter ... interrompe!

Nell'hardware moderno, un interruzione è un segnale emesso dall'hardware per avvisare la CPU di un cambio di stato. Permette alla CPU di evitare il polling rapido di tutti i dispositivi 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 interrupt handler per elaborare il segnale. Si scopre che questo gestore è il posto perfetto per ottenere casualità! Quando si misura la tempistica degli interrupt a livello di nanosecondi, è possibile ottenere rapidamente un bel po 'di casualità. Questo perché gli interrupt vengono attivati ​​per ogni sorta di cose, dai pacchetti che arrivano sul NIC ai dati letti da un disco rigido. Alcune di queste fonti di interruzione sono altamente non deterministiche, come un disco rigido azionamento che si basa sul movimento fisico di un attuatore.

Una volta che sono stati raccolti sufficienti bit casuali dal sistema operativo, un piccolo seme di almeno 128 bit può essere inserito in un crittograficamente sicuro PRNG per generare un flusso illimitato di dati pseudocasuali. A meno che qualcuno non possa prevedere esattamente quando si sono verificati tutti gli interrupt passati, con precisione dei nanosecondi, non saranno in grado di derivare il seme e non saranno in grado di prevedere il futuro PRNG. Ciò rende l'output completamente adatto alle chiavi TLS.

* Un orientato alla sicurezza PRNG è chiamato PRNG crittograficamente sicuro o CSPRNG. L'uso di un normale PRNG quando un'applicazione richiede un CSPRNG può provocare sicurezza vulnerabilità.

75
forest

Storicamente, gli RNG hardware adatti per la crittografia non erano comunemente disponibili sul PC: ad esempio secondo questa domanda AMD ha aggiunto il supporto solo pochi anni fa, quindi anche oggi un fornitore di software non può semplicemente supporre che sarà disponibile. Questo è presumibilmente il motivo per cui OpenSSL (come discusso nella tua citazione) stava usando 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 lo conosco terribilmente - ma ovviamente in quello lo scenario di un bug nel software può comportare numeri casuali errati, come effettivamente accaduto.)

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

Va anche detto che i RNG hardware non sono così semplici da implementare come suggerisce la tua domanda ... 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 ultrasuono ad esso? Anche in condizioni ideali, è probabile che ci sia una sorta di distorsione 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 elaboralo crittograficamente . Ma a quel punto sei tornato alla domanda se l'algoritmo (o la sua implementazione) è stato deliberatamente sabotato, o forse non è così robusto come si credeva.

17
Harry Johnston

Perché sono difficili da testare

Mentre è facile testare che un generatore di numeri casuali produce output con il formato giusto, determinare se è statisticamente casuale è molto più coinvolto e probabilmente non verrà incluso in una suite di test automatizzata. Un sacco di altro codice sarà molto più ovvio se lo rompi.

Crypto deve avere ragione

In generale, assicurarsi che il codice sia corretto è difficile. Una grazia salvifica per un sacco di codice è che solo una piccola parte degli errori di correttezza comporta vulnerabilità della sicurezza. Ma con il codice crittografico - inclusi i generatori di numeri casuali - molti errori di correttezza comporteranno vulnerabilità. Il codice crittografico deve essere corretto, sicuro e assicurarsi che sia corretto è difficile.

Il manutentore Debian ha commesso un errore grave

Il codice non è in realtà così fragile. Per essere reso insicuro, sono stati richiesti importanti guasti dal manutentore. Solo chop out righe che generano avvisi con solo controlli superficiali che non hanno interrotto nulla, è piuttosto scadente.

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

12
paj28

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

Ad esempio, se un avversario con un trasmettitore altamente focalizzato RF aveva la capacità di influenzare il tuo generatore di numeri casuali in modo che alcuni campioni di sua scelta avrebbero una probabilità del 95% di cederli, mentre il resto avrebbe solo una probabilità del 5% di farlo. Se uno dovesse semplicemente leggere 128 bit da un tale generatore e inserirli in una chiave a 128 bit, un attaccante che focalizzava un attacco di forza bruta su schemi di bit vicini a quello usato per influenzare il generatore avrebbe una probabilità molto maggiore di rapido successo che se il generatore fosse stato imparziale. Supponiamo, tuttavia, che invece di selezionare i bit uno alla volta, uno abbia selezionato gruppi di 7 bit e li abbia uniti insieme Ciò aumenterebbe di sette volte il tempo necessario per generare una chiave a 128 bit, ma l'influenza di un attaccante sarebbe ridotta da 95/5 a 74/26, riducendo notevolmente la probabilità che la chiave finisse per essere vicina al modello di bit dell'attaccante stava cercando di forzare.

In alternativa, supponiamo che si debbano generare 128 bit casuali, li hash in qualche modo e quindi li xor con altri 128 bit casuali. Ciò richiederebbe solo la generazione di 256 bit anziché 896, ma renderebbe molto difficile per un utente malintenzionato sfruttare qualsiasi distorsione nel generatore. Anche se l'enumerazione dei pattern più probabili a 95.000.000.000.000 di bit a 128 bit avrebbe circa il 50% di probabilità di abbinare un gruppo di 128 bit usato prima dell'hash, o quello con cui il valore di hash è stato xor, la distribuzione finale dopo lo xor sarebbe improbabile che ci siano sfruttabili distorsioni o perdite di informazioni.

4
supercat

Gli RNG sicuri comunemente usati come Linux/dev/random, ChaCha20 o RdRand funzionano bene per molti casi convenzionali. Tuttavia, sono tutt'altro che a prova di idiota. Supponi di fare qualcosa di divertente come non riuscire a impostare l'orologio in tempo reale durante la generazione di numeri casuali all'avvio. Se non capisci come ciò influirà sul tuo RNG, qualcuno che lo fa potrebbe uscire con la tua chiave privata. C'è poco spazio per l'errore qui perché una piccola quantità di non casualità può compromettere un intero protocollo crittografico come la generazione di chiavi.

Mentre i problemi con ingenui implementazioni roll-your-own di generatori di numeri casuali o interferenze fisiche nel tuo hardware rendono buone discussioni, la maggior parte delle vulnerabilità nelle notizie con generatori di numeri casuali, come il problema Debian che hai menzionato, sono non a causa di questi problemi. I maggiori problemi 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. Il NSA non ha bisogno di backdoor la tua generazione di chiavi se sei uno di ,75% dei client TLS usando chiavi a bassa entropia. In sintesi, gli sviluppatori ignorano il pochi, se del caso, avvertono e ritengono che il loro RNG funzionerà in qualsiasi applicazione.

Cos'è l'entropia e dove ne trovo?

Poiché tutti i programmi per computer producono gli stessi output con gli stessi input, devono leggere da una fonte di entropia (o dati imprevedibili) nel sistema operativo o nell'hardware. Oggi 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 erano l'eccezione piuttosto che la regola fino al 2010.

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

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

  • Il bug Debian che hai notato utilizzava solo l'ID processo per l'entropia.
  • Se si utilizza un sistema operativo senza testa e preconfigurato che genera chiavi all'avvio, molte fonti di entropia di Linux potrebbero essere prevedibili. fonte
  • Android Java Cryptography Architecture è stato trovato che richiede l'inizializzazione esplicita da una buona fonte di entropia su alcuni dispositivi.
  • Generare numeri casuali troppo rapidamente in Linux esaurisce il pool di entropia più velocemente di quanto possa essere rifornito, 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/dev/random. A volte non riesci a 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 da clonare le smart card a imbrogliare 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 a forza bruta, specialmente se l'algoritmo è noto ed è reversibile, può essere calcolato rapidamente o è noto un testo in chiaro. Questo è stato il caso di problemi con Windows XP , libreria Dropbear SSH , XorShift128 + in Chrome e algoritmo twister di Messerne =, tra molti altri.

Richiedere una mitigazione avanzata per questi attacchi di stato noto rende l'RNG fragile. Il modo migliore per mitigare gli attacchi allo stato noto è di non utilizzare un algoritmo vulnerabile (come la maggior parte CSRNG ). Questa domanda spiega anche in modo più dettagliato esattamente cosa rende sicuro un buon RNG. Tuttavia, anche i CSRNG a volte presentano anche dei punti deboli (ad esempio la vulnerabilità RNG nel kernel Linux 2.6.1 ). Quindi la difesa in profondità richiede mitigazioni come l'uso di stati separati per generatori di numeri casuali (forse uno per utente), l'aggiornamento frequente del seme e attraverso le protezioni dagli attacchi dei canali laterali e dagli overflow del buffer.

Passando la colpa tra sviluppatori e utenti

Spesso questi RNG sono fragili a causa della comunicazione errata delle limitazioni tra gli sviluppatori di librerie o i creatori di sistemi operativi che non sono in grado di progettare un sistema infallibile e gli utenti che se ne aspettano uno. Linux, ad esempio, obbliga gli utenti a scegliere tra alta latenza/dev/random e potenzialmente bassa entropia/dev/urandom. Come altro esempio, PHP prima della 5.3 non aveva supporto per PRNG forti in Windows attraverso 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 c'è un numero infinito di potenziali modelli. Quindi, come puoi davvero guardare una sequenza e dire che non è casuale? (Dilbert pertinente )

In realtà, la rilevazione di schemi in numeri casuali è un campo maturo, sebbene imperfetto, e la questione se sia possibile rilevare la non casualità è stata affrontata da M.G. Il documento di Kendall e B. Babington-Smith del 1938. puoi dimostrare che specifici tipi di pattern non hanno una probabilità significativamente maggiore di apparire rispetto al caso casuale. Ad esempio, posso verificare se la cifra 1 è più comune rispetto ad altre cifre, con soglie determinate da un test chi-quadrato. Finché questi modelli testati sono almeno in remoto probabili e si controlla un insieme abbastanza lungo di numeri generati, le probabilità di un falso positivo sono basse. Mentre alcuni problemi nascosti con alcuni generatori di numeri casuali possono rimanere inosservati per anni , se hai eseguito la crittoanalisi di base e quindi applica i test di livello industriale come descritto in questa domanda allora non posso sbagliare troppo.

Tuttavia, i progettisti potrebbero anche sottovalutare i loro aggressori (come avresti dovuto prevedere le persone avrebbe decodificato e cronometrato la tua slot machine? ). Peggio ancora, a volte il generatore di numeri casuali o la generazione di entropia non vengono mai controllati da un esperto e viene esaminato solo il risultato dell'uso del 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 della maggior parte della sicurezza informatica: hai un set 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.

1
Cody P