Archiv der Kategorie: Kryptographie

Kein Schutz beim Offline-Tracking

Hallo zusammen,

in der Informationssicherheit lassen sich viele Probleme durch einfache Lösungsmuster erschlagen. Beispiele sind z.B. der Einsatz SSL/TLS zur Gewährleistung der Vertraulichkeit der Informationen auf dem Transportweg oder der Einsatz von Hash-Verfahren, um der Klartextspeicherung eines Passwortes zu entgehen. Diese Denkmuster wird man sowohl in der Hochschullehre, als auch (in abgeschwächter Form) bei beruflichen Weiterbildungen finden. Kritisch wird es jedoch dann, wenn diese Denkmuster nicht mehr länger für den jeweiligen Anwendungsfall durchdacht und blind angewendet werden.

Das passiert leider häufiger als man denkt und an dieser Stelle muss ich mich schonmal bei Tom Lukaß, Autor des wirklich tollen Artikels Offline-Tracking: Kundenfrequenzmessung in Ladengeschäften (vom 06.07.2016) entschuldigen, allerdings liefert mir dieser ein gutes Beispiel. Der Beitrag behandelt das WLAN-Tracking: Dabei werden die Mobilgeräte zur Besucherverfolgung (z.B. in einem Supermarkt) verwendet und durch spezielle Hardware kann ebenfalls eine Positionsbestimmung durchgeführt werden. Der Autor empfiehlt die Anwendung eines Hashverfahrens, damit die genauere Identifikation des Besuchers ausgeschlossen bzw. die MAC-Adresse anonymisiert wird:

Das WLAN-Tracking sollte aufgrund von anonymisierten MAC-Adressen durchgeführt werden. Die MAC Adresse lässt sich anonymisieren, in dem man sie gleich nach dem Eingang auf dem Router mit einer zufälligen Zahlenreihe ergänzt (sog. SALT) und aus der erweiterten Adresse einen Hashwert bildet. Das kann man sich wie einen einmaligen digitalen Fingerabdruck vorstellen.

Um dieser Identifizierung zu entgehen, soll also die MAC-Adresse verändert bzw. anonymisiert verarbeitet werden. Den hier geschilderten Anonymisierungsvorgang, also die Erweiterung um einen SALT-Wert mit anschließender Hashwertbestimmung, kennt man bereits von der Passwortspeicherung.

Dies findet auch so Anwendung, wie aus einer FAQ eines Geräteherstellers für solche Trackingsysteme ersichtlich wird:

Datenschutz ist eines der Kernthemen der infsoft Plattform. So bieten unsere Systeme zahlreiche Methoden wie Hash-Algorithmen (SHA-1) zur Anonymisierung von MAC Adressen bei Analyse- und Trackingverfahren. […]

Die Vermutung dabei ist, dass MAC-Adressen sich in in gleicher Weise durch einen Hashwert „verdecken“ lassen, wie dies bei Passwörtern der Fall ist. Das ist auch prinzipiell nicht falsch, aber nicht ganz zu Ende gedacht. Das Problem ist hier die geringe Diversität an MAC-Adressen: Eine MAC-Adresse ist eine 48 Bit langer Identifikator einer Netzwerkschnittstelle, welcher üblicherweise in hexadezimaler Darstellung in Erscheinung tritt (z.B. 50-7B-9D-CB-C0-22). Durch die 48 Bit ist die maximale Anzahl existierender MAC-Adressen schon gleich auf 281.474.976.710.656 (281 Billionen) festgesetzt. Wenn ich also alle denkbaren MAC-Adressen durchrechne, ist die getrackte MAC-Adresse natürlich ebenfalls dabei.

Noch vor 10 Jahren wäre dies auch hinreichend „schwierig“ gewesen. Seit jedoch die Kryptowährungen (z.B. Bitcoin) so einen Hype erlebt haben, sind genau für diese Probleme extrem starke Berechnungslösungen verfügbar. Der Antminer R4 kostet derzeit ca. 1000 USD und erbringt eine Leistung von 8,6 TH/s. Das sind 8.600.000.000.000 (8,6 Billionen) Hashes pro Sekunde. Das macht offensichtlich: Im worst case werden 32 Sekunden benötigt, um die MAC-Adresse, mit beliebigem SALT, aus dem Hashwert herauszurechnen. Ein einfaches Hashen einer MAC-Adresse erbringt weder eine Pseudonymisierung, noch eine Anonymisierung. Ist der SALT-Wert fest, können die Berechnungen gespeichert und erneut verwendet werden (Rainbowtable), womit die Deanonymisierung in Echtzeit erzielt wird. In diesem Fall können auch günstigere 1 TH/s Lösungen für ca. 100 USD verwendet werden.

Somit wird klar, dass ein einfaches Hashen hier keinen Mehrwert bietet. Es ist stellt sogar eine Gefahr dar, da das Datum aus juristischer Perspektive fälschlicherweise als anonymisiert betrachtet werden könnte und damit seinen datenschutzrechtlichen Schutz verliert.

Mit unsicherem Code ins Weltall

Hallo zusammen,

zur Abwechslung mal was über Krypto. Ein Bekannter hat mir einen Hinweis gegeben, dass in einer Stargate SG1 Folge (S7E09 „Avenger 2.0“) auf einer Tafel etwas geschrieben stand, was recht „kryptisch“ aussieht. Hier ein Bild der Szene (ca. Minute 12):

Bildzitat aus Stargate SG1 Episode Staffel 7 Folge 9 "Avenger 2.0"

Bildzitat aus Stargate SG1 Episode Staffel 7 Folge 9 „Avenger 2.0“

Auf den ersten Blick vermutet man Java, was natürlich recht amüsant wäre: Ob (damals Sun) Oracle wohl eine JVM für Stargates (bzw. Wahlgeräte) anbietet? Tatsächlich ist es jedoch C#, was es nicht weniger amüsant macht. Da es eine über 10 Jahre alte Episode ist, ist dies natürlich auch anderen schon aufgefallen. Es handelt sich bei diesem Quelltext um eine etwas intensiver kommentierte Version einer Klasse zur Entschlüsselung von Dateien auf dem Dateisystem, die man hier finden kann. Analog gibt es natürlich auch eine Version zur Verschlüsselung.

Es ist natürlich so, dass die „Macher“ der Serie nur etwas kryptisch aussehenden Programmtext präsentieren wollten und sind dabei über diese Zeilen gestolpert. Aber aus Neugier habe ich mir das Programm etwas näher angesehen. Es besteht aus einer Hilfsklasse StoreCryptoStream, aus einer Klassenmethode zur Generierung des Schlüsselmaterials (GenerateKey) und einer weiteren Klassenmethode zur Vorbereitung und Durchführung der Entschlüsselung (DecryptData).

In der DecryptData-Methode werden Streams eingerichtet und die Entschlüsselung durchgeführt. Aufmerksam wurde ich, als ich mir die GenerateKey-Methode genauer angesehen habe, welche aus einer Passphrase (String) das zur Verschlüsselung (DES) passende Schlüsselmaterial generiert:

          symKey = new byte[8];
          symIV = new byte[8];

          SHA1_CSP sha = new SHA1_CSP();
          sha.Write(bt)
          sha.CloseStream();
          for (int i = 0; i < 8; i++) {
              symKey[i] = sha.Hash[i];
          }
          for (int i = 8; i < 16; i++) {
              symIV[i - 8] = sha.Hash[i];
          }

Das fand ich recht interessant: Hier werden, aus dem Hashwert (SHA1) der Passphrase (String), Schlüssel und Initialisierungsvektor abgeleitet. Da wir bei DES (DecryptData-Methode) eine 64 Bit Schlüssellänge (wovon 56 effektiv sind) und 64 Bit Blocklänge haben, brauchen wir also 128 Bit die uns durch den 160 Bit SHA1 zur Verfügung stehen. Ein Hashverfahren zu verwenden um aus einer Passphrase Schlüsselmaterial zu gewinnen ist ja nicht neu: Dies findet auch bei PBKDF2 statt. Es wird zur Erhöhung der Brute-Force-Resistenz eingesetzt, da die Berechnung eine gewisse Zeit in Anspruch nimmt und nicht abgekürzt werden kann. Dabei werden jedoch sehr viel mehr Iterationen durchgeführt (z.B. 100 000) und nicht nur eine.

Die meisten symmetrischen Blockchiffren benötigen keinen Initialisierungsvektor (IV): so auch der DES nicht. Da allerdings regelmäßig keine blockweise Verschlüsselung sondern ein Betriebsmodus zum Einsatz kommt, hat er einen festen Platz in den Programmbibliotheken. Normalerweise wird der IV vor der Verschlüsselung zufällig generiert und vor/nach der Übermittlung als Klartext mitgesendet. Der Empfänger kann mittels geheimen Schlüssels und mitgesendeten IVs das Chiffrat entschlüsseln. Die Generierung eines IVs aus der Passphrase hat den enormen praktischen Vorteil, dass diese dem verschlüsselten Ciphertext nicht beigefügt sein muss. Der Nachteil ist, dass der IV dann nicht mehr zufällig generiert wird sondern deterministisch vom Schlüssel bzw. der Passphrase abhängt.

So was Ähnliches wird zwar auch im SSH Protokoll durchgeführt. So wird dort unter Einsatz einer Hashfunktion und unterschiedlichen Salt-Werten mehrere Schlüssel und IVs generiert. Allerdings wird hierbei schon zu einem frühen Zeitpunkt der „Zufall“ eingebracht und genau diese Zufälligkeit fehlt beim gezeigten Programm vollständig.

Ist das jetzt gut oder schlecht? Ich habe dazu recherchiert und mir meine eigenen Gedanken gemacht und die Antwort ist: Es kommt darauf an, ist aber fast immer schlecht.

Nehmen wir z.B. Stromchiffren (wie, mittlerweile unsicher, RC4). Hier würde, bei gleichem Passwort, immer der gleiche IV und damit der gleiche Schlüsselstrom generiert werden. Sofern zwei verschlüsselte Texte mit dem gleichen Schlüsselstrom verschlüsselt sind, könnten diese gegenseitig ge-xor-t und damit der Schlüsselstrom herausgerechnet werden. Ebenso bei bei Blockchiffren mit dem entsprechenden Betriebsmodus wie dem Cipher Feedback Mode (CFB) oder dem Output Feedback Mode (OFB): Da hier aus einer Blockchiffre eine Stromchiffre konstruiert wird, haben wir exakt das gleiche Problem. Bei diesen Verfahren hängt die Sicherheit sehr stark an der Zufälligkeit des IVs, welcher so jedoch nicht mehr zufällig ist.

Wie ist es bei einer Blockchiffre im ECB und CBC Modus? Beim ECB-Modus sind wir schmerzfrei, denn dort wird der IV nicht verwendet. Müssen dabei jedoch die allgemeine Unsicherheit des ECBs hinnehmen. Beim CBC-Modus (den ich schonmal erklärt habe) haben wir zunächst auch kein Problem. Allerdings muss man hierbei gut aufpassen: Verschlüsselungsbibliotheken werden beim CBC-Modus den IV ans Ende des Chiffretextes setzen, da dieser üblicherweise zufällig generiert und zur Entschlüsselung gebraucht wird. Das bedeutet aber, dass wir dem verschlüsselten Text ein (Teil)Hash des Passwortes mitsenden! Möglicherweise kann genau dieser Teilhash dann in einer Rainbowtable für SHA1 gefunden und entschlüsselt werden. Ebenso erleichtern wir dem Angreifer die vollständige Schlüsselsuche beträchtlich. Allgemein wird der IV als „öffentlich“ angesehen und wird dementsprechend ungeschützt sein. Eine Klassifizierung, welcher ein einfacher SHA1 Hash der Passphrase nicht haben sollte.

Zusammenfassend sollte man den IV zufällig generieren und auch genau so verwenden. Nur wenn man ganz genau weiß was man tut, kann man von dieser Regel abweichen.

Wie ist es nun bei diesem Programm? Das ist leider nicht ganz klar, denn der Programmtext lässt sich (zumindest unter Visual Studio) nicht mehr übersetzen: in über 10 Jahren hat sich C# diesbezüglich weiterentwickelt. Man könnte das Programm zwar durch Anpassungen wieder lauffähig bekommen, würde jedoch damit ggf. auch die Funktionsweise beeinflussen. Es ist zu vermuten, dass hier der ECB-Modus zum Einsatz kam und so der IV keine Rolle spielt. Wenn der CBC eingesetzt wurde, müsste man prüfen, ob dem Ciphertext der IV beigelegt war. So oder so war jedoch schon damals (und ist heute weiterhin) von der Nutzung dieses Quelltextes (bzw. einer lauffähigen Variante) grundsätzlich abzuraten.

Dies könnte auch der Grund sein, weshalb der in dieser Episode programmierte „Avenger“ (Computervirus) so unsicher war ;-).

Unclevere Hardware

Hallo zusammen,

durch einen Beitrag von fefe bin ich auf diese Amazon Rezension aufmerksam geworden.

Bei diesem Produkt handelt es sich, soweit ich dies aus der Produktbeschreibung herauslesen konnte, um eine „smarte“ Steckdose, die über WLAN bzw. eine App gesteuert werden kann. Der Rezension nach basiert dies auf dem ESP8266-Chip, von welchem ich auch ein paar besitze. Sie sind derzeit der günstigste Weg (2-3€), eine (kleine) elektronische Schaltung ins WLAN zu bekommen sofern man keine zu hohen Ansprüche hat und etwas Geduld mitbringt.

Der Rezensionist hat sich etwas Mühe gemacht, das Gerät genauer unter die Lupe zu nehmen. Sofern sich die steuernde Hardware (Smartphone+App) im WLAN befindet, werden die Befehle wohl direkt an die Steckdose übermittelt. Sofern der Nutzer jedoch außer Haus ist, wird das Ganze über einen Server in China gelenkt:

If your phone is connected to the same network as the socket then this is just done by sending a command directly, but if not you send a command via an intermediate server in China (the socket connects to the server when it joins the wireless and then waits for commands).

Ich denke die technischen Gründe hierfür sind klar. Der Hersteller wollte damit Probleme durch wechselnde IP-Adressen und vor allem notwendige NAT-Weiterleitungsregeln umgehen. Es muss auch beachtet werden, dass insb. im asiatischen Raum die Verwendung von NAT deutlich intensiver ist als in Europa. Daher ist IPv6 dort auch schon weiter fortgeschritten als hier. Wäre interessant, ob die Steckdose hierfür im Sekundentakt (polling) eine Anfrage stellt und mit welchem Protokoll. Sinnvoll gelöst wäre es (mMn), wenn in gewissen Intervallen ein UDP-Datagramm gesendet und damit eine Lücke im NAT geöffnet wird, durch die der Server dann antworten kann, wenn es notwendig ist. Flusskontrolle ist hier ohnehin nicht gefragt und quittieren kann man die Befehle auch manuell.

Weiter geht’s in der Rezension:

The command packets look like they’re encrypted, but in reality there’s no real cryptography here at all. I wrote a simple program to decode the packets and looked at them in more detail. There’s a lot of unnecessary complexity in the packet format, but in the end the relevant things are just a command and the MAC address of the socket. On the local network this is sent directly to the socket, otherwise it goes via the server in China. The server looks at the address and uses that to decide which socket to pass it on to. Other than the destination, the packets are identical.
This is a huge problem. If anybody knows the MAC address of one of your sockets, they can control it from anywhere in the world. You can’t set a password to stop them, and a normal home router configuration won’t block this.

Hier ist natürlich ein Nerv getroffen. Hier scheint einfach die primitivste Form (Security by obscurity) gewählt worden zu sein: Die App übermittelt dem Server einen Befehl bzgl. einer MAC-Adresse und bei einer Anfrage von einer MAC-Adresse wird dieser Befehl weitergegeben. Hier ist natürlich offensichtlich, dass die MAC-Adresse Bestandteil des Protokolls ist, da diese auf dem Weg durch das Internet verloren geht. Eine Überprüfung findet daher nicht statt. Offenkundig kann daher jeder sowohl App, als auch Steckdose spielen.

Aber ich möchte die Sache noch etwas weiter durchdenken und überlegen, wie ICH dieses Problem gelöst hätte. Damit meine ich eine Lösung mit EINFACHEN MITTELN die auf dieser schwachbrüstigen Hardware auch funktionieren kann.

Die Tatsache, dass in der App kein Passwort hinterlegt werden kann, wäre zunächst mal noch kein Indikator für ein unsicheres Gerät. Die App könnte bei erstmaliger „Bekanntmachung“ mit der Steckdose passendes Schlüsselmaterial über WLAN austauschen, ähnlich wie bei Bluetooth: Bei erstmaliger Inbetriebnahme würfelt sich die Hardware einen Schlüssel. Hier muss noch beachtet werden, dass „Würfeln“ für diese Hardware ein schwieriges Problem ist. Daher würde ich bevorzugen, dass sowohl App, als auch Steckdose, gemeinsam ein Passwort ausknobeln. Die Smartphone-Hardware müsste gute Fähigkeiten dazu haben. Ob bei Nutzung mehrerer Smartphone-Apps verschiedene Passwörter Verwendung finden, lasse ich an dieser Stelle mal offen. Besser wäre es, aber notwendig wäre es nicht; kommt auf die Hardware an.

Das gemeinsam gefundene Schlüsselmaterial kann fortan die App verwenden um Befehle an die Steckdose zu verschlüsseln. Hierbei muss man eine Designentscheidung treffen: Möchte man einen Schutz der Vertraulichkeit und Integrität, oder genügt der Schutz der Integrität allein. Bei letzterem würde eine Hash-Funktion zur Absicherung genügen. Ich wähle ersteres, da der Aufwand nicht viel größer ist:

CMD = E(MAC + ZAEHLER + BEFEHL , SCHLUESSEL) + MAC

wobei E(Klartext,Schüssel)=Chiffretext eine symmetrische Verschlüsselungsfunktion (mit ordentlichem Betriebsmodus) und „+“ eine Konkatenation ist. So verschlüsseln wir den Befehl auf Basis des gemeinsam ausgetauschten Schlüsselmaterials. Der Zähler hat den Zweck, dass das Kryptogramm unabhängig vom Befehl (und unabhängig vom Betriebsmodus) nicht immer identisch aussieht. Durch die diffusiven Eigenschaften der Verschlüsselungsfunktion ändert sich das Kryptogramm bei Änderung des Zählers.

Hierbei haben wir jedoch noch das Problem des Replay-Angriffs vernachlässigt. Jemand, der dieses Kryptogramm abfängt, könnte diesen Befehl immer und immer wieder senden. Dies bekommt man mit einem Challenge-Response zunächst gelöst, würde das Protokoll jedoch wieder gegenüber Man-in-the-Middle angreifbar machen: theoreitisch ein Vorteil, aber nicht praktisch. Daher sehe ich hier nur zwei Möglichkeiten:

  1. die Steckdose merkt sich den Zähler im Kryptogramm und ignoriert Befehle die darunter liegen oder
  2. App und Steckdose besitzen synchronisierte Uhren.

Da Lösung 2 vermutlich über die Fähigkeiten der Hardware hinausgehen, muss man sich wohl mit 1 begnügen. Dabei muss man ggf. aber auch noch im Kopf behalten, dass dies beim Zugriff von mehreren Geräten/Apps gleichzeitig zu Problemen führt. Die bekommt man aber in den Griff.

Vermutlich wird man das Replay-Problem (oder ein verzögertes Senden) nicht mit einfachen Mitteln in den Griff bekommen. Jedoch wäre schon allein die Tatsache, dass nicht jeder in der Lage ist die Steckdose zu schalten und jeden Schaltprozess beobachten zu können. Ein Gewinn, der nur etwas mehr Implementierungsarbeit gekostet hätte.

Die Frage danach, inwieweit Personen mit Zugriff auf das WLAN auch (langfristig) Zugriff auf die Steckdose haben, lasse ich an dieser Stelle ebenfalls unbeachtet. Derzeit ist mein WLAN auch noch eine absolut vertrauenswürdige Zone für mich und die kürzliche Änderung des Telemediengesetzes wird daran wohl auch zunächst nichts ändern. Aber das ist eine andere Geschichte.

Unsicher ist Unsicher

Hallo zusammen,

über Facebook bin ich auf einen Wettbewerb gestoßen, den ich euch nicht vorenthalten möchte:

Deine Aufgabe ist es, ein Programm zu realisieren, mit dessen Hilfe es möglich ist, ausgewählte Dateien (und Verzeichnisse?) zu verschlüsseln und später wieder zu entschlüsseln.

[…]

  • Verschlüsselung von Daten über die Konsole oder ein GUI
  • Implementierung eines Verschlüsselungsalgorithmus (gerne auch ein eigens entwickelter Algorithmus!)
  • Entschlüsselung der Daten über gleiches Programm

[…]

Quelle: Code Competition: Sicher ist Sicher. https://www.it-talents.de/cms/aktionen/code-competition/code-competition-04-2016

Bereits in den Kommentaren auf Facebook wurde dem Betreiber von dieser Idee abgeraten. Verschlüsselungsverfahren sollten nur von dafür qualifizierten Personen konzipiert werden. Fehler können bei der Anwendung selbiger ohnehin noch genug gemacht werden. Natürlich ist es eine gute Sache, junge Menschen für die Programmierung zu begeistern. Allerdings werden auf diese Weise die Security Audit Findings von morgen generiert. Ich stelle mir das in 5-7 Jahren so vor:

Chef: Wir brauchen in unserer Software dringend noch eine Verschlüsselungslösung um die sensiblen Daten der Kunden zu schützen.
Talentierter Mitarbeiter: Ich habe da im Studium mal etwas gebaut, ist aber vermutlich nicht ganz si…
Chef: Perfekt!

Trotzdem hat mich dieser Ausschreibungstext inspiriert, was man wohl alles an „billigen Lösungen“ einreichen könnte, um die 222 € zu gewinnen (oder den Raspberry Pi 3). Mal von einfachen Substitutions- und Permutationslösungen abgesehen, könnte man sich einfach einer Feistelchiffren-Konstruktion bedienen (wie in DES/3DES oder Blowfish). Es hat den Vorteil, dass man sich über die Entschlüsselung keine Gedanken machen muss.

Noch einfacher wäre es, eine Stromchiffre zu konstruieren. Für den Schlüsselstrom könnte man einfach einen PRNG (Pseudozufallsgenerator) mit einem Seed initialisieren und auf den Klartext auf-XOR-en. Das wäre nur eine Zeile – und sogar die gleiche für Ver- und Entschlüsselung.  Das fiese daran ist, dass das Ergebnis recht zufällig aussieht und ein Blackbox-Audit vermutlich sogar bestehen würde. Hier exemplarisch in Python und nur für Text, aber das geht mit einer Datei natürlich genauso gut:

>>> import random

>>> text = "hier kann ein beliebig langer Klartext geschrieben werden"

### Verschlüsselung ###
>>> random.seed("hier den Schlüssel!"); text="".join([chr(ord(e)^random.getrandbits(8)) for e in text])
>>> text
'\xeb\xbdP~0v\xa3\xb8[c\x0f\xb7\xaa\xbe\xaf\x1f\x15#\xd2:\x17\xbeU\xfesJ\x1d\x18\xcbmb\xe256*\x9ct\xc2\rl0\xbb\x9e\xbc0GV\xc5\xadG\xa89\xa0_"\x9f\xaa'

### Entschlüsselung ###
>>> random.seed("hier den Schlüssel!"); text="".join([chr(ord(e)^random.getrandbits(8)) for e in text])
>>> text
'hier kann ein beliebig langer Klartext geschrieben werden'

Anstelle des PRNG könnte man auch ein Hash-Verfahren nehmen und mit einem Schlüssel initiieren. Sicher ist daran jedoch nur das Lachen der Auditoren.

Mich würden die Einreichungen sehr interessieren. Vermutlich wird am Ende die ausgefallenste Lösung gewinnen und die Sicherheit eher auf der Strecke bleiben.

 

Von Kühen zu Turing

Hallo zusammen,

heute möchte ich präsentieren, welche „Alltagsprobleme“ sich in der Kryptologie wiederfinden.

Vor kurzem hat mich jemand angeschrieben, er säße vor einem kleinen mathematischen Problem. In seinem Dorf ist ein so genanntes Kuhfladen-Bingo geplant. Dafür muss ein Feld von fester Größe, in eine dynamische Anzahl kleinerer unterteilt werden. Nochmal langsam:

Wir haben zunächst das große Feld bzw. die Wiese. Diese hat eine konstante Größe bzw. im Falle, dass sie rechteckig ist, eine Länge und eine Breite. Jetzt haben wir x Lose verkauft und wollen dieses Feld in x-viele gleichgroße „kleine“ Felder aufteilen. Die Summe aller kleinen Flächen entspricht der Gesamtgröße – also wir wollen stets einen Gewinner und keine „unbesetzten“ Felder. Es soll also ein Schachbrettmuster auf dieses Feld gelegt werden, wobei in diesem Fall die kleinen Felder nicht quadratisch sein müssen.

Mathematisch ausgedrückt, suchen wir zwei ganzzahlige n und m, wobei n*m = x und x die Anzahl der verkauften Lose ist. Kennen wir n und m, können wir die Länge bzw. Breites des Feldes durch n bzw. m teilen und erhalten die Größe der „kleinen“ Rechtecke. Ein Beispiel:

Das Feld ist L=8 x B=16 Meter groß. Es wurden zufällig 1024 Lose verkauft. Also suchen wir:

n * m = 1024

Eine Lösung ist: n = 4, m=256. Demnach teilen wir die Länge L=8m durch 4 und erhalten l=2m – außerdem die Breite B=16m durch 256 und erhalten b=0,0625m. Ein kleines Feld hat also die Ausmaße l=4m und b=6,25cm. Wie wir allerdings schnell erkennen, gibt es bei dieser Gleichung mehrere Lösungen. Ebenso wären n=8, m=128 und sogar die triviale Lösung n=1 und m=1024 in der Lösungsmenge enthalten.

Einen naiven Lösungsalgorithmus finden wir also schnell: wir suchen einen Teiler von x im Intervall [2, sqrt(x)] also zwischen 2 und der Wurzel von x. Bei x=1024 ist das die 2, die 4, die 8, die 16 und die 32. Das lässt sich relativ einfach mit einer Schleife realisieren.

Daraufhin ergab sich die Frage, ob dafür nicht auch eine bessere bzw. effizientere Lösung existiert. Das Beste wäre eine Formel, in welcher nur die Variablen einzutragen sind und dann ein brauchbares (nichttriviales) Ergebnis präsentiert. An dieser Stelle möchte ich dem Leser Zeit geben um darüber nachzudenken. Auch bezüglich der Frage, warum sich dieses Problem in einem Blog über Kryptologie wiederfindet.

~

Ich habe eben gezeigt, dass wir bei diesem Problem zwei ganzzahlige Teiler suchen: n und m bzw. n*m=x. Ich ändere nun mal die Namen der Variablen: p*q=m. Sei also m ein RSA-Modul, also das Produkt zweier Primzahlen, so sind p und q ganzzahlige Teiler von m. Wir haben also „mehr oder weniger“ nach einem effizienten Algorithmus bzw. einer Formel gesucht, die RSA-Verschlüsselung zu brechen. Wären wir an jenem Abend erfolgreich gewesen, würde ich diesen Blogeintrag an einem Strand in der Karibik zu Ende schreiben.

Wie schon oft erwähnt, ist die „schwierige“ Suche nach den Primzahlen p und q genau das, was die RSA-Verschlüsselung ausmacht. Und die Tatsache, dass für p*q=m (p,q prim) bisher noch kein effizienter Algorithmus gefunden wurde, bietet uns Schutz bei Online Banking, Zertifikaten (PKI), VPN-Tunneln und vielem mehr.

Moooooooment. Da steht doch p*q=m (p,q prim) – also wir suchen zwei Primzahlen dessen Produkt m ergibt. Bei unserem Problem oben war jedoch die Rede von einem beliebigen Teiler! Stimmt. Es folgt ein Ausflug in die Zahlentheorie und theoretische Informatik.

Angenommen wir hätten das oben beschriebene Feldaufteilungsproblem effizient gelöst, dann wären wir im Besitz einer Formel oder eines Algorithmus, den wir einfach F nennen – F für Feld. Wir übergeben dem Algorithmus F also die Anzahl der Lose und selbiges generiert uns zwei ganzzahlige Teiler n und m. Auf der anderen Seite haben wir das RSA-Problem – wir besitzen also einen „langsamen“ Algorithmus für dieses Problem und nennen diesen R. Wir übergeben R ein RSA-Modul (also das Produkt zweier Primzahlen) und es liefert uns das entsprechende p und q.

Damit sind F und R also informell definiert. Nun übergeben wir, nur aus Spaß, unserem Feldproblem F ein RSA-Modul, sagen wir r(=p*q). Warum auch nicht – es ist ja auch nur eine Zahl. F liefert uns nun also zwei ganzzahlige Teiler n und m wobei gilt: n*m=r. Jetzt wird’s spannend: nach dem Fundamentalsatz der Arithmetik ist die Primfaktorzerlegung eindeutig und stets existent. D.h. das, was wir hier zurückbekommen, müssen p und q sein. Warum? Angenommen es gäbe noch eine andere Aufteilung z.B. a*b=r, dann hätte sowohl a, als auch b eine Primfaktorzerlegung (Existenz!) welche nicht mit p*q übereinstimmt. Das ist ein Widerspruch zur Eindeutigkeit – somit haben wir indirekt p=n und m=q bewiesen. #

Dieser Teil muss nun nicht unbedingt verstanden worden sein. Wichtig ist nur, dass wir das Problem R, also die Zerlegung eines RSA-Moduls, mit Hilfe von F lösen können. In der Informatik spricht man hier auch von Turingreduzierbarkeit. Wenn wir wissen, dass wir R mittels F lösen können, dann muss R „leichter“ sein als F, bzw. „R ist turingreduzierbar auf F“ oder „F ist Orakel für R“. So lassen sich Probleme in Klassen einteilen, was relativ komfortabel ist: sobald wir einen guten Algorithmus für F gefunden haben, ist auch effizient R gelöst. So müssen wir also nur nach einer Lösung für F suchen, wobei diese auch schwieriger sein könnte als R. Äquivalenz liegt vor, wenn eine Reduktion in beiden Richtungen möglich ist. Um die Frage vorweg zu nehmen: dies ist hier der Fall; F und R sind Turing-Äquivalent (ohne Beweis).

So sind wir von den Kühen, über die Kryptologie, zur theoretischen Informatik gekommen.

Sicherheit beim Online-Poker

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.

Primfaktorzerlegung und NP

Hallo,

zunächst eine Warnung: dieser Beitrag ist relativ schwierig und ohne Vorkenntnisse in theoretischer Informatik nicht zu verstehen.

Im Laufe einer Lehrveranstaltung hat sich die Frage gestellt, ob die Primfaktorzerlegung (genauer: RSA – also 2 Primfaktoren) in NP liegt bzw. sogar NP-vollständig ist – ums populärer auszudrücken: wie viel Ärger bekommen wir, falls P=NP gilt.

Wir haben allerdings an dieser Stelle jedoch das Problem, dass die Komplexitätsklasse NP bzw. die Laufzeitfunktion NTIME auf Sprachprobleme – also Entscheidungen definiert ist. Innerhalb der Literatur finden sich wenig und vor allem sehr oberflächliche Aussagen darüber („es ist leicht einzusehen dass dieses Problem in NP liegt…“). Die letzten Wochen habe ich intensiver darüber nachgedacht und ich denke, eine brauchbare Lösung anbieten zu können.

Zunächst wichtige Vorarbeit:  die Frage, ob eine natürliche Zahl eine Primzahl ist oder nicht, liegt in P (also deterministischer Polynomialzeit). Erreicht wird dies durch den AKS-Primzahltest. Damit ist auch die Frage, ob eine Zahl n (ungleich 1) Primteiler besitzt in P feststellbar, da dies immer der Fall ist, sofern es sich um keine Primzahl handelt (Hauptsatz der Zahlentheorie).

Im nächsten Schritt prüfen wir, ob die Zerlegung des RSA-Moduls in NP liegt.

Nichtdeterministische ZerlegungNehmen wir hierzu beispielhaft die Primzahlen p=7 und q=11 also M=p*q = 7*11=77, binär dargestellt 1001101. Mittels eines naiven Nichtdeterministischen Algorithmus, können wir von 1 bis sqrt(M) alle möglichen Teiler durchprobieren. Dass dies in NP liegt, soll mittels der Abbildung gezeigt werden. Die Baumtiefe entspricht n/2, also die halbe Eingabelänge n(=7). Der Übersicht halber hier nur die Tiefe 3 anstelle 4.

Durch diese Verzweigung erhalten wir also alle Lösungskandidaten h.

Im blauen Kasten prüfen wir nun, ob h ein Primteiler von M ist. Sowohl der Primzahltest „ist h eine Primzahl?“ liegt in P (wie oben erwähnt), als auch die Division „ist h ein Teiler von M“. Auch würde der Primzahltest des zweiten Divisors in P liegen. Dementsprechend liefert der skizzierte Nichtdeterministische Algorithmus am Ende ein „ja“, da 111 (=7) sowohl Primzahl, als auch Teiler von M (77) ist.

Wir haben also nun festgestellt, dass die Frage nach der Primfaktorzerlegung in NP liegt. Das hilft uns allerdings nur bedingt, da diese Antwort schon vorher bekannt war. Per Definition besitzt ein RSA-Modul zwei Primteiler, daher würde der Algorithmus natürlich stets ein ja liefern. Wir müssen also dieses Entscheidungsproblem (1)  nutzen, um effizient das Optimierungsproblem (2) zu lösen.

Aus diesem Grund definieren also das Problem in folgender Weise neu:

Eingabe: (M,k) wobei m das RSA-Modul (bestehen aus dem Produkt zweier Primzahlen), und k eine beliebige Zahl k<=M.

Zulässige Lösung: ja/nein

Frage: liegt ein Primfaktor des RSA-Moduls M unterhalb von k.

Wir übergeben also das Modul M=(p*q) und fragen, ob sich der kleinere Primfaktor unterhalb von k befindet. Dieses Entscheidungsproblem ändert am oben skizzierten Algorithmus die Laufzeit nur um einen konstanten Faktor, welche in der polynomiellen Unschärfe sowieso verschwindet. Wir sind inder Lage, wie in der nächsten Abbildung zu sehen, mittels einer binären Suche den Primfaktor exakt zu bestimmen:


Binäre Suche nach dem Primfaktor

Können wir also das Entscheidungsproblem (1) als Orakel verwenden, so lässt sich auch dieses Optimierungsproblem (2) sehr effizient (logarithmisch) lösen. Die binäre Suche geht in der polynomiellen Unschärfe verloren, womit wir informell bewiesen haben: bei P=NP liegt die Faktorisierung auch in P.

Welche Auswirkungen hätte P=NP auf den Alltag? Diese Frage lässt sich leider nicht beantworten, da nicht jeder Algorithmus in P auch effizient ist. Wäre der Exponent jedoch niedrig, wären die Folgen schwerwiegend: die PKI würde zusammenbrechen, wodurch sicheres Online Banking unmöglich wäre. Jedes asymmetrische und damit auch jedes hybride Verschlüsselungssystem wäre hinfällig. Die Quantenkryptographie, die hiervon nicht betroffen wäre, liefert keinen adäquaten Ersatz.

Hoffen wir also, dass P != NP gilt.

Peer to Peer – Sicherheit

Hallo zusammen,

vor Kurzem ist in einem Spieleforum die Frage aufgekommen, wie es mit der Sicherheit von Peer-to-Peer Systemen aussieht. Vermutlich werden jetzt viele Leser an die juristischen Folgen durch, populär ausgedrückt, „illegale Downloads“ denken. Damit soll sich dieser Beitrag allerdings nicht befassen. Außerdem muss auch die Frage geklärt werden, wieso sich ein „Spieler“, eine möglicherweise leicht Klieschee behaftete Gruppe, dafür interessiert.

Insbesondere MMORPGs zeichnen sich durch einen sehr dynamischen Inhalt aus, was für viele einen Reiz darstellt, eine beachtliche Menge an Zeit zu investieren. Dies erfordert jedoch einen permanenten Aktualisierungsvorgang aller Clients. Viele „Kleinigkeiten“, wie Art/Position/Verhalten von s.g. NPCs können durchaus „on the fly“ dem Spieler mitgeteilt werden. Umfangreichere Änderungen, insbesondere neue Grafiken, erfordern jedoch eine Änderung des Programms bzw. der verwendeten Bibliotheken. Hiervon soll allerdings der Spieler möglichst wenig betroffen sein – insbesondere soll er nicht gezwungen sein auf dubiosen Webseiten die Patches zu laden und dann auf dem jeweiligen Rechner zu installieren. Jedoch ein Client-Server Modell, bei dem ein Server die Daten für alle Clients bereitstellt, ist nur für geringe Benutzerzahlen praktikabel. So bedeutet ein 100 MB Update, was durchaus nicht selten ist, bei 100.000 Spielern nunmal 10.000.000 MB Traffic, also 10 TB. An dieser Stelle sei noch anzumerken, dass es durchaus Spiele mit 5-10 Millionen aktiven Spieler gibt. Außerdem besteht ein betriebswirtschaftliches Interesse, die Kosten solcher Prozesse möglichst gering zu halten.

Was also tun? Das Thema liefert die Antwort: Peer to Peer Netzwerke, kurz P2P. Wie funktioniert das?
Nunja, viele leichtverständliche Informationen findet man auf einschlägigen Webseiten. Ich möchte an dieser Stelle insbesondere auf das P2P Netz eingehen, welches überwiegend beim Filesharing eingesetzt wird. Auch wenn „Filesharing“, „Peer to Peer“, etc. vielen Lesern die roten Alarmglocken schlagen lässt: es ist eine Technik, die von vielen Unternehmen eingesetzt wird und daran ist überhaupt nichts Illegal. Sie eignet sich allerdings auch zum Tausch von geschütztem Material wodurch sie häufig in einen falschen Zusammenhang gesetzt wird. Um dieses System in kurzen Worten zu erklären, möchte ich mich der Schneeball-Metapher bedienen:

Durch umfangreiche Aufklärungsarbeit der öffentlich rechtlichen Funk und Fernsehanstalten sollte vielen Lesern bekannt sein, wie ein Schneeballsystem (oder ein Kettenbrief) funktioniert. Wir definieren eine Person, die ein Produkt an eine Reihe von Personen anbietet und nennen diesen Tracker. Diese Reihe von Personen bemühen sich, aus eigenem Interesse, möglichst viele weitere Personen für dieses Produkt zu gewinnen. Wir bezeichnen alle Personen, die daran interessiert sind, als Schwarm. Angenommen jeder Teilnehmer gibt das Produkt (oder die Information) nur an zwei Andere weiter, haben wir nach 30 Schritten schon eine Schwarmgröße von 1.073.741.823 (2^30-1). Der Aufwand für den Einzelnen, 2 weitere zu „finden“ bzw. zu bedienen, war relativ gering – in der Gesamtheit war das Produkt jedoch ein riesen Erfolg.

Als Informatiker möchte ich jedoch an dieser Stelle anmerken, dass es sich hierbei um einen Baum der Ordnung 2 handelt – hingegen ein P2P System als ein Multigraph anzusehen ist. Übertragen auf das „Updateproblem“: der Tracker wirft den Patch also in die Menge (den Schwarm) und die Spieler organisieren sich untereinander diesen zu verteilen. Also läd man, bei diesem Vorgang, nicht vom offiziellen Server, sondern von Personen „wie dich und mich“ – jedoch natürlich nur von den Beteiligten.

Nun zurück zu dem besorgten Spieler. Grundsätzlich handelt es sich hierbei auch um Programmaktualisierungen. D.h. der Programmcode wird entweder ersetzt oder Neuer wird eingefügt – je nach Updatestrategie. Ein Beweis hierfür ist auch leicht erbracht: Updater sind immer „extra“ Programme, also kein Unterprozess. So findet sich in dem entsprechenden Spielordner stets das Spiel selbst, als auch ein Updater als ausführbare (exe) Datei.

Und daher nun endlich die Frage: Können mir andere Spieler „Schadcode“ übergeben, der sich dann, durch den Updatevorgang, auf meinem Rechner befindet?

Damit habe ich mich etwas Näher befasst. Zunächst muss natürlich klar sein, dass diese Frage nicht für alle Spiele geklärt werden kann. Grundsätzlich werden Daten von unbekannten Quellen geladen und diese können durchaus Fehlerhaft sein – gewollt oder ungewollt. Das ist die schlechte Nachricht. Die Gute ist, dass sich viele Spielebetreiber Techniken bedienen, die sich mittlerweile als Standard etabliert haben. Das relativ bekannte „BitTorrent“ Protokoll ist eines dieser – wofür es auch sehr viele und gute Clients gibt. Bei dieser Technik erhält der Client ein File genannt „Torrentfile“. Dieses enthält eine Auflistung der Dateien, die geladen und verteilt werden müssen – zusätzlich weitere triviale Informationen.
Am Ende, das lässt uns wieder aufatmen, ein SHA-1 Hash für jeden Part. Wer mag, kann an dieser Stelle einen Exkurs zum aktuellen Stand der Technik bzgl. der Sicherheit des SHA-1 unternehmen.

~

Wieder zurück? Gut. Denn selbst wenn wir ein Programm hätten, das uns „günstig“ Kollisionen des SHA1 aufzeigt, wäre es sehr unwahrscheinlich, dass dabei ein Teil eines ausfühbaren Programmes herauskommt und gleichzeitig auch den gewollten Schadcode enthält. Diese Thematik lässt sicherlich Platz für Diskussionen – allerdings kann an dieser Stelle und an diesem Tag festgehalten werden, dass der SHA-1 Hashalgorithmus für diesen Einsatzzweck noch völlig genügt. Was ein Hashcode „genau“ ist, habe ich in diesem Beitrag beschrieben: http://cryptblog.de/2008/06/18/hacken-fur-anfanger/

Es besteht also keinen Anlass zur Beunruhigung. Sofern der Tracker das Torrentfile korrekt an den Benutzer überträgt, ist ein P2P System (basierend auf BitTorrent), für diesen Einsatzzweck ausreichend sicher.

Zufällige Entscheidungen

Hallo zusammen,

vor kurzem hatten ein Kommilitone und ich ein Problem. Wir wollten (über das Internet) ausknobeln, wer von uns mit dem Auto fahren muss und wer dafür Alkohol trinken kann. Ein Schnick-Schnack-Schnuck über das Internet sozusagen. Beide hatten wir nach einer Lösung für dieses Problem gesucht jedoch keine wirklich gute gefunden. Zuletzt entschieden wir uns dazu, es über die Anzahl der Heise.de-News des nächsten Tages zu bestimmen. Je nachdem ob es eine gerade oder ungerade Anzahl ist, muss der eine oder der andere.

Die Frage ist also, ob es dafür bessere Lösungen gibt. Mit Hilfe einer dritten, unabhängigen Instanz sollte dies nicht so schwierig sein, einige Lösungsbeispiele habe ich dafür mal ausgearbeitet:

Beide Parteien könnten mit einem Client auf einen Server verbinden. Sobald alle verbunden sind, gibt dieser eine zufällige Zahl aus. So hat man, synchronisiert, allen Teilnehmern dieses Ereignis zugänglich gemacht.

Oder man könnte eine Webseite bereitstellen, die alle 5 Minuten eine zufällige Zahl ausgibt. So könnten beide Parteien Vermutungen über die nächste Ausgabe treffen und diesbezüglich eine Entscheidung finden. Um dieses Beispiel zu verdeutlichen habe ich diese Webseite angefertigt: http://www.cryptblog.de/random.php.

Eine weitere Möglichkeit wären Kryptogramme eines Servers: Partei A bezieht ein aktuelles Kryptogramm von einem Server, welches eine verschlüsselte Zahl enthält. Er übergibt das Kryptogramm der Partei B und beide einigen sich darauf, welche Entscheidung bei einer geraden/ungeraden getroffen wird. Die Entschlüsselung ist allerdings erst später (~5 Minuten) möglich. Ich denke allerdings, dass diese Lösung unnötig kompliziert ist und kaum einen Vorteil gegenüber den anderen besitzt.

Aber nun die Frage: ist es möglich eine solche Entscheidung zu treffen, ohne dass ein Dritter (Server) beteiligt ist? Meine Antwort darauf ist JA. Folgendes Verfahren habe ich mir überlegt:

Sowohl A, als auch B, denken sich eine möglichst große zufällige Zahl (a und b) aus. Mit Hilfe einer Webseite, die hier lediglich als „Taschenrechner“ dient, berechnen A und B jeweils einen Hash (Fingerabdruck, beispielsweise MD5) ihrer Zahl, also z.B. H(a) und H(b). Über ein beliebiges Kommunikationsmedium kann nun dieser Hashwert ausgetauscht werden. Außerdem müssen sich A und B jeweils für eine gerade oder ungerade Zahl entscheiden. Durch diesen Austausch, haben sich beide auch damit einverstanden erklärt, dieses Verfahren zu nutzen. Nachdem also Hashwerte ausgetauscht sind, ist jeder im Besitz seiner eigenen Zahl und einem Fingerabdruck der Zahl des anderen.

Jetzt kann jeder seine Zahl dem anderen nennen, ob nun A oder B zuerst ist egal. Beide Zahlen werden miteinander addiert, also m = a + b berechnet, und je nachdem ob diese Zahl gerade oder ungerade ist, fällt die Entscheidung für A oder B aus. Aufgrund des vorherigen Austausch der Hashwerte, ist ein nachträgliches ändern der Zahl nicht möglich bzw. A und B können die Aussagen des anderen verifizieren.

Um dieses Beispiel zu verdeutlichen, existiert eine neue Sektion und ein Script um die Durchführung zu vereinfachen: http://cryptblog.de/muenzwurf/.

Nochmal grob zusammengefasst:

zufallprotokoll
A prüft H(b)=H(b‘), B prüft H(a)=H(a‘). Sofern beides wahr, kann von a’=a und b’=b ausgegangen werden.
Beide berechnen m = a+b.

Mittels diesem Protokoll hat jeder Teilnehmer eine 50% Chance zu gewinnen:

geradeungerade

In der Anwendung ist folgendes zu beachten:

Die Hashfunktion sollte einigermaßen sicher sein und um Rainbowtables entgegenzuwirken, sollten die Zahlen möglichst groß sein. Sofern dies erfüllt ist, können auch JavaScript Lösungen zum berechnen verwendet werden, wie z.B. http://aktuell.de.selfhtml.org/artikel/javascript/md5/ .

Nachtrag:
Grundsätzlich kann man dieses System auch, leicht modifiziert, für das bekannte Stein-Schere-Papier einsetzen, indem ein Hash von Stein|Zufallszahl, Schere|Zufallszahl oder Papier|Zufallszahl gebildet und später ausgetauscht wird. Das macht die vorherige Absprache ob gerade oder ungerade unnötig.