Zwei gegenseitig nicht vertrauenswürdige Parteien möchten Daten austauschen.

  • Ich versuche, einen neuen Algorithmus für eine Anwendung herauszufinden, die ich schreibe. Client A hat eine Datei fA. Client B hat die Datei fB. Jede Partei ist nicht vertrauenswürdig und versucht, die andere Partei zu reißen. Client A möchte die fB und Client B möchte fA.

    Wie kann ich einen Algorithmus erstellen, wenn es ihnen nicht möglich ist, den anderen Spieler zu vermasseln?

     For example:
        A encrypts fA and send the file to B.
        B encrypts fB and sends it to A.
    
    Now, both A and B have an encrypted version of the file they want. 
    How can they both share the decryption key at the same time... or what?
     

    Ist das überhaupt möglich? Dies bricht meine Gedanken.

    Da jeder Client versucht, die andere Partei zu reißen, kann Client A die Datei fA nicht an Client B senden, und es wird davon ausgegangen, dass Client B seine Datei zurücksendet. Wenn Client A zuerst "ohne Gewähr" sendet, läuft Client B einfach mit der Datei davon.

    Im wirklichen Leben hält eine Person den Pot in einer Hand, die andere hält das Geld in der anderen. Sie handeln beide Hände gleichzeitig. Der Kerl mit dem Bargeld landet jetzt beim Pot und umgekehrt. Wie kann ich etwas Ähnliches mit Computerbits machen? (Client A und B befinden sich an verschiedenen Orten in einem Netzwerk.)

    BEARBEITEN: Beachten Sie, dass jede Partei einen Hash der Datei hat, die sie erhalten sollen. Daher können die Parteien keine Junk-Datei an den anderen Kerl senden, ohne dass er es weiß. Ein vertrauenswürdiger Dritter stellt den Hash bereit.

    13 January 2012
    Ilmari Karonen
8 answers
  • Es ist möglich, aber der Algorithmus ist etwas komplex und die Hashes müssen speziell konstruiert werden. Die Grundidee ist folgende:

    Was Sie brauchen, ist eine Möglichkeit für jede Partei, der anderen Partei einen nachprüfbaren "Hinweis" zu geben, der den Suchraum für die mögliche Datei reduziert, beispielsweise durch eine Faktor 10. Sobald eine Partei keine Hinweise mehr gibt, gibt auch die andere keine Hinweise mehr. Ein Betrüger kann also im schlimmsten Fall einen Hinweis geben, den Sie ihm nicht gegeben haben.

    Das bedeutet, dass Sie möglicherweise 10-mal so viele Berechnungen durchführen müssen, wie er es versucht, den Computer wiederherzustellen file, aber das ist nicht genug, um die Aufgabe für ihn möglich zu machen, aber für Sie unmöglich.

    Eine Möglichkeit, dies zu tun, besteht darin, die Datei so zu codieren, dass jedes Byte zum Wiederherstellen von Byte benötigt wird Byte davon (zum Beispiel können Sie dies ohne Verschwendung von Bytes mit einem Löschcode tun). Dann können Sie den Hash tatsächlich aus vier Hashwerten machen. Eine ist die gesamte codierte Datei. Das nächste ist von der Datei mit den letzten zwei Bytes, die fehlen. Das nächste ist von der Datei mit den nächsten drei Bytes, die fehlen. Das letzte ist die Datei, bei der die nächsten vier Bytes fehlen.

    Sie können dann alle bis auf die letzten 10 Bytes der Datei mit der anderen Seite austauschen und dies durch Hash bestätigen. Dann können Sie die nächsten vier Bytes austauschen und überprüfen. Dann die nächsten drei und so weiter durch die vier Runden. Im schlimmsten Fall hat ein Betrüger 256-mal mehr Arbeit als er. Wenn er also die Datei innerhalb eines Tages benötigt, erhalten Sie die Datei schlimmer noch binnen 256 Tagen.

    Sie können zu Nibbles wechseln und diese 16 statt 256 zum Preis von mehr machen Hashes und mehr Austausch.

    12 January 2012
    Michal SznajderChris Meek
  • Es gibt einen klassischen Artikel von Boneh und Naor , in dem eine mögliche Lösung beschrieben wird ein Problem, das Ihrem ähnlich ist. Sie stützt sich auf "zeitliche Verpflichtungen". Wenn ein Datenelement D gegeben ist, das einige algebraische Eigenschaften erfüllt, ist es möglich, einen Wert C zu berechnen, der an eine andere Partei mit den folgenden Eigenschaften gesendet werden kann:

    • kann der anderen Partei effizient nachgewiesen werden, dass der in C versteckte Wert D die "erfüllt". algebraische Eigenschaften ", ohne jedoch D selbst anzuzeigen (ein Zero-Knowledge-Beweis );
    • Sie können zu einem späteren Zeitpunkt D selbst anzeigen, und die Gegenstelle kann schnell überprüfen, ob D der Verpflichtung entspricht C ;
    • Wenn Sie nicht D anzeigen, kann der andere Teilnehmer D von C , jedoch zum Preis einer umfangreichen Berechnung, deren Kosten nach Belieben konfiguriert und beliebig hoch gemacht werden können; Außerdem ist diese Berechnung der Parallelität zuwider, dh sie kann nicht beschleunigt werden, indem mehr Hardware auf sie geworfen wird.
    • Sie können eine feinkörnige partielle Offenlegung machen, dh geben Informationen weglassen, die den Rechenaufwand für die Zwangsöffnung der Verpflichtung verringern (diese Teilinformationen geben keine Informationen zu D ), die andere Partei muss noch C , aber diese Aufgabe wird kostengünstiger gemacht.)

    Hinweis: Der ZK-Proof deckt auch die Kosten der Zwangsöffnung: den Prüfer dieses Proofs ist überzeugt, dass er die Zusage mit einer gegebenen Anstrengung zwangsweise auf $ 2 ^ k $ eröffnen könnte.

    Im Boneh-Naor-Protokoll sind die Daten D eine digitale Signatur und die "algebraischen Eigenschaften" von D sind die Tatsache, dass D tatsächlich eine gültige Signatur über einem bestimmten bekannten Text T ist. Der Kontext ist vertraglich bindendng: Alice und Bob möchten einen Vertrag T unterschreiben, aber beide möchten ihre Unterschrift nicht preisgeben, ohne vom Peer einen Vertrag zu erhalten (wenn Bob eine Unterschrift von Alice über T hat aber Alice erhält keine Unterschrift von Bob über T , dann erlangt Bob einen taktischen Vorteil (was Alice vermeiden will) und umgekehrt. Das Protokoll sieht also so aus:

    • Alice berechnet ihre Signatur S A über T berechnet dann eine Zusage C A über S A und den ZK-Beweis, dass die Die verbindliche Unterschrift ist gültig. Die Verpflichtungsstärke (Kosten der Zwangseröffnung) wird auf einen extrem hohen Wert von $ 2 ^ k $ eingestellt, ähnlich den Kosten für das tatsächliche Durchbrechen des öffentlichen Schlüssels von Alice (d.h. Alice sendet C A (+ ZK-Proof) an Bob.
    • In ähnlicher Weise berechnet Bob seine eigene Signatur S B , die Zusage C B und den ZK-Proof; Bob sendet C B (+ ZK-Proof) an Alice.
    • Alice und Bob überprüfen die ZK-Proofs.
    • Alice macht eine erste partielle Offenbarung ihrer Verpflichtung; Mit diesen Informationen könnte Bob nun mit einem Aufwand $ 2 ^ {k-1} $ erzwingen C A .
    • Bob antwortet mit Seine Verpflichtung wird teilweise offenbart, und die Kosten für die Zwangsöffnung von Alice werden auf $ 2 ^ {k-1} $ reduziert.
    • Alice dann erfolgt eine zweite teilweise Aufdeckung, wodurch die Kosten für die Öffnung der Kraft C B auf $ 2 ^ {k-2} $ reduziert werden.
    • Und so weiter.

    Wenn entweder Alice oder Bob das Protokoll zu einem beliebigen Zeitpunkt ausbricht, können sowohl Alice als auch Bob möglicherweise nur den Eröffnungsjob beenden zu ähnlichen Kosten: Die Kosten für Alice sind nicht mehr als doppelt so hoch wie für Bob und nicht weniger als die Hälfte für Bob. In diesem Sinne ist das Protokoll fair .

    Der Eckpfeiler des Protokolls sind die "algebraischen Eigenschaften": An jedem Punkt müssen Alice und Bob stehen überzeugt, dass die Kraftöffnung ultimativ wäre

    12 January 2012
    Thomas Pornin
  • Im wirklichen Leben löst das Austauschen zur gleichen Zeit dieses Problem nicht.

    • Lochen den Kerl, nehmen Sie das Geld und laufen Sie.
    • Bringt eine Waffe mit
    • Bringt ein paar Freunde mit, die ihn überwältigen
    • etc ...

    Der richtige Weg, um dieses Problem zu lösen, ist die Verwendung eines escrow .

    Dasselbe gilt für Bits. Sie müssen einen vertrauenswürdigen Drittanbieter haben, der die Authentizität und Korrektheit der auszutauschenden Dateien überprüft.

    Kryptografie bietet die Möglichkeit, sicherzustellen, dass eine Nachricht aus einer bestimmten Quelle stammt. Sie kann jedoch nicht überprüfen, ob der Inhalt einer Datei die Anforderungen des Empfängers erfüllt.

    EDIT: Wie wird der Hash erhalten? Von dem nicht vertrauenswürdigen Spieler? Wenn ja, können sie nicht wissen, dass es kein Müll ist. Wenn sie es an einer anderen Stelle haben, muss dies ein vertrauenswürdiger Dritter sein, der für die Hinterlegung von Verpflichtungen verwendet werden könnte ...

    EDIT2: Das Problem läuft darauf hinaus, dass beide Parteien die Berechtigung dazu haben eine verschlüsselte Nachricht, ohne sie entschlüsseln zu können, bevor sie die jeweils andere Nachricht entschlüsseln kann. Dies ist ohne einen Drittanbieter, der den Klartext beider Nachrichten überprüfen kann, nicht möglich.

    EDIT3: Der Festplattenspeicherplatz muss auf dem Escrow (E) -Host erhalten bleiben .

    • E stellt sicher sicher, dass fA verwendet wird.
    • E überprüft fA und generiert ein öffentliches / privates Schlüsselpaar (pubA / privA)
    • E verschlüsselt fA mit privA enc (fA, privA)
    • E generiert einen Hash der Datei enc (fA, privA) und speichert es
    • E gibt A privA sicher und hält pubA geheim

    Jetzt muss B dasselbe tun.

    • B stellt E sicher mit fB zur Verfügung.
    • E überprüft fB und generiert ein öffentliches / privates Schlüsselpaar (pubB / privB)
    • E verschlüsselt fB mit privA enc (fB, privB)
    • E generiert einen Hash der Datei enc (fB, privB) und speichert ihn
    • E gibt B privB sicher und behält pubB
    12 January 2012
  • Ohne einen vertrauenswürdigen Drittanbieter oder Kommunikationskanal mit ungewöhnlichen Eigenschaften ist es nachweislich, dass kein solcher Algorithmus vorhanden ist. Hier ist der Beweis:

    1) Jeder Algorithmus kann abwechselnd als Folge von Nachrichten A bis B, dann B bis A modelliert werden. Wenn der Algorithmus aufeinanderfolgende Sendevorgänge in dieselbe Richtung hat, fügen Sie sie zusammen und betrachten Sie eine einzelne Nachricht.

    2) Wenn der Algorithmus "optionale" Nachrichten enthält, z. B. A und B erhalten ihre Dateien immer noch ohne sie, betrachten Sie den Algorithmus ohne solche Meldungen. Angenommen, keine Seite sendet optionale Nachrichten (da dies nicht unbedingt erforderlich ist, bedeutet "optional".

    3) Nach der letzten nicht-optionalen Nachricht muss A sein Datei und B müssen über eine Datei verfügen.

    4) Vor der letzten nicht optionalen Nachricht dürfen weder A noch B eine Datei haben. Wenn beide Seiten über eine Datei verfügen, ist die nicht optionale Nachricht definitionsgemäß optional. Dies ist ein Widerspruch. Und vor der letzten nicht optionalen Nachricht kann es nicht sein, dass genau eine Seite über eine Datei verfügt. Andernfalls kann eine Seite die letzte Nachricht nicht senden, wenn sie diese Nachricht nicht senden und ihre Datei abrufen, der anderen Seite jedoch keine Datei zuweisen soll.

    5) Somit muss die letzte Nachricht Informationen, die A zuvor unbekannt waren, und Informationen, die zuvor B nicht bekannt waren, übermitteln. Aber keine der beiden Seiten kann Informationen übertragen, die sie nicht kennt. Somit kann keine Seite die letzte Nachricht senden. Daher kann das Protokoll keine letzte Nachricht enthalten, kann nicht terminiert werden und kann daher nicht existieren.

    Sie können dies jedoch auch mit speziell konstruierten Hashes tun. Die Grundidee ist, dass jede Seite die andere Information liefert, die den Suchraum der anderen Partei reduziert. Wenn also eine der beiden Parteien sehr früh abfällt, hat keine der Parteien genügend Informationen, um ihre Suche zu ermöglichen. Wenn einer der beiden Beteiligten später ausfällt, hat der andere Teilnehmer immer noch genügend Informationen, um seine Datei zu erhalten, nur mit zusätzlicher Arbeit.

    12 January 2012
    Michal SznajderChris Meek
  • Sie können dies mit RSA-Nachrichtensignatur erreichen .

    RSA funktioniert wie folgt. Wählen Sie zwei (große) Primzahlen p und q und setzen Sie

     n = p*q
     

    Dann wählen Sie einen öffentlichen Schlüssel e, so dass

     gcd(e,phi(n)) = 1
     

    wobei phi Eulers totient-Funktion ist, also phi(n) = (p-1)(q-1). Stellen Sie den privaten Schlüssel d als multiplikatives Invers von e mod phi(n) ein, dh

     e * d = 1 (mod phi(n))
     

    Sie verschlüsseln eine Nachricht mit

     C = M^e (mod n)
     

    und dekodieren eine codierte Nachricht mit

     M = C^d (mod n)
     

    Nehmen Sie nun Alice und Bob als unzuverlässig an. Lassen Sie Alice ein System (n_A, e_A, d_A) und Bob ein System (n_B, e_B, d_B) auswählen. Angenommen, Alice möchte Bob eine Nachricht senden M. Alice sendet dies mit zwei verschlüsselten Nachrichten an Bob:

     C1 = M^(e_B) // ENCODE THE MESSAGE USING BOB'S PUBLIC KEY
    C2 = M^(d_A) // SIGN THE MESSAGE USING ALICE'S PRIVATE KEY
     

    Um die Nachricht zu decodieren, führt Bob Folgendes aus:

     M1 = C1^(d_B) // DECODE THE MESSAGE USING BOB'S PRIVATE KEY
    M2 = C2^(e_A) // DECODE THE SIGNATURE USING ALICE'S PUBLIC KEY
     

    Wenn die Nachrichten übereinstimmen, weiß Bob, dass Alice die Nachricht gesendet hat (oder sonst gehackt wurde).

    12 January 2012
  • In der Regel funktionieren eine Kombination aus öffentlichen und privaten Schlüsseln (RSA). Aber Ihre Einschränkungen sind so streng, dass ich glaube, dass keine Lösung funktionieren würde. Am Ende des Tages kann A jede Junk-Datei anstelle von FA senden, und es gibt keine Möglichkeit, dass B es kennt. Wenn es möglich ist, dass B weiß, was A gesendet hat, ist es tatsächlich fA, dann kann ich mir wahrscheinlich etwas einfallen lassen.

    EDIT: Ich nehme das zurück. Selbst wenn Sie die Authentizität der Datei überprüfen können, ist es wahrscheinlich nicht möglich, Ihr Problem zu lösen.

    Wenn Sie Schlüssel synchron austauschen:

    1. Nehmen wir an, Sie tauschen die Schlüssel gleichzeitig aus. Da Sie den von Ihnen gesendeten Schlüssel zurückerhalten können, ist es auch nicht möglich, an jedem Ende keinen Betrug zu gewährleisten.
    2. Wenn der Schlüssel nicht gleichzeitig ausgetauscht werden kann, ... dann vergessen Sie das nicht !

    Die einzige Lösung ist die Übertragungsurkunde.

    12 January 2012
  • Im verteilten Computing gibt es kein "gleichzeitiges" oder "gleichzeitig". Es gibt nicht einmal eine zu 100% korrekte Methode, um zu ermöglichen, dass zwei entfernte Computer die Atomzeit vereinbaren. Sie möchten, dass beide Dateien gleichzeitig verfügbar sind (Schlüssel werden gleichzeitig gesendet). Wenn eine Partei einen Sekundenbruchteil früher beendet, kann sie sich zurückziehen.

    Sie können versuchen, den Zeitraum zu verringern, in dem sie sich zurückziehen können, indem Sie eine Art Handshaking-Methode . Handshaking wird in Telecom verwendet, um Parameter auszuhandeln. Sie könnten etwas herausfinden, um den Schlüsselaustausch zu vereinbaren oder die Zeit oder das Intervall, in dem dies stattfinden wird.

    12 January 2012
  • Hier sind meine zwei Cents. Da Sie bereits gesagt haben, dass ein vertrauenswürdiger Dritter die Hashes bereitstellt, müssen Sie Folgendes tun:

    Beide Teams erhalten auch Hashes ihrer eigenen Dateien, sodass Team A über h (fA) und Team B über h (fB) verfügt. Der Hash ist stark genug, um einige Jahre zu knacken (2048-Bit-Verschlüsselung oder etwas anderes).

    Jedes Team sendet dem anderen eine Summe seiner Hashes. Also sendet Team A h (fA) + h (fB) und Team B sendet h (fB) + h (fA).

    Jetzt haben beide Teams die Summe der Hashes, aber nicht die echten Dateien. Wenn die Summe der Hashes übereinstimmt, gehen beide Teams zur dritten Partei und fragen nach dem Al-Hash-Algo. Da sich beide Teams darauf einigen, den Algo herauszugeben, tut dies der Dritte und jedes Team erhält, was es will.

    Der Schlüssel ist die Verwendung eines gemeinsamen, unauflösbaren Algo, um die Dateien zu hashieren.

    Was sagen Sie dazu?

    27 January 2012
    Rob Burke