Perché Math.random () non è progettato per essere crittograficamente sicuro?

210

La funzione JavaScript Math.random() è progettata per restituisce un singolo valore in virgola mobile n tale che 0 ≤ n < 1. È (o almeno dovrebbe essere) ampiamente noto che l'output è non crittograficamente sicuro. Le implementazioni più moderne utilizzano l'algoritmo XorShift128 + che può essere facilmente rotto . Poiché non è affatto raro che le persone di utilizzino erroneamente quando hanno bisogno di meglio casualità, perché i browser non lo sostituiscono con un CSPRNG? So che Opera lo fa *, almeno. L'unico ragionamento che potrei pensare sarebbe che XorShift128 + sia più veloce di un CSPRNG, ma su computer moderni (e anche non così moderni), sarebbe banale produrre centinaia di megabyte al secondo usando ChaCha8 o AES-CTR. Questi sono spesso abbastanza veloci che un'implementazione ben ottimizzata può essere strozzata solo dalla velocità di memoria del sistema. Anche un'implementazione non ottimizzata di ChaCha20 è estremamente veloce su tutte le architetture e ChaCha8 è più che due volte più veloce.

Capisco che non possa essere ridefinito come CSPRNG poiché lo standard non fornisce esplicitamente alcuna garanzia di idoneità per l'uso crittografico, ma sembra che non vi sia alcun svantaggio per i venditori di browser che lo fanno volontariamente. Ridurrebbe l'impatto dei bug in un gran numero di applicazioni Web senza violare lo standard (richiede solo che l'output sia round-to-close-even IEEE 754 numeri), prestazioni decrescenti o violazione della compatibilità con le applicazioni Web.

MODIFICA: alcune persone hanno sottolineato che questo potrebbe potenzialmente indurre le persone ad abusare di questa funzione, anche se lo standard dice che non si può fare affidamento su di esso per la sicurezza crittografica. Nella mia mente, ci sono due fattori opposti che determinano se utilizzare o meno un CSPRNG sarebbe un vantaggio di sicurezza netto:

  1. Falso senso di sicurezza : il numero di persone che altrimenti utilizzerebbero una funzione progettata per questo scopo, come window.crypto , decidi invece di utilizzare Math.random() perché è crittograficamente sicuro sulla piattaforma di destinazione prevista.

  2. Sicurezza opportunistica : il numero di persone che non conoscono meglio e utilizzano comunque Math.random() per le applicazioni sensibili che potrebbero essere protette dal proprio errore. Ovviamente, sarebbe meglio educarli, ma questo non è sempre possibile.

Sembra sicuro assumere che il numero di persone che sarebbero protette dai propri errori supererebbe di molto il numero di persone che sono cullate in un falso senso di sicurezza.

* Come indicato da CodesInChaos, questo non è più vero ora che Opera è basato su Chromium.

Diversi importanti browser hanno riportato segnalazioni di bug che suggeriscono di sostituire questa funzione con un'alternativa crittograficamente sicura, ma nessuna delle modifiche sicure suggerite è atterrato:

Gli argomenti per corrispondono sostanzialmente alla mia. Gli argomenti contro di essa variano da prestazioni ridotte su microbenchmark (con scarso impatto nel mondo reale) a equivoci e miti, come l'idea errata che un CSPRNG si indebolisca nel tempo quando viene generata più casualità. Alla fine, Chromium ha creato un oggetto crittografico completamente nuovo e Firefox ha sostituito il proprio RNG con l'algoritmo XorShift128 +. La funzione Math.random() rimane completamente prevedibile.

    
posta forest 15.03.2018 - 07:11
fonte

11 risposte

429

Ero uno degli implementatori di JScript e del comitato ECMA a metà degli anni '90, quindi posso fornire una prospettiva storica qui.

The JavaScript Math.random() function is designed to return a floating point value between 0 and 1. It is widely known (or at least should be) that the output is not cryptographically secure

Innanzitutto: la progettazione di molte API RNG è orribile . Il fatto che la classe Random .NET possa banalmente essere usata in modo errato in più modi per produrre sequenze lunghe dello stesso numero è terribile. Un'API in cui il modo naturale di usarlo è anche il modo sbagliato è un API "pit of failure"; vogliamo che le nostre API siano luoghi di successo, in cui il modo naturale e il modo giusto siano gli stessi.

Penso sia giusto dire che se avessimo saputo allora cosa sappiamo, l'API casuale di JS sarebbe diversa. Anche le cose semplici come cambiare il nome in "pseudocasuale" sarebbero d'aiuto, perché come si nota, in alcuni casi sono importanti i dettagli di implementazione. A livello di architettura, ci sono buone ragioni per cui vuoi random() per essere una fabbrica che restituisce un oggetto che rappresenta una sequenza casuale o pseudo-casuale, piuttosto che semplicemente numeri di ritorno. E così via. Lezioni apprese.

In secondo luogo, ricordiamo quale era lo scopo fondamentale del design di JS negli anni '90. Fai ballare la scimmia quando muovi il mouse . Abbiamo pensato agli script di espressione incorporati come di consueto, abbiamo pensato che i blocchi di script di riga da due a dieci fossero comuni e l'idea che qualcuno potesse scrivere cento righe di script su una pagina era davvero insolita. Ricordo la prima volta che ho visto un programma JS di diecimila righe e la mia prima domanda alle persone che mi chiedevano aiuto perché era così lento rispetto alla loro versione C ++ era una versione di "sei pazzo ?! 10KLOC JS ?! "

L'idea che qualcuno avrebbe avuto bisogno di criptare casualità in JS era ugualmente pazza. Hai bisogno che i tuoi movimenti di scimmia siano cripto-resistenti e imprevedibili? Improbabile.

Inoltre, ricorda che era la metà degli anni '90. Se non ci fossi, posso dirti che era un mondo molto diverso da quello attuale per quanto riguardava la crittografia ... Vedi esportazione di crittografia .

Non avrei nemmeno considerato mettere la casualità della forza di crittografia in qualcosa che è stato fornito con il browser senza ricevere un'enorme quantità di consulenza legale dal team di MSLegal. Non volevo toccare la crittografia con un palo di dieci piedi in un mondo in cui il codice di spedizione era considerato esportare munizioni ai nemici dello stato . Sembra pazzesco dal punto di vista di oggi, ma era il mondo che era .

why do browsers not replace it with a CSPRNG?

Gli autori del browser non devono fornire una ragione per NON fare una modifica. Le modifiche costano denaro e tolgono lo sforzo dai cambiamenti migliori; ogni cambiamento ha un costo opportunità enorme.

Piuttosto, devi fornire un argomento non solo per spiegare perché il cambiamento sia una buona idea, ma perché è il miglior uso possibile del loro tempo. Questo è un piccolo cambiamento per il cambio.

I understand that it could not be re-defined as a CSPRNG as the standard explicitly gives no guarantee for suitability for cryptographic use, but there seems to be no downside to doing it anyway

Il rovescio della medaglia è che gli sviluppatori sono ancora in una situazione in cui non possono sapere in modo affidabile se la loro casualità è cripto-forza o no, e possono cadere più facilmente nella trappola di affidarsi a una proprietà che è non garantito dallo standard. La modifica proposta in realtà non risolve il problema, che è un problema di progettazione.

    
risposta data 15.03.2018 - 16:10
fonte
114

Perché in realtà esiste un'alternativa crittograficamente sicura a Math.random() :

window.crypto.getRandomValues(typedArray)

Ciò consente allo sviluppatore di utilizzare lo strumento giusto per il lavoro. Se vuoi generare belle immagini o bottino gocce per il tuo gioco, usa il veloce Math.random() . Quando hai bisogno di numeri casuali protetti da crittografia, utilizza il più costoso window.crypto .

    
risposta data 15.03.2018 - 11:22
fonte
62

JavaScript (JS) è stato inventato nel 1995.

  1. Potenzialmente illegale: la crittografia era ancora sotto stretto controllo delle esportazioni nel 1995, quindi un buon CSPRNG potrebbe anche non essere legale da distribuire in un browser.
  2. Prestazioni: storicamente, i CSPRNG (generatori di numeri pseudo casuali crittograficamente sicuri) sono molto più lenti dei PRNG, quindi perché utilizzare un CSPRNG per impostazione predefinita?
  3. Nessuna mentalità sulla sicurezza: nel 1995, SSL (quello che ora conosciamo come TLS) è stato rilasciato un anno fa. L'intera idea di sicurezza, e in particolare la sicurezza del browser, non esisteva realmente.
  4. Non è necessario: nel 1995, la crittografia sicura disponibile pubblicamente era molto nuova in primo luogo; le applicazioni web non esistevano ancora perché JS era appena stato inventato; e JS è stato progettato come un linguaggio lento e interpretato per aiutare le pagine a essere dinamiche. Nessuno ha pensato che "facciamo un CSPRNG lento per impostazione predefinita per una semplice funzione casuale" era assolutamente necessario.
  5. Pochissima necessità, infatti, che non ci fosse alternativa: JS non aveva nemmeno un'API generalmente supportata per un CSPRNG fino a dicembre 2013, quindi la crittografia corretta nelle applicazioni Web era quasi impossibile fino a qualche anno fa .
  6. Consistenza: piuttosto che modificare una funzione esistente per avere un significato diverso, hanno creato una nuova funzione con un nome diverso. Puoi accedere a CSPRNG ora tramite crypto.getRandomValues .

In breve: legacy, ma anche velocità e coerenza . I PRNG non sicuri sono ancora molto più veloci perché non puoi supporre che tutto l'hardware abbia il supporto AES, né dipendere dalla disponibilità o sicurezza di RDRAND.

Personalmente, penso che sia tempo di scambiare tutte le funzioni casuali con CSPRNG e rinominare le funzioni più veloci e insicure in qualcosa come fast_insecure_random() . Dovrebbero essere necessari solo da scienziati o altre persone che fanno simulazioni che necessitano di molti numeri casuali, ma dove la prevedibilità del RNG non è un problema. Ma per una funzione con due decenni di storia, in cui esiste un'alternativa da soli quattro anni (nel 2018), posso capire perché non siamo ancora arrivati a quel punto.

    
risposta data 15.03.2018 - 12:13
fonte
19

Questo è troppo lungo per un commento.

Credo che ci sia una premessa errata nella tua domanda:

on modern (and even not so modern) computers, it would be trivial to output hundreds of megabytes per second using ChaCha8 or AES-CTR

Stai pensando a un browser desktop su una macchina collegata alla rete elettrica o un laptop con una batteria da 10Ah honky grande.

Viviamo in un mondo sempre più mobile-mobile, e mentre i dispositivi mobili in questi giorni sono abbastanza potenti hanno due importanti vincoli: il calore e la durata della batteria. A differenza di un processore desktop che può facilmente raggiungere 100C, non è possibile masterizzare la mano dall'utente dello smartphone. E le batterie del telefono in genere mantengono forse 1/3 tanto quanto un laptop (se sei fortunato). Semplicemente non ci sono buoni motivi per aggiungere la generazione di calore / il consumo di energia in più se non ne hai bisogno.

    
risposta data 15.03.2018 - 12:56
fonte
16

Il motivo più grande è che esiste un'alternativa a Math.random() : vedi la risposta di Philipp . Quindi chiunque abbia bisogno di una cripto strong può averlo, e chi non lo fa può risparmiare tempo e (batteria) potere.

Ma supponendo che tu abbia chiesto, "perché, anche se c'è un'alternativa più strong, gli sviluppatori non hanno aggiornato Math.random () lo stesso - cioè, reso random () un derivato di getRandomValues () - in ordine rafforzare automaticamente molte app là fuori? " - quindi non penso che questo sia realmente rispondibile con alcuna confidenza, tranne che da quegli sviluppatori che hanno preso la decisione (aggiornamento: e come destino avrebbe voluto, abbiamo una tale risposta ).

In linea di principio - come hai già detto - non esiste una ragione valida .

Inoltre, la maggior parte dei team di sviluppo ha un notevole arretrato di cose che sono più urgenti da fare; e anche un cambiamento apparentemente piccolo come questo richiede test, regressione e andare contro la regola " Se non è rotta, non aggiustarlo ", una forma più strong del criterio YAGNI.

    
risposta data 15.03.2018 - 08:15
fonte
14

Numeri casuali e bit crittografici sono animali completamente diversi. Non sono nemmeno usati per lo stesso scopo. Se vuoi un numero casuale distribuito equamente tra 0 e 42, allora vuoi una distribuzione uniforme senza uno schema evidente. Nota che se mod un numero maggiore con uno più piccolo, allora non è esattamente una distribuzione uniforme. Questo esempio è facile da vedere per un numero casuale da 0 a 31 preso mod 27. Da 0 a 4 vengono visualizzati due volte più spesso da 5 a 31.

Finché non parli di criptorandom, la nozione di entropia non viene nemmeno discussa. Un po 'di entropia raddoppia lo spazio di ricerca per indovinare il numero (per l'utente previsto dei numeri).

Quando chiedi bit criptorandom, stai chiedendo N bit di entropia. Non è abbastanza buono avere uno schema non ovvio, perché se viene scoperta una funzione che la genera (non importa quanto complicata), allora ci sono in realtà 0 bit di entropia dal punto di vista di chiunque conosca questa funzione.

Un buon esempio di questo è un generatore di numeri pseudo-casuali tipo Fortuna. Si cripta un numero 1 con una chiave per il primo numero casuale (in cui il blocco di cifratura è un numero grande), quindi si cripta il numero 2 con una chiave per il secondo numero casuale e così via. Per quanto riguarda l'utente che non conosce la chiave (di bit K) per il cifrario, un blocco di cifratura a N bit perfetto avrà N bit di entropia per quel blocco.

Se espandi ad un milione di bit di dati pseudo-casuali da esso, allora hai ancora solo K bit di entropia se continui con la stessa chiave K. In altre parole: se tu avessi un libro di 1 milione i bit che conosci sono stati generati con un singolo cifrario sotto K, quindi non cercare di indovinare tutti i bit del flusso di cifratura. Basta limitarsi a indovinare la chiave e generare il flusso di crittografia da esso.

Quindi un generatore di numeri casuali è spesso un codice che continua a essere seminato con più casualità, in quanto può essere raggiunto. Per confronto, un semplice generatore di numeri casuali [0,1] non può avere più entropia del numero di bit nel numero; e in genere avrà una distribuzione dispari che non è esattamente quello che vuoi. Crypto ha bisogno di centinaia di bit, quando i numeri in virgola mobile sono solo a 32 o 64 bit, e l'algoritmo stesso toglie gran parte dell'entropia .... presumendo che tu voglia qualcosa di uniformemente distribuito da [0..1], piuttosto che dire un rappresentazione in virgola mobile fatta di bit casuali. Non so nemmeno quale distribuzione avrebbe avuto.

    
risposta data 16.03.2018 - 04:29
fonte
8

Hai tipo di rispondere alla domanda da solo:

the standard explicitly gives no guarantee for suitability for cryptographic use

Quindi, piuttosto che modificare l'implementazione, l'attenzione dovrebbe essere rivolta a educare gli sviluppatori a scegliere lo "strumento giusto per il lavoro" ™.

Dato questo, e il sovraccarico tecnico di alterare l'implementazione di una funzione comunemente utilizzata, così come il fatto che ci sono già soluzioni specifiche a questo problema (vedere la risposta di @Philipps), non vi è alcun motivo convincente per apportare la modifica.

    
risposta data 15.03.2018 - 12:39
fonte
5

La programmazione del linguaggio di programmazione deve considerare molte cose. I browser sono molto potenti e ottimizzano javascript molto oggi. Ma quando consideri i sistemi embedded, potresti non avere alcuna buona fonte di casualità. Ad esempio ci sono microcontrollori che eseguono un ambiente nodeJ (simile).

Un tale microcontrollore non ha fonti casuali che garantiscono numeri casuali crittograficamente sicuri. Quindi è necessario richiedere il collegamento di un dispositivo che può fornire un input casuale a un pin per essere in grado di implementare un linguaggio di programmazione che fornisce forti garanzie sui numeri casuali. E avresti bisogno di un po 'di conoscenza per costruire un dispositivo che fornisca abbastanza casualità e per elaborare l'input dal dispositivo in modo appropriato.

    
risposta data 15.03.2018 - 11:10
fonte
5

Come gli altri, vorrei sottolineare che Math.random() non è crittograficamente sicuro perché in genere non è necessario. Ma andrei oltre e sostengo che non è saggio scrivere un algoritmo crittograficamente sicuro in una specifica a meno che non si abbia una buona ragione.

Che cosa significa essere crittograficamente sicuro? Bene, c'è sempre la noiosa definizione di "nessuno sa come rompere ancora". Ma cosa succede quando qualcuno lo infrange? Se hai specificato un CSPRNG, devi anche includere un modo per interrogare quale algoritmo è in uso, o altrimenti farlo in modo che l'utente finale possa essere certo di ciò che sta ottenendo.

Questo probabilmente porta anche alla necessità di essere in grado di supportare più generatori, in modo che l'utente possa selezionare quello di cui si fida. Ciò aggiunge enorme complessità. All'improvviso una funzione a 1 riga in un'API è diventata una suite.

Inoltre, quando inizi a parlare di crypto, inizi a parlare di cercare di essere sicuro nel generatore. Hai menzionato l'utilizzo di AES per generare numeri casuali: la tua implementazione AES deve essere immune agli attacchi dei canali laterali? Quando si scrive una biblioteca con lo scopo specifico di fornire garanzie crittografiche, non è del tutto irragionevole dover fare quella domanda. Per una specifica, potrebbe essere terribilmente irragionevole. L'immunità agli attacchi dei canali laterali è una cosa difficile da descrivere molto nel linguaggio delle specifiche.

E che cosa hai ottenuto inserendolo in una specifica? La maggior parte degli utenti di PRNG non ha bisogno di garanzie crittografiche, quindi è sufficiente sprecare cicli di CPU per loro. Coloro che vogliono garanzie crittografiche cercheranno probabilmente una libreria che supporti la suite completa di funzionalità necessarie per essere a proprio agio con tale crittografia, quindi non si fidano di Math.random() comunque. Tutto ciò che rimane sono i dati demografici che hai citato: persone che hanno commesso un errore e hanno usato uno strumento quando non dovrebbero farlo. Bene, posso dirti dall'esperienza, i principali linguaggi di programmazione sono non un luogo in cui cercare un'API che non puoi usare in modo errato per errore. Sono pieni di frasi "se lo fai, è colpa tua".

Inoltre, considera questo: se si utilizza Math.random() e si assumono garanzie crittografiche, quali sono le probabilità che si possa commettere un errore crittografico fatale da qualche parte nell'algoritmo? Un CSPRNG% diMath.random() può fornire un falso senso di sicurezza e potremmo trovare ancora più errori!

    
risposta data 16.03.2018 - 23:04
fonte
3

Tutti sembrano aver perso un po 'di sfumature qui: gli algoritmi crittografici richiedono che un numero sia matematicamente e statisticamente casuale su tutte le esecuzioni dell'algoritmo. Ciò significa, ad esempio, durante un gioco o un'animazione, che potresti usare una sequenza di numeri in psuedorandom e questo sarebbe perfetto per un "tipo di numero casuale".

Tuttavia, se questo numero può essere manipolato o previsto, ad esempio un numero casuale seminato (che è il comportamento predefinito delle funzioni casuali di Windows), allora questo seme è effettivamente prevedibile. Se riesco a manipolare la tua applicazione per riavviarla e quindi utilizzare un numero casuale con seme, posso prevedere quale numero "casuale" sceglierai. Se questo è possibile, allora la crittografia può essere sconfitta. Una preoccupazione secondaria può anche essere che alcuni algoritmi richiedono una distribuzione garantita di numeri attraverso lo spettro, che alcuni generatori psuedorandom non possono garantire.

I generatori di numeri casuali crittograficamente dispongono di un ampio set di input per creare entropia, ad esempio misurazione del rumore del colpo dall'ingresso del microfono, tick del giorno del giorno, checksum dei registri di ram, numeri seriali ecc. Quanti più ingressi possibili per renderlo se non impossibile, quindi incredibilmente difficile da manipolare e prevedere. In senso crittografico, la performance non è l'obiettivo, ma la "vera" casualità.

Quindi, a seconda del tuo caso d'uso, potresti volere un'implementazione ragionevolmente casuale e performante di un numero casuale, ma se stai facendo uno scambio di chiavi diffie-hellman hai bisogno di un algoritmo crittograficamente sicuro.

    
risposta data 22.03.2018 - 14:51
fonte
-1

Un'altra considerazione che non ho visto menzionare a nessuno (o che ho appena trascurato) è che alcuni usi della funzione Math.random() dipendono effettivamente dalla ripetibilità al momento del seeding come se fosse una volta precedente. Cambiarlo ora interromperà quegli usi.

    
risposta data 24.03.2018 - 00:02
fonte

Leggi altre domande sui tag