Entropia e casualita'

Se siete degli utenti Gnu/Linux interessati al mondo della crittografia, allora, probabilmente, già saprete quale sia l'importanza dell'entropia. Se non lo sapeste allora fareste meglio a informarvi.

Cos'è l'entropia?

Esistono varie definizioni di entropia a seconda dell'ambito in cui viene trattata e sono fra di loro correlate.
Possiamo però affermare che, genericamente, l'entropia è la misura del disordine di un sistema, della sua imprevedibilità.

In Informatica l'entropia è stata definita per la prima volta da Claude Shannon:

La mia più grande preoccupazione era come chiamarla. Pensavo di chiamarla informazione,
ma la parola era fin troppo usata, così decisi di chiamarla incertezza. Quando discussi
della cosa con John Von Neumann, lui ebbe un'idea migliore. Mi disse che avrei dovuto
chiamarla entropia, per due motivi: "Innanzitutto, la tua funzione d'incertezza è già
nota nella meccanica statistica con quel nome. In secondo luogo, e più
significativamente, nessuno sa cosa sia con certezza l'entropia, così in una discussione
sarai sempre in vantaggio

Claude Shannon

In parole povere l'entropia misura la casualità contenuta in una sequenza di bit.

Ad esempio, se una stringa formata da 32 bit completamente casuali allora essa avrà 32 bit di entropia. Se, invece, la stessa stringa di 32 bit potesse assumere solamente 4 valori, ciascuno con una probabilità di presentarsi pari al 25%, allora l'entropia della stringa sarebbe di soli 2 bit.

Per quel che ci riguarda possiamo, matematicamente, definirla in in questo modo:

$$
H = L * \log_{2}(N)
$$

dove:

• $H$ è l'entropia;
• $L$ è il numero totale di simboli (lunghezza);
• $N$ numero di valori che ciascun simbolo può assumere, essendo ciascun valore equalmente probabile ;
• $log_{2}$ definito come il logaritmo in base 2 di N è uguale a $\log(N)/\log(2)$.

Facciamo un esempio, volendo calcolare l'entropia di una password composta da 16 cifre tra scelte tra 0 e 9 usiamo la formula in questo modo:

$$
H = 16 * \log_{2}(10) = 16 * ( \log(10)/\log(2) ) = 16 * 3,322 = 53,151 bits
$$

Usando la codifica ASCII estesa possiamo rappresentare ciascun carattere con 8 bit, quindi anche i numeri da 0 a 9 saranno rappresentati da 8 bit. Se ho 16 cifre allora mi serviranno 16*8 bit = 128 bit per rappresentarli. Ma questa sequenza di 16 numeri avrà solamente 53,151 bit di entropia.

L'entropia, infatti, non tiene conto dei bit reali che formano la stringa, ma della certezza acquisita che si ha su una quantità di informazione. Si può quindi affermare che la grandezza dell'entropia è data dalla conoscenza di un determinato valore, tanto più incrementa tale conoscenza, tanto più decrementa la sua entropia.

La casualità è, oggi, necessaria in tutte le comunicazioni cifrate. Infatti la maggior parte degli algoritmi crittografici in uso oggi necessitano di dati casuali. Ad esempio, quando ci si connette ad un sito web protetto tramite il protocollo HTTPS, tra il client ed il server remoto viene instaurata una connessione cifrata protetta da una chiave di sessione temporanea, generata casualmente. Se i pc non potessero disporre di un modo per creare una stringa casuale la sicurezza di tutte le comunicazioni sarebbe a rischio.

Generatori di numeri pseudo-casuali

Purtroppo i computers sono delle macchine deterministiche che, per loro natura, non possono generare la casualità. Quello che possono fare è, partendo da un dato realmente casuale, detto seme o seed, tramite algoritmi matematici, generare delle sequenze di bit che hanno le stesse proprietà delle sequenze casuali. Tali algoritmi sono i cosiddetti generatori di numeri pseudo-casuali o PRNG (pseudo random number generator).

In crittografia si utilizzano prng creati appositamente per essere usati in questo ambito e detti CSPRNG (cryptographically secure random number generator).
Le specifiche richieste da un normale PRNG sono soddisfatte anche da un CSPRNG, ma non è vero l'inverso. Le specifiche soddisfatte da un CSPRNG si dividono in due gruppi: il primo è che abbiano buone proprietà statistiche (cioè che passino i test i casualità), il secondo è che resistano bene agli attacchi, anche nel caso in cui vengano scoperte parte delle variabili che dovrebbero rimanere segrete. La maggior parte dei generatori di numeri pseudocasuali non sono utilizzabili come CSPRNG poiché, pur soddisfacendo i test statistici, non sono progettati per resistere ad attacchi matematici appositamente studiati.

I computer, normalmente, dispongono di varie e differenti fonti di entropia, come ad esempio l'orario di ogni pressione dei tasti ed i movimenti del mouse. Altra opportunità è offerta dalle fluttuazioni temporali di accesso ai dischi rigidi magnetici in riferimento alle turbolenze che si verificano all'interno del disco stesso.

Tutti questi dati vengono dati in pasto ad una funzione di hashing ed il risultato usato come seed di un CSPRNG. Il problema consiste nel fatto che queste fonti di entropia non sono realmente casuali, cioè la loro entropia è bassa.

Per fortuna, in natura, esistono fenomeni che sono completamente casuali e quindi sono ottime fonti di entropia, come ad esempio il decadimento radiattivo, il rumore termico o Johnson–Nyquist noise, l'effetto valanga nei diodi, il rumore atmosferico, l'effetto fotoelettrico, etc.

Esistono in commercio dispositivi, detti HRNG (Hardware random number generator) o TRNG (True random number generator), che fruttando uno o più fenomeni fisici, generano sequenze casuali di bit, che possono essere usate direttamente, dopo opportune operazioni, o possono essere usate come seed dei csprng.