Reducere de la multi-utilizator la un singur utilizator
În primul rând, observați că există o reducere între securitatea multi-utilizator și securitatea standard pentru un singur utilizator pentru schema de semnătură:
s-a dovedit în 2002 de către Galbraith, Malone-Lee și Smart (GSM) care pentru orice sistem de semnătură, atacând schema în setarea multi-utilizator cu $N$ cheile publice nu pot crește rata de succes a atacatorului (care este raportul dintre probabilitatea de succes și timpul de rulare) cu un factor mai mare de $N$ comparativ cu atacarea schemei în setarea cu un singur utilizator.
Acesta este un rezultat puternic, folosind notația dvs. înseamnă aproximativ că în setarea MU limita dvs. este delimitată de $\frac{Nt}{2^k}$ este tu $\frac{t}{2^k}$ în setarea SU.
DAR nu cunoaștem niciun atac practic care să realizeze un astfel de bound for scheme de semnătură. Observați că dacă ar fi cazul, dacă am avea un N mare, cum ar fi 2^32 de exemplu, impactul asupra securității schemelor de semnătură ar fi uriaș!
De obicei preferăm mai strâns reduceri.
Observați că atacă împotriva schemelor de semnătură într-un cadru multi-utilizator nu trebuie amestecate cu atacuri împotriva MAC-uri în acel cadru, care nu sunt neapărat la fel de bune ca schemele de semnătură așa cum se discută în excelentul "O altă privire la Tightness„Lucrare de Chatterjee, Menezes și Sarkar și continuarea acesteia”O altă privire la Tightness II". Ambele sunt lecturi excelente pe acest gen de probleme.
Vă recomand să citiți și „Securitatea schemelor de semnătură într-o setare cu mai mulți utilizatori" de Menezes și Smart din 2004, deoarece se referă la definițiile de securitate în setarea MU pentru schemele de semnătură:
susținem că definiția de securitate bine acceptată pentru schemele de semnătură (nefalsificarea existențială împotriva atacurilor adaptive cu mesaje alese) de Goldwasser et al. [18] nu este adecvat pentru setarea multi-utilizator. Din fericire, se pare că această definiție poate fi extinsă cu ușurință pentru a lua în considerare aceste atacuri în setarea multi-utilizator.
Ei sunt, de asemenea, preocupați de așa-numitele „atacuri de substituție cheie”, care sunt acoperite de definițiile lor.
Cel mai remarcabil (sublinierea mea):
În Secțiunea 2.2, am susținut că un adversar al unei scheme de semnătură în setarea multi-utilizator are succes dacă produce o falsificare existențială sau o înlocuire a cheii. În ambele cazuri, atacul este împotriva unei anumite chei publice. Prin urmare, este suficient să luăm în considerare setarea multi-utilizator în care există inițial o singură cheie publică. Acest lucru este fără pierderi de generalitate deoarece adversarul care atacă o entitate poate simula celelalte entități prin alegerea cheilor lor publice, astfel încât să cunoască cheile private corespunzătoare..
Evident, de asemenea, un adversar în setarea cu un singur utilizator se reduce în mod natural la unul în setarea cu mai mulți utilizatori.
Și ajung la concluzia că nu există real nevoie să ne îngrijorăm de setarea multi-utilizator pentru schemele de semnătură de îndată ce le putem lega la o cheie publică și avem un rezultat foarte interesant:
Schemele de semnătură care sunt sigure în setarea cu un singur utilizator pot fi transformate cu ușurință în scheme care sunt sigure în conformitate cu noua noastră definiție în setarea cu mai mulți utilizatori, prin hashing cheia publică împreună cu mesajul atunci când se calculează rezumatul mesajului
N.B.: acest lucru explică în mod deosebit de ce adăugăm cheia publică la rezumatul mesajului în schema de semnătură „de tip Schnorr”.EdDSA".
(De fapt, ar putea fi și pentru că DJB a găsit un defect în reducerea de la setarea cu un singur utilizator la setarea multi-utilizator care fusese dată de GSM în 2002, dar între timp avem o alta dovada asta arată că nu este necesar pentru semnăturile Schnorr... Dar DJB a făcut experimente atunci când a creat EdDSA, cred ;))
Modelul de atac multi-utilizator pentru scheme de semnătură
De asemenea, vă rugăm să observați că modelul de atac pentru falsuri în setarea multi-utilizator este că adversarul este dat $n$ semnarea oracolelor, câte unul pentru fiecare cheie publică, și are voie să facă cel mult $q$ întrebări la aceste oracole.
La sfârșitul atacului, adversarul trebuie să iasă (cel mult cu probabilitate $\epsilon$) un tuplu care conține:
- unul dintre $n$ chei publice, $y$
- un mesaj $m$
- o semnatura $\sigma$,
astfel încât semnătura $\sigma$ este valabil pentru mesaj $m$ sub cheia publică $y$.
Unde $m$ nu ar fi trebuit să fie o interogare către oracolul de semnare corespunzător acelei chei $y$.
Securitatea unei astfel de scheme este apoi definită în funcție de $q$, $n$.
Acest model este cunoscut sub numele de „nefalsificarea multi-utilizator împotriva atacurilor cu mesaje alese” (MU-UF-CMA).
Despre semnificația securității pentru schemele de semnătură
De asemenea, înainte de a „defini” securitatea pentru schema de semnătură în orice setare, trebuie să știm „ce fel de securitate” încercăm să obținem.
Este frumos să spunem că „schema de semnătură oferă k-biți de securitate în setarea cu un singur utilizator”, dar împotriva ce fel de atacuri?
Pe acest subiect, hârtie seminală de Goldwasser, Micali și Rivest este o lectură bună, deși puțin învechită și puțin lipsită de setarea multi-utilizator cu siguranță.
Cea mai comună noțiune de securitate pentru schema de semnătură se numește „EUF-CMA”, ceea ce înseamnă „nefalsificare existențială în cazul atacurilor adaptive cu mesaje alese”, adică ar trebui să fie dificil pentru un adversar să vină cu un mesaj „falsificat” pentru un cheia publică dată.
(Există și o noțiune de SUF-CMA „Strong Existential Unforgeability sub Chosen Message Attack”, care încearcă să reducă maleabilitatea schemelor de semnătură)
Dar într-un cadru multi-utilizator, există o altă noțiune care este interesantă și anume aceea de „Atacurile de înlocuire cheie" (KSA), unde putem genera o nouă cheie publică care ar verifica, de asemenea, o pereche dată (mesaj, semnătură). Și există atacuri de înlocuire a cheilor în schemele de semnătură EUF-CMA sigure! (De exemplu, în NTRUSign sau în „Scurt schema de semnături fără oracole aleatorii)
Ceea ce este cu adevărat interesant cu KSA, este că a semnatar rău intenționat poate fi și actor într-un astfel de decor!
Pe k-biți de securitate
În cele din urmă, „a avea k-biți de securitate” este într-adevăr împotriva unui model de atac (dar care?) și este de fapt o modalitate pentru noi comparaţie Criptografia cu cheie publică cu atacuri cripto/bruteforce cu cheie simetrică. Este o modalitate prin care obișnuim să avem o metrică care ne permite să le comparăm, dar uneori este destul de dificil de evaluat în termeni absoluti.
Există hârtii precum cele de pe https://www.keylength.com/ care vă permit să vedeți diferitele moduri pe care le avem de a „estima” securitatea cripto-ului asimetric în comparație cu cea a cripto-ului simetric și, după cum puteți vedea acolo, valorile se schimbă de la o hârtie la alta.
În cele din urmă, ceea ce încercăm să evaluăm cu metrica k-bit este dificultatea de a întrerupe o schemă în comparație cu un atac bruteforce. (Iti recomand sa citesti acest eseu de DJB asupra atacurilor bruteforce.)
Dar asta e folosirea celor mai bune cunoscut atacuri împotriva acestor scheme de chei publice și, prin urmare, nu este absolut, este o măsură relativă.
Definiția ta, folosind $t/2^k$ este aproximativ cel al unui atac bruteforce:
numărul de încercări împărțit la „numărul maxim”.
Deci, ceea ce spui este, practic, că definim „a avea k-biți de securitate” ca fiind „la fel de dificil ca un atac bruteforce asupra unei chei de k-biți”, cu care sunt pe deplin de acord. Noi facem.
Dar o „definiție corectă tipică a Securitate" pentru schemele de semnătură cu cheie publică nu se va baza pe acea noțiune de "biți de securitate". Are încă noțiunea de parametru de securitate $k$ și încă folosește o valoare $\mathbb{1}^k$ ca intrare de obicei, dar este folosit ca o modalitate de a limita adversarul să facă mai puțin decât un simplu atac bruteforce și, prin urmare, este, de asemenea, o intrare pentru adversar, dar ar fi definit folosind un model de atac, cum ar fi mai sus.
Acesta este motivul pentru care am discutat anterior despre „modelul de atac” și nu vă pot oferi o definiție mai bună decât „Da, sigur: în mod ideal, bruteforce ar trebui să fie de aceeași dificultate ca în setarea cu un singur utilizator pentru falsuri în cea cu mai mulți utilizatori”.
Dar din moment ce nu avem o reducere generală „la fel de strânsă” decât atât, nu putem spune cu siguranță dacă este de fapt cazul sau nu în general. Dar cu siguranță este cazul semnăturilor Schnorr ca ambele de mai sus legat hârtii.
Observați că răspunsul lui fgrieu sugerează și acea noțiune de etanșeitate, dar din punct de vedere invers.
