TLDR: atacul luat în considerare nu este ușor. Este posibil, sau nu, în funcție de ipoteza neenunțată.
Mai întâi vom reformula întrebarea¹.
Presupunem un sistem de criptare asimetric, similar cu manualul RSA, cu
- generarea de chei a unei perechi de chei publice/private $(\mathrm{pk},\mathrm{sk})$,
- criptare $c:=E_\mathrm{pk}(p)$ Unde $p$ este textul simplu, $c$ este textul cifrat
- decriptarea potrivirii $p:=D_\mathrm{sk}(c)$ care funcționează pentru toți $c$ obtinut ca $E_\mathrm{pk}(p)$
- Unde $p$ și $c$ sunt dintr-un interval comun $[0,n)$, cu $n$ încorporate în $\mathrm{pk}$ și $\mathrm{sk}$.
Presupunem că acest sistem de criptare este securizat atac de text clar cunoscut.
Ne asumăm un ideal funcția hash $\operatorname{Hash}$ cu ieșire în $[0,h)$, cu $h\le n$ pentru toți $(\mathrm{pk},\mathrm{sk})$ sistemul de criptare generează.
Deducem a semnatura digitala schema unde
- generarea cheilor este ca în criptare
- semnătura mesajului $m$ este $s=D_\mathrm{sk}(\operatorname{Hash}(m))$
- procedura de verificare $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ iesiri Trece dacă $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$, sau Eșuează in caz contrar.
Subliniez că aceasta nu este o modalitate obișnuită de a construi semnătura: nicio schemă de semnătură în uz pe scară largă nu se potrivește destul de², și multe precum DSA, ECDSA, EdDSA sunt foarte diferite.
Întrebarea se întreabă dacă un hacker poate selecta $m$ și $s$ astfel încât $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ ieșire Trece, adică așa încât $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$.
Vești bune: sistemul de semnătură verifică cu succes atunci când mesajul și semnătura sunt nemodificate. Argument: deoarece setul de intrare și ieșire de criptare $E_\mathrm{pk}$ sunt aceleași și există o funcție de decriptare $D_\mathrm{sk}$ care inversează $E_\mathrm{pk}$ pentru toți $p$, ambii $E_\mathrm{pk}$ și $D_\mathrm{sk}$ sunt permutări ale acelui set, una inversă celeilalte. Asa pentru toti $c$ în acel set îl ține $E_\mathrm{pk}(D_\mathrm{sk}(c))=c$. Aplicând aceasta cu $c=\operatorname{Hash}(m)$, care condiția $h\le n$ face posibil pentru toti $m$, înțelegem asta $E_\mathrm{pk}(s)=E_\mathrm{pk}(D_\mathrm{sk}(\operatorname{Hash}(m)))=\operatorname{Hash}(m)$, prin urmare $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ ieșire Trece.
Mai multe vești bune: nu este ușor pentru adversarii posesor de $\mathrm{pk}$ a selecta $m$ și $s$ astfel încât $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$. Nimic simplu nu pare să funcționeze:
- Când adversarii aleg prima dată arbitrar $m$, și calculați $c=\operatorname{Hash}(m)$, acea $c$ este asemănător aleatoriu, cu excepția faptului că se află în submulțimea inferioară $[0,h)$ de $[0,n)$. Când vor mai încerca să găsească $s$ cu $c=E_\mathrm{pk}(s)$, ei se confruntă, în esență, cu problema decriptării unui text cifrat arbitrar, și asta este greu (se poate dovedi că descifrarea unui text cifrat arbitrar trebuie să fie dificilă în ipoteza KPA pe care am făcut-o despre cifru).
- Când adversarii aleg prima dată arbitrar $s$ și calculează $E_\mathrm{pk}(e)$, primesc o valoare arbitrară $c$ în $[0,n)$. Nu există asigurare asta $c$ este în raza de acțiune $[0,h)$ (și dacă nu, nu poate fi hash-ul niciunui mesaj $m$). Chiar dacă adversarii pot rezolva acest obstacol alegând $s$ astfel încât $c$ este în raza de acțiune $[0,h)$ (care manual RSA permite, de exemplu, prin realizarea $s=0$ sau $s=1$), o funcție hash ideală este de așa natură încât este greu de găsit din punct de vedere computațional $m$ care hashes la o valoare dată arbitrară $c$ în intervalul de ieșire al hash-ului: aceasta este prima rezistență preimagine a hash-ului.
- Când adversarii pun mâna pe a $(m,s)$ pereche care trece verificarea, ar putea încerca să găsească $m'$ în afară de $m$ cu $\operatorname{Hash}(m')=\operatorname{Hash}(m)$, care ar asigura că $(m',s)$ trece verificarea. Dar o funcție hash ideală este de așa natură încât este dificil din punct de vedere computațional să faci asta: aceasta este a doua rezistență preimagine a hash-ului.
- Adversarii ar putea încerca să creeze două mesaje distincte $m$ și $m'$ cu $\operatorname{Hash}(m)=\operatorname{Hash}(m')$, obțineți semnătura $s$ de $m$, și astfel ar fi falsificat altul $(m',s)$ care trece verificarea. Acest lucru este mult mai ușor decât atacurile anterioare (de exemplu, acest lucru este fezabil cu SHA-1 ca $\operatorname{Hash}$, când niciun atac anterior nu este fezabil), dar totuși o funcție hash ideală este de așa natură încât este dificil din punct de vedere computațional să faci asta: aceasta este rezistența la coliziune a hash-ului.
Cele de mai sus nu constituie o dovadă validă de securitate și, mai rău: ar fi dovedit greșit să concluzi că sistemul de semnătură este sigur. În special, cu $h=2^{256}$ (de exemplu, hash-ul este SHA-256) și atunci când sistemul de criptare este manual RSA, acest sistem de semnătură este vulnerabil la o falsificare imaginabilă. Să presupunem un sistem cu cupoane $m$ a formei
A Cupon în valoare de 123.456,78 USD, referință 4C0D5F62CAF6AF32
Să presupunem că semnatarul verifică că a propus $m$ este un cupon bine formatat, că referința sa este unică, primește plata prețului indicat, iar în aceste condiții semnează $m$. The Desmedt și Odlyzko atacă lăsați adversarii să joace acest sistem, cumpărând semnături de cupoane cu valoare redusă și folosind aceste semnături pentru a găsi semnătura unui cupon de valoare mare.
Vești mai bune: cu unele ipoteze adăugate este posibil dovedi că acest sistem de semnătură este sigur. O ipoteză care funcționează pentru RSA este aceea $h$ are aproape tot atâtea biți ca $n$. Acest sistem de semnătură este cunoscut ca Hash de domeniu complet. Dovada este grea, atât de mult încât atunci când FDH a fost luat în considerare pentru prima dată de Mihir Bellare și Peter Rogaway: Securitatea exactă a semnăturilor digitale - Cum să semnați cu RSA și Rabin, în procedurile Eurocrypt 1996, nu au putut dovedi un nivel de securitate satisfăcător (și au conceput un sistem de semnătură mai complex: RSA-PSS, baza pe scară largă RSASSA-PSS). Un nivel de securitate mai bun a fost obținut ani mai târziu de Jean-Sébastien Coron: Despre securitatea exactă a hashului de domeniu complet, în procedurile Crypto 2000 (dar semnătura RSA se stabilizase deja și FDH nu este utilizat pe scară largă).
¹ Principalele diferențe cu formularea întrebării:
- Semnăm cu decriptarea, nu cu criptarea, deoarece criptarea cu cheia privată și posibilitatea de a decripta cu cheia publică contrazice scopul criptării. De asemenea, nu funcționează în practică, inclusiv cu RSA așa cum este implementat, chiar dacă eliminăm pașii de completare: formatul cheii publice este $(n,e)$ adesea cu o limită de mărime pt $e$, formatul cheii private este $(n,e,d,p,q,d_p,d_q,q_\text{inv})$și încercarea de a împinge cheia publică acolo unde este așteptată cheia privată, sau invers, va eșua.
- Specificăm un set finit de text cifrat de aceeași dimensiune ca și setul de text simplu, prin urmare criptarea deterministă, altfel generarea sau verificarea semnăturii ar eșua uneori în condiții normale de utilizare.
- Facem din mesaj o intrare a procedurii de verificare, pentru că așa este definită semnătura în teorie și implementări practice moderne.
² RSASSA-PKCS1-v1_5 este singurul pe care îl știu care se apropie, oricum ar fi $\operatorname{Hash}$ este construit prin concatenarea unui prefix în funcție de dimensiunea biților a $n$ și $H(m)$, Unde $H$ este un hash standard, cum ar fi SHA-256, deci $\operatorname{Hash}$ nu este o funcție hash ideală, deoarece este de așteptat să apară aleatoriu pe domeniul său de ieșire.
