Hallo zusammen,

erneut ein Problem, erneut eine Lösung.

Bei einem Online-Poker Spiel (PokerTH, ein Open-Source-Projekt unter GPL) habe ich mir die Frage gestellt, wie fair so ein System überhaupt sein kann, unabhängig von der zugrunde liegenden Netzstruktur (P2P, Client/Server).

Das ist meiner Meinung nach eine sehr wichtige Frage, da der Einsatz, anders als in meinem Fall, auch Echtgeld sein könnte. Nehmen wir an, der Server (bzw. der Betreiber) würfelt die Karten und übermittelt sie den Teilnehmern. Dann muss dieser auch absolut vertrauenswürdig sein. An dieser Stelle entscheidet ganz allein die Serverapplikation über Sieg oder Niederlage der Spieler – zumindest bei reinen Glücksspielen. Hier hätte jemand mit Serverzugriff gleichzeitig Einblick in alle Karten. Böswillig könnte man sogar unterstellen, der Betreiber nimmt selbst am Spiel teil und nutzt diese Kenntnis aus – ein solches Spiel kann nicht gewonnen werden. In einem Netzwerk von gleichberechtigten, also ein P2P-Netzwerk, existiert dagegen kein Host, daher müsste ein LEA (Leader Election Algorithm) entscheiden, wer die Spielrunde leitet. Das Problem bleibt jedoch bestehen: ein Teilnehmer der Runde besitzt die Möglichkeit das Spiel zu manipulieren.

Die andere Seite ist jedoch genauso kritisch. Würfelt der Teilnehmer/Spieler die eigenen Karten, ist dies ganz offensichtlich (insbesondere bei einem Open Source Projekt), keine gute Idee. Eine weitere Möglichkeit wäre, dass ein Teilnehmer die Karten des unmittelbaren Banknachbarn bestimmt, aber von Fairness kann hier auch kaum gesprochen werden.

Beide Lösungen sind nicht wirklich überzeugend und bedeuten stets, dass mindestens einer einen Vorteil erhält. Letztenendes besteht das Problem, dass alle Teilnehmer gemeinsam etwas bestimmen müssen, also wer welche Karten bekommt, ohne diese konkret zu erfahren. Gibt es dazu eine Lösung? Die Antwort lautet: ja.

Aber leider nicht von mir, sondern von Adi Shamir, Ron Rivest und Len Adleman – den Entwicklern der RSA Verschlüsselung. Es handelt sich um ein Protokoll für ein faires Pokerspiel, welches hier zu finden ist. Bevor ich nun die Algorithmus skizziere, möchte ich allerdings noch erklären was eine kommutative Chiffre ist. Normalerweise muss beim Ver- und Entschlüsseln eine Reihenfolge eingehalten werden, z.B.:

D_key1(E_key1(x))

und

D_key1(D_key2(E_key2(E_key1(x))))

also sozusagen wie bei einer Zwiebel: jede Schale muss sauber und nacheinander aufgetragen und wieder entfernt werden um an den Inhalt zu gelangen. Bei einer Kommutativen Chiffre ist diese Reihenfolge irrelevant – funktionieren würde also ebenso:

D_key2(D_key1(E_key2(E_key1(x))))

Also: die Reihenfolge der Entschlüsselung spielt keine Rolle. Diese Eigenschaft wird beim folgenden Pokerprotokoll ausgenutzt, wobei es in der Praxis effektiv keine Einschränkung darstellt:

1. Parteien A und B einigen sich bezüglich einer klaren Kodierung der Spielkarten.
2. Die Partei A wählt einen beliebigen geheimen Schlüssel und verschlüsselt jede Karte einzeln.
3. Partei A mischt die Karten
4. Partei A übermittelt die neuen (verschlüsselten und gemischten) Karten der Partei B; B weiß daher nicht, welche Karten sich wo befinden.
5. B verschlüsselt ebenso jede Karte mit einem Schlüssel -> jede Karte ist nun sowohl von A als auch von B mit jeweils einem Schlüssel verschlüsselt worden.
6. B mischt die Karten.
7. B übermittelt die doppelt verschlüsselten und gemischten Karten der Partei A.
8. A entschlüsselt alle Karten mit seinem Schlüssel (hier tritt die Kommutativität hervor).
9. A verschlüsselt nun jede Karte einzeln, mit jeweils einem anderen Schlüssel. Die Karten sind nun alle mit einem Schlüssel von B verschlüsselt, sowie jede einzelne mit einem jeweils anderen Schlüssel von A.
10. A übermittelt B die neuen Karten.
11. B entfernt seine alte Verschlüsselung (erneut die Kommutativität).
12. B verschlüsselt, genau wie A, jede Karte mit einem eigenen und anderen Schlüssel.
13. B übergibt A die verschlüsselten Karten.
14. A legt die Karten für alle Teilnehmer (hier 2) offen.

Was liegt nun vor? Die Karten wurden alle gemischt und doppelt verschlüsselt – jeweils mit einem anderen Schlüssel von A und  B. Die Karten liegen nun „auf dem Tisch“ und die Teilnehmer einigen sich darüber, wer welche Karten bekommt. Werden die ersten 5 Karten A zugeteilt, teilt B die dafür notwendigen Schlüssel mit, und umgekehrt. Jeder besitzt also nun Karten aus diesem Kartenpool die nur dem Spieler selbst bekannt sind. Ein grundsätzlich sehr solides Verfahren. Insbesondere ist es relativ intuitiv, da in der ersten Runde die Karten lediglich verdeckt gemischt werden und in der zweiten Runde dafür gesorgt wird, dass niemand die gemischten Karten „einsehen“ kann.

Wie schon erwähnt, muss hier zwar keine asymmetrische, jedoch eine kommutative Chiffre verwendet werden. In der oben genannten Quelle wird erklärt, dass ein XOR hier nicht genügt. Wie jedes Protokoll/Verfahren hat auch dieses Schwachstellen, welche sich allerdings beheben lassen und eventuell in einem eigenen Beitrag behandelt werden.

Ob nun die oben genannte Open Source Software diese Verfahren einsetzt, kann ich nicht beantworten – vielleicht irgendein anderer interessierter Leser. Grundsätzlich besteht jedoch die Möglichkeit solch ein Pokerspiel durchzuführen – unter Umständen wesentlich sicherer als in den Spielcasinos.