Crittografia: ruolo e validazione dei generatori di numeri casuali

Nel mondo della crittografia e non solo, il concetto di generazione di numeri casuali è sempre stato un tema molto discusso e di rilievo. Le motivazioni dietro alla centralità si questo tema nel mondo IT nascono dalla difficoltà implementativa della realizzazione di un generatore di numeri casuali.

La sfida è infatti quella di sviluppare un generatore che sia in grado di avvicinarsi il più possibile alla “randomicità perfetta”. Vale a dire che i numeri che esso genera devono essere il più possibile imprevedibili e uniformemente distribuiti all’interno dello spazio di valori che questi possono assumere.

Applicazioni e importanza dei generatori di numeri casuali nella crittografia

Naturalmente, le proprietà statistiche di un generatore di numeri casuali diventano tanto più importanti quanto più importante è il ruolo che esso deve ricoprire. Un generatore utilizzato a scopo didattico, per esempio, può non avere proprietà statistiche eccelse ma sufficienti a svolgere i compiti che gli sono attribuiti. Un secondo generatore che deve essere utilizzato per simulazioni di processi stocastici, invece, dovrà avere proprietà statistiche molto più robuste affinché le simulazioni siano quanto più attendibili possibile.

Un campo in cui le proprietà richieste ad un generatore sono le massime possibili è proprio la crittografia. Esso viene utilizzato da un algoritmo crittografico per la generazione delle chiavi e dei segreti di cui l’algoritmo ha bisogno per operare. Per tale motivo, dalla bontà delle proprietà statistiche dei numeri che esso genera dipende direttamente la sicurezza dell’algoritmo crittografico stesso.

Sorgenti di entropia

Il coefficiente che viene utilizzato solitamente per misurare l’imprevedibilità degli output forniti da un generatore viene chiamato entropia. Nel campo dell’informatica, essa si misura in bit di entropia per bit di output.

In un mondo ideale, per un utilizzo crittografico, vorremmo che un generatore sia in grado di fornire un bit di entropia per bit di output prodotto (che fornisca quindi entropia piena). Raggiungere tale obiettivo però non è così banale quando si deve tenere in considerazione anche il fattore di consumo di risorse.

Generazione fisica e software

Per ottenere valori casuali bisogna infatti partire dal campionamento di processi (principalmente fisici) che presentano comportamenti naturalmente randomici. Per fare un esempio, il generatore di numeri casuali normalmente utilizzato dal sistema operativo Linux (/dev/random o /dev/urandom) è basato sul campionamento di segnali derivanti da processi fisici che sono in esecuzione nell’hardware del PC (interrupt di sistema, tempi di accesso alle cache, movimenti del mouse, etc.). Tutte queste sorgenti sono campionate a specifici intervalli di tempo e i valori raccolti sono poi rielaborati e correlati per produrre una stringa di bit in output.

Oltre al campionamento di processi fisici, negli ultimi anni sono state sviluppate anche sorgenti di entropia puramente software che non sfruttano il concetto di campionamento ma bensì la complessità degli odierni calcolatori. Un esempio di questo tipo di sorgente è il CPU Time Jitter RNG [1], il quale si basa sull’utilizzo dei timestamp ad alta precisione dei processori odierni.

Questa sorgente di entropia misura i tempi di esecuzione di uno specifico numero di operazioni tramite un delta tra un timestamp preso prima e uno preso dopo l’esecuzione di tale sequenza. Questo delta non sarà mai uguale tra un’esecuzione e l’altra a causa della complessità del calcolatore stesso, il quale dovrà eseguire numerosi accessi a cache e altre memorie per portare a termine la sequenza di operazioni richiesta. Questa variazione nei tempi di esecuzione (anche detta Jitter) viene utilizzata come sorgente di entropia unica di quest’implementazione.

Limiti delle sorgenti di entropia

Il CPU Time Jitter RNG e altre implementazioni similari danno un’alternativa ai classici metodi di campionamento ma rimane comunque poco efficiente a livello di risorse per farne un utilizzo massivo, visto il numero di operazioni complesse richieste al calcolatore per generare la quantità di bit necessaria in output al chiamante.

Per tale motivo, se si fa un utilizzo costante di questo tipo di sorgenti, queste possono divenire “stuck”. Il significato di questo stato è che la quantità di entropia disponibile nella pool della sorgente non è sufficiente a soddisfare le richieste di tutti in processi in coda. Essi saranno quindi costretti ad aspettare che nuovi valori vengano aggiunti alla pool per poterne usufruire.

Questo comporta che un HRNG (Hardware Random Number Generator) o TRNG (True Random Number Generator) come quelli appena descritti non può soddisfare in maniera efficiente, a livello di risorse, tutte le richieste che probabilmente gli arriveranno.

Pseudo-Random Number Generators (PRNGs)

Per ovviare a questo problema, quello che si fa nella pratica è utilizzare i PRNG (Pseudo-Random Number Generators) che, come il nome evidenzia, producono output pseudo-randomici. Tali generatori prendono in input da una sorgente come quelle descritte in precedenza solo una limitata stringa di bit che verrà utilizzata per “instanziare” il PRNG, ovvero inizializzare il suo stato interno. Questa stringa iniziale prende il nome di seed.

Meccanismo deterministico

Da questo punto in poi, il PRNG utilizzerà un meccanismo totalmente deterministico per generare gli output pseudo-randomici che saranno poi forniti ai processi che ne fanno richiesta.

È chiaro quindi come la sicurezza di questo tipo di meccanismi risieda principalmente nella segretezza del seed iniziale e del suo internal state ad ogni preciso istante. Visto che questi seguono un processo totalmente deterministico nella generazione dei numeri, la conoscenza dell’internal state o del seed iniziale permetterebbe ad un potenziale attaccante di determinare automaticamente tutta la sequenza di output generati da un PRNG fino a quando un nuovo reseeding non avviene.

Questo meccanismo però permette al contempo di generare una serie di output pseudo-randomici a partire da un unico input effettivamente randomico (il seed) in modo deterministico e quindi estremamente efficiente.

L’utilizzo della sorgente di entropia effettiva sarà infatti limitato alle richieste degli input utilizzati dal PRNG come seed iniziale e per il reseeding periodico. Quest’ultimo deve avvenire a intervalli precisi in modo da evitare che il meccanismo deterministico cominci a ripetere output già prodotti o cominci ad esaurire lo spazio di valori che i suoi output possono assumere.

Se pensiamo ad un meccanismo deterministico che, a partire da un seed randomico, produce output di 64 bits, il possibile spazio di valori che questo può produrre sarà 2⁶⁴. Dopo un certo numero di output, esso inizierà a produrre output già visti e a ripassare per la stessa sequenza di stati interni, finendo così in un loop. Questo accadrà alla prima ripetizione di un internal state già visto. Per evitare che questo accada, il PRNG deve periodicamente effettuare un reseeding, ottenendo un nuovo input dalla sorgente di entropia.

La sicurezza e la struttura di un PRNG

Il concetto di PRNG risolve quindi, a livello pratico, il problema di produrre randomicità in modo efficiente. Tuttavia, non tutti i PRNG sono uguali e forniscono le stesse garanzie di sicurezza.

Quello che si fa per quantificare la “bontà” di un’implementazione di un PRNG è effettuare una serie di analisi statistiche su un campione di output abbastanza ampio.

Al termine di queste analisi, ad uno specifico algoritmo che implementa un PRNG viene assegnato un valore di security strength, che viene definita come:

“La quantità di lavoro necessaria per rompere un algoritmo o un sistema in qualunque modo” – NIST SP 800-90Ar1, section 4

Questa quantità si misura in bit. Ad esempio, se un algoritmo ha una security strength di 64 bit, il numero di operazioni mediamente necessarie per rompere tale algoritmo è di 2⁶⁴.

Nel caso dei PRNG, la security strength rappresenta il numero di operazioni necessarie per indovinare un valore di output prodotto da quest’ultimo.

In un applicazione crittografica, solitamente si necessita di un PRNG che sia in grado di supportare una security strength sufficiente da garantire la sicurezza delle chiavi e dei segreti generati. Esempio, se devo generare una chiave di 128 bit, ho bisogno di un PRNG che mi garantisca una security strength di almeno 128 bit nei sui output.

Il meccanismo DRBG (Deterministic Random Bit Generator)

Lo standard crittografico di riferimento per questo tipo di algoritmi è la NIST SP 800-90Arev1. Questo standard definisce una serie di meccanismi che, sfruttando una sorgente di entropia e un algoritmo crittografico deterministico, sono in grado di produrre output pseudo-randomici che supportino una security strength che va dai 128 fino ai 256 bit. Il nome di questi meccanismi è DRBG o Deterministic Random Bit Generator.

Questi meccanismi utilizzano funzioni crittografiche ben conosciute come Hash functions (e.g., SHA-1, SHA-256, SHA-512, etc.), l’algoritmo HMAC per la generazione di message authentication codes oppure un block cipher come l’agoritmo a chiave simmetrica AES in modalità counter.

Il cuore di un DRBG è il suo internal state, costituito da due o più valori che sono derivati direttamente dal seed fornito da una sorgente di entropia al momento dell’istanziazione del DRBG stesso. I valori di questo internal state vengono poi utilizzati dagli algoritmi deterministici (AES, SHA, o HMAC) per “generare” output pseudo-randomici che vengono restituiti al chiamante. L’internal state è mantenuto costantemente aggiornato dal DRBG stesso man mano che nuovi output vengono generati, tramite un processo deterministico chiamato update. Questo permetterà al DRBG di generare valori diversi in output alla prossima chiamata.

Da notare però come anche questo processo è deterministico e, per tale ragione, un DRBG necessita di un ulteriore processo che introduca elementi non deterministici per poter continuare ad operare in maniera imprevedibile. Tale processo prende il nome di reseeding e si caratterizza nell’ottenere periodicamente un nuovo seed dalla sorgente di entropia utilizzato poi per aggiornare nuovamente l’internal state del DRBG.

Il periodo massimo che può trascorrere tra due seeding del DRBG è definito direttamente dalla SP 800-90Arev1 per ognuno dei meccanismi che questa definisce.

La validazione di un RNG

Ora che abbiamo descritto in generale la struttura di un RNG, possiamo capire quanto sia importante che, in un contesto di sicurezza, questi algoritmi vengano validati per assicurarsi che le loro performance siano adeguate all’utilizzo che se ne deve fare.

Uno dei processi più strutturati di validazione dei random number generator utilizzati dai moduli crittografici è portato avanti all’interno delle validazioni del CMVP (Cryptographic Module Validation Program), effettuate secondo I requisiti dello standard FIPS 140-3.

Ad ogni modulo che viene validato secondo questo standard, viene richiesto che utilizzi un generatore di numeri casuali approvato e validato da un laboratorio di validazione.

Validazione della sorgente di entropia

La validazione di un generatore di numeri casuali secondo lo standard FIPS si divide in due parti: la validazione della sorgente di entropia sulla quale questo si basa e la validazione della componente deterministica che, solitamente, il modulo crittografico stesso implementa.

Come abbiamo detto in precedenza, la sorgente di entropia è la parte effettivamente non determinista di un generatore di numeri casuali (quello che prima abbiamo definito come TRNG). Il programma che si occupa della validazione di queste sorgenti si chiama ESV (Entropy Source Validation) program. Questa validazione avviene seguendo i requisiti della SP 800-90B pubblicata dal NIST e che descrive le proprietà costitutive e statistiche che una sorgente di entropia deve soddisfare per essere considerata approvata.

Nella pratica, tramite l’utilizzo di tool appositi, la sorgente di entropia viene testata su tutti gli ambienti operativi (anche detti operational environments) dove il modulo crittografico che la utilizza andrà ad essere utilizzato una volta certificato. Il testing prevede la raccolta di grandi quantità di output presi direttamente dalla sorgente di entropia e chiamati samples. Le proprietà statistiche di questi samples vengono poi analizzate per ottenere una stima della quantità di bit di entropia per bit di output che la sorgente è in grado di generare.

Al termine di questo processo di testing, la sorgente riceve un certificato ESV dove viene riportata la quantità di bit di entropia per bit di output che essa è in grado di produrre all’interno degli operational environments dove è stata testata.

Validazione della parte deterministica del generatore

Il secondo step della validazione di un generatore di numeri casuali si occupa invece di validare la parte deterministica del generatore. L’unico modello deterministico approvato secondo lo standards FIPS 140-3 è quello del DRBG di cui abbiamo parlato in precedenza. La SP di riferimento è quindi la NIST SP 800-90Arev1 che definisce come un DRBG debba essere implementato e i requisiti che questo deve rispettare.

La validazione quindi prevede prima di tutto una code review dell’implemetazione del DRBG all’interno del modulo crittografico volta a verificare che il design sia conforme a tutti i requisiti dettati dalla SP menzionata in precedenza.

Successivamente, il laboratorio sviluppa un functional test volto a testare i limiti esecutivi dell’implementazione del DRBG stesso e altri requisiti come la segretezza dell’internal state del DRBG o la cancellazione di valori sensibili quando questi non sono più utilizzati imposti dallo standard FIPS stesso.

Infine, il DRBG è sottoposto ad una serie di KAT (Known Answer Test), sviluppati tramite il programma CAVP (Cryptographic Algorithm Validation). Qui, tramite l’utlizzo di un server preposto, vengono generati una serie di vettori di input che vengono poi eseguiti su tutti gli operational environments del modulo crittografico. Il risultato dell’esecuzione di questi vettori è una serie di output che viene rimandata al server CAVP. Quest’ultimo si occupa poi di validare questi risultati per verificare che l’algoritmo (nel nostro caso il DRBG) abbia prodotto i risultati attesti. Alla fine di questo ultimo processo, l’implementazione del DRBG in questione riceve un certificato CAVP che attesta il suo corretto funzionamento all’interno degli operational environments dove è stata testata.

Certificazioni e testing

Mettendo quindi insieme una sorgente di entropia validata che ha ottenuto un certificato ESV e un’implemetazione di DRBG validata che ha ottenuto un certificato CAVP, si ottiene un generatore di numeri casuali completo e approvato per l’utilizzo all’interno di un modulo crittografico certificato FIPS 140-3.

Focus sull’operational environment

Bisogna porre particolare attenzione alla questione operational environment. I certificati ottenuti da una sorgente di entropia e da un’implementazione di DRBG sono validi SOLO se questi sono utilizzati all’interno degli operational environments elencati nei certificati stessi. Per operational environments si intende la combinazione di hardware, firmware e/o software dove un modulo crittografico è in esecuzione.

Se un operational environment cambia o è assente dal certificato, lo specifico algoritmo non è considerato come validato all’interno di quell’operational environement. Per poter essere utilizzato, dovrà quindi essere testato e validato sul nuovo operational environment in questione. Questo rende l’idea su quanto stringente sia la validazione degli algoritmi crittografici all’interno dello standard FIPS 140-3.

Conclusioni

Il livello di attenzione che si pone in standard come il FIPS sulla validazione dei generatori di numeri casuali evidenzia ancora di più l’importanza del ruolo che questi ricoprono in un contesto crittografico e di sicurezza informatica. Perciò questo pone un accento sul bisogno di utilizzare, in campo di sicurezza, prodotti che siano sempre stati testati e certificati.

Al contempo, sviluppare un implementazione che sia in grado di soddisfare i requisiti necessari per soddisfare un utilizzo sicuro in crittografia non è banale.

Questo è probabilmente il principale motivo per il quale i generatori di numeri casuali sono da anni uno dei topic più caldi da trattare in ambito di sicurezza informatica.

Considerato poi che l’evoluzione tecnologica apre costantemente nuove frontiere di sviluppo dei generatori di numeri casuali (e anche di attacco di questi ultimi), con buona probabilità questi rimarranno ancora a lungo un tema centrale nel panorama di sicurezza. Insieme a loro, le certificazioni che ne garantiscono la corretta implementazione ed utilizzo saranno sempre di fondamentale importanza.

Bibliografia