Dată o funcție hash $\mathcal H()$ și o valoare hash $H$ care se află în codomeniul/gama de ieșiri ale $\mathcal H()$, puteți determina dacă $H$ poate fi produs de $\mathcal H()$ (adică este $H$ în imaginea lui $\mathcal H()$)?
Voi presupune că „codomeniul/gamă de ieșiri” este definit fără referire la ceea ce iese de fapt hash-ul (mai degrabă decât ca setul de ieșiri reale ale hash-ului, ceea ce ar face ca totul să fie atins prin definiție).
Dacă o funcție hash $\mathcal H$ a fost astfel încât pentru o parte considerabilă din dat $H$ în codomeniul său se poate expoziţie intrare $M$ astfel încât $H(M)=H$, atunci acea funcție nu ar fi rezistentă la preimagine. Astfel, expoziția menționată trebuie să fie imposibilă din punct de vedere computațional pentru o întâmplare $H$.
Dacă modelăm un hash ca funcție aleatoare $\{0,1\}^*\la\{0,1\}^n$, apoi conform colector de cupoane problema, numărul așteptat de hashe-uri ale mesajelor aleatorii pentru a atinge toate valorile este $E=2^n\,(n\,\ln(2)+\gamma)+1/2+o(1)$. În practica criptografică $n\ge128$ prin urmare $\log_2(E)\aprox n+\log_2(n)-0,53$. Astfel, în medie, ar trebui să hashing mai puțin decât toate mesajele de exact 33 de octeți pentru a ajunge la toate valorile pentru un hash ideal de 256 de biți, dar trebuie să hash mai mult decât toate mesajele de exact 65 de octeți pentru a atinge toate valorile pentru un 512-biți ideal. putin hash. A face atât de multe hashe-uri este imposibil.
Pentru funcțiile hash obișnuite, cum ar fi SHA-1, SHA-256, SHA-512 și cred că SHA-3, așa cum se spune în aceea alt raspuns, nu avem nicio dovadă matematică că fiecare valoare de ieșire poate fi atinsă. Cel mai bun lucru pe care putem spune este că este probabil valabil (chiar și limitându-se la mesajele care se potrivesc unui singur bloc, și cu atât mai mult cu mai multe), dar ar fi surprinzător dacă ar putea fi fie dovedit, fie infirmat.
Dar cred că putem construi o funcție hash care dovedit atinge tot spațiul său de ieșire, dar are în mare măsură proprietățile așteptate de la un hash criptografic. Iată un hash candidat de șir de biți arbitrar care ajunge, în mod demonstrabil, la întreg $\{0,1\}^{512}$.
Voi folosi un 3072 de biți prime sigure $p$, adică așa încât $q=(p-1)/2$ este, de asemenea, prim; si un generator $g$ a grupului multiplicativ $\mathbb Z_p^*$, acesta este $g\in[2,p-2]$ cu $g^q\equiv-1\pmod p$. Putem folosi $p=2^{3072}-2^{3008}+2^{64}\,(\left\lfloor2^{2942}\,\pi\right\rfloor+1690314)-1$ al Grup MODP pe 3072 de biți, și $g=\left\retajul 2^{3070}\,e\right\rfloor$.
Calculați hash-ul $H(M)\in\{0,1\}^{512}$ a mesajului de intrare $M\în\{0,1\}^*$ după cum urmează:
- Convertiți șirul de biți $M$ la un întreg $m$ conform convenției big-endian și urmăriți lungimea biților $\ell$ de $M$.
- Calcula
$$\begin{align}
m_0&=m\bmod(p-1)\
h_0&=(g^{m_0}\bmod p)-1\
h_1&=\left\lfloor h_0/2^{1024}\right\rfloor\bmod2^{512}\
h_2&=\left\lfloor h_0/2^{1664}\right\rfloor\bmod2^{512}\
m_1&=\stânga\l etaj m/(p-1)\dreapta\retaj\
\end{align}$$
Notă: constantele 1024 și 1664 selectează poziția a două segmente arbitrare de 512 biți care nu se suprapun în reprezentarea binară a $h_0$.
- Convertit $h_1$ la șir de biți $H_1\in\{0,1\}^{512}$, $h_2$ la șir de biți $H_2\in\{0,1\}^{512}$, și $m_1$ la șir de biți $M_1\in\{0,1\}^{\ell}$ conform convenției big-endian.
- Calculați și ieșiți $H=H_1\oplus H_2\oplus\operatorname{SHA3-512}(M_1)$.
Transformarea dintre $m_0$ și $h_0$ este o bijectie a $[0,p-2]$. Dacă urmează, am putea găsi o preimagine $M$ din oricare $H\în\{0,1\}^{512}$ dacă am putea rezolva DLP-ul în grupul multiplicativ $\mathbb Z_p^*$: reparam $M_1=0^{3072}$ (prin urmare $\ell=3072$ și $m_0=m$), $h_0=2^{640}\,h_1$ (prin urmare $H_2=0^{512}$), care ne permite să calculăm $H_1=H\oplus\operatorname{SHA3-512}(M_1)$, atunci $h_1$, atunci $h_0=2^{640}\,h_1$. Rezolvăm problema DLP $(g^{m_0}\bmod p)=h_0+1$ a obține $m_0$, atunci $m$, apoi pe 3072 de biți $M$.
Argumentul meu că hash-ul este rezistent la coliziuni și rezistent la preimagine este că $M\mapsto(M_1,m_0)$ este injectiv, $m_0\mapsto H_1\oplus H_2$ pare a fi destul de greu de inversat sau de ciocnit, iar XORing asta cu un hash bun fără legătură de $M_1$ mai puțin de jumătate din rezistența la coliziune.
Există vreun beneficiu la care te poți gândi?
Nu văd niciunul tehnic real beneficiază de o funcție hash care, în mod demonstrabil, atinge tot codomeniul său, deoarece nu putem face diferența experimental cu o funcție hash standard bună fără această proprietate. Pe de altă parte, ar fi satisfăcător din punct de vedere intelectual. Problema este că orice îmi vine în minte (cum ar fi candidatul de mai sus) dacă este mai lent și mai puțin sigur la o lățime de ieșire dată decât este un hash standard și această considerație practică ponderează beneficiul intangibil de a fi sigur că toate valorile de ieșire pot fi atinse.
Nu văd niciun beneficiu pentru o funcție hash care, în mod demonstrabil, nu poate atinge o parte din spațiul său de ieșire și, astfel, este imposibil din punct de vedere computațional să afișați o astfel de valoare de ieșire sau imposibil de a spune dacă o anumită valoare a spațiului de ieșire este accesibilă.
Îmi imaginez aplicații pentru hashuri care probabil nu pot ajunge la câteva cunoscut valori în spațiul lor de ieșire (de exemplu, o astfel de valoare poate fi rezervată ca indicator al unui caz special). Pe de altă parte, putem construi cu ușurință astfel de hashe-uri din primitive standard. De exemplu, pentru un hash de 256 de biți care nu poate ajunge $0^{256}$, putem folosi (cu conversii obișnuite între șiruri de biți și numere întregi) $M\mapsto(\operatorname{SHAKE128}(M,416)\bmod(2^{256}-1))+1$. Și, în practică, am putea folosi la fel de bine orice hash standard de 256 de biți.
