it-swarm-eu.dev

Craccare un generatore congruenziale lineare

Di recente stavo ascoltando il podcast sulla sicurezza, e hanno detto per inciso che il generatore di congruenza lineare (LCG) è banale da decifrare. Uso il LCG in una classe di calcolo statistico del primo anno e ho pensato che decifrarlo avrebbe creato un bel problema "extra".

Esistono dei modi piacevoli per decifrare il LCG che non comportano forza bruta?


Non sono sicuro che questa domanda sia OT, ma non ero sicuro di dove altro pubblicare la domanda. Inoltre, i miei tag non sono molto utili poiché non ho abbastanza rappresentante per creare nuovi tag.

34
csgillespie

Sì. Esistono modi estremamente efficienti per interrompere un generatore congruenziale lineare.

Un generatore congruenziale lineare è definito da sn + 1 = a sn + b mod m, dove m è il modulo. Nella sua forma più semplice, il generatore emette semplicemente sn come nnumero pseudocasuale. Se m è noto all'attaccante e a, b non sono noti, Thomas ha descritto come romperlo.

Se nessuno di a, b, m è noto, si può ancora rompere un generatore congruenziale lineare, recuperando prima m. È un esercizio interessante derivare da come farlo in modo efficiente; si può fare. Mostrerò come di seguito; non continuare a leggere se preferisci provare a capirlo da solo.

Per recuperare m, definire tn = sn + 1 - Sn e n = |tn + 2 tn - t2n + 1|; quindi con alta probabilità avrai m = gcd (u1, u2, ..., u10). 10 qui è arbitrario; se lo fai k, allora la probabilità che ciò fallisca è esponenzialmente piccola in k. Posso condividere un puntatore al perché funziona, se qualcuno è interessato.

La lezione importante è che il generatore congruenziale lineare è irrimediabilmente insicuro e completamente inadatto per l'uso crittografico.


Aggiunto: @AviD mi odierà ancora di più :), ma ecco la matematica per cui funziona, per chi l'ha richiesto.

L'idea chiave: tn + 1 = sn + 1 - Sn = (a sn - b) - (a sn-1 - b a sn - comen-1 = a tn) == mod m e tn + 2 = a2 tn mod m e tn + 3 = a3 tn mod m. Perciò tn + 2 tn - tn + 12 = 0 mod m, ovvero |tn + 2 tn - tn + 12| è un multiplo casuale di m. Nifty fact fact: il gcd di due multipli casuali di m sarà m con probabilità 6/π2 = 0,61; e se prendi il gcd di k di questi, questa probabilità si avvicina molto a 1 (esponenzialmente veloce in k). È bello o cosa?

36
D.W.

Un generatore congruenziale lineare è lineare, che dovrebbe dire tutto.

Vale a dire, hai uno stato s, che viene aggiornato con: s ← come + b mod w, per due costanti a e b e un modulo conveniente w (in genere 232: s, a e b sono parole a 32 bit); l'output consiste nei valori successivi di s. Se hai tre uscite successive (s, s1 e s2), quindi ottieni due equazioni lineari in due incognite (a e b), che possono essere facilmente risolte con l'aritmetica elementare.

Questo può essere esteso alle varianti in cui si ottengono solo parti dei valori s, possibilmente non consecutivi. Se a e b sono due costanti a 32 bit, sono necessari solo circa 96 bit di output per ricalcolare le costanti.

18
Thomas Pornin

Un altro metodo di risoluzione per m deriva da questo paper .

In sostanza, questo metodo sfrutta il fatto che il generatore di congruenza lineare fallisce notevolmente il test degli aerei. Il determinante di una matrice 3x3 che utilizza 4 output è un multiplo di m .

Il gcd di due multipli ( n_1 e n_2 di m è m se x_1 = n_1 / m e x_2 = n_2 / m sono co-prime.

La probabilità che k numeri interi siano co-primi è data da 1/ζ (k), quindi la probabilità che x_1 e x_2 sono co-prime è 1/ζ (2) o 6/π ^ 2, circa il 61%.

Come ha detto @Thomas, una volta trovato m il resto del problema è facile.

3
Jon Takagi