Hashingul recursiv este ciclic?

Dacă reintroduc ieșirea lui H în H, acesta va acoperi întreg spațiul de ieșire al lui H înainte de a se repeta?

Luați în considerare următorul scenariu:

A=1;
In timp ce(){
   A=H(A);
   imprimare (A)
}

Vor fi cicluri scurte? De exemplu. Există valori ale lui A care H(A) = A (un ciclu de 1) Valori ale lui A unde H(A) = B și H(B) = A (ciclu de 2)

Există vreo modalitate de a demonstra că fie nu există astfel de cicluri pentru un anumit hash, fie de a pune o limită inferioară celui mai scurt ciclu.

Douglas Hofstadter într-una dintre cărțile sale (Fie „The Mind’s I”, fie „Metamathematical Themas”, cred) are o propoziție

Această propoziție are un „a”, unul „b”,...

Problema este să găsești valorile care o fac adevărată. Dacă doar numărați decuparea curentă și corectați propoziția și repetați, propoziția converge destul de repede către o afirmație adevărată.

Deci, cum se conectează asta la criptografie.

Bănuiesc, dar nu am demonstrat, că „atractorul ciudat” de mai sus este destul de arbitrar.

{Textul întreg al războiului și păcii} Această declarație are...

va converge, de asemenea, spre o afirmație corectă.

Luați în considerare un hash, H. Să presupunem că există cicluri scurte de H. Vor exista și cicluri de (D+H) unde D este o bucată arbitrară de date. Acestea vor avea aceeași lungime? (Nu văd un motiv bun pentru care ar trebui să fie)

Dacă o fracțiune apreciabilă de hashuri sunt membri ai unui ciclu scurt (pentru o valoare scurtă: 1 milion? 1 miliard?), atunci există următoarea vulnerabilitate:

Luați dosarul D.

• Modificați D pentru a se potrivi cu scopurile dvs. O parte a acestui proces ar trebui să fie scurtarea cu lungime (valoare hash) Apelați acest fișier D'

+ stă sau se concatenează

• Calculați A = H(D)
• Calculați A2 = H(A+D')
• Calculați A3 = H(A2+D')

Dacă A este ciclic, veți ajunge în cele din urmă la un A_n a cărui iterație următoare produce A.

• Înlocuiți fișierul D cu A_n+D'

În ceea ce privește securitatea, trebuie să știm care este probabilitatea ca un anumit A să fie ciclic într-un timp rezonabil. Desigur, rezonabil depinde de cât de important este documentul. Dar dacă puteți demonstra că există o probabilitate foarte mică de a găsi un ciclu sub 10^15 sau cam asa ceva, atunci acest tip de atac nu este practic. Dacă există o șansă de 2% ca un anumit hash să fie ciclic în mai puțin de un milion de iterații, există o problemă potențială.

Când studiază o astfel de problemă, criptografii asimilează un hash criptografic $H$ la a functie aleatorie sau oracol aleatoriu (sau cartografiere aleatorie deși este puțin învechit) care se repetă. Probabilitățile sunt calculate pe mulțimea tuturor hashurilor posibile. Aceasta este o aproximare, dar dacă rezultatele reale sunt diferite în mod distinct, aceasta ar fi o modalitate de a distinge hash-ul de o funcție aleatorie, deci o rupere a hash-ului după definițiile moderne. Prin urmare, respectiva aproximare este satisfăcătoare și cu atât mai bine poate fi pentru un hash criptografic neîntrerupt.

Vor fi cicluri scurte?

Probabil, și cu atât mai mult cu cât slăbim definiția de scurt. Dar (cu excepția hashurilor foarte mici) este puțin probabil ca un ciclu scurt să fie atins dintr-un punct de pornire aleatoriu $A$; și (pentru hashuri criptografice standard cu o ieșire suficient de mare încât să fie rezistente la coliziuni) este puțin probabil să putem prezenta vreun ciclu, indiferent de dimensiunea acestuia.

Există valori ale $A$ astfel încât $H(A)=A$ (un ciclu de 1)

Dacă setul de destinație al hash-ului are dimensiune $n$ (Unde $n=2^b$ Pentru o $b$-bit hash, de ex. $n=2^{256}$ pentru SHA-256), atunci probabilitatea ca să existe un ciclu de mărime 1 este ușor de calculat ca complement al probabilității ca niciunul dintre $n$ indică hashuri către sine, adică $p_1(n)=1-(1-1/n)^n$. Aceasta începe de la $p_1(1)=1$, $p_1(2)=3/4=0,75$, $p_1(3)=19/27\aprox.0,7037$, și $p_1$ converge rapid spre 1-1 USD/e\aproximativ 0,6321 USD.

Astfel, există > 63,2% probabilitate să existe un ciclu de dimensiunea 1 într-un hash criptografic dat, cum ar fi SHA-256, SHA-384 sau SHA-512. Și nu putem spune mai bine pentru niciunul dintre aceste hashes.

Nu știu cum să fac în mod corespunzător același lucru pentru ciclurile de dimensiunea 2, dar nu mă îndoiesc că este fezabil și probabilitatea este mare pentru $n\ge2$.

Este posibil să se calculeze valoarea așteptată a multor caracteristici ale ciclurilor pentru o funcție/hash aleatorie iterată. În special, pentru mari $n$, numărul așteptat de pași înainte de a atinge o valoare anterioară pornind de la un punct aleatoriu este $\aprox\sqrt{\pi\,n/2}$, iar lungimea așteptată a ciclului atins este jumătate din aceasta. O referință clasică este Philippe Flajolet și Andrew M. Odlyzko, Statistici de cartografiere aleatoare, în procedurile Eurocrypt 1989, și Raport de cercetare RR-1114, INRIA, 1989.

Există vreo modalitate de a demonstra că fie nu există astfel de cicluri pentru un anumit hash, fie de a pune o limită inferioară celui mai scurt ciclu.

Nu, pentru un hash criptografic neîntrerupt cu o dimensiune de ieșire suficient de mare încât să fie rezistent la coliziuni (adică $\sqrt n$ este atât de mare încât acest număr de hashe-uri nu poate fi calculat); să zicem, orice hash neîntrerupt de 256 de biți sau mai mare. Pentru partea de întrebare care se pune este că este posibil să dovedim că nu există un astfel de ciclu, chiar ar trebui să calculăm $n$ hash-uri (până la ultima nu putem fi siguri că nu există un ciclu de dimensiunea 1), astfel orice hash neîntrerupt de 128 de biți sau mai mare va fi potrivit.

Deci, cum se conectează (construcția repetată a lui Douglas Hofstadter) la criptografie?

O tehnică destul de similară este utilizată în atacarea unor criptosisteme. Construim o funcție, o iterăm până când găsim un ciclu (care, prin urmare, este scurt, altfel nu l-am putea găsi), iar punctul de intrare în ciclu dă o coliziune, iar coliziunea rezolvă problema deoarece funcția a fost construită cu acel explicit. scop. Asta e inima rho lui Pollard metoda de rezolvare a Problemei Logaritmului Discret, care este cel mai bun atac teoretic pe care îl avem pentru această problemă în unele grupuri utilizate în criptografie.

Observați că nici funcția din cele de mai sus, nici funcția construită de Douglas Hofstadter nu constituie un hash criptografic securizat. Pentru că nu sunt, putem găsi un ciclu și rezolva problema la îndemână.