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.
Mal etwas aus der Welt der Hardware. Bei der Entwicklung einer kleinen IoT-Anwendung stand ich vor der Herausforderung festzustellen, ob der ESP32 genügend Leistung bieten würde. Es war jedoch keine einfache Aufgabe, eine leistungsstärkere WLAN-fähige Alternative zu finden. Obwohl ich Teensy-Boards für andere Anwendungszwecke äußerst interessant und leistungsstark finde, musste ich feststellen, dass sie keine Unterstützung für Wi-Fi bieten.
Allerdings gibt es da noch ein Bauteil, dass in den letzten Monaten etwas schwierig zu erhalten war, aber mittlerweile (Stand Oktober 23) wieder günstig zu erwerben ist: der Raspberry Pi Zero 2W. Dieser verfügt über 1 Ghz und Vier-Kern-Prozessor.
ESP32 (links) und Raspberry Pi Zero 2W (rechts)
Neben der Plattform stellt sich jedoch auch die Frage nach der Programmiersprache. Grundsätzlich lässt sich natürlich alles in C implementieren, aber bei komplexeren Anwendungen ist dies nicht unbedingt komfortabel. Und wenn man in der Implementierung was vergessen hat, zeigt sich sowas gerne erst einige Wochen bis Monate später.
Ein komfortablerer Ansatz wäre die Verwendung von Python im Sinne von MicroPython oder CircuitPython. Dies wirft jedoch die Frage auf, ob diese Lösungen zu viele Ressourcen beanspruchen. Aus diesem Grund führte ich einfaches Benchmarking durch. Dabei handelte es sich lediglich um das Inkrementieren einer Variablen, was natürlich nicht unbedingt repräsentativ ist. Dennoch reichte es aus, um ein Gespür für die Leistungsfähigkeit und den Ressourcenverbrauch der Plattformen zu erhalten.
Demzufolge verglich ich die Leistung von C auf dem ESP mit CircuitPython auf dem ESP und dem Raspberry Pi Zero. Darüber hinaus untersuchte ich, wie sich MicroPython auf einem Raspberry Pi Zero mit Betriebssystem verhält. Einige Tests führte ich auch mit mehreren Threads durch.
Benchmarkergebnisse Teil 1
Die aus diesen Ergebnissen abgeleitete Schlussfolgerung deutet darauf hin, dass CircuitPython im Vergleich zu anderen Optionen vergleichsweise langsam sein könnte. Es ist jedoch wichtig zu betonen, dass diese Schlussfolgerung ausschließlich auf den Ergebnissen dieses Tests basiert. Andere potenzielle Vorteile werden dabei nicht berücksichtigt.
Für mich persönlich war es überraschend, dass MicroPython auf einem Raspberry Pi Zero mit einer Raspbian Lite Installation äußerst gute Ergebnisse liefert. Ich hätte erwartet, dass das Betriebssystem zu viele Ressourcen verbraucht und somit den „Bare Metal“-Installationen unterlegen ist. Dies scheint jedoch nicht der Fall zu sein.
Auf Nachfrage eines Freundes hin habe ich noch eine C-Implementierung auf dem Pi mit (Raspbian Lite) OS getestet. Dies hätte ich besser nicht ausprobiert; der Vergleich von oben ergänzt um die Ausführung der C-Implementierung mit einem und vier Threads:
Benchmarkergebnisse Teil 2
Der Vollständigkeit halber sollte jedoch angemerkt werden, dass die vier Threads ohne Synchronisation (ohne Verwendung von Locks oder Mutex) ausgeführt wurden. Bei einer einfachen Inkrementierung schien dies nicht erforderlich zu sein.
Fazit: C(++) ist (leider) immer besser. Ursprünglich dachte ich die Differenz wäre viel geringer — die Ergebnisse vermitteln jedoch ein anderes Bild. Daher drängt sich die Frage auf, ob der Komfort einer Python-Implementierung bei so viel Leistungsverlust noch gerechtfertigt ist. Wenn man jedoch auf Python setzen möchte wäre die Wahl von MicroPython auf einem RaspberryPi Zero mit Betriebssystem die Beste.
Wir kennen es doch alle: Hin und wieder wird aus irgendeinem lästigen Grund ein neues Passwort oder eine neue PIN benötigt. Dabei soll es auch noch etwas sein, das sich leicht merken lässt und von den bisher verwendeten unterscheidet.
Insbesondere bei Multi-Faktor-Authentifizierung genügt auch schonmal eine vier-, sechs- oder achtstellige PIN: Wenn wir eine neue EC-Karte, einen neuen Personalausweis erhalten oder zur Entsperrung unseres Smartphones. Aber wie sieht es eigentlich mit der Sicherheit von solchen PINs aus?
Grundsätzlich lehrt uns die Kombinatorik, dass bei 10 unterschiedlichen Ziffern (0-9) zur Auswahl und bei einer vierstelligen PIN genau 10 hoch 4 also 10.000 verschiedene Kombinationen existieren. Im schlechtesten Fall müssten diese alle ausprobiert werden — im Mittel würde ein Angreifer nach der Hälfte, also nach 5000 Versuchen, die korrekte PIN durch systematisches Ausprobieren ermitteln können.
Üblicherweise sperren sich aber Geräte nach mehrmaligen Fehleingabe: Dies ist häufig schon bei drei Fehlversuchen der Fall. So betrachtet sind die vierstelligen PINs also nicht so übel: Die Wahrscheinlichkeit bei drei Versuchen die korrekte PIN in einem dieser Versuche zu wählen liegt bei 0,03 %.
Aber dabei darf auch die Realität nicht vergessen werden: Auf den Tasten des Gerätes hinterlassen wir stets einen Fingerabdruck der häufig auch ohne Hilfsmittel erkennbar ist. Insbesondere bei der Glasscheibe eines Smartphones ist dies vermutlich jedem schon selbst aufgefallen. Probleme dieser Art wurden auch schon im Beitrag Neulich im Supermarkt angedeutet. Wenn wir nun vor der Auswahl einer PIN stehen, möchten wir es dem potenziellen Angreifer möglichst schwer machen. Intuitiv würde man also vermutlich eine PIN wählen die aus vier verschiedenen Ziffern besteht um eine möglichst hohe Sicherheit zu erzielen. Aber ist das wirklich besser?
In der Schule lernt man (häufig), dass sich die Anzahl der möglichen Permutationen (Anordnungen) von n-vielen Elementen über die Fakultätsfunktion n! berechnen lässt. So lassen sich vier verschiedene Ziffern auf 4!=24 unterschiedliche Arten anordnen. Aber es könnte auch sein, dass nur zwei verschiedene Ziffern verwendet wurden oder nur drei oder sogar nur eine Ziffer. Wie berechnet man in so einem Fall die Anzahl der Möglichkeiten?
Hierzu betrachten die Anzahl der Permutationen mit nicht unterscheidbaren Elementen. Sind m von insgesamt n Objekten nicht unterscheidbar, können diese auf m! verschiedene Positionen verteilt werden. Die Anzahl der Permutationen insgesamt (n!) werden um diese Kombinationen reduziert.
\frac{n!}{m_1! \cdot m_2! \cdot \ldots}
Die m1, m2, etc. stellen dabei die Gruppen von mehrfach vorkommenden Elementen dar. Als Beispiel: Hinterlassen wir nach Eingabe der PIN nur einen Fingerabdruck auf der Taste 4 so gibt es vier nicht unterscheidbare Elemente (m1=4) und somit ergibt sich:
\frac{4!}{4!}=1
Wenn wir hingegen auf zwei Tasten, z. B. der 3 und der 5 einen Fingerabdruck hinterlassen wissen wir nicht, ob die Zahl 3 einmal, zweimal oder dreimal in der PIN genutzt wird. In Frage kommen daher Kombinationen wie (3,3,3,4) aber auch (4,4,3,3) oder (4,4,4,3). Somit missen wir zweimal eine Gruppe von 3 identischen Ziffern berücksichtigen (die Ziffer 3 dreifach oder die Ziffer 4 dreifach) und zusätzlich die Permutationen, wenn die Ziffer 3 und die Ziffer 4 beide doppelt verwendet wurden. In diesem Fall erhalten wir 14 Möglichkeiten diese anzuordnen.
\frac{4!}{3!}+\frac{4!}{2!*2!}+\frac{4!}{3!}=14
Wie sieht das Ganze bei drei verschiedenen Ziffern aus? Sehen wir beispielsweise bei der 1, der 2 und der 3 einen Fingerabdruck, muss eine Ziffer doppelt genutzt worden sein. Wir berechnen die möglichen Permutationen bei (1,1,2,3). Wir wissen aber nicht welche der drei Ziffern doppelt verwendet wurde. So könnten auch Permutationen von (2,2,1,3) oder (3,3,1,2) in Frage kommen. Daher müssen wir diese drei Mal addieren.
Bei vier unterschiedlichen Ziffern hingegen, erhalten wir ganz klassisch (Permutationen ohne Wiederholung) die bereits oben beschriebenen 24 verschiedene Kombinationen. Wir können uns diese zwei Fälle auch in Python generieren und anzeigen lassen. Hierzu kann die Methode permutations aus itertools hilfreich sein.
from itertools import permutations
kombinations = [[1,1,2,3],[2,2,1,3],[3,3,1,2]]
#kombinations = [[1,2,3,4]]
all = []
for k in kombinations:
perm = permutations(k)
for i in list(perm):
if i not in all:
all.append(i)
print(all)
Betrachten wir die Ergebnisse in der Tabelle sehen wir, dass die meisten Permutationen bei 3 Ziffern zustande kommen. Dies natürlich unter der Prämisse, dass wir nicht wissen welche der drei Ziffern doppelt verwendet wurden.
1 Ziffer
2 Ziffern
3 Ziffern
4 Ziffern
1 Permutationen
14 Permutationen
36 Permutationen
24 Permutationen
Zusammenfassend ist zu sagen, dass sofern nur diese Art des Angriffs, dass ein Angreifer auf Basis der Fingerabdrücke oder anderen Spuren die Ziffern der PIN ermitteln kann berücksichtigt wird, eine PIN aus drei verschiedenen Ziffern am sichersten ist. Unnötig zu sagen, dass sich dieses Muster auch bei fünf- oder sechsstelligen PINs fortsetzt: Es ist stets besser eine Ziffer doppelt zu verwenden. Insbesondere sollte von einer PIN mit zwei Ziffern abgesehen werden, da ein Angreifer bei drei Versuchen diese mit einer Wahrscheinlichkeit von 21 % erraten würde; bei 3 Ziffern sinkt die Wahrscheinlichkeit hingegen auf 8,3 %.
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.
bei der Betrachtung von Whitepapern zu Produkten wird man häufig mit diversen Bingo-Begriffen überflutet. Auf diese Weise soll dem uninformierten Interessenten, das ist zumindest meine Vermutung, ein Gefühl von Expertise vermittelt werden. Ein Beispiel ist das Whitepaper von schul.cloud der heinekingmedia GmbH in Hannover. In ihrer Stellungnahme zum Datenschutz und den detaillierten Informationen zur Verschlüsselung werden mit diversen Begriffen hantiert, deren nähere Betrachtung lohnenswert ist.
Bildzitat aus dem Whitepaper (Quelle: schul.cloud).
TLS Transport Verschlüsselung: 4096 Bit RSA Schlüssel
Grundsätzlich ist natürlich nichts einzuwenden, wenn mit einer größeren Schlüssellänge (4096 Bit) als üblich (2048 Bit) wirbt. Wenn man sich allerdings das Zertifikat des Webauftritts anschaut findet sich hier nur einen 2048 Bit Schlüssel. Natürlich ist es möglich, dass es sich bei diesem Dienst um einen anderen Endpunkt handelt, allerdings ist es fraglich, weshalb hier nicht konsequent alle Endpunkte den gleichen Schutz aufweisen. Dies würde mein Vertrauen zumindest erhöhen, auch wenn es nicht unbedingt erforderlich ist. Die sonst übliche Argumentation, dass dies ggf. Mobilgeräte überfordern könnte, kann an dieser Stelle jedenfalls nicht herhalten.
Signierungsalgorithmus: SHA256withRSA
Mir ist unklar, welche Information daraus entnommen werden soll. Natürlich sollte kein MD5 oder SHA1 Hashverfahren zur Signaturerzeugung angewendet werden, aber es ist kaum ein Qualitätsmerkmal das speziell beworben werden muss. Klingt aber kryptisch, technisch und aus diesem Grund möglicherweise überzeugend.
Downgrade Attack Prevention
Ich finde es etwas befremdlich, dass mit Absicherungen nach dem Stand der Technik Werbung betrieben wird. Das SSLv3 abgeschaltet sein muss sollte mittlerweile allen Verantwortlichen bekannt sein. Die meisten Client-Bibliotheken würden dies ohnehin nicht länger unterstützen. Auch der Wechsel von HTTPS auf HTTP kann leicht in dieser kontrollierten Client/Server-Umgebung ausgeschlossen werden. Aber Attack Prevention klingt, als ob extreme Schutzmaßnahmen getroffen wurden – was tatsächlich passiert ist: eine Zeile in der Konfigurationsdatei des Servers.
Secure Renegotiation
Wer mehr darüber erfahren möchte, muss sich einfach den CVE-Eintragaus dem Jahr 2009 durchlesen. Ich finde es einfach ärgerlich, schon fast etwas sträflich, mit Standards werben, die bald ihr 10 Jähriges Jubiläum feiern.
Wichtige Fragen bleiben hingegen offen: Woher stammt das Schlüsselmaterial? Welche Kontrolle hat der Nutzer über das Schlüsselmaterial? Wie wird der Gesprächspartner authentisiert?
Insbesondere der letzte Punkt wird in vielen Messengern vernachlässigt. Threema hat dies durch eine manuelle Prüfung und Ampel-Symbolik gelöst. Whatsapp verheimlicht den Wechsel öffentlicher Schlüssel bzw. blendet diesen nur auf Verlangen ein. Damit gibt es bei Whatspp keine wirksame Authentifizierung. Möglicherweise ist das je nach Anwendungskontext auch nicht notwendig, aber es sollte dem Nutzer zumindest klar sein.
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.
Für einen Vortrag habe ich mir mal den Spaß gemacht zu schauen, wie viel Webtracking auf den Webseiten der „großen“ politischen Parteien zu finden ist… ich war erschrocken. Daher habe ich heute die Daten nochmal aktualisiert und mich zu diesem Blogeintrag entschlossen.
Nur 2/8 Parteien gelingt es, ihre Webseite halbwegs sauber zu gestalten. Platz 3 geht an die CDU, die immerhin nur durch Google Analytics (GA) auffällt. Beim Rest war stets Google und häufig Facebook dabei. Das bedeutet, dass bei 6/8 Parteiwebseiten mindestens ein Google Service zu finden ist.
Hier nun eine Einzelwürdigung der Ergebnisse:
cdu.de: Meiner Meinung nach hat google-analytics dort nicht verloren. Sonst soweit in Ordnung.
die-linke.de: Der Youtube Content erzeugt auch das Doubleclick Cookie. Altruja.de, wohl zum Sammeln von Spenden, bekommt man sicher auch ohne Einbettung gelöst.
gruene.de: Das YT Problem, darüber hinaus eine Verbindung zu Facebook. Interessanterweise hervorgerufen durch die FB SDK und nicht durch einen Like-Button.
csu.de: Drittparteien wie adform und intelliad klingen nicht nach funktionalen Bestandteilen der Webseite. Neben recht viel Inhalt von Facebook findet man natürlich auch GA.
fdp.de: Der Beitrag von „cloudflare.com“ auf der Webseite beschränkt sich auf eine Ressource. Cloudinary wird zum Hosting der Bilder verwendet. Doubleclick, so alleine für sich, war recht überraschend und ist ein Indikator für Tracking zu Werbezwecken.
Und auch wenn ich verstehen kann, dass für Parteien das „Wer ist auf meiner Seite?“ relativ wichtig ist, finde ich diese massive Einbindung von Google Services sehr befremdlich. Natürlich lässt sich darüber streiten, welchen Wert die Parteiwebseite bei einer Wahl wirklich hat. Als normaler Bürger wäre ich jedoch der naiven Vorstellung erlegen, dass ich mich auf diesen Seiten bewegen kann, ohne von Google oder Facebook getrackt zu werden. Dies ist nachweislich überwiegend nicht der Fall.
Ob diese Einbettungen rechtlich in Ordnung sind, möchte ich als Informatiker nicht entscheiden und lasse dies daher offen. So oder so hoffe ich, dass mit der Privacy Verordnung dies in Zukunft klarer entschieden werden kann, auch wenn ich diesbezüglich eher pessimistisch bin und eine rechtliche Legitimation des Status quo erwarte.
Abschließend noch kurz ein paar Worte zur Technik der Erhebung. Während ich in diesem Blogeintrag eher meine persönliche und fachliche Meinung zum Ausdruck bringe, ist es mir sehr wichtig, die Ergebnisse der Erhebung auch transparent und nachvollziehbar offenzulegen. Aus diesem Grund finden sich die HAR-Dateien (HTTP Archive) zum Download bereit. Durchgeführt wurde die Analyse mit einem Firefox 55.0.3 ohne weitere Addons gesteuert durch Selenium (Python) 3.5.0 wobei nur die Landingpage geöffnet wurde.
However, in Anbetracht der massiven Einbettung von Google ist die Frage im Titel vielleicht doch nicht so weit hergeholt.
kürzlich (nagut, ist schon etwas länger her) bin ich in einem Supermarkt über dieses hochinteressante Zutrittskontrollsystem gestolpert:
Das Problem erkennt man ja schon aus der Ferne; trotzdem noch etwas näher:
Also die 4, 6 und 7 ist ja schonmal sicher; über die 5 lässt sich streiten.
Schon aus frühen MacGyver Episoden und öffentlich-rechtlichen Krimiproduktionen kennen wir das Problem des hinterlassenen Fettfilms auf den Tasten. Wenn man so ein System etabliert ist es daher empfehlenswert mehrere Kombinationen festzulegen und diese halbwegs gleichmäßig unter den berechtigten Personen zu verteilen. Noch besser hat jeder Nutzer seinen eigenen Code — auch wenn dies ggf. zu einem hohen administrativen Aufwand führt.
So oder so: Selbst wenn für diesen Raum kein hoher Schutzbedarf besteht ist es so schon etwas peinlich… und amüsant.
