Problema criptografului dining

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 5 octombrie 2020; verificările necesită 3 modificări .

Problema criptografului dining este despre modalități de a evalua în siguranță o funcție booleană OR în multe feluri . David Chaum a identificat prima dată această problemă în 1988 și a folosit un exemplu ilustrativ pentru a arăta că este posibil să se trimită mesaje anonime fără restricții privind expeditorul și imposibilitatea de urmărire a adresei destinatarului [1] [2] . Rețelele de comunicații anonime capabile să rezolve această problemă sunt adesea denumite rețele DC .

În ciuda cuvântului „diner”, problema criptografilor dining nu are nimic de-a face cu problema filozofilor dining .

Descriere

Trei criptografi s-au adunat la masă. Chelnerul îi anunță că mâncarea lor a fost deja plătită de cineva. Ar putea fi unul dintre criptografi sau Agenția Națională de Securitate (NSA). Criptografii respectă dreptul unui prieten de a efectua o plată în mod anonim, dar vor să afle dacă Agenția Națională de Securitate a plătit. Așa că decid să implementeze un protocol în doi pași.

În primul pas, la fiecare doi criptografi au determinat un secret comun de un bit, acceptând să arunce o monedă. S-au ascuns în spatele meniului în așa fel încât doar cei doi criptografi care aruncă pot vedea rezultatul aruncării. Să presupunem că după aruncarea unei monede criptografii A și B au un secret comun - , criptografii A și C - , B și C - .

În al doilea pas, fiecare criptograf anunță public un bit, care se calculează după cum urmează:

Să presupunem că niciunul dintre criptografi nu a plătit, atunci criptograful A va anunța , B va anunța , C - . Pe de altă parte, dacă criptograful A a făcut o plată, el va anunța .

La sfârșitul celei de-a doua etape, adevărul este dezvăluit. Unul dintre criptografi efectuează operația XOR a tuturor biților declarați. Dacă rezultatul este , atunci aceasta înseamnă că niciunul dintre criptografi nu a plătit (deci putem concluziona că plata a fost făcută de NSA). În caz contrar, dacă unul dintre criptografi a plătit, atunci identitatea lui rămâne necunoscută tuturor celorlalți colegi.

Pentru această problemă, David Chaum a inventat termenul „Dinner Cryptographer Problem”, precum și un nume pentru rețelele capabile să rezolve această problemă [2] [3] .

Restricții

Lucrarea originală a lui David Chaum postulează câteva limitări care pot afecta utilizarea practică a protocolului de rețea DC.

Ciocniri Dacă doi criptografi au plătit pentru prânz, atunci mesajele lor se vor suprapune, iar rezultatul operațiunii XOR pentru perechea în cauză va fi 0. Această situație se numește coliziune, caz în care doar un participant plătitor are voie să folosească acest lucru. protocol pentru a-și transmite mesajul în runda curentă [4] [2] . Încălcări Orice criptograf rău intenționat care nu dorește ca grupul să comunice cu succes poate bloca protocolul, astfel încât rezultatul final al operațiunii XOR să fie inutil. Este posibil să comiteți o atrocitate prin trimiterea de biți arbitrari în loc de rezultatul corect al operației XOR. Această problemă apare deoarece protocolul original a fost conceput fără un mecanism care să verifice dacă participanții respectă protocolul în mod corect [5] [2] [6] . Complexitate Protocolul necesită secrete partajate în perechi între participanți, ceea ce este dificil atunci când există un număr mare de participanți [7] [8] .

Generalizări

Rețelele DC sunt generalizate pentru a furniza transmisii mai mari de un bit pentru mai mult de trei participanți și pentru litere arbitrare ale alfabetului, altele decât binarul 0 și 1.

Trimiterea de mesaje lungi

Pentru ca un expeditor anonim să poată transmite mai mult de un bit de informație într-o rundă de execuție a protocolului de rețea DC, un grup de criptografi pot repeta pur și simplu protocolul de câte ori este necesar pentru a crea numărul dorit de biți ( pe baza lăţimii de bandă a canalului). În rețelele DC, perechile de participanți au posibilitatea de a conveni în prealabil asupra unei chei comune, folosind, de exemplu, o cheie obținută folosind protocolul Diffie-Hellman . Fiecare participant setează apoi această cheie partajată local într -un generator de numere pseudo-aleatoare pentru a produce cât mai multe „coin flips” comune posibil, permițând expeditorului anonim să transmită câțiva biți de informații [9] [2] .

Mai mulți membri

Protocolul poate fi aplicat unui grup format din participanți, fiecare dintre care împărtășește o cheie secretă cu restul participanților. În fiecare rundă a protocolului, dacă un participant dorește să trimită un mesaj care nu poate fi urmărit către întregul grup, el își inversează biții anunțați public. Participanții pot fi reprezentați ca un grafic complet , unde vârfurile sunt participanții și marginile sunt cheile lor secrete partajate [2] [4] .

Grafic de acces partajat

Protocolul poate fi rulat folosind un grafic incomplet al cheii publice, care poate îmbunătăți performanța și scalabilitatea rețelelor practice DC. Cu toate acestea, în cazul utilizării unui grafic incomplet, există riscul ca participanții la coluziune să poată împărți graficul de partajare în componente separate de conectivitate și să realizeze încălcarea anonimatului. De exemplu, pentru un grup de mai mult de trei participanți, opțiunea de topologie în inel este atractivă , unde fiecare criptograf care stă la masă împărtășește o cheie secretă numai cu colegii care stau imediat la stânga și la dreapta lui. Această topologie este atractivă, deoarece fiecare criptograf trebuie să coordoneze două aruncări de monede într-o rundă, mai degrabă decât aruncări, așa cum este cazul în cazul graficului cheie complet original. Cu toate acestea, dacă agenții NSA Adam și Charlie, așezați imediat la stânga și la dreapta lui Commoner Bob, ar fi să se complice în secret și să-și dezvăluie cheile secrete unul altuia, atunci ar putea determina cu certitudine dacă Bob este expeditorul mesajului curent din bitul din în cadrul rundei în cauză, indiferent de numărul total de participanți. Acest efect se datorează faptului că participanții conspirați, Adam și Charlie, „împart” graficul de acces public în două componente disparate independente, dintre care una este formată doar din Bob, cealaltă din toți ceilalți participanți onești [5] .

O altă topologie a rețelei publice DC utilizată în sistemul Dissent pentru scalare [10] poate fi descrisă ca o topologie client-server . Această opțiune definește două tipuri de participanți care joacă roluri diferite: un număr potențial mare de utilizatori care doresc să rămână anonimi și un număr mult mai mic de persoane de încredere al căror rol este de a asigura anonimatul tuturor utilizatorilor. Într-o astfel de topologie, fiecare dintre utilizatori partajează o cheie secretă cu fiecare dintre părțile de încredere, dar utilizatorii nu împărtășesc cheile secrete între ei în mod direct, la fel cum mandatarii nu partajează cheile secrete între ei - rezultatul este un matricea de interacțiune . Dacă numărul de persoane de încredere este mic, atunci fiecare utilizator trebuie să cunoască doar câteva secrete partajate, ceea ce îmbunătățește eficiența interacțiunii utilizatorului în același mod ca și în topologia inelului. Cu toate acestea, atâta timp cât cel puțin un membru al persoanei de încredere este cinstit și nu își dezvăluie secretele sau nu se complică cu alți membri, acest administrator onest devine un hub care conectează toți utilizatorii onești într-unul care interacționează cu toate părțile sale la componentă, indiferent dacă alți utilizatori sau persoane de încredere au intrat în coluziune necinstită. Utilizatorii nu trebuie să știe sau să ghicească care confidenti sunt sinceri; siguranța acestora, potrivit autorilor protocolului, depinde doar de existența a cel puțin unui împuternicit cinstit, neconluzitor.

Alfabete și operatori alternativi

Deși protocolul simplu de rețea DC folosește binar ca alfabet de transmisie și operatorul XOR pentru a combina textele cifrate, protocolul de bază adoptă oricare alfabet și folosește operatori asemănători XOR validi pentru utilizarea în criptarea Werman . O astfel de flexibilitate apare în mod natural, deoarece secretele sunt distribuite între multe perechi de participanți, care, de fapt, implementează criptarea Verman între ei într-o rundă a rețelei DC [11] .

O alegere alternativă a alfabetului de rețea DC este utilizarea unui grup finit potrivit pentru utilizarea în criptografia cu cheie publică. De exemplu, este acceptabil să folosiți grupuri Schnorr sau curbe eliptice . Această alegere a alfabetului permite participanților să utilizeze dovezi de zero cunoștințe pentru a verifica textul cifrat produs de protocol. În special, se verifică dacă unul dintre participanți încalcă protocolul, iar anonimatul oferit de rețeaua DC este respectat în timpul verificării. Această tehnică a fost propusă pentru prima dată de Goll și Juels [12] și implementată în Verdict , o implementare a Dissent [13] .

Evitarea și manipularea coliziunilor

Lucrarea originală a lui Chaum propune următoarea metodă de gestionare a coliziunilor. Utilizatorul care trimite în prezent un mesaj în rețeaua DC primește bitul rezultat în fiecare rundă a transmisiei sale. Dacă bitul rezultat nu se potrivește cu cel pe care dorește să-l transmită în runda curentă, utilizatorul ajunge la concluzia că a avut loc o coliziune. Așteaptă un număr aleator de runde și își retrimite mesajul. Chaum propune alegerea unor parametri de redirecționare specifici pe baza analizei traficului din rețea [4] .

Disidența previne coliziunile neintenționate în rețea prin utilizarea unui program de transfer de mesaje. Programul este creat prin amestecarea aleatorie a participanților, fiecare participant știind care dintre biții de transmisie propuși aparțin cozii sale, dar nu cine deține biții rămași [14] .

Herbivore invită, de asemenea, participanții să convină asupra unui program de mesaje pentru fiecare rundă de comunicare. Fiecare participant selectează un interval aleator al programului de transmisie, iar dacă acest interval este folosit de altcineva, atunci participantul în cauză refuză să transfere. Dacă un participant așteaptă prea mult timp pentru slotul său, se va reconecta automat la grup după o perioadă de timp determinată de protocol. Protocolul prevede verificarea integrității datelor folosind algoritmul de hashing MD5 [15] .

Contracararea încălcărilor protocolului

Herbivore împarte rețeaua DC în mai multe grupuri, permițând participanților să se îndepărteze de încălcări. Participantul își poate părăsi grupul actual și poate verifica pe alții până când găsește un grup care nu are încălcări [16] . Această abordare poate duce la faptul că un atacator cu acces la multe grupuri ale rețelei DC poate manipula comportamentul unui participant, conducându-l să participe la un grup în care toți ceilalți participanți sunt în coluziune [17] .

Dissens implementează mai multe scheme pentru a contracara încălcările. Protocolul original [18] folosește programe aleatorii de transmitere a mesajelor și propagă tabelul de transmisie împreună cu dimensiunea mesajului curent. Această abordare vă permite să verificați corectitudinea secvenței de text cifrat în rețeaua DC prin calcularea funcției hash . Cu toate acestea, această tehnică duce la mari, conform calculelor autorilor, întârzieri în transmiterea mesajelor. Ulterior, a fost propusă o altă schemă de contramăsuri care nu se amestecă pentru a construi un program de transmisie în absența perturbațiilor, dar dacă în rețea încep perturbări, amestecarea se reia și devine posibil să se calculeze contravenientul. Cele mai recente versiuni ale Dissent acceptă verificarea completă a rețelei DC la un cost de calcul semnificativ datorită utilizării unui criptosistem cu cheie publică . În același timp, versiunile moderne de Dissent pot rula în modul hibrid , care folosește rețele DC tradiționale bazate pe XOR în cazul normal și utilizează rețele DC verificabile numai în caz de încălcare. Potrivit autorilor protocolului, această abordare face posibilă calcularea intrusului mai rapid decât este posibil prin construirea unui program de transmisie bazat pe amestecare [19] .

Note

  1. ↑ The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988 , 1.4. dovada de securitate.
  2. ↑ 1 2 3 4 5 6 Criptografia aplicată. Protocoale, algoritmi, texte sursă în limbaj C. Ediția a 2-a, 2002 , 6.3 Mesaje difuzate anonime.
  3. ↑ The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988 , Introducere.
  4. ↑ 1 2 3 The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988 , 1. Generalizing the Approach.
  5. ↑ 1 2 The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988 , 1.3. Ciocnirea participanților.
  6. ↑ Probleme despre cavaleri și spărgători
  7. ↑ The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988 , 2.3. Exemple de grafice pentru partajarea cheilor.
  8. ↑ A 2-Round Anonymous Veto Protocol, 2009 , 3. Performance.
  9. ↑ Dining Cryptographers Revisited, 2004 , 2 Context.
  10. ↑ Disidența în cifre: realizarea unei scale puternice de anonimat, 2012 , 3.2 Ipoteze de proiectare și implementare.
  11. ↑ Mesaje anonime responsabile în mod proactiv în Verdict, 2013 , 2.3 Generalizări practice.
  12. ↑ Dining Cryptographers Revisited, 2004 , 4.1 Intuiție și instrumente.
  13. ↑ Mesaje anonime responsabile în mod proactiv în Verdict, 2013 , 5.1 API-ul primitiv DC-net verificabil.
  14. ↑ Dissens: Accountable Anonymous Group Messaging, 2010 , 5.5 End-to-End Reliability.
  15. ↑ Erbivor: un protocol scalabil și eficient pentru comunicarea anonimă, 2003 , 4.2 Round Protocol.
  16. ↑ Eluding Carnivores: File Sharing with Strong Anonymity, 2004 , 3 Erbivor.
  17. ↑ Denial of service or denial of security?, 2004 , 1. INTRODUCERE.
  18. ↑ Dissent: Accountable Anonymous Group Messaging, 2010 , 7. LUCRĂRI CONEXE.
  19. ↑ Mesaje anonime responsabile în mod proactiv în verdict, 2013 , 4.4 Hybrid XOR/Verifiable DC-Nets.

Literatură