funcția hash inversă face posibilitățile să crească exponențial, dar există un număr finit de intrări. Cum?

Când încercați să inversați o funcție hash, există pierderi, de ex.

a+b=c
dat c=5, încercați să reveniți la a,b (pasul anterior)
(a,b)=(5,0),(4,1),(3,2),(2,3),(1,4),(0,5)

dar, având în vedere oricare dintre perechile (a, b), obținem c=5 în pasul următor și fiecare dintre aceste perechi are aceeași creștere exponențială aplicată la inversarea lor. Astfel, se pare că fiecare pas înapoi pe care îl faci crește numărul de valori posibile care duc la c=5 exponențial.

De asemenea, nici două ramuri nu se pot recombina la inversare, deoarece ar necesita ca una (a,b,c) să se împartă în două posibile (a,b,c), ceea ce este aleatoriu, nu determinist și atât de imposibil în hashing.

Problema este că există un număr finit de intrări și un număr finit de valori posibile (a,b,c). Pare un paradox, iar singura soluție pe care o pot găsi este că unele căi sunt în fundături, de ex. ((a,b,c)!=posibil de făcut din oricare altul (a,b,c)). Cu toate acestea, nu cred că există astfel de (a,b,c), așa că poate am o soluție greșită?

funcția hash inversă face posibilitățile să crească exponențial, dar există un număr finit de intrări. Cum?

Este exact ceea ce ne așteptam (nuvela); fiecare necunoscută crește posibilitatea cu 2, prin urmare veți obține o exponențială - vă puteți gândi la tabelul de adevăr pentru a vedea asta. Există o intrare finită la SHA-256 datorită regulilor de umplutură, adică $2^{128}-1$. Intrarea dvs. poate să nu fie atât de mare, încă finită.

Inversarea operației de hashing SHA-256 cu rezolvarea ecuațiilor (numim asta atac algebric) este aproape imposibil, deoarece trebuie să rezolvați un calcul simbolic (SAT) și 3SAT este NP-Complete. Nu există nicio garanție că fiecare instanță SHA-256 este insolubilă. Când considerăm că atacul algebric revendicat al AES (XSL) nu este mai rapid decât forța brută. Mă aștept ca runda de 64 de SHA-256 să fie mai greu de criptoanaliza cu atacuri algebrice. Acest lucru încă nu înseamnă că pentru unele valori hash instanța va fi, de asemenea, insolubilă.

Chiar și pentru spațiul de intrare pe 64 de biți, mă aștept că algebricul este mai greu decât căutarea spațiului de intrare pe 64 de biți pentru a găsi imaginea prealabilă a ieșirii hash date.

În calculul dvs., eliminați unele posibilități ale variabilelor, la asta ne așteptăm, totuși, runda 64 a cifrului bloc intern al SHA-256 numit SHACAL2 nu vă va permite să-l executați prea mult. Nu aceasta este calea ataca SHA-256.

cartea lui Bard; Criptanaliză algebrică este un punct de plecare pentru atacul algebric. Și vezi cum noul lor anunț ajută la spargerea criptare keeloq simplă în timp ce SHA-256 este mult mai complex de luat în considerare.

Cred că confuzia ta vine din analiza unei singure operații în loc de o funcție hash ca un întreg. Este adevărat că inversarea unei operații precum adăugarea introduce o altă variabilă de intrare pentru fiecare iterație. Dar asta ignoră modul în care o astfel de operație este utilizată în cadrul unei funcții hash. Dacă te uiți la o funcție precum SHA-256, o operație precum adăugarea se încadrează într-o rețea bine definită de alte operațiuni care transformă intrările în ieșiri. Rețeaua acceptă 512 de biți de intrare și produce 256 de biți de ieșire, iar definiția este fixă, așa că nu prea este loc să vorbim despre „creștere exponențială”. Ceea ce este adevărat este că încercarea de a rezolva pentru un set de intrări care produce o ieșire dorită este de așteptat să ia efort exponențial este dimensiunea problemei.