6.1.3. Traditional Pseudo-random Sequences (Sequenze Pseudo-casuali Tradizionali)

6.1.3. Traditional Pseudo-random Sequences (Sequenze Pseudo-casuali Tradizionali)

Questa sezione parla di sorgenti tradizionali di numeri deterministici o "pseudo-casuali". Questi tipicamente iniziano con una quantità "seed" e usano operazioni numeriche o logiche semplici per produrre una sequenza di valori. Si noti che nessuna delle tecniche discusse in questa sezione è adatta per uso crittografico. Sono presentate per informazione generale.

[KNUTH] ha un'esposizione classica sui numeri pseudo-casuali. Le applicazioni che menziona sono simulazioni di fenomeni naturali, campionamento, analisi numerica, test di programmi per computer, processo decisionale e giochi. Nessuna di queste ha le stesse caratteristiche dei tipi di usi di sicurezza di cui stiamo parlando. Solo nelle ultime due potrebbe esserci un avversario che cerca di trovare la quantità casuale. Tuttavia, in questi casi, l'avversario normalmente ha solo una singola possibilità di usare un valore indovinato. Nell'indovinare password o nel tentare di violare uno schema di cifratura, l'avversario normalmente ha molte, forse illimitate, possibilità di indovinare il valore corretto. A volte l'avversario può memorizzare il messaggio da violare e attaccarlo ripetutamente. Si assume anche che gli avversari siano aiutati da un computer.

Per testare la "casualità" dei numeri, Knuth suggerisce una varietà di misure, incluse quelle statistiche e spettrali. Questi test controllano cose come l'autocorrelazione tra diverse parti di una sequenza "casuale" o la distribuzione dei suoi valori. Ma questi test potrebbero essere soddisfatti da una sequenza casuale costante memorizzata, come la sequenza "casuale" stampata nelle CRC Standard Mathematical Tables [CRC]. Nonostante soddisfi tutti i test suggeriti da Knuth, quella sequenza è inadatta per uso crittografico, poiché gli avversari DEVONO essere assunti avere copie di tutte le sequenze "casuali" comunemente pubblicate e essere in grado di individuare la sorgente e prevedere valori futuri.

Una tipica tecnica di generazione di numeri pseudo-casuali è il generatore di numeri pseudo-casuali a congruenza lineare. Questa tecnica usa aritmetica modulare, dove il valore numerato N+1 è calcolato dal valore numerato N da

    V    = ( V  * a + b )(Mod c)
     N+1      N

La tecnica sopra ha una forte relazione con i generatori di numeri pseudo-casuali a registro a scorrimento lineare, che sono ben compresi crittograficamente [SHIFT*]. In tali generatori, i bit sono introdotti a un'estremità di un registro a scorrimento come Exclusive Or (somma binaria senza riporto) di bit da tap fissi selezionati nel registro. Per esempio, consideriamo il seguente:

  +----+     +----+     +----+                      +----+
  | B  | <-- | B  | <-- | B  | <--  . . . . . . <-- | B  | <-+
  |  0 |     |  1 |     |  2 |                      |  n |   |
  +----+     +----+     +----+                      +----+   |
    |                     |            |                     |
    |                     |            V                  +-----+
    |                     V            +----------------> |     |
    V                     +-----------------------------> | XOR |
    +---------------------------------------------------> |     |
                                                          +-----+

   V    = ( ( V  * 2 ) + B  XOR  B ... )(Mod 2^n)
    N+1         N         0       2

La qualità degli algoritmi tradizionali di generazione di numeri pseudo-casuali è misurata da test statistici su tali sequenze. Valori accuratamente scelti a, b, c e V iniziale o posizionamento accuratamente scelto del tap del registro a scorrimento nel semplice processo sopra possono produrre statistiche eccellenti.

Queste sequenze possono essere adeguate nelle simulazioni (esperimenti Monte Carlo) fintanto che la sequenza è ortogonale alla struttura dello spazio esplorato. Anche lì, pattern sottili possono causare problemi. Tuttavia, tali sequenze sono chiaramente inadatte per l'uso in applicazioni di sicurezza. Sono completamente prevedibili se lo stato iniziale è noto. Dipendendo dalla forma del generatore di numeri pseudo-casuali, la sequenza può essere determinabile dall'osservazione di una breve porzione della sequenza [SCHNEIER, STERN]. Per esempio, con i generatori sopra, si può determinare V(n+1) data la conoscenza di V(n). In effetti, è stato dimostrato che con queste tecniche, anche se viene rilasciato solo un bit dei valori pseudo-casuali, il seed può essere determinato da sequenze brevi.

Non solo i generatori a congruenza lineare sono stati violati, ma le tecniche sono ora note per violare tutti i generatori a congruenza polinomiale [KRAWCZYK].