Faire Würfel über Netzwerk ohne vertrauenswürdigen Dritten

Obwohl es ein ziemlich grundlegendes Problem sein sollte, habe ich keine Lösung dafür gefunden: Wie kann man ohne vertrauenswürdigen Dritten über ein Netzwerk würfeln?

Die M Spieler würfeln N Würfel, ein Spieler nach dem anderen. Kein Spieler darf vor dem nächsten Wurf "schummeln", dh das Ergebnis zu seinem Vorteil ändern oder "in die Zukunft schauen".

Ist das möglich?

Ich denke, die Lösung wäre so etwas wie eine Krypto mit öffentlichem Schlüssel, bei der jeder Spieler eine verschlüsselte Nachricht abgibt. Nachdem alle Nachrichten gesammelt wurden, tauschen Sie die Schlüssel aus, um die Nachrichten zu dekodieren. Dann wird das sha1(joined string of all decrypted messages) mod 6 + 1verwendet, um den Würfel zu bestimmen.

Das Hauptproblem, das ich habe: Da die Nachricht [c / s] irgendetwas sein sollte, weiß ich nicht, wie ich Manipulationen an den privaten Schlüsseln verhindern kann. Esp. Der letzte Spieler, der seinen Schlüssel abgibt, könnte leicht schummeln (denke ich).

Das Spiel sollte sogar fair bleiben, wenn sich alle Spieler gegen einen Spieler "verschwören".

Zufälligkeit kombinieren

Sie benötigen einen Algorithmus, mit dem jeder Spieler einen Beitrag zur endgültigen Zufallszahl leisten kann, sodass er das Endergebnis auf jeden möglichen Wert ändern kann, unabhängig davon, was die anderen zur Zufallszahl beigetragen haben. Auf diese Weise können sogar alle anderen Spieler versuchen, gegen einen einzelnen Spieler zusammenzuarbeiten, können jedoch nicht über das Ergebnis entscheiden (oder es in irgendeiner Weise beeinflussen).

Wie geht das? Stellen Sie sich vor, wir wollen einen Würfel mit 6 Seiten simulieren. Wenn wir alleine spielen, verwenden wir einen Zufallszahlengenerator, der eine große Zufallszahl r ausgibt. Dann erhalten wir den Endwert durch Berechnung result = (r mod 6)+1. Das gleiche gilt für mehrere Spieler, die ihre Würfel einzeln rollen. Stellen Sie sich vor, Sie haben eine Schachtel (oder Urne). Jeder Spieler lässt seinen Zufallszahlengenerator (verborgen) laufen und schreibt diese Zahl (r1, r2, r3, ... rn) auf ein Blatt Papier und legt sie in die Schachtel. Jetzt nehmen die Spieler alle Zahlen aus der Schachtel und berechnen ihre Summe, um die Zufallszahl der Gruppe zu generieren r = r1+r2+r3+r4+...+rn. Dieser wird verwendet, um das Ergebnis mit zu berechnen result = (r mod 6)+1. Wenn die anderen Spieler betrügen würden (indem sie zusammenarbeiten), könnte ein einzelner Spieler das Ergebnis trotzdem auf einen beliebigen Wert ändern.

Warum ist das so? Stellen Sie sich vor, wir hätten 3 Spieler. Spieler 1 und Spieler 2 versuchen Betrüger und arbeiten zusammen gegen Spieler 3. Spieler 1 und Spieler 2 nur beitragen r1und r2der Summe r. Was sie also entscheiden können, ist das Ergebnis r1+r2. Der Wert ((r1+r2+r3) mod 6) + 1ist der gleiche wie (((r1 mod 6) + (r2 mod 6) + (r3 mod 6)) mod 6) + 1. Da die Spieler 1 und 2 r1 und r2 entscheiden können, können sie den Teil bestimmen, den (r1 mod 6) + (r2 mod 6)wir diesen nennen c. Das Endergebnis ist dann ((c + (r3 mod 6)) mod 6) + 1.

Was auch immer Spieler 1 und 2 versuchen, r3 kann das Ergebnis auf einen beliebigen Wert von 1 bis 6 ändern, ohne die Wahrscheinlichkeiten zu ändern. Wenn Sie es nicht glauben, versuchen Sie c = 0 und r3 = 0 .. 5, was Ihnen das Ergebnis 1 bis 6 ergibt. Versuchen Sie c = 1 und r3 = 0 .. 5, es gibt Ihnen die Ergebnisse 2,3, 4,5,6,1. Versuchen Sie c = 2, r3 = 0 .. 5. Sie erhalten: 3,4,5,6,1,2.

Um dieses Phänomen darzustellen, stellen Sie sich ein Glücksrad einer Spielshow vor. Es hat 6 Zonen (0, 1, 2, 3, 4, 5), die "digital" einrasten. Sie können eine Taste drücken, um sie eine Zone vorwärts zu drehen (von 0 bis 1, von 1 bis 2, von 2 bis 3, ... von 5 bis 0 usw.). Das Spiel beginnt mit dem Rad auf Position "0" und jeder Spieler schreibt eine positive Zahl auf (versteckt). Jetzt müssen sie die Stifte weglegen, damit jeder die Nummer ändern kann und jeder Spieler allen anderen seine Nummer zeigen muss. Jetzt drückt jeder Spieler den Knopf so oft, wie er auf sein Blatt Papier geschrieben hat. Und wir bekommen unsere endgültige Zufallszahl (0..5). Dieses Spiel würde sehr lange dauern und wäre sehr ärgerlich, wenn wir nicht daran denken würden, Folgendes zu befolgen: Jedes Mal, wenn der Knopf 6 Mal gedrückt wird, befindet sich das Rad wieder an derselben Position. So kann jeder Spieler nur seine Zahl berechnen "(r1+r2+r3) mod 6 = ((r1 mod 6) + (r2 mod 6) + (r3 mod 6)) mod 6.

Werte austauschen

Jetzt haben wir über ein Netzwerk keine "Box", um die Zufallswerte des Players (vertrauenswürdiger Dritter) einzugeben. Wir können auch nicht überprüfen, ob die Spieler ihre Stifte weggelegt haben. Dafür brauchen wir einen anderen Algorithmus.

Kolrabi hat es bereits erklärt. Sie können von jedem Spieler zuerst einen Hash-Wert (z. B. SHA1-Hash) des Zufallswerts berechnen lassen. Dann müssen sie alle ihren Hash-Wert an die anderen weitergeben. Wenn Sie es richtig machen, kann niemand einfach "schnell" die Zufallszahl daraus berechnen. So kann niemand einfach den Hash der anderen nehmen, um das Endergebnis auf deterministische Weise zu ändern (Stellen Sie sich vor: Er ist der letzte Spieler und dreht das Rad nur so oft vorwärts. Aber er weiß nicht, wie die Position ist Das Rad ist, wenn er anfängt, es zu drehen - also kann er das Ergebnis nicht entscheiden.

Wenn jeder die Hashes aller anderen hat, überprüft jeder, ob er die gleichen Hashes von allen anderen hat. Ich weiß nicht, ob das wirklich nötig ist. Aber danach hat jeder die gleichen Hashes.

Tauschen Sie nun die Zufallszahlen aus. Jeder überprüft, ob die Zahlen mit dem Hash-Wert übereinstimmen (indem er die Hash-Werte aller Zahlen berechnet und überprüft, ob sie den Hashes entsprechen, die der Spieler zuvor ausgetauscht hat).

Wenn es oben kein Problem gab (alle hatten die Hashes korrekt ausgetauscht, Hashes stimmen mit den Zufallswerten überein), können Sie das Ergebnis berechnen, indem Sie die Zufallswerte aufsummieren und "mod x" + 1 berechnen, wodurch Sie das Ergebnis eines Würfels mit x erhalten Seiten. Dieses Ergebnis sollte (ich bin kein Kryptograph) zufällig gleichmäßig verteilt sein, solange mindestens ein Spieler einen Zufallszahlengenerator verwendet, der gleichmäßig verteilte Werte generiert.

Was bedeutet "Wenn du es richtig machst"?

Sie müssen verhindern, dass ein Spieler die Zufallswerte aus den Hashes berechnet. Es gibt mindestens zwei Möglichkeiten, wie ein Spieler dies tun kann:

1. Er probiert einfach alle Werte 0, 1, 2, 3 ... durch und berechnet die Hashes. Wenn der Hash übereinstimmt, hat er den Wert für den Hash gefunden. Um zu verhindern, dass dieser Ansatz erfolgreich ist, sollte Ihr Zufallszahlenbereich sehr groß sein (nicht nur 0 bis 5 oder 0 bis 65535, die ein Spieler innerhalb kurzer Zeit schnell überprüfen kann). Eine 32-Bit-Nummer sollte in Ordnung sein. Aus diesem Grund sollten die Spieler die Ausgabe des Zufallsgenerators und nicht den Wert "mod 6" austauschen. Wenn Ihr Zufallszahlengenerator Ihnen nicht liefert, dass große Werte mehrere Zufallszahlen erzeugen und zu einer einzigen großen Zahl kombinieren (verwenden Sie Bitverschiebungsoperationen, um sie zu kombinieren; fragen Sie, ob Sie dies tun müssen und nicht wissen, wie Sie dies tun sollen es ... es ist wichtig, dies richtig zu machen!). In den meisten Fällen ist der Zufallswertbereich des Generators jedoch groß genug ...

2. Die zweite Methode wäre die Verwendung einer Nachschlagetabelle. Wenn Sie wissen, dass die Zahlen in einem bestimmten Bereich liegen, können Sie alle Hashes im Voraus berechnen und in einer alphabetisch sortierten Datenbank speichern. Später können Sie einfach den Hash nachschlagen, um den Wert zu erhalten. Um dies zu verhindern, können Sie zwei Dinge tun: a) Der Nummernkreis (wie oben) muss sehr groß sein, damit es unmöglich wird, eine solche Datenbank zu speichern. b) Tauschen Sie in jeder neuen Runde eine zufällige Zeichenfolge aus (die von allen Spielern in Teilen beigesteuert wird und nicht verborgen werden muss). Diese zufällige Zeichenfolge ist bei der Berechnung der Hashes an alle Werte anzuhängen. Sie können also keine Datenbank erstellen, bevor Sie diese zufällige Zeichenfolge kennen - oder Sie mussten eine Datenbank für eine solche zufällige Zeichenfolge erstellen, die noch mehr Rechenleistung und Speicherplatz benötigen würde.

Eine andere Möglichkeit zu betrügen wäre, die Zufallszahl in eine andere Zahl zu "ändern", die den gleichen Hashwert hat. Der Ansatz wäre der gleiche wie oben. Während es in den meisten Fällen sehr schwierig ist, eine andere Zahl mit demselben Hashwert zu finden, kann dies vorberechnet werden, wenn Sie nur den Hash der Zahl verwenden. Daher sollten Sie die zufällige Präfix- (oder Suffix-) Zeichenfolge austauschen, die bei der Berechnung des Hashwerts hinzugefügt werden muss. Ich bin mir nicht 100% sicher, aber ich erinnere mich, dass es für den MD5-Hashing-Algorithmus eine Technik gab, mit der schnell andere Übereinstimmungswerte für denselben Hash berechnet werden können, wenn Sie einen Wert erhalten, der zu diesem Hash führt. Verwenden Sie also besser kein MD5. Ich weiß nichts über diese Art von Angriff für SHA1, aber es könnte einen geben.

Wenn Sie das oben genannte Recht ausgeführt haben, sollten Sie die Sicherheit der Methode weiter verbessern, indem Sie die Zeit für den Austausch der Hashes und Werte begrenzen. Nur wenn der Austausch innerhalb einer bestimmten Frist ausgeführt wird, sollte er gültig sein. Dies stellt sicher, dass keine Partei genug Zeit hat, um einen der oben genannten "Hacks" anzuwenden. Wenn es zu lange dauert, muss der Vorgang wiederholt werden.

Was noch gelöst werden muss

Eine der Parteien ist möglicherweise noch in der Lage, das Ergebnis durch Anwendung der oben genannten Techniken zu beeinflussen. In den meisten Fällen (z. B. 99.99999% der Fälle, abhängig von den Parametern) ist die Zeit zu kurz. Bei genügend Chancen könnte eine Partei jedoch das Glück haben, das Hashing zu brechen. Zum Beispiel könnte ein Spieler einfach nach dem Zufallsprinzip Zahlen ausprobieren, um einen anderen "zufälligen" Wert mit demselben Hash-Wert zu finden, den er so lange wie möglich an die anderen Spieler gesendet hat (letzter Ansatz) (damit ihn das Timeout nicht erwischt). Insbesondere wenn der Spieler sich von allen anderen zuerst ihre zufälligen Werte senden lässt, weiß er, welche Art von Werten ihm den größten Gewinn bringen würde. Also konnte er diese einfach ausprobieren. Der böse Spieler ließ dann entweder alles aus und startete neu (um eine weitere Chance zu erhalten, ohne zu verlieren) oder ließ das Spiel einfach weitergehen und die nächste Würfelrunde für einen weiteren Versuch verwenden. Sie könnten entscheiden, dass ein Spieler automatisch verlieren würde, wenn er seinen Hash oder Zufallswert nicht innerhalb des Timeouts liefert. Dies reduziert das Problem, erhöht aber dennoch die Chance eines Spielers um einen sehr sehr kleinen Betrag.

Diese Schwäche ist besonders kritisch, wenn diese sehr geringe zusätzliche Chance ausreicht, um zu stören ... Zum Beispiel, wenn ein Spieler auf diese Weise über ein komplexes Ergebnis entscheiden und viel Geld gewinnen könnte. Nehmen wir zur Fantasie an, Sie wenden diesen Algorithmus auf ein Lotteriespiel an, bei dem einer der "Spieler" der Bank-Server ist. Wir ignorieren im Moment, dass bei vielen Spielern die Datenübertragung nicht realistisch wäre (jede Person musste jeder anderen Person ihren Hash und ihren Zufallswert mitteilen, was zu N * (N-1) / 2 führte Nachrichten mussten ausgetauscht werden, was für nur N = 2000 Spieler über 1 Million ist und sich quadratisch erhöht). Okay, zurück zum Thema. Wenn nur ein Spieler seinen Hash "brechen" würde und über das Ergebnis entscheiden könnte, könnte er illegal einige Millionen Dollar aus dem Jack Pot gewinnen ... Verstanden?

Wenn Sie eine so kritische Anwendung haben, müssen Sie die Wahrscheinlichkeit berechnen, dass mindestens ein Spieler seinen Hash-Code innerhalb der Zeit knackt. Dann multiplizieren Sie dies mit dem maximal möglichen Gewinn aller Spieler, die nicht unter Ihrer Kontrolle stehen (z. B. ist der Bankspieler vertrauenswürdig). Dies würde Ihnen den maximalen Verlust pro Runde geben. Im Lotteriebeispiel würde die Lotteriebank so viel Geld pro Runde verlieren, wenn alle Spieler versuchen würden zu betrügen. Die Lotteriechancen müssten daher in einer Weise angepasst werden - oder die Wahrscheinlichkeit eines erfolgreichen "Hacks" muss weiter verringert werden.

Um die Wahrscheinlichkeit zu verringern, können Sie: a) die Timeout-Zeit verkürzen, b) eine kompliziertere Hashing-Funktion verwenden, c) längere Zahlen verwenden ODER: d) das Ergebnis auf mehrere Runden verteilen.

Das Verteilen des Ergebnisses auf mehrere Runden würde funktionieren, indem nur ein Teil des "Ergebnisses" innerhalb einer Runde entschieden und mehrere Runden ausgeführt würden. Für das Lotteriebeispiel könnte jede Zahl ihre eigene Runde haben. Auf diese Weise hätte ein glücklicher Betrüger nur die Möglichkeit, jedes Mal eine Zahl zu ändern, wenn er es schafft, den Hash zu brechen. Er müsste also 6 Mal hintereinander Glück haben (wenn die Lotterie 6 Zahlen auswählt), um den Jackpot illegal zu gewinnen. WARNUNG: Jede Runde sollte nur einen bestimmten Teil des Ergebnisses beeinflussen (z. B. eine der Zahlen in der Lotterie). Tauschen Sie nicht einfach mehrere zufällige Werte / Hashes aus und fassen Sie sie wie zuvor zusammen. Wenn Sie dies tun, kann ein Spieler, der in der letzten Runde Glück hat, das gesamte Ergebnis (!) Ändern. Sie können jedoch beispielsweise eine Runde für jedes "Bit" einer Zufallszahl ausführen.

Ein weiteres Problem ist, dass ein Spieler das Spiel "stören" kann, indem er das Ganze immer wieder auslaufen lässt. Dies kann ein Problem sein, wenn die Spieler anonym sind und Sie nicht einfach Leute verbannen können, die nicht fair spielen.

OK, ich hoffe das deckt alle Probleme und Angriffe ab ...

Viel Glück ;-)

Es sollte möglich sein. Zumindest der Teil "Manipulationserkennung".

Du wirst brauchen:

1. Ein Zufallszahlengenerator mit guter Kryptografiestärke, der Zufallszahlen erstellt, die schwer vorherzusagen oder zu erraten sind.
2. Ein guter Hashing-Algorithmus, relativ langsam zu Bruteforce, schwer umzukehren.

Dann schlage ich den folgenden Algorithmus vor.

1. Lassen Sie jeden Kunden eine Zufallszahl festlegen. Machen Sie es so lang, dass es für einen Angreifer schwierig ist, jeden möglichen Wert auszuprobieren. Möglicherweise die Länge der Ausgabe Ihres Hash-Algorithmus.
2. Lassen Sie jeden Client einen Hash dieser Nummer an jeden anderen Client senden.
3. Wiederholen Sie die Schritte 1 und 2 für die Anzahl der benötigten Würfelwürfe.
4. Lassen Sie jeden Kunden seine Zufallszahlen an jeden anderen Kunden senden.
5. Wenn ein Kunde seine Meinung über seine Nummer "geändert" hat, stimmen die Hashes nicht mit seinen Nummern überein.
6. Verwenden Sie nur "gute" Zahlen, die mit ihren Hashes übereinstimmen, um das Ergebnis der Würfe zu generieren.

Auf diese Weise kennt kein Kunde das Ergebnis eines Wurfs, bevor er seine Nummern sendet, und kann nicht vorhersagen, welche Nummern das Ergebnis verändern würden. Sie können ihre eigenen Nummern ungültig machen, aber es nützt ihnen nichts.

Wenn mindestens ein Kunde ehrlich ist und der Zufallszahlengenerator gut ist, kann ein fairer Wurf erzielt werden. Wenn jedoch jeder betrügt, wird es nicht sein. Aber in diesem Fall will sowieso niemand ein faires Spiel spielen.

Was dies jedoch nicht vermeiden kann, ist, dass ein Kunde vorgibt, das Ergebnis einer Rolle sei anders als es wirklich ist. Wenn sie die Realität ablehnen, können Sie nicht wirklich viel tun.

Wenn eine Zufallszahl generiert werden muss, lassen Sie jeden Spieler eine Zufallszeichenfolge generieren.

Jeder Spieler erstellt eine kryptografische Signatur seiner Zeichenfolgen und sendet diese an alle anderen Spieler. Nachdem alle Spieler bestätigt haben, dass sie die Unterschriften erhalten haben, werden die Zeichenfolgen selbst an alle Spieler gesendet.

Alle Spieler überprüfen jetzt die Signaturen, verketten diese Zeichenfolgen und erstellen einen Hash davon mithilfe einer kryptografisch sicheren Hash-Funktion.

Dieser Hash wird dann verwendet, um die Zufallszahl zu generieren.

Solange mindestens ein Spieler eine unvorhersehbare Zeichenfolge zum gesamten Hash beiträgt, ist das Ergebnis unvorhersehbar. Das einzig mögliche Angriffsszenario wäre, wenn einer der Spieler vorhersagen kann, welche zufällige Zeichenfolge die anderen erzeugen werden. Das ist der Grund, warum zuerst die Signaturen ausgetauscht werden: Wenn die Signaturen vorher ausgetauscht werden, kann ein Spieler nicht darauf warten, dass die anderen ihre Zeichenfolgen senden und dann eine Zeichenfolge generieren, die zu einem günstigen Ergebnis führen würde.

Vielleicht lassen Sie 2 Clients seinen eigenen Zufallsstartwert haben, den die anderen Clients nicht kennen. Wenn Sie eine neue Zufallszahl benötigen, generieren alle Clients eine Nummer. Dann fügen Sie alle für einen gemeinsamen Startwert hinzu und machen die endgültige Zufallszahl.