La teoria del caos ha qualche applicazione pratica nella sicurezza informatica?

5

Avendo scoperto la teoria del caos all'università qualche anno fa, sono curioso sin da ora di sapere se ha trovato qualche utilità pratica nell'informatica.

Lasciami spiegare dove immagino possa essere usato ...

Il caos, in senso matematico, è un comportamento stocastico ("casuale") in un sistema deterministico ("non casuale"). I sistemi caotici hanno tre proprietà chiave:

  • sono limitati
  • sono non ripetuti
  • sono sensibili alle condizioni iniziali

Ad esempio, prendi la caotica funzione di mappa iterativa f (x) = 2x 2 - 1 . Per gli ingressi tra -1 e +1 (esclusi -1, -0.5, 0, 0.5 e 1), l'iterazione di questa funzione produce risultati caotici. Ad esempio:

    x     |    f(x)
----------+-----------
0.700000  | -0.020000
-0.020000 | -0.999200
-0.999200 | 0.996801
0.996801  | 0.987226
0.987226  | 0.949229
0.949229  | 0.802070
0.802070  | 0.286633
0.286633  | -0.835683
-0.835683 | 0.396731

I risultati sono limitati (l'output è sempre maggiore di -1.0, inferiore a 1.0) e non ripetuto (prova a ripetere su di esso alcune migliaia di volte - hai vinto non vedo alcuno schema emergente). Se si modifica il primo valore di x anche di una piccola quantità (ad esempio si usi 0,700001) inizierete a vedere i risultati divergenti considerevolmente da quelli sopra riportati dopo solo poche iterazioni. In altre parole, questa funzione è anche sensibile alle condizioni iniziali .

Potrei immaginare che abbia un numero di applicazioni in informatica come un generatore di numeri pseudo-casuali prevedibile. Ad esempio, potresti utilizzare qualcosa come la funzione precedente come base per uno di quei key fob sicuri utilizzati per "qualcosa che tu avere con te "l'autenticazione. Immagina di usare f (x) = 2x 2 - 1 in tale dispositivo. A condizione che il dispositivo e il server siano stati seminati con esattamente lo stesso input iniziale, continueranno a rimanere sincronizzati per sempre (tenendo conto dei problemi di temporizzazione), poiché la funzione è completamente deterministica. Diciamo che hai usato le prime sei cifre dopo il punto decimale come la chiave visualizzata all'utente e convalidata dal server. Se qualcuno ha guardato oltre la vostra spalla, visto il valore corrente e lo ha immesso nella stessa funzione, non è ancora possibile prevedere i valori futuri del dispositivo grazie alla sensibilità della funzione alle condizioni iniziali: solo l'ingresso a sei cifre decimali non ha valore.

Quindi, la mia intuizione è corretta? Il caos ha trovato un tale uso nella sicurezza informatica?

    
posta Simon Whitaker 16.02.2013 - 13:36
fonte

2 risposte

7

Il caos non è sufficiente . Un PRNG crittograficamente sicuro deve produrre un output imprevedibile : non dovrebbe essere sufficiente, per qualcuno che osserva un lungo flusso di valori prodotti dal PRNG, ma non conoscendo il suo stato interno, per predire il prossimo bit con una probabilità di successo sostanzialmente diversa da 0,5 (cioè le previsioni non dovrebbero funzionare meglio della fortuna). Nel caso di f (x) = 2x 2 - 1 , è sufficiente osservare un valore di output per calcolare lo stato interno (se f (x) = y quindi x = ± sqrt ((y + 1) / 2) e quindi prevedere il comportamento futuro del generatore, il che renderebbe un PRNG estremamente debole.

Un PRNG sicuro produce un output che è indistinguibile dalla casualità; in quanto tale, sembra caotico . Essere caotici è necessario per un PRNG sicuro, ma non è mai abbastanza vicino, come mostra l'esempio sopra.

La teoria del caos affascina alcune persone perché si occupa di comportamenti caotici che emergono da funzioni fisiche "normali", il che è sorprendente perché la fisica "mondana" ci ha abituati ad aspettarci un comportamento lineare e lineare delle grandezze fisiche ( termodinamica ne è il primo esempio) . Tuttavia, la sicurezza del computer funziona su computer che già vivono in un mondo discreto, quindi non lineare (sono tutti zeri e uno). Nei computer, il comportamento caotico è la norma; per la crittografia, dobbiamo andare molto oltre.

La teoria del caos sarebbe rilevante se si costruisse un PRNG senza usare un computer , ma invece si basasse su alcuni strumenti della fisica macroscopica. In quel caso, il caos sarebbe tutto ciò con cui dovresti lavorare. La teoria del caos è lo strumento giusto per spiegare perché una macchina della lotteria è un buon RNG. Ma questo non si applica ai computer in cui completa precisione è la norma: non è possibile misurare una quantità fisica con più di una dozzina di cifre o precisione, e il valore che si ottiene è sempre approssimativo in una certa misura, come se il mondo ha mantenuto la precisione extra sulla sua manica metaforica; ma puoi ottenere esattamente mille bit, e non c'è niente di più in un computer.

    
risposta data 16.02.2013 - 19:02
fonte
-1

In pratica stai descrivendo HMAC e TOTP .

    
risposta data 16.02.2013 - 14:56
fonte

Leggi altre domande sui tag