Az étkező kriptográfus probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. október 5-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

Az étkező kriptográfus problémája a logikai VAGY függvények sokféle módon történő biztonságos kiértékelésének módjaival foglalkozik . David Chaum először 1988-ban azonosította ezt a problémát, és egy szemléltető példával mutatta be, hogy lehetséges névtelen üzeneteket küldeni a feladóra vonatkozó korlátozások és a címzett címének nyomon követhetetlensége nélkül [1] [2] . A probléma megoldására alkalmas névtelen kommunikációs hálózatokat gyakran DC hálózatoknak nevezik .

A „diner” szó ellenére az étkező-kriptográfusok problémájának semmi köze az étkezőfilozófusok problémájához .

Leírás

Három kriptográfus gyűlt össze a vacsoraasztalnál. A pincér közli velük, hogy valaki már kifizette az ételüket. Lehet az egyik titkosító vagy a Nemzetbiztonsági Ügynökség (NSA). A kriptográfusok tiszteletben tartják egy barátjuk jogát, hogy névtelenül fizessen be, de ki akarják deríteni, hogy a Nemzetbiztonsági Ügynökség fizetett-e. Ezért úgy döntenek, hogy egy kétlépcsős protokollt hajtanak végre.

Az első lépésben minden második kriptográfus egy bit közös titkát határozta meg azzal, hogy beleegyezett egy érme feldobásába. Úgy bújtak el az étlap mögé, hogy csak a két dobáló kriptográfus látja a dobás eredményét. Tegyük fel, hogy az érme feldobása után A és B titkosítóknak van egy közös titka - , A és C - , B és C - kriptográfusoknak .

A második lépésben minden kriptográfus nyilvánosan bejelent egy bitet, amelyet a következőképpen számítanak ki:

Tegyük fel, hogy egyik kriptográfus sem fizetett, akkor A kriptográfus bejelenti , B , C - . Másrészt, ha A kriptográfus fizetett, bejelenti .

A második szakasz végén kiderül az igazság. Az egyik kriptográfus végrehajtja az összes deklarált bit XOR műveletét. Ha az eredmény , akkor ez azt jelenti, hogy egyik kriptográfus sem fizetett (tehát arra következtethetünk, hogy a fizetést az NSA teljesítette). Ellenkező esetben, ha az egyik kriptográfus fizetett, a személyazonossága ismeretlen marad a többi kollégá számára.

Erre a problémára David Chaum megalkotta a "Dinner Cryptographer Problem" kifejezést, valamint a probléma megoldására képes hálózatok elnevezését [2] [3] .

Korlátozások

David Chaum eredeti munkája számos korlátozást feltételez, amelyek befolyásolhatják a DC hálózati protokoll gyakorlati használatát.

Ütközések Ha két kriptográfus fizetett az ebédért, akkor üzeneteik átfedik egymást, és a kérdéses pár XOR műveletének eredménye 0 lesz. Ezt a helyzetet ütközésnek nevezzük, ebben az esetben csak egy fizető résztvevő használhatja ezt. protokoll az üzenetének az aktuális fordulón belüli továbbítására [4] [2] . Szabálysértések Minden rosszindulatú titkosító, aki nem akarja, hogy a csoport sikeresen kommunikáljon, blokkolhatja a protokollt, így az XOR művelet végeredménye használhatatlan. Lehetséges atrocitást elkövetni az XOR művelet helyes eredménye helyett tetszőleges bitek küldésével. Ez a probléma azért merül fel, mert az eredeti protokollt olyan mechanizmus nélkül tervezték, amely ellenőrizné, hogy a résztvevők tisztességesen követik-e a protokollt [5] [2] [6] . Bonyolultság A protokoll páronként megosztott titkokat igényel a résztvevők között, ami nagyszámú résztvevő esetén nehéz [7] [8] .

Általánosítások

Az egyenáramú hálózatokat úgy általánosították, hogy egy bitnél nagyobb átvitelt biztosítsanak háromnál több résztvevő számára, valamint az ábécé tetszőleges, bináris 0-tól és 1-től eltérő betűihez.

Hosszú üzenetek küldése

Annak érdekében, hogy egy névtelen küldő egynél több bit információt tudjon továbbítani az egyenáramú hálózati protokoll végrehajtásának egy körében, a titkosítók egy csoportja egyszerűen megismételheti a protokollt annyiszor, ahányszor szükséges a kívánt számú bit létrehozásához ( a csatorna sávszélessége alapján). Az egyenáramú hálózatokban a résztvevőpároknak lehetőségük van előre megállapodni egy közös kulcsban, például egy Diffie-Hellman protokollal kapott kulcs használatával . Ezután minden résztvevő helyileg beállítja ezt a megosztott kulcsot egy pszeudo-véletlen számgenerátorba , hogy a lehető legtöbb közös "érmefeldobást" produkálja, lehetővé téve a névtelen feladó számára, hogy néhány bit információt továbbítson [9] [2] .

További tagok

A protokoll alkalmazható olyan résztvevőkből álló csoportra, amelyek mindegyike megoszt egy titkos kulcsot a többi résztvevővel. A protokoll minden fordulójában, ha egy résztvevő olyan üzenetet szeretne küldeni, amely nem követhető az egész csoporthoz, megfordítja nyilvánosan bejelentett bitjeit. A résztvevők teljes gráfként ábrázolhatók , ahol a csúcsok a résztvevők, az élek pedig a megosztott titkos kulcsaik [2] [4] .

Megosztott hozzáférésű grafikon

A protokoll futtatható egy hiányos nyilvános kulcs gráf használatával, ami javíthatja a gyakorlati egyenáramú hálózatok teljesítményét és méretezhetőségét. Hiányos gráf használata esetén azonban fennáll annak a veszélye, hogy az összejátszás résztvevői a megosztási grafikont külön kapcsolódási összetevőkre bonthatják, és az anonimitás megsértését érhetik el. Például egy háromnál több résztvevőből álló csoport számára vonzó a gyűrűs topológia opció , ahol az asztalnál ülő kriptográfusok csak a tőle közvetlenül balra és jobbra ülő kollégákkal osztanak meg titkos kulcsot. Ez a topológia vonzó, mivel minden kriptográfusnak két érmefeldobást kell koordinálnia egy körben, nem pedig dobásokat, mint az eredeti teljes kulcsgráf esetében. Ha azonban az NSA ügynökei, Adam és Charlie, akik közvetlenül Bob közember bal és jobb oldalán ülnek, titokban összejátszanának és felfednék egymásnak titkos kulcsaikat, akkor biztosan megállapíthatnák, hogy Bob-e az aktuális üzenet feladója. a kérdéses fordulón belül, függetlenül a résztvevők teljes számától. Ez a hatás annak köszönhető, hogy az összeesküvő résztvevők, Adam és Charlie a nyilvános hozzáférési gráfot két független, egymástól eltérő komponensre „bontották”, amelyek közül az egyik csak Bobból, a másik az összes többi becsületes résztvevőből áll [5] .

A Dissent rendszerben a skálázáshoz [10] használt nyilvános egyenáramú hálózat másik topológiája kliens-szerver topológiaként írható le . Ez az opció kétféle résztvevőt határoz meg, akik különböző szerepet töltenek be: potenciálisan nagy számú felhasználót , akik névtelenek akarnak maradni, és sokkal kisebb számú megbízható személyt, akiknek feladata az összes felhasználó anonimitásának biztosítása. Egy ilyen topológiában a felhasználók mindegyike megoszt egy titkos kulcsot a megbízható felekkel, de a felhasználók nem osztanak meg egymással közvetlenül titkos kulcsokat, ahogyan a megbízottak sem osztanak meg egymással titkos kulcsokat - az eredmény egy interakciós mátrix . Ha a megbízható személyek száma kicsi, akkor minden felhasználónak csak néhány megosztott titkáról kell tudnia, ami ugyanúgy javítja a felhasználói interakció hatékonyságát, mint a gyűrűs topológiában. Mindaddig azonban, amíg a megbízható személy legalább egy tagja őszinte, és nem adja ki titkait, vagy nem játssza össze a többi taggal, addig ez a becsületes vagyonkezelő olyan csomóponttá válik , amely az összes becsületes felhasználót egy olyan egységbe kapcsolja össze, amely minden részével együttműködik az összetevővel. függetlenül attól, hogy más felhasználók vagy megbízható személyek tisztességtelen összejátszásba léptek-e. A felhasználóknak nem kell tudniuk vagy találgatniuk, mely bizalmasaik őszinték; biztonságuk a jegyzőkönyv készítői szerint csak legalább egy becsületes, nem összejátszó meghatalmazott meglététől függ.

Alternatív ábécék és operátorok

Bár az egyszerű DC-hálózati protokoll binárist használ átviteli ábécéként és XOR operátort a rejtjelezett szövegek kombinálásához, az alapprotokoll bármelyik ábécét alkalmazza, és XOR-szerű operátorokat használ, amelyek érvényesek a Werman titkosításhoz . Ez a rugalmasság természetesen felmerül, mivel a titkok sok résztvevőpár között vannak elosztva, amelyek valójában a Verman-titkosítást valósítják meg egymás között a DC hálózat egy körén belül [11] .

Az egyenáramú hálózati ábécé egyik alternatívája egy véges csoport használata, amely alkalmas a nyilvános kulcsú kriptográfiában való használatra. Például elfogadható Schnorr-csoportok vagy elliptikus görbék használata . Az ábécé ezen megválasztása lehetővé teszi a résztvevők számára, hogy nulla tudásalapú bizonyítást alkalmazzanak a protokoll által előállított rejtjelezett szöveg ellenőrzésére. Különösen azt ellenőrzik, hogy valamelyik résztvevő megsérti-e a protokollt, és az ellenőrzés során megfigyelik a DC hálózat által biztosított anonimitást. Ezt a technikát először Goll és Juels [12] javasolta, és a Verdictben , a Dissent [13] megvalósításában alkalmazták .

Ütközés elkerülése és kezelése

Chaum eredeti írása a következő módszert javasolja az ütközések kezelésére. Az egyenáramú hálózaton éppen üzenetet küldő felhasználó az átvitel minden egyes fordulójában megkapja a kapott bitet. Ha az eredményül kapott bit nem egyezik azzal, amelyet az aktuális körben továbbítani akar, a felhasználó arra a következtetésre jut, hogy ütközés történt. Véletlen számú kört vár, és újra elküldi az üzenetet. Chaum konkrét továbbítási paraméterek kiválasztását javasolja a hálózat forgalmának elemzése alapján [4] .

A különvélemény üzenetátviteli ütemterv használatával akadályozza meg a nem szándékos hálózati ütközéseket. Az ütemezés a résztvevők véletlenszerű megkeverésével jön létre, és minden résztvevő tudja, hogy a javasolt átviteli bitek közül melyik tartozik a sorába, de azt nem, hogy kié a fennmaradó bitek [14] .

A Herbivore arra is felkéri a résztvevőket, hogy állapodjanak meg az egyes kommunikációs körök üzenetküldési ütemezésében. Minden résztvevő kiválaszt egy véletlenszerű időközt az ütemezésből az átvitelhez, és ha ezt az időközt valaki más használja, akkor a kérdéses résztvevő megtagadja az átvitelt. Ha egy résztvevő túl sokáig vár a résidőre, a protokoll által meghatározott idő elteltével automatikusan újracsatlakozik a csoporthoz. A protokoll lehetővé teszi az adatok integritásának ellenőrzését az MD5 hashing algoritmus segítségével [15] .

Protokollsértések elhárítása

A Herbivore több csoportra osztja az egyenáramú hálózatot, lehetővé téve a résztvevőknek, hogy elkerüljék a jogsértéseket. A résztvevő elhagyhatja jelenlegi csoportját, és ellenőrizhet másokat, amíg nem talál olyan csoportot, amely mentes a jogsértésektől [16] . Ez a megközelítés oda vezethet, hogy egy támadó, aki hozzáfér a DC hálózat számos csoportjához, manipulálhatja egy résztvevő viselkedését, ami arra készteti, hogy részt vegyen egy olyan csoportban, ahol az összes többi résztvevő összejátszásban áll [17] .

A különvélemény számos sémát valósít meg a jogsértések ellen. Az eredeti protokoll [18] véletlenszerű üzenetátviteli ütemezéseket használ, és az átviteli táblázatot az aktuális üzenet méretével együtt továbbítja. Ez a megközelítés lehetővé teszi a titkosított szöveg szekvencia helyességének ellenőrzését a DC hálózatban a hash függvény kiszámításával . Ez a technika azonban a szerzők számításai szerint nagy késésekhez vezet az üzenetek továbbításában. Később egy másik ellenintézkedési sémát javasoltak, amely nem keveri az átviteli ütemezést zavarok hiányában, de ha zavarok kezdődnek a hálózatban, a keverés folytatódik, és lehetővé válik az elkövető kiszámítása. A Dissent legújabb verziói a nyilvános kulcsú kriptorendszer használatának köszönhetően jelentős számítási költségek mellett támogatják a teljes DC-hálózati ellenőrzést . Ugyanakkor hibrid módban is futhatnak a Dissent modern verziói , amelyek normál esetben hagyományos XOR alapú DC hálózatokat használnak, és csak szabálysértések esetén használnak ellenőrizhető egyenáramú hálózatokat. A protokoll készítői szerint ez a megközelítés lehetővé teszi a behatoló gyorsabb kiszámítását, mint a keveredésen alapuló átviteli ütemezés felépítése [19] .

Jegyzetek

  1. ↑ The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988 , 1.4. a biztonság igazolása.
  2. ↑ 1 2 3 4 5 6 Alkalmazott kriptográfia. Protokollok, algoritmusok, forrásszövegek C nyelven. 2. kiadás, 2002 , 6.3 Anonymous Broadcast Messages.
  3. ↑ The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988 , Bevezetés.
  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. A résztvevők ütközése.
  6. ↑ Problémák a lovagokról és a lovagokról
  7. ↑ The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988 , 2.3. Példa kulcsmegosztási grafikonokra.
  8. ↑ A 2-Round Anonymous Veto Protocol, 2009 , 3. Teljesítmény.
  9. ↑ Dining Cryptographers Revisited, 2004 , 2 Háttér.
  10. ↑ Különvélemény a számokban: erős anonimitási skála, 2012 , 3.2 Tervezési és telepítési feltételezések.
  11. ↑ Proaktívan elszámoltatható névtelen üzenetküldés az ítéletben, 2013 , 2.3 Gyakorlati általánosítások.
  12. ↑ Dining Cryptographers Revisited, 2004 , 4.1 Intuíció és eszközök.
  13. ↑ Proactively Accountable Anonymous Messaging in Verdict, 2013 , 5.1 Verifiable DC-net Primitive API.
  14. ↑ Különvélemény: elszámoltatható névtelen csoportos üzenetküldés, 2010 , 5.5 Végpontok közötti megbízhatóság.
  15. ↑ Herbivore: A Scalable and Efficient Protocol for Anonymous Communication, 2003 , 4.2 Round Protocol.
  16. ↑ Eluding Carnivores: File Sharing with Strong Anonymity, 2004 , 3 Növényevő.
  17. ↑ Szolgáltatás megtagadása vagy biztonság megtagadása?, 2004 , 1. BEVEZETÉS.
  18. ↑ Különvélemény: elszámoltatható névtelen csoportos üzenetküldés, 2010 , 7. KAPCSOLÓDÓ MUNKÁK.
  19. ↑ Proaktívan elszámoltatható névtelen üzenetküldés: Verdict, 2013 , 4.4 Hibrid XOR/Verifiable DC-Nets.

Irodalom