DISCLAIMER: La ricerca effettuata nel seguente articolo è stata testata con Google Chrome e Javascript (Versione V8 11.1.277.17).

Premessa Link to heading

Siete programmatori alle prime armi, state seguendo un corso di programmazione con Javascript e la lezione parla di come generare numeri casuali. Finita la lezione, accendete il vostro pc e iniziate a scrivere un progettino che simula una lotteria. Siete sicuri che la vostra app non possa essere rotta? Siete sicuri che non ci sia un metodo per poter mandare in bancarotta la vostra lotteria?

La mia ricerca è iniziata proprio con queste domande fatte durante una chiacchierata con un collega.

Matematica e casualità Link to heading

Se hai mai frequentato un corso di Statistica e Probabilità, ti sarai sicuramente interfacciato con lo strano, ma profondamente importante, modo in cui i matematici pensano alla casualità. Una volta assimilato ciò, non potrai fare altro che rabbrividire quando sentirai parlare di numeri casuali. Ad ogni modo, se parliamo di matematica, sappiamo benissimo come i numeri non sono casuali. È questa non casualità che rende i numeri utili per contare dopotutto. Per arrivare al concetto di casualità in matematica abbiamo bisogno di far riferimento alle funzioni.

Valore casuale

Come possiamo vedere dall’immagine, abbiamo un valore esterno che viene passato ad una funzione che restituirà un valore casuale sulla base di esso. Un matematico dice che una “variabile casuale” è una funzione il cui valore dipende da uno stato del mondo mentre evolve nel tempo. Se lo stato rilevante del mondo in quel momento T è St, allora una variabile casuale può essere descritta come xt=f(St).

PRNG: Che cosa sono? Link to heading

I PRNG non sono altro che dei “Generatori di numeri Pseudo-Casuali”. Svolgono ciò di cui parlavamo prima. Prendono un valore in ingresso per dare in uscita un valore pseudo-randomico. Sia chiaro che se riesci a scrivere come si evolve nel tempo, allora la tua funzione non è casuale, quindi nemmeno tutti i PRNG implementati dal computer sono casuali. Questo perché dobbiamo preoccuparci del fatto che un PRNG sia in grado di emettere l’intero set di valori possibili. Ad esempio: se hai un PRNG a 8 bit, vuoi che sia in grado di assumere tutti i valori da 0 a 255. (Questo è il significato di “Pseudo-”.)

V8 e Math.random: Conosciamoli Link to heading

Ho fatto cenno a questi argomenti, molto vasti e più complessi di come descritti, per arrivare a rendere comprensibile la mia ricerca. Cioè, il problema di V8 con la casualità di Math.random(). Per descrivere V8, cito wikipedia:

V8 è un motore JavaScript open source sviluppato da Google, attualmente incluso in Google Chrome. V8 è scritto in C++ e supporta ECMAScript.

Funzionamento V8

Per quanto riguarda “Math.random()”, restuisce un valore in virgola mobile nel range [0,1). Mi permetto di citare le parole di MDN:

Il metodo statico Math.random() restituisce un numero pseudocasuale a virgola mobile maggiore o uguale a 0 e minore di 1, con una distribuzione approssimativamente uniforme su tale intervallo, che è quindi possibile ridimensionare all’intervallo desiderato. L’implementazione, seleziona il seme iniziale per l’algoritmo di generazione di numeri casuali che non può essere scelto o resettato dall’utente.

Se pensate a ciò che ho detto prima, riguardo ai numeri casuali, c’è una cosa che sicuramente avrete notato da questa citazione. Non ci è data la possibilità di scegliere il valore esterno da cui dipende il valore casuale in uscita. Diamo uno sguardo a tutto questo in dettaglio…

Math.random() e la sua implementazione Link to heading

Come abbiamo visto nelle parole citate da Wikipedia su V8, la sua implementazione è interamente scritta in C++. Se siete interessati a dargli un’occhiata, trovate disponibile il codice sulla sua pagina github. In particolare, in questo articolo andremo ad analizzare una parte del codice del progetto per trovare il punto debole nella generazione di numeri pseudo-casuali. Per completezza vi inserisco anche il link a quella parte di codice: Random-Number-Generator.

“Math.random()” per svolgere il suo lavoro, implementa una classe di PRNG chiamata XorShift. In particolare è stato utilizzato “XorShift128+” ideato da Saito e Matsumoto. Esso utilizza 128 bit di stato interno e ha un periodo massimo di 2^(128) - 1. Se vi interessa saperne di più, vi lascio il link ad un documento dell’Università degli Studi di Milano.

Analizziamo il codice seguente:

static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
    uint64_t s1 = *state0;
    uint64_t s0 = *state1;
    *state0 = s0;
    s1 ^= s1 << 23;
    s1 ^= s1 >> 17;
    s1 ^= s0;
    s1 ^= s0 >> 26;
    *state1 = s1;
}

Questo che vedete sopra è una parte del codice che si occupa di generare il valore pseudo-randomico in Math.random(). Come potete notare è un insieme di operazioni di xor e di shift verso destra, o sinistra. In breve abbiamo due stati: Stato0 e Stato1. Nel codice lo Stato0 assume il valore dello Stato1. Sul valore dello Stato0 verranno effettuate tutte le operazioni di xoring e shifting, per poi completare lo swap tra i due stati.

Se vi state chiedendo cosa sono i due stati, sono quei valori che non possiamo scegliere quando utilizziamo Math.random(). In buona sostanza sono il “valore esterno” a cui abbiamo fatto cenno durante il discorso della casualità. E quindi, da cosa dipendono? Dalle ricerche che sono riuscito a fare, molto probabilmente dipendono dalla piattaforma su cui è eseguita la funzione(Node.Js o Browser ad esempio) o da qualche fonte di casualità del Sistema Operativo.

Dov’è il numero in virgola mobile? Link to heading

Per i più attenti fino ad adesso, sarà sorto un dubbio. Abbiamo detto che Math.random() genera valori nel range [0,1) ma la funzione vista sopra non fa altro che restituire un valore intero senza segno a 64bit. Come lo otteniamo il nostro numero in virgola mobile? La risposta è in un’altra funzione sempre all’interno dello stesso file linkato in precedenza. Analizziamola:

static inline double ToDouble(uint64_t state0) {
    // Exponent for double values for [1.0 .. 2.0)
    static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
    uint64_t random = (state0 >> 12) | kExponentBits;
    return base::bit_cast<double>(random) - 1;
}

Questa funzione non fa altro che prendere il valore dello Stato0 e convertirlo in virgola mobile nel range [0,1). Come? Leggendo le prime due righe di codice appare evidente, soprattutto ad un ragazzo iscritto al primo anno alla facoltà di informatica, che si sta parlando dello standard IEEE 754.

=> IEEE 754 in breve Link to heading

Un numero in virgola mobile, secondo lo standard IEEE è rappresentato su WORD di 32, 64 o 128 bit divisi in tre parti:

un bit di segno s;
un campo di esponente e;
un campo di mantissa m;

Per praticità diamo uno sguardo solo alla rappresentazione dei numeri in virgola mobile su parole da 64 bit.

Rappresentazione numeri in virgola mobile

Infine ci muniamo della formula per calcolare il valore:segno*2^esponente*mantissa. La precisione è di circa 16 cifre decimali.

Questo è il metodo con cui un calcolatore riesce a rappresentare un numero con la virgola a doppia precisione.

Dopo questo breve cenno tecnico, torniamo alla nostra ricerca. Come facciamo a rompere questo algoritmo? Non dobbiamo fare tanta fatica, possiamo usare uno strumento molto utile in queste situazioni: Un SMT solver.

SMT Solver e ricerca Link to heading

Gli SMT (Satisfiability Modulo Theories) trovano spazio in vari campi della sicurezza informatica. Possiamo suddividerli in tre sottogruppi: Ricerca di bug, Generazione di exploit e Malware Analysis.

Non vedremo nel dettaglio gli SMT, ma ci basta sapere che questi strumenti funzionano e si basano su solide teorie matematiche.

Per la nostra ricerca useremo un SMT sviluppato da Microsoft: Z3.

Lo script: Z3 e Python Link to heading

Finalmente entriamo in azione! Cerchiamo di scrivere uno script che ci permetta di rompere “Math.random()” usando Z3 e Python. Prima di metterci a lavoro, cerchiamo di ricapitolare in breve ciò che ci serve per il nostro script:

Due variabili per il numero da prevedere: Stato0 e Stato1;
Una sequenza invertita di 5 numeri generati sul momento da Math.random();
Ripetere la procedura effettuata da Math.random() nella generazione dei suoi numeri in modo da poter aggiungere delle condizioni di verifica al nostro risolutore confrontando le mantisse;
Se la soddisfacibilità è verificata dal risolutore, convertire il valore dello Stato0 in double;

Iniziamo a scrivere l’exploit aggiungendo le variabili e la lista su cui lavoreremo.

import z3
import struct

risolutore = z3.Solver() # Inizializziamo un risolutore

sequenza = [][::-1] # Sequenza generata invertita -> Array.from(Array(5), Math.random)

state0, state1 = z3.BitVecs("state0 state1", 64) #Creiamo due variabili vettoriali di bit in Z3 con 64 bit per il nostro numero da predire

Adesso dobbiamo:

Eseguire l’algoritmo di XorShift128 sulle nostre variabili vettoriali (Stato0 Stato1) per ogni valore nella lista di valori random;
Impachettare l’iesimo valore della sequenza come double aggiungendo 1;
Decomprimere il valore double come un “intero senza segno a 64 bit” così da estrarre nel successivo passaggio i 52bit della mantissa dell’iesimo valore;
Infine aggiungiamo la condizione al nostro risolutore per confrontare la mantissa del numero che vogliamo prevedere e quella dell’iesimo elemento nella sequenza;

Ecco come ho sviluppato i precedenti passaggi:

for i in range(len(sequenza)):
    # Algoritmo XorShift128 sul valore che andremo a predire
    s1 = state0
    s0 = state1
    state0 = s0
    s1 ^= s1 << 23
    s1 ^= z3.LShR(s1, 17)
    s1 ^= s0
    s1 ^= z3.LShR(s0, 26)
    state1 = s1

    float_64 = struct.pack("d", sequenza[i] + 1) 
    u_long_long_64 = struct.unpack("<Q", float_64)[0] # Valore della sequenza reso come un intero senza segno a 64 bit
    mantissa = u_long_long_64 & ((1 << 52) - 1) # Recupero della mantissa dell'iesimo valore della sequenza

    # Condizione per confrontare la mantissa dell'iesimo valore e quella dello Stato0
    risolutore.add(int(mantissa) == z3.LShR(state0, 12))

Terminato il loop, chiediamo al risolutore se la soddisfacibilità è verificata. In caso di veridicità, estraiamo il valore dello Stato0 dal modello e usando lo standard IEEE 754 visto in precendenza, lo trasformiamo in un numero in virgola mobile nel range [0,1).

if risolutore.check() == z3.sat:
    model = risolutore.model()

    states = {}
    for state in model.decls():
        states[state.__str__()] = model[state]

    state0 = states["state0"].as_long()

    # Funzione ToDouble replicata
    u_long_long_64 = (state0 >> 12) | 0x3FF0000000000000
    float_64 = struct.pack("<Q", u_long_long_64)
    valore_successivo = struct.unpack("d", float_64)[0]
    valore_successivo -= 1

    print(valore_successivo)

Per quanto riguarda la conversione in double dello Stato0, ho replicato la funzione ToDouble utilizzata nell’implementazione di “Math.random()” nella parte finale dello script. Sottriamo 1 poiché normalmente verrebbe generato un numero nel range [1,2).

Salviamo questo script in un file ed eseguiamolo!

Risultato dello script

Come potete vedere, ho generato una sequenza di 5 numeri con la console disponibile in DevTools di Google Chrome, successivamente l’ho inserita nel mio script prima di eseguirlo.

Finalmente abbiamo uno script che prevede i numeri generati da “Math.random()”.

!NB: Con qualche piccola modifica è possibile generare più di un numero con una sola esecuzione dello script.

Conclusione Link to heading

Siamo alla fine dell’articolo. È stato un bel viaggio tra matematica, informatica e sicurezza del software.

Se fate una veloce ricerca, noterete come V8 abbia già avuto problemi in passato con “Math.random()”. L’algoritmo XorShift128+ è stato implementato solo alla fine del 2015. Prima di lui veniva utilizza un algoritmo chiamato MWC1616 sviluppato da George Marsaglia nel 1999.

Vi staranno sicuramente frullando tante domande in testa. E tra le tante vi starete sicuramente chiedendo se quindi esiste un metodo per generare dei numeri pseudo-casuali in modo più sicuro? Si. L’alternativa sarebbe quella di utilizzare dei “Generatori di numeri Pseudo-Casuali crittograficamente sicuri” (CSPRNG).

Vi ringrazio per essere arrivati fin qui.

Ogni parere costruttivo è molto importante per la propria crescita, se trovate dei problemi nell’articolo o informazioni errate, vi prego di contattarmi in privato in modo che io possa apprenderlo e correggerlo.

V8: Tra matematica e mentalismo

Indice Link to heading