Mulțumită Samuel Neves pentru că m-a îndreptat în direcția corectă. Am aruncat o privire la referinta mentionata, și se referă la modul în care Teorema 6.1 eșuează pentru securitate slabă. De asemenea, acoperă un MAC care este slab sigur fără interogări de verificare, dar își pierde securitatea în prezența interogărilor de verificare.
De ce se defectează teorema 6.1
Am descoperit că subtilitatea apare în modul în care sunt definite jocurile de atac. Adversarul poate trimite orice pereche mesaj-etichetă $(m, t)$ pentru verificare atâta timp cât nu se află printre perechile semnate anterior. Ceea ce este important este că, în definiția originală a securității, adversarul câștigă jocul de atac dacă și numai dacă adversarul trimite o pereche de mesaj-etichetă validă, nevăzută anterior, pentru verificare. Echivalența rezultă din definiția condiției câștigătoare.
Cu toate acestea, în condiții de securitate slabă, direcția înainte rămâne valabilă (trimiterea unui mesaj valid $(m, t)$ pereche unde $m$ nu a fost văzut niciodată înainte formează clar o pereche validă niciodată văzută înainte), dar direcția înapoi eșuează. Direcția înapoi ar putea eșua deoarece adversarul ar putea obține a $(M, T)$ pereche dintr-o interogare de semnare și apoi trimiteți o interogare validă $(M, \bar{T})$ pereche prin modificarea etichetei $T$. $(M, \bar{T})$ este o pereche validă și nevăzută anterior, dar adversarul nu reușește să câștige deoarece perechea implică un mesaj care a fost semnat anterior.
În cazul în care Teorema 6.1 eșuează pentru securitate slabă este atunci când autorii susțin $\text{Pr}[W_0] = \text{MAC}^\text{vq}\text{adv}[\mathcal{A, I}]$ care presupune că câștigarea jocului de atac este echivalent cu prezentarea unei perechi mesaj-etichetă validă, nevăzută anterior. În exemplul extrem de mai sus, acesta nu este cazul, așa cum este posibil $W_0$ să apară, dar fără a câștiga jocul de atac de securitate slab.
Cum se rezolvă exercițiul
În ceea ce privește cum să construiți un sistem MAC care este slab sigur fără interogări de verificare, dar nu este slab sigur cu interogări de verificare, în principiu, construiți un sistem în care după ce primiți $(M, T)$ dintr-o interogare de semnare un adversar poate construi cu ușurință valid $(M, \bar{T})$ perechi. Prezentând aceste perechi valide, dar necâștigătoare, adversarul învață suficiente informații pentru a sparge sistemul MAC.
Lăsa $\mathcal{K} = \{0,1\}^\ell$ și $|\mathcal{T}|$ fii super-poli. Lăsa $F$ fi un PRF definit peste $(\mathcal{K, M, T})$, $k \stackrel{R}{\gets} \mathcal{K}$ și $\mathcal{I} = (S, V)$ fi un MAC definit peste $(\mathcal{K, M, T} \times \{\perp, 0,\ldots,\ell-1\})$. Algoritmul de semnare este definit a fi $S(m) = (F(k, m), \perp)$ iar algoritmul de verificare este
V(m, (t, i))
// Validați eticheta față de PRF
d = F(k, m) == t
dacă !d sau i == â
întoarce d? accept : respinge
// Returnează bitul al cheii
returnează k[i] == 1 ? accept : respinge
Proprietatea corectitudinii este valabilă deoarece a doua componentă a $S(m)$ este $\perp$ care intră în instrucțiunea if. Acest sistem MAC este în esență sistemul determinist MAC derivat din $F$ dar cu un câmp index suplimentar.
Mai întâi observăm asta $\mathcal{I}$ este slab sigur fără interogări de validare. Dacă un adversar câștigă, atunci adversarul a trimis o pereche validă $(m, (t, i))$ Unde $m$ nu a fost văzută înainte. Acest lucru înseamnă $\textsf{accept}$ a fost returnat ceea ce presupune $d$ este adevărat în $V(m, (t, i)))$ (fie declarația if a fost introdusă unde $\textsf{accept}$ a fost returnat sau instrucțiunea if nu a fost executată, ceea ce implică $d$ nu a fost fals). Acest lucru se întâmplă cu o probabilitate neglijabilă prin Teorema 6.2 ca $d$ fiind adevărat înseamnă că s-a făcut un fals împotriva MAC-ului determinist derivat din $F$ (acest MAC este securizat conform definiției mai puternice a securității).
In orice caz, $\mathcal{I}$ nu este slab sigur cu interogările de verificare. Un adversar care rupe securitatea este
Fie m un mesaj arbitrar
Obțineți (m, (t, â)) de la contestator
k[0..l-1] = 0
pentru i = 0 .. l-1
Fie r răspunsul contestatorului la interogarea de validare (m, (t, i))
dacă r == accept
k[i] = 1
altfel
k[i] = 0
// Cheia a fost reconstruită
Fie m' un mesaj arbitrar care nu este egal cu m
// Calculați eticheta lui m' cu cheia reconstruită
Fie t' = S(m')
Trimiteți interogarea de validare (m', (t', â)) contestatorului
