Ce înseamnă nefalsificarea existențială într-o schemă de semnătură digitală?

Într-o schemă de semnătură digitală (Gen, Sign, Verfiy) care satisface corectitudinea și nefalsificarea existențială, puteți presupune că rezultatele lui Sign() nu se pot distinge din punct de vedere computațional de aleatorii?

Ce înseamnă nefalsificarea existențială într-o schemă de semnătură digitală?

Numai „nefalsificarea existențială” înseamnă că adversarii nu pot crea semnături care să verifice mesajele pentru care nu au deja o semnătură. Strict vorbind, spargerea de nefalsificat existențial poate numai Adversarii medii ajung să aibă un mesaj și o semnătură care se verifică, dar mesajul este fără nicio utilitate pentru adversari.

Există, de asemenea, „nefalsificare existențială puternică”, ceea ce înseamnă, în plus, că adversarii nu pot crea semnături noi care să verifice, împotriva oricărui mesaj. ECDSA este un exemplu de schemă cu infalsabilitate existențială, dar nu cu nefalsabilitate existențială puternică. Asta pentru că dacă $(r,s)$ este o semnătură validă pentru un mesaj, apoi pentru altul $(r,n-s)$ este valabil și pentru același mesaj.

Adjectivul „existențial” se opune obiectivului mai dificil pentru adversari de a semna un mesaj pe care ei aleg, în întregime („fals selectiv”) sau parțial (de exemplu, alegerea unui prefix al documentului), să aibă un sens util pentru un scop nefast împotriva sistemul utilizând semnătură digitală.„Existențial” se referă la faptul „există” o pereche (mesaj, semnătură) cu mesaj nou (sau/și semnătură nouă) care trec verificarea în ceea ce produc adversarii.

„Nefalsificarea existențială” este adesea urmată de „atacul sub mesajul ales”, adică se presupune că adversarii pot obține semnături pentru mesajele la alegere. Mesajele pe care le trimit spre semnare sunt reduse față de cele care sunt considerate falsuri reușite. În falsificarea existențială puternică, semnăturile pe care le obțin în acest fel sunt în mod similar reduse. Atacul cu mesajul ales se opune perechilor cunoscute (mesaj, semnătură) și atacului fără mesaj.

Este obișnuit ca o falsificare existențială să poată fi extinsă la mesaje semnificative sau exploatată într-un fel ocolitor (cum ar fi o depășire a tamponului, refuzul serviciului sau injectarea de cod). De asemenea, este obișnuit ca adversarii să influențeze suficient mesajele care sunt semnate pentru a face posibil un atac, chiar dacă acesta nu se califică drept un atac cu drepturi depline cu mesajul ales. Există, de asemenea, pericolul ca adversarii să pretindă că alți adversari au distrus securitatea, rupând încrederea în sistem. Prin urmare, a devenit linia de bază pentru a solicita Existential UnForgeability în cazul unui atac cu mesaje alese (EUF-CMA). Acest lucru protejează în mod adecvat împotriva modificării mesajului fără aprobarea deținătorului unei chei publice.

ma refer la acest raspuns pentru o taxonomie mai formală a variantelor UF.

Cea mai bună practică pentru schemele moderne de semnătură este puternic EUF-CMA, plus Rezistență la coliziune caracteristică, și Proprietate exclusivă universală. Vedeți Dennis Jackson, Cas Cremers, Katriel Cohn-Gordon și Ralf Sasse: Pare legitim: Analiza automată a atacurilor subtile asupra protocoalelor care folosesc semnături, în Arhiva Cryptology ePrint, Raport 2019/779, inițial în procedurile ACM CCS 2019.

Într-o schemă de semnătură digitală (Gen, Sign, Verfiy) care satisface corectitudinea și nefalsificarea existențială, puteți presupune că rezultatele lui Sign() nu se pot distinge din punct de vedere computațional de aleatorii?

Nu. De exemplu RSASSA-PSS este probabil sEUF-CMA, dar semnăturile sale se pot distinge de aleatoriu (prin examinarea bitului de ordin înalt al primului octet al semnăturii nedecorate, care este orientat spre 0, cu excepția cazului în care cheia publică are mulți biți de ordin înalt la 1, sau/ și ceva în procedura de semnătură este conceput pentru a face o astfel de părtinire mai puțin detectabilă; ceea ce este ușor, dar neobișnuit). Asta chiar și fără cheia publică sau mesajul. Evident, dacă cheia publică și mesajul sunt cunoscute, nicio schemă de semnătură corectă nu poate avea semnătura care nu poate fi distinsă de aleatorie; verificatorul este un distins!

În mod informal, este incapacitatea unui atacator de a falsifica o semnătură pentru orice mesaj, care nu este semnat de un semnatar legitim. Acum, pentru a evalua unforgeability existențial (UE) a unei scheme de semnătură, avem nevoie de un adversar cu un model de atac.

1. Atac numai cu cheie (EU-KOA): În mod informal, adversarul are doar o cheie publică și are voie să aleagă orice mesaj pentru falsificarea semnăturii după obținerea cheii publice

$(pk,sk)\leftarrow Gen$

Fugi adversarul $A(buc,1^n)$

Obține răspuns $(m,s) $ ca pereche de semnătură a mesajului pentru adversar

2. Atac cu mesaje cunoscute (EU-KMA): În mod informal, adversarul are acces la multe mesaje, perechi de semnături împreună cu cheia publică înainte de care poate folosi ca informații pentru a falsifica semnătura pe orice alt mesaj.

$(pk,sk)\leftarrow Gen$

Fugi adversarul $A(buc,1^n)$

Genera $m_1,m_2...m_k$ mesaje și semnați-le pe toate. Trimite perechi mesaj-semnătură $(m_1,s_1),(m_2,s_2)...(m_k,s_k)$

Obține răspuns $(m,s) $ ca pereche de semnătură de mesaj pentru adversar unde $m \notin {m_1,m_2..m_k}$

3. Atacul cu mesaje alese (CMA): în mod informal, adversarul poate obține semnături pentru mesajele la alegere. Modelăm acest lucru dând adversarului acces la un oracol de semnare. $(pk,sk)\leftarrow Gen$

Fugi adversarul $A(pk,1^n,O^{sk})$ Aici $O^{sk}$ semnează oracol

Interogări adversare $m_1,m_2...m_k$ mesaje către $O^{sk}$ și obțineți semnături. Mesajele pot fi alese adoptiv. Adversarul obține perechi mesaj-semnătură $(m_1,s_1),(m_2,s_2)...(m_k,s_k)$

Obține răspuns $(m,s) $ ca pereche de semnătură de mesaj pentru adversar unde $m \notin {m_1,m_2..m_k}$

Inutil să spunem că numărul și lungimea mesajelor sunt de funcție polinomială a unui parametru de securitate, precum și orice calcul pe care îl efectuează un adversar este timp polinomial. Schema de semnătură nu este de nefalsificat existențial sub niciun model de atac, dacă adversarul reușește să răspundă cu o pereche de semnături de mesaj validă cu o probabilitate deloc neglijabilă.

Este diferită de falsificarea selectivă în care atacatorul nu poate alege liber mesajul pentru care să falsească semnătura după începerea atacului și de falsificarea universală în care mesajul pentru care să falsească semnătura este furnizat adversarului (care implică faptul că atacatorul poate falsifica semnătura pentru orice mesaj chiar furnizat de altcineva).