generazione di numeri pseudocasuali

Esame di laboratorio di crittografia
Lorenzi Stefano
matricola 754752
GENERAZIONE
DI NUMERI
PSEUDOCASUALI
1
Indice generale
GENERAZIONE DI NUMERI CASUALI..........................................................................................3
Introduzione.....................................................................................................................................3
ALGORITMI DI GENERAZIONE DI NUMERI PSEUDOCASUALI.............................................5
Panoramica sugli algoritmi esistenti................................................................................................5
Metodo della congruenza lineare.....................................................................................................5
Ansi X9.17.......................................................................................................................................7
Blum Blum Shub.............................................................................................................................8
LibMTPRNG...................................................................................................................................9
SOFTWARE.......................................................................................................................................10
Presentazione del software.............................................................................................................10
Attacchi agli algoritmi........................................................................................................................13
Attacco all'algoritmo a congruenza lineare....................................................................................13
Attacco all'algoritmo Ansi X9.17..................................................................................................13
Input-Base attacks.....................................................................................................................13
Crittoanalisi...............................................................................................................................14
Attacco a Blum Blum Shub......................................................................................................14
Bibliografia.........................................................................................................................................15
2
GENERAZIONE DI NUMERI CASUALI
Introduzione
Un generatore di numeri casuali è uno strumento capace di fornire una sequenza di
numeri casuali, ovvero non deterministici. Questi numeri sono idealmente infiniti e non
sono influenzabili da alcun fattore esterno.
Tali numeri ricoprono un ruolo importante nella crittografia, basta pensare agli schemi di
autenticazione reciproca e nello scambio delle chiavi, dove per prevenire attacchi a replay
dei pacchetti vengono utilizzati dei numeri “nonce”. Un altro esempio di tale importanza è
la generazione della chiave pubblica nell'algoritmo RSA.
Queste applicazioni danno origine a due requisiti distinti e non necessariamente
compatibili:
●
●
Casualità
Imprevedibilità
Casualità
Un elaboratore non ha la possibilità di generare una sequenza casuale, bensì l’unico
modo è utilizzare opportuni algoritmi che generano numeri apparentemente casuali.
Questi vengono, quindi, chiamati numeri pseudo-casuali, poiché venendo a conoscenza
dell’algoritmo e del seme (primo elemento) utilizzati è possibile determinare la sequenza
che verrà generata.
Tali algoritmi per essere considerati “generatori casuali” in senso statistico devono avere
due caratteristiche:
●
●
Distribuzione uniforme: Generando una quantità elevata di numeri, ognuno di essi
deve apparire con una frequenza simile.
Indipendenza: non deve essere possibile determinare l'ennesimo numero,
guardando gli n-1 numeri.
Se è semplice verificare se una sequenza segue o meno una distribuzione uniforme, non
è altrettanto semplice dimostrarne l'indipendenza. Per definire l'indipendenza è possibile
eseguire diversi test che aiutano ad avere una certa possibilità che i numeri generati siano
indipendenti.
Nell'ambito della crittografia, la progettazione di algoritmi di numeri che sembrano
statisticamente casuali ricoprono un ruolo fondamentale: un esempio è la generazione di
numeri primi nella creazione della chiave pubblica in RSA. Per la generazione di tali
numeri, un approccio a forza bruta prevede la divisione del numero N per ogni interno
dispari minore di  N . Ma se N è un numero molto grande (nell'ordine di 10150), i tempi
richiesti sarebbero troppo alti, e questa è una situazione piuttosto comune nella
crittografia.
3
Per risolvere tale problema esistono algoritmi in grado di verificare se un numero è primo,
ad esempio producendo una sequenza di numeri casuali ed eseguendo semplici calcoli.
Se tale sequenza è sufficientemente lunga, sarà possibile determinare con una buona
sicurezza se un numero è primo.
Imprevedibilità
Se da una parte è importante generare numeri apparentemente casuali, dall'altra è
fondamentale che, data una sequenza, sia impossibile determinare i numeri successivi.
In altre parole, ogni numero generato è statisticamente indipendente dai precedenti.
Prendiamo come esempio due serie di 1 e 0.
0, 1, 0, 1, 0, 1, 0, 1, 0, 1...
1, 1, 0, 1, 0, 1, 1, 0, 0, 1, ...
Apparentemente si è portati a definire la prima sequenza deterministica, poiché si
riconosce una certa periodicità o un algoritmo capace di generarla; la seconda sembra
essere “più casuale” e non si trova alcuna regola capace di formarla (quindi non è
prevedibile).
4
ALGORITMI DI GENERAZIONE DI NUMERI
PSEUDOCASUALI
Panoramica sugli algoritmi esistenti
Esistono diversi algoritmi per la generazione di numeri pseudo-casuali, che si
differenziano per il tipo di algoritmo usato.
Alcuni si basano su calcoli matematici, altri su sistemi crittografici. Nella quasi totalità, essi
producono una sequenza di numeri interi uniformemente distribuiti tra 0 e un certo valore
massimo, oppure di numeri reali tra 0 e 1. Questi ultimi si possono sempre ottenere dai
primi semplicemente dividendo per il valore massimo, come ad esempio alcune librerie dei
linguaggi di programmazione.
Prima di essere usato, un generatore deve essere inizializzato assegnando un opportuno
valore a un parametro numerico, o gruppo di parametri, che viene chiamato seme (in
inglese seed). Ogni volta che si usa lo stesso seme, si otterrà sempre la stessa identica
sequenza.
Un'attenta analisi matematica è richiesta per assicurare che i numeri generati abbiano le
necessarie proprietà statistiche. Robert R. Coveyou dell'Oak Ridge National Laboratory ha
intitolato un articolo: "La generazione dei numeri casuali è troppo importante per essere
lasciata al caso."
Metodo della congruenza lineare
Tale metodo permette, dato un valore iniziale x0 detto seme, di ottenere una sequenza di
numeri pseudo-casuali mediante l’applicazione ripetuta della seguente formula:
xi+1 = (a * xi + c) (MOD m)
dove:
a
c
m
xi
è un coefficiente intero positivo detto moltiplicatore
è un coefficiente intero non negativo detto incremento
è un coefficiente intero positivo detto modulo
è il generico numero della sequenza
Il metodo prende il nome dalla seguente definizione:
due numeri x e y si dicono congrui modulo m, e scriveremo x ≡ y (mod m), se essi
differiscono per un multiplo intero di m, ossia se x (mod m) ≡ y (mod m).
Il metodo è detto moltiplicativo se c=0, misto se c ≠ 0. Se a=1, il metodo è detto additivo.
Facciamo degli esempi: partiamo attribuendo le seguenti assegnazioni:
5
a=3
c=5
m=11
Se X0=3, la sequenza che si ottiene applicando la formula della congruenza modulare è [3,
3, 3, 3,], ossia una sequenza assolutamente non casuale.
Le cose cambiano se scegliamo X0=1; in questo caso, la sequenza ottenuta è la seguente:
1, 8, 7, 4, 6, 1, 8, 7, 4, 6, 1, ...
Possiamo notare che i primi 5 numeri vengono riprodotti interamente.
Infine, se X0=2, si ottiene:
2, 0, 5, 9, 10, 2, 0, 5, 9, 10, 2, ...;
Anche in questo caso otteniamo una sequenza di 5 numeri ripetuti.
Se modifichiamo il valore di a assegnandogli il valore 12, e poniamo X0=1, ottieniamo:
1, 6, 0, 5, 10, 4, 9, 3, 8, 2, 7, 1, 6, 0, 5, ...
Essa è una sequenza di periodo 11 e cioè pari a m, e senza ripetizione di numeri.
In questo ultimo esempio è interessante osservare che non solo generiamo 11 numeri tutti
diversi e che copriamo l'intero periodo, ma la sequenza si ripete.
Questo ci permette di poter generare molti numeri con una distribuzione uniforme. Quindi
possiamo sostenere che questo algoritmo ha le seguenti proprietà:
1. l'algoritmo genera l'intero periodo di numeri, ossia prima di ripetersi ha generato
tutti i numeri compresi tra 0 e m.
2. La sequenza generata è apparentemente casuale.
3. I calcoli sono eseguiti facilmente da un calcolatore.
Come abbiamo potuto osservare, questo algoritmo funziona bene se sono stati scelti dei
parametri opportuni.
Per quanto riguarda l'implementazione di questo algoritmo su un elaboratore è importante
impostare m al valore del massimo intero rappresentabile da quel processore, in modo
tale che la sequenza generata abbia un periodo molto ampio, ricordando che il bit più
significativo rappresenta il segno. Per processori a 32 bit, un valore utile di m è 231-1.
Per rappresentare tutto il periodo occorre però fare attenzione alla scelta di a e c. Si può
dimostrare però che se m è primo e c = 0, allora vengono generati m-1 valori con la sola
assenza del valore 0 (231-1 è un numero primo).
Purtroppo degli oltre 2 miliardi di numeri a disposizione, solo pochi possono essere scelti
per il parametro a (un valore spesso utilizzato per a è 75 = 16807)
Da tutto ciò si possono ricavare le seguenti osservazioni:
●
La lunghezza massima raggiungibile dalla sequenza generata senza ripetizione
6
●
●
●
vale m
Particolari scelte di a e c possono ridurre notevolmente la lunghezza utile della
sequenza
Il valore di X0 (seme) può essere determinante dalla lunghezza della sequenza
E' fondamentale che il periodo sia il più ampio possibile per rendere l'algoritmo più
sicuro da eventuali attacchi.
E’ allora necessario individuare dei criteri per assegnare ad a, c, m e al seme dei valori in
modo che la sequenza riprodotta sia la più lunga possibile.
Alcuni studiosi hanno approfondito tale aspetto e hanno individuato i seguenti criteri
necessari e sufficienti che garantiscono l'ottimalità del metodo:
1. I parametri c e m devono essere coprimi cioè MCD(c,m) = 1
2. Ogni divisore primo di m deve dividere (a-1)
3. Se m è multiplo di 4, anche (a-1) lo deve essere.
Questi studiosi hanno individuato quindi i seguenti valori nel rispetto dei suddetti criteri:
KNUTH
m = 2 31; a = int (π * 10 8) ; c = 453806245
GOODMAN e MILLER
m = 2 31 -1; a = 7 5 ; c = 0
GORDON
m = 2 31; a = 5 13 ; c = 0
LEORMONT e LEWIS
m = 2 31; a = 2 16 + 3 ; c = 0
Ansi X9.17
E' uno dei generatori più forti dal punto di vista crittografico. Esso fa uso del Triple-Des in
modalità EDE (Encrypt-Decrypt-Encrypt); come input ha un numero random e segreto
(generalmente la data e ora del dell'elaboratore) di 64 bit. Infine, ha un valore intero m
(random) come seme, e due chiavi per il triple-des.
La robustezza di questo algoritmo sta nel fatto che è usato il triple-des per tre volte ed una
chiave da 112 bit: questo equivale a nove crittografie DES. Quindi, un ipotetico attaccante
dovrebbe violare una grossa quantità di dati.
Tale algoritmo può essere rappresentato nel seguente modo
R = E[E(T) XOR V]
V = E[E(T) XOR R]
dove
●
E() = è il TripleDes
●
DTi = Timestamp
●
Vi = Initialization Vector
●
Ri = random number to be generated
7
Blum Blum Shub
Questo algoritmo, molto usato, è sostanzialmente un generatore di bit, ed ha dato forse la
più forte prova di potenza crittografica.
Il funzionamento è il seguente:
1. Bisogna generare due numeri p e q, numeri primi (molto grandi) diversi tra loro e
ciascuno congruente a 3 modulo 4 (ossia p e q divisi per 4 avranno resto 3)
2. Si imposta n come p*q
3. Si seleziona il seme,ossia un numero random s, tale che 1<=s<=n-1. Inoltre s deve
essere coprimo con n [ossia gcd(s,n)=1]
4. Quindi x0 ←s2 mod n.
5. Xi = (Xi-1) 2 mod n
6. Bi = xi mod 2
7. Concatenando i bit ottenuti al punto precedente, si genera un numero della
dimensione desidarata.
Come per l'algoritmo a congruenza lineare questo algoritmo per essere sicuro deve avere
un valore di n molto grande, nell'ordine di 1024 bits.
8
LibMTPRNG
Matthew Davis e Sameer Niphadkar propongono un algoritmo senza seed, basato sul
multithreading e sul non-determinismo.
Il loro ragionamento si basa sul fatto che lo scheduling dei thread all'interno di un processo
è abbastanza casuale, non esiste una priorità e lo stato di running può dipendere da una
molteplicità di eventi. Questo non-determinismo è intensificato dai moderni calcolatori
multiprocessore, dove più thread possono girare in parallel. In sostanza, non è prevedibile
un modello di comportamento, a meno che lo scheduler non eserciti una grande influenza.
Da queste premesse gli autori hanno scritto LibMTPRNG (Multithreaded Pseudo-Random
Number Generator Library), una libreria statica sulla falsariga di rand(), che è definita nello
standard C99.
Si basa su un intero a 32 bit e si associano 2 thread per ogni bit; quando viene richiesto un
numero pseudo-casuale, viene rilasciato un mutex su un oggetto condiviso e si fanno
partire i primi 32 thread, garantendo un accesso atomico attraverso meccanismi di mutual
exclusion.
Ciascun thread manipola un solo bit e incrementa un contatore, il quale stabilirà la fine del
processo e quindi la disponibilità del numero pseudo-casuale.
Una descrizione più dettagliata si trova in un articolo tecnico pubblicato ial seguente
indirizzo: http://www.ddj.com/hpc-high-performance-computing/216900024, articolo che
costituisce, a conoscenza del sottoscritto, l'unica documentazione disponibile, oltre
naturalmente ai sorgenti.
I test di effettiva casualità sono stati condotti seguendo le indicazioni di Some Difficult-topass Tests of Randomness, su sistemi Linux e Solaris. I risultati non sono eccezionali, ma
gli autori sostengono che indagando più a fondo i meccanismi paralleli e alcuni eventi,
come le race condition, si potrà migliorare questa interessante idea.
9
SOFTWARE
Presentazione del software
Utilizzando gli algoritmi presentati in questo lavoro, ho implementato un software che
genera grandi quantità di numeri pseudo casuali.
Inoltre, visto che il software è stato implementato in Java, ho utilizzato anche il generatore
nativo di numeri casuali di questo linguaggio, ed ho voluto vedere come tali algoritmi
funzionano nella pratica.
I parametri che ho voluto osservare sono:
●
●
Se i numeri hanno una distribuzione uniforme
Il tempo richiesto nella generazione di queste sequenze
Come possiamo vedere dall'immagine, è possibile configurare dei parametri, in
particolare:
10
●
●
●
●
Il numero minimo
il numero massimo
La quantità dei numeri da generare
Inoltre per il metodo a congruenza lineare è possibile variare i parametri di
input(modulo, moltiplicatore e incremento)
E' evidente che qualora decidessi di impostare un range compreso tra 0 e 231 – 1, avrei
sempre una distribuzione uniforme. Con range più piccoli, ad esempio tra 0 e 9, il numero
verrebbe generato nel seguente modo: X = N mod 10, dove N è il numero generato
dall'algoritmo scelto. Questo comporta che si ottiene una distribuzione uniforme solo dopo
aver generato una lunga sequenza si numeri: in altre parole, più il range è grande, meno
numeri occorrono per avere una distribuzione uniforme.
Come possiamo vedere dalle immagini, su range piccoli occorrono almeno 100.000
numeri per avere una distribuzione uniforme. Questo valore è più o meno uguale per tutti
gli algoritmi provati.
Figura A : 1000 numeri
Figura B: 100.000
Figura C: 1.000.000
Il dato invece che cambia molto è quello inerente al tempo per generare questi numeri.
Nella tabella seguente sono riportati i tempi necessari utilizzati dal mio calcolatore per la
generazione di un milione di numeri:
Congruenza lineare
98 millisecondi
Ansi X9.17
32,5 secondi
Blum Blum Shub
13 secondi
Java Random
134 millisecondi
Java Security
2187 millisecondi
È evidente come la complessità del calcolo incida sul tempo. Se da una parte il metodo
della congruenza lineare è molto veloce, dall'altra è anche il meno sicuro: infatti, tale
sistema dipende principalmente dal seme, e se un ipotetico attaccante volesse violare tale
11
algoritmo dovrebbe andare alla ricerca di un solo valore. Dall'altro lato, il metodo Ansi
X9.17, seppur decisamente più lento, per venire attaccato necessita di conoscerne il
seme, il timestamp, e 2 chiavi del triple des (ben 4 valori).
Anche la differenza tra le 2 librerie Java è notevole (ricordo che la libreria Random è poca
sicura, è basata sull'algoritmo a congruenza lineare con un seme di 48 bit).
Il software è stato sviluppato con la versione 1.6 di Sun Microsystem ed utilzza le librerie
JfreeChart 1.0.12 reperibili all'indirizzo http://www.jfree.org/jfreechart/download.html
La figura sottostante riporta il diagramma UML
12
Attacchi agli algoritmi
Attacco all'algoritmo a congruenza lineare
Se l'attaccante conosce il valore di m e 3 numeri consecutivi, allora si può sferrare il
seguente attacco:
●
●
●
Xi+1 ≡(aXi + c) mod m
Xi+2 ≡(aXi+1 + c) mod m
Xi+2 - Xi+1 ≡(aXi+1 + c - aXi - c) mod m ≡ a(Xi+1 - Xi) mod m
Vediamo un esempio con i seguenti dati:
m=9, Xi = 3, Xi+1 = 7, Xi+2 = 0
(0 - 7) ≡a(7-3) mod 9 ← → 4a ≡2 mod 9
Quindi il parametro a sarà 5.
5 * 3 + c ≡15 + c mod 9 ≡6 + c mod 9 ≡ 7 mod 9
Il parametro c = 1.
Ora che siamo a conoscenza di tutti i parametri, sapremo che dopo i numeri 3, 7 e 0 ci
sarà il numero 1, poi il 6, poi il 4,...
Attacco all'algoritmo Ansi X9.17
Sono diversi i modi per attaccare questo algoritmo, ma tutti hanno una complessità
maggiore rispetto all'attacco visto nel paragrafo precedente
Input-Base attacks
Un input-base attacks si verifica quando un utente malintenzionato è in grado di utilizzare
la
conoscenza o il controllo dell'input. Questa tipologia di attacco può essere
ulteriormente suddivisa known-input, replayed-input, e chosen-input attacks.
Un chosen-input attacks può essere pratico contro smart - card e altri sistemi di crittografia
hardware.
Replayed-input attacks sono simili ai precedenti, ma richiedono un meno sofisticacazioni
di controllo da parte del attaccante.
Known-input attacks può essere in ogni situazione in cui alcuni dei elementi di input,
possono essere facilmente prevedibili, ad esempio se viene usato il timestamp di un pc in
rete, i cui orari sono osservabili dall'attaccante.
13
Crittoanalisi
Seppur generalmente viene usato il triple-des in modalità EDE, l'algoritmo di crittografia
potrebbe anche essere diverso, quindi bisogna essere attenti a quale algoritmo si sceglie
e quali conoscenze di crittoanalisi ci sono su quell'algoritmo.
Attacco a Blum Blum Shub
E' decisamente il più complesso da attaccare tra quelli visti, in particolare perché bisogna
fattorizzare n per trovare i valori di p e q, ma come sappiamo la fattorizzazione è uno dei
problemi non ancora risolti efficientemente dalla matematica (come la soluzione del
logaritmo discreto), non a caso molti sistemi di cifratura si basano su tali presupposti
(RSA, El-Gamal). Questo algoritmo però, è un generatore di bit e il numero random è la
concatenazione dei bit generati precedentemente, questo comporta che anche qualora
venga fattorizzato n, ciò non basta, bisogna infatti fattorizzare tante volte n quanti sono il
numero di bit del numero random generato.
14
Bibliografia
●
Critttografia e sicurezza delle reti – William Stallings McGraw-Hill
●
A. Menezes, P, van Oorschot, S. A. Vanstone - Handbook of Applied Cryptography CRC Press 1996 (chap 5)
●
Wikipedia
15