Zur besseren Veranschaulichung habe ich die zuvor erläuterte vereinfachte Kyber-Variante nun auch in einem Excel-Dokument zusammengefasst. Es führt alle Berechnungen zur Ver- und Entschlüsselung durch und ist möglicherweise auch als Lehrmaterial geeignet.
Im vorherigen Beitrag habe ich die Kyber-Falltür auf der Basis Learning with Errors (LWE) erläutert. Diese Vereinfachung schränkt jedoch dahingehend ein, dass nur ein Bit verschlüsselt übertragen werden kann. Die offiziell vom NIST spezifizierte Kyber-Variante basiert auf Module Learning with Errors (MLWE). Erläuterungen dazu finden sich in diesem Blogartikel. Dabei werden, anders als in der vereinfachten Variante, die Operationen in einem Polynomring durchgeführt. Um auch diese praxisnahe Variante anschaulich zu machen, habe ich die notwendigen Operationen im Polynomring über Lambda-Funktionen in Excel implementiert. In einem aktuellen Microsoft Excel sollten diese funktionieren. In dieser Variante ist somit auch die Verschlüsselung von bis zu vier Bits möglich.
Für die Nutzung beider Beispiele wird voraussichtlich ein Microsoft Excel 365 oder 2024 erforderlich sein, in denen Lambda-Funktionen unterstützt werden.
Kyberkristalle geben dem Lichtschwert seine Farbe – das sollte allgemein bekannt sein. Darüber hinaus handelt es sich bei CRYSTALS-Kyber um ein vom NIST empfohlenes asymmetrischen Verfahren, das auch im Zeitalter der Quantencomputer noch sicher ist. An dieser Stelle ist einzuräumen, dass wir mit der Aussage noch vorsichtig sein müssen. Jüngst wurden Seitenkanalangriffe bekannt und zur Berechnung der Sicherheit gab es einen wirklich dummen Rechenfehler. Im April 2024 stellte sich kurzzeitig Panik ein: in einem Papier wurde Kyber als gebrochen erklärt. Allerdings wurde die Aussage von den Autoren recht zügig widerrufen.
WolfSSL hat mittlerweile Kyber integriert. Auch Amazon Web Services scheint Kyber mittlerweile zu verwenden. Es ist meine feste Erwartung, dass Kyber auch in TLS 1.4 Einzug halten wird. Im Signal-Protokoll ist es schon produktiv im Einsatz. Im Februar 2024 wurde von Apple verkündet, dass Kyber für IMessage eingesetzt werden soll.
Ich habe mir deshalb die Arbeit gemacht, Kyber genauer zu betrachten und so aufzubereiten, dass es ohne tiefgehende mathematischen Kenntnisse nachvollziehbar wird. Achso, falls die Frage aufkam: Ja, die Anspielung an Star Wars war bei der Namenswahl von den Entwicklern beabsichtigt.
Hinweis: Im Folgenden wird eine vereinfachte Form von Kyber erläutert, um das Konzept und die Falltür leichter verständlich zu machen. Eine noch detailliertere Darstellung findet sich in diesem Blogartikel.
Die Falltür
Der erste Schritt, um eine asymmetrische Verschlüsselung zu verstehen, ist die Betrachtung der Falltürfunktion. Das ist die Funktion, die sich in eine Richtung leicht berechnen lässt, jedoch nur schwer umzukehren ist. Genauer soll die Umkehrung, also die Entschlüsselung, nur mit dem Wissen des privaten Schlüssels möglich sein. Bei Kyber besteht die Falltür aus einem Problem, welches eigentlich leicht zu verstehen ist, jedoch auch für Quantencomputer ein schwieriges Problem darstellen soll: Learning with Errors (LWE).
Wir können uns LWE mal ganz langsam über simple Grundlagen aus der linearen Algebra nähern. Das Produkt einer Matrix A mit einem Vektor s ergibt einen Vektor t; hier mit entsprechendem Berechnungsbeispiel.
Nicht ganz neu ist, dass wir (je nach Matrix A) die Operation umkehren können. Mit dem Gauß-Verfahren gelingt dies mit polynomieller Laufzeitkomplexität. Mit A-1 wird hier die Umkehrung durchgeführt, also das s aus A und t berechnet.
Wir erweitern nun die ursprüngliche Berechnung um eine weitere additive Komponente: den Fehler e. Nach der Multiplikation von Matrix und Vektor addieren wir diesen Fehler hinzu.
Die Umkehrung hierfür ist jedoch ein schwieriges Problem. Es ist die Schwierigkeit, aus der Gleichung (A und t) mit unbekanntem Fehler e die ursprüngliche Variable s zu bestimmen. Ein Teil des Problems ist, dass es bei unbekanntem s und e mehrere Möglichkeiten gibt, die Gleichung zu erfüllen. Es gibt also nicht länger eine eindeutige Lösung, sondern es kommen verschiedene (s,e)-Kombinationen in Frage.
Wir sind aber noch nicht ganz fertig, denn für LWE kommt noch ein weiteres „Problem“ hinzu. Wir würden es auch vermissen, wenn es fehlen würde: eine Primzahl. Somit werden die Komponenten der Matrizen und Vektoren (und die Berechnungsergenisse) modulo q gerechnet.
Bei diesen kleinen Zahlen scheint das mit dem Modulo eher unsinnig. Daher werden wir A und q für die weiteren Beispiele etwas vergrößern. Wir setzen daher q auf 47 und nehmen auch für A und s neue Werte. Kyber schreibt vor, dass e und s keine großen Werte aufweisen sollen und wir werden später auch leicht nachvollziehen können, weshalb das so ist. Bitte einen kurzen Moment Zeit nehmen, um die Berechnung nachzuvollziehen, die neuen Werte werden auch bis zum Ende beibehalten.
Tatsächlich ist damit die Falltür für Kyber schon vollständig erläutert. Die Matrix A und das Ergebnis t stellen den öffentlichen Schlüssel dar. Der Vektor s ist der private Schlüssel. Bei e handelt es sich um einen Fehler der normalverteilt gewürfelt wird. Für s und e besteht bei Kyber die Einschränkung, dass die Werte nicht zu hoch sein dürfen. Die Primzahl q ist Teil des Verfahrens und ändert sich nicht: im „echten“ Kyber ist q immer 3329.
Merke: (A, t) ist der öffentliche Schlüssel, bei s handelt es sich um den geheimen Schlüssel und e ist ein Fehlervektor.
Jetzt, wo das Schlüsselmaterial generiert ist, kann dies übermittelt werden. In unserem Fall ist der Sender die Person, die gerne eine Nachricht übermitteln möchte, und der Empfänger soll diese im Anschluss entschlüsseln. Somit hat der Empfänger das Schlüsselmaterial generiert und übermittelt dies dem Sender.
Bevor es weitergeht, folgt an dieser Stelle noch ein kleiner Disclaimer. Die hier vorgestellte Falltür basiert auf dem Learning with Errors (LWE) Problem. Bei Kyber kommt allerdings Module Learning with Errors M-LWE zum Einsatz. Das ändert nichts daran, dass es sich bei A um eine Matrix und bei s, e und t um Vektoren handelt. Allerdings sind die Komponenten der Matrizen und Vektoren keine Elemente aus einem Restklassenring, sondern es sind Polynome aus einem Polynomring. Dies bedeutet, dass Addition (trivial) und Multiplikation (etwas schwieriger aufgrund Polynomdivision) in dieser algebraischen Struktur durchgeführt wird. Das ist für die Verschlüsselung leider nicht ganz unwichtig, wenn mehr als nur ein Bit verschlüsselt werden soll. Aber an dieser Stelle wollte ich von diesem Polynomring zunächst abstrahieren. Aufgrund der Abstraktion können wir deshalb nur ein Bit verschlüsseln, was uns aber erstmal genügen muss. Wem das doch nicht genügt, bekommt in diesem Blogartikel Kyber auf Basis von M-LWE näher erläutert.
Der Einsatz eines Polynomrings ändert im Übrigen nichts daran, dass alle Koeffizienten Modulo q gerechnet werden. Primzahlen sind und bleiben wichtig: auch für Verschlüsselungen im Zeitalter der Quantencomputer.
Verschlüsselung
Wir haben nun erfolgreich Schlüsselmaterial erzeugt. Der Sender, der eine Nachricht verschlüsseln möchte, wird nun im Folgenden zwei Komponenten erzeugen: u und v. Wir wissen noch nicht, wie diese aussehen. Aber vermutlich lässt sich schon erahnen, dass eine dieser Komponenten die Nachricht m enthalten wird. Spoileralarm: In v ist die verschlüsselte Nachricht enthalten und u wird benötigt um diese, mit Kenntnis des privaten Schlüssels s, beim Empfänger auszupacken. Wir können also v als ein gut verpacktes DHL-Paket mit unserer Nachricht ansehen und mit u und s können wir den Karton öffnen.
Bevor wir uns mit u und v befassen, müssen wir zunächst über die Nachricht m sprechen. Eine Nachricht besteht üblicherweise aus mehreren Bits. Mit der hier betrachteten Vereinfachung (ohne Polynomring) können wir leider nur genau ein Bit verschlüsseln. Das ist natürlich weder sinnvoll noch sicher, aber einfacher zu verstehen. Manchmal genügt auch ein einfaches Ja oder Nein, oder?
Um in Kyber eine Nachricht zu übermitteln, muss diese vorher skaliert werden. Wir haben uns bereits oben auf ein q=47 geeinigt. Angenommen, wir möchten ein „Ja“ verschlüsseln, dann wählen wir für m eine Zahl oberhalb der 24 (das ist q/2 aufgerundet). Wir kodieren eine 1, also ein „Ja“, z. B. mit m=31. Hätten wir hingegen eine 0, also ein „Nein“, wäre z. B. m=11 möglich gewesen. Große Zahl ist 1, kleine Zahl ist 0 und es ist erstmal egal, ob 30, 31 oder 32 für das Ja steht. Das passiert auch in Kyber mit jedem Bit der Nachricht. Warum wir das machen, wird später erläutert. Unser „Ja“ wurde also mit m=31 kodiert – wenn wir von der Nachricht sprechen, ist also die 31 gemeint und steht für ein Ja.
Zur weiteren Verschlüsselung werden ein Vektor r, ein Vektor e1 und ein Skalar e2 mit zufälligen Werten benötigt, allerdings: Wie oben bei e und s sollen es kleine Koeffizienten sein, also in diesem Beispiel mit 1, 2 oder 3. An dieser Stelle nochmal ganz deutlich: Das sind zufällig gewählte Werte, wir können diese auch unbeschadet anders wählen!
Mir ist bewusst, dass das jetzt ein ganzer Haufen Buchstaben sind. A, s, e, t, u, v, r… damit könnte man in Scrabble schon viele Punkte erzielen! Es ist ohne Frage schwierig, hier den Überblick zu behalten. Die gute Nachricht ist: r, e1 und e2 können wir unmittelbar nach der Verschlüsselung wieder vergessen. Diese Werte brauchen wir dann nicht mehr und haben somit nur einen kurzen Auftritt.
Nun sind wir bereit, um uns u und v genauer anzusehen. Das schmerzt möglicherweise auf den ersten Blick, wird dann aber mit dem zweiten Blick besser. Beginnen wir mit u.
Das „T“ im Exponenten beschreibt hier die transponierte Matrix. Transponieren bedeutet, dass wir die Matrix einmal an der Hauptdiagonalen spiegeln: Aus Zeilen werden Spalten und umgekehrt. Schauen wir uns das an:
Zugegeben, bei einer 2×2-Matrix ist transponieren nicht so aufregend: Die Hauptdiagonale bleibt unverändert und es tauschen nur zwei Komponenten. Ist halt so!
Um u zu berechnen, müssen wir also die bereits bekannte Matrix A transponieren und mit dem Zufallsvektor r multiplizieren und e1 addieren. Falls es nicht direkt bemerkt wurde: bei u kommt wieder unsere Falltür ins Spiel, nur mit neuen Werten. Die Falltür wurde also sowohl zur Generierung des öffentlichen Schlüssels benutzt als auch hier zur Verschlüsselung. Warum das A transponiert wurde, wird später noch erläutert.
Wenn man es ganz genau betrachtet, wurde hier das gewürfelte r durch das transponierte A und mit e1 „verschlüsselt“. Somit ist das r bei Übermittlung nicht mehr sichtbar und ohne Lösung des LWE-Problems auch nicht (einfach) berechenbar.
Jetzt schauen wir uns die zweite Komponente, also das v näher an:
Hierfür wird die t-Komponente aus dem öffentlichen Schlüssel transponiert, mit dem Zufallsfektor r multipliziert und sowohl der Fehler e2 als auch die Nachricht m aufaddiert. Am Ende, wie immer, modulo q.
Die Struktur ist recht ähnlich wie zuvor, jedoch handelte es sich bei A um eine Matrix und bei t um einen Vektor, der transponiert wird. Das ist auch dringend notwendig, damit das Skalarprodukt auch definiert ist. Schauen wir uns schnell das Berechnungsbeispiel an, denn damit wird die Berechnung schnell klar.
Wir haben nun erfolgreich unsere Nachricht m=31 verschlüsselt und erhalten zur verschlüsselten Übermittlung der Nachricht die 6. Zur Entschlüsselung ist natürlich beides erforderlich: das u und das v.
Sind u und v erfolgreich beim Empfänger angekommen, können wir nun mit der Entschlüsselung der Nachricht starten.
Merke: (u,v) werden vom Sender zum Empfänger übermittelt. Dabei ist v die vom Sender verschlüsselte Nachricht und u enthält erforderliche Informationen zur Entschlüsselung.
Entschlüsselung
Eigentlich ist das Schlimmste schon geschafft. Denn während die Verschlüsselung etwas Arbeit ist, gestaltet sich die Entschlüsselung doch recht einfach. Dabei ist mneu das Ergebnis der Entschlüsselung. Später wird noch deutlich, weshalb dort mneu und nicht nur m steht.
Wir transponieren also unseren geheimen Schlüssel s und multiplizieren dies mit dem vom Sender empfangenen Vektor u. Aus dieser Skalarmultiplikation kommt ein Wert heraus, der von v subtrahiert wird. Machen wir das einfach und schauen mal was passiert.
Vielleicht noch kurz zur Erinnerung: Wenn bei Operationen ein Wert kleiner 0 herauskommt, wie hier bei 6-118=-112, wird so häufig q aufaddiert, bis wir wieder in den positiven Bereich kommen. Da -18+(3*47)=29 ist, ist 29 auch das Ergebnis der Operation.
Nur wenn wir s transponieren, bekommen wir das Skalarprodukt errechnet. Aber… machen wir damit nicht einiges kaputt, wenn wir das einfach transponieren? Nein, denn in v steckt ja auch das transponierte t und im transponierten t steckt impliziert auch das (dann transponierte) s. Das schauen wir uns im nächsten Abschnitt aber noch genauer an.
Wir haben nun erfolgreich die übermittelte Nachricht entschlüsselt. Aber… was ist denn das? Das mneu=29 weicht ja von der ursprünglichen Nachricht m=31 ab? Alles falsch? Nein! Das ist richtig und erwartet. Immerhin haben wir mit r, e, e1 und e2 mehrere „Fehler“ in der Berechnung, die am Ende nicht alle wieder entfernt werden können. Wir haben für diese Fehler jedoch stets kleine Koeffizienten gewählt. Daher ist hier die Erwartung, dass sich das Ergebnis auch nur leicht verschiebt. Bei Kyber kommen wir deshalb nicht exakt auf den ursprünglich verwendeten Wert. Aber dadurch, dass es eine „kleine“ oder eine „große“ Zahl ist, können wir das ursprüngliche Bit wiederherstellen.
In der folgenden Tabelle sehen wir, mit welchem Klartext m (vor der Verschlüsselung) wir nach der Verschlüsselung landen.
Tabelle 1: Verschlüsselung/Entschlüsselung mit unterschiedlichen Nachrichten.
Wenn wir vor der Verschlüsselung einen niedrigen Wert für „Nein“ und einen hohen Wert (wie hier die 31) für „Ja“ wählen, erhalten wir nach der Entschlüsselung auch wieder niedrige und hohe Werte zurück, die wir anschließend auf die Aussagen mappen können. Wir haben somit einen Entscheidungsbereich für das jeweilige Bit. An der Tabelle 1 können wir sehen, dass wenn wir ein „Nein“ mit 11 kodiert und verschlüsselt hätten, wir die 9 als Ergebnis bekommen und dementsprechend einem „Nein“ zuordnen würden.
Aus diesem Grund wird auch klar, weshalb wir in dieser vereinfachten Version mit einem Koeffizienten auch nur ein Bit ver- und entschlüsseln können. In Kyber verwenden wir einfach mehrere diese Werte hintereinander in einem Polynom, um mehrere Bits (256) auf einen Schlag zu verarbeiten.
Korrektheit
Der beste Weg die Korrektheit des Verfahrens nachzuvollziehen zu können, ist am Ende anzufangen und rückwärts die Variablen zu substituieren. Um die Darstellung zu vereinfachen, verzichte ich auf das „mod q“ – das darf einfach mitgedacht werden. Wir starten daher bei der Entschlüsselung und ersetzen jeweils u und v durch die vorherigen Berechnungen.
Wir sind noch nicht ganz fertig, denn auch das t (welches in u enthalten ist) haben wir ganz am Anfang aus A, s und e berechnet:
Wir ersetzen nun entgültig v und u und schauen uns das Ergebnis an, ohne dabei den Überblick zu verlieren.
Nun stellt sich die Frage, was man hier alles vereinfachen kann. Zum einen kann man sich die Rechengesetze zur transponierten Matrix ansehen. Ich fasse es kurz zusammen:
(A + B)T = AT + BT
(A * B)T = BT * AT
Auf dieser Basis können wir die erste Klammer, das ursprüngliche t, ganz einfach umwandeln:
Zum anderen können wir diese Klammer mit dem r ausmultiplizieren, welches unmittelbar daneben steht.
Jetzt schauen wir uns mal die rechte Seite an. Bitte daran denken das Vorzeichen vor dem s zu berücksichtigen!
Also multiplizieren wir die rechte Seite aus wie bekannt.
Da wir jetzt fertig sind, können wir alle Klammern entfernen und uns das Ergebnis anschauen.
Eine ganze Menge Zeug. Aber wie in der Schule schaut man einfach, ob ein Produkt doppelt mit unterschiedlichem Vorzeichen vorkommt. Das ist glücklicherweise der Fall!
So können wir erkennen, dass wir die Matrix A vollständig entfernt bekommen. Aber es wird auch sichtbar, dass einiges übrig bleibt. Wir können mal überlegen, ob wir hier noch etwas verbessern können.
Zur Erinnerung: e hat zwar der Empfänger gewählt, aber das r stammt vom Sender. Das e2 stammt auch vom Sender und können wir als Empfänger nicht entfernen. Zwar kennen wir als Empfänger den privaten Schlüssel s, jedoch stammt e1 vom Sender und ist daher unbekannt. An den Farben lässt sich leicht erkennen, dass wir hier als Empfänger nichts mehr tun können. Daher sind wir hier fertig.
An dieser Stelle sollte klar werden, warum die Koeffizienten für die Fehler e, e1, e2 und r klein gewählt wurden. Sie verbleiben nach der Verschlüsselung noch im Ergebnis und können nicht restlos entfernt werden. Im Extremfall kann dies tatsächlich dazu führen, dass die Nachricht nicht korrekt entschlüsselt werden kann. Das wurde jedoch im Verfahren bereits berücksichtigt, sollte aber nur selten eintreten.
Epilog
Das war’s. Wir haben erfolgreich ein „Ja“ verschlüsselt und konnten (anhand Tabelle 1) auch sehen, dass es mit einem „Nein“ auch funktioniert hätte. Wir haben mehrfach die Falltür sehen können, sowohl bei der Schlüsselerzeugung, als auch zur Berechnung von u und v.
Es gibt tatsächlich noch einiges zu Kyber zu berichten – z. B. wie sich die Sicherheitsstufen unterscheiden. Wer gerne noch eine Ebene tiefer vordringen möchte, kann sich den Baby Kyber von Ruben Gonzalez ansehen, in dem auch genauer auf die Berechnungen im Polynomring eingegangen wird. Natürlich weise ich auch gerne auf das Originalpapier hin.
Ergänzung: Ich habe diese vereinfachte Kyber-Variante nun auch in einem Excel-Dokument zusammengefasst und in diesem Beitrag veröffentlicht.
Ich vermute einigen geht es so wie mir: Man schaut nicht jeden Tag in die neuen NIST-Empfehlungen. In diesem Fall kann durch die Lappen gehen, dass der 3DES nicht länger als „sichere Verschlüsselung“ gilt. Der/Die/Das NIST schreibt (https://csrc.nist.gov/news/2023/nist-to-withdraw-sp-800-67-rev-2):
The scheduled withdrawal of SP 800-67 Rev. 2 will signify that TDEA is no longer an approved block cipher.
Beim 3DES handelt es sich bekannterweise um eine dreifache Anwendung des DES. Ursprünglich war hier geplant, dass drei unabhängige Schlüssel zum Einsatz kommen (TDEA). Über den Meet-in-the-Middle-Angriff hat sich jedoch gezeigt, dass drei unabhägige Schlüssel nur wenig Mehrwert gegenüber zwei unabhängige Schlüssel erbringen. Dennoch hat der TDEA mit drei Schlüsseln nun noch etwas länger gelebt als die Variante mit nur zwei unabhängigen Schlüsseln.
Für das BSI ist der 3DES schon tot; hier wird schon länger nur noch AES in seinen drei Schlüssellängen empfohlen. Auch in TLS 1.3 findet sich nur noch AES und ChaCha20. Bei ChaCha20 handelt es sich jedoch um eine Stromchiffre.
Wer sich also nach den führenden Instutionen richten möchte und eine Blockcipher verwenden will, muss den AES nehmen. Auch wenn ich niemandem zum 3DES geraten hätte, beunruhigt mich diese überschaubare Diversität auf dem Blockverschlüsselungsmarkt ein wenig.
Ich bin kürzlich über eine Datenschutzerklärung gestolpert, die einen interessanten Absatz zum Thema Datensicherheit enthielt:
Wir verwenden innerhalb des Website-Besuchs das verbreitete SSL-Verfahren (Secure Socket Layer) in Verbindung mit der jeweils höchsten Verschlüsselungsstufe, die von Ihrem Browser unterstützt wird. In der Regel handelt es sich dabei um eine 256 Bit Verschlüsselung. Falls Ihr Browser keine 256-Bit Verschlüsselung unterstützt, greifen wir stattdessen auf 128-Bit v3 Technologie zurück.
Eine schnelle Googlesuche zeigte, dass dieser Textbaustein in vielen Datenschutzerklärungen zu finden ist. Interessanterweise auch in Webauftritten von Kanzleien und Datenschutzberatern. Meine Vermutung ist, dass diese Textpassage aus einem nicht ganz sauberen Datenschutzgenerator stammt, denn die von mir betrachteten Webseiten hatten mehrheitlich ihre Datenschutzerklärungen im Zuge der DS-GVO im Jahr 2018 angepasst.
Wollen wir uns jedoch den Inhalt mal etwas genauer ansehen. Mit den 256-Bit ist wohl die Schlüssellänge der symmetrischen Chiffre gemeint. Wie jedoch schon unlängst bekannt ist, stellt diese Angabe nur einen kleinen Teil der Sicherheit dar. Die gesamte SSL/TLS Ciphersuite entscheidet über die Sicherheit. Mit Verabschiedung von TLS 1.3 wurden beispielsweise alle CBC-Modi in den symmetrischen Chiffren entfernt – zuoft waren diese für Verwundbarkeiten mitverantwortlich. Dies gilt gleichermaßen für beide Schlüssellängen, weshalb die Angabe ob Chiffren mit 256 Bit oder 128 Bit zum Einsatz kommen kein Qualitätsmerkmal darstellt.
Etwas mehr musste ich über die v3-Technologie grübeln. In Verbindung mit der Schlüssellänge der symmetrischen Chiffre ergibt dies keinen Sinn. Mir ist keine Versionierung bekannt, die in gleicher Weise auf alle symmetrischen Chiffren zutreffen würde. Die Angabe bezieht sich also vermutlich auf die SSL-Version. Es soll, meiner Vermutung nach, dies zum Ausdruck bringen, dass sofern SSL 3.1 (=TLS 1.0) nicht vom Browser unterstützt wird, SSL 3.0 verwendet wird. Würde dies in der Anwendung tatsächlich zutreffen, wäre die Webseite hochgradig angreifbar, da SSL 3.0 schon seit 2015 als unsicher eingestuft und in modernen Browser nicht länger nutzbar ist. Auch SSL 3.1 und TLS 1.1 werden im Laufe des Jahres 2020 in den Ruhestand gehen.
Es entbehrt nicht einer gewissen Ironie, dass SSL 3.1 im Jahr 1999 veröffentlicht wurde und auch von älteren Betriebssystemen wie Windows XP und Windows Server 2003 Unterstützung fand. Der Satz stellte jedenfalls schon damals keinen Mehrwert dar, da eine symmetrische 256 Bit Verschlüsselung nicht zwangsweise über eine mit 128 Bit zu stellen ist. So würde ich damals wie heute ein AES128 über ein RC4 mit 256 Bit Schlüssellänge stellen. Es ist sogar schon in einer gewissen Weise bedenklich, wie lange sich dieser sinnbefreite Textbaustein im Netz gehalten hat.
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.
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“
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 = newbyte[8];
symIV = newbyte[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 ;-).
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:
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:
die Steckdose merkt sich den Zähler im Kryptogramm und ignoriert Befehle die darunter liegen oder
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.
ü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.
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.
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:
Parteien A und B einigen sich bezüglich einer klaren Kodierung der Spielkarten.
Die Partei A wählt einen beliebigen geheimen Schlüssel und verschlüsselt jede Karte einzeln.
Partei A mischt die Karten
Partei A übermittelt die neuen (verschlüsselten und gemischten) Karten der Partei B; B weiß daher nicht, welche Karten sich wo befinden.
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.
B mischt die Karten.
B übermittelt die doppelt verschlüsselten und gemischten Karten der Partei A.
A entschlüsselt alle Karten mit seinem Schlüssel (hier tritt die Kommutativität hervor).
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.
A übermittelt B die neuen Karten.
B entfernt seine alte Verschlüsselung (erneut die Kommutativität).
B verschlüsselt, genau wie A, jede Karte mit einem eigenen und anderen Schlüssel.
B übergibt A die verschlüsselten Karten.
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.
