Der Wettbewerb für Post-Quanten-Kryptographie ist vorbei!
The Morpheus Tutorials
https://www.youtube.com/watch?v=C-NNAk4ccaM

Transkript (automatisch erstellt)

0:00 Meine sehr verehrten Damen und Herren, ich darf Sie zu unserer heutigen Verleihung begrüßen für den ersten standardisierten asymmetrischen Postquantenverschlüsselungsalgorithmus.
0:09 Herzlichen Glückwunsch, Crystal Skyver! Mit ihm die drei ersten standardisierten digitalen Signaturverfahren, die postquantensicher sind,
0:19 Crystal's Dilithium. Und man sagt die beiden seinen Verwandt, Falcon und Sphinx.
0:24 Applaus bitte! Postquanten-Kryptographie ist ein eigenes Forschungsfeld und am 5.
0:36 Juli hat das NIST, das National Institute for Standardization and Technology, die ersten vier Postquantenalgorithmen veröffentlicht, die jetzt standardisiert sind.
0:46 Ich habe mir länger überlegt, ob und wie ich das hier verpacke, aber dass ich das Thema vorstellen will, dürfte klar sein.
0:53 Immerhin gibt es eine Krypto-Playlist von mir mit über 100 Videos. Dieses Video hier soll aber für alle sein.
0:58 Jeder kann das verstehen, wie beeindruckend das ist und was wir da eigentlich gerade Historisches gemacht haben.
1:04 Wir werden dementsprechend keine Beweise oder genauen Berechnungen machen. Dazu müsste ich selbst vermutlich erst mal ein bisschen mehr Mathe lernen, sondern wir
1:12 wollen verstehen, was genau eigentlich der Hintergrund ist, dass wir solche Verfahren überhaupt brauchen und wie die jetzt eben zustande kamen.
1:19 Was stimmt denn mit den alten Verfahren nicht und wie funktioniert Krypto eigentlich grundlegend? An der Stelle möchte ich nochmal ganz kurz auf unseren Sponsor eingehen.
1:30 Das ist heute wieder GetInIT. Bei GetInIT könnt ihr sehr schnell und einfach einen Job in, natürlich, der IT-Branche finden.
1:38 Die größten Firmen haben ihre Jobangebote auch bei GetInIT hinterlegt. Das Tolle, du musst nichts weiter tun, als dich auf der Plattform anzumelden und dein
1:46 Profil auszufüllen. Hinterlege dort, welche Skills du hast, zum Beispiel agile Softwareentwicklung oder Kanban
1:52 und was dein Werdegang und deine Ziele sind. Anschließend melden sich die Firmen bei dir.
1:57 Der Prozess ist für dich natürlich vollkommen kostenlos und auch mit viel weniger Arbeit verbunden, als wenn du selbst auf die Suche gehen würdest.
2:04 Fangen wir also kurz mit den Grundlagen an. Wie ihr in der Einleitung gehört habt, geht es nur um asymmetrische Verfahren, die hier
2:11 standardisiert wurden. Es gibt aber grob gesagt vier Arten von Kryptoverfahren, die so regelmäßig zum Einsatz kommen.
2:19 Symmetrische und asymmetrische Verschlüsselung, Hashing und digitale Signaturen. Symmetrische Verschlüsselung, zum Beispiel mit AIS, funktioniert so.
2:29 Wir beide wollen kommunizieren und haben denselben Schlüssel und Verschlüsseln genau damit und wir entschlüsseln auch wieder damit.
2:36 Die Dinger sind tatsächlich ziemlich unknackbar mittlerweile. Früher nicht unbedingt.
2:41 Das einzige was man tun kann, ist nämlich den Schlüssel zu knacken. Und selbst das funktioniert im rein kryptografischen Verfahren eigentlich nicht wirklich.
2:50 Das geht nämlich Jahrhunderte. Hashing ist auch ein symmetrisches Verfahren.
2:55 Ihr könnt es euch so vorstellen. Ich packe was in eine Hash-Funktion rein und raus kommt eine Zeichenkette, die immer
3:01 gleich lang ist. Packe ich dasselbe nochmal rein, kommt auch wieder derselbe Kram raus.
3:06 Ändere ich auch nur einen Buchstaben, habe ich keine Ahnung mehr, was das Ergebnis von meiner Hash-Funktion ist oder sein wird.
3:14 Umkehren lässt sich die Berechnung auch absolut nicht. Asymmetrische Verfahren, also Verschlüsselung und Signaturen, sind aber noch viel spannender,
3:23 wie ich finde. Nun hat jeder Teilnehmer, also du und ich, einen öffentlichen und einen privaten Schlüssel.
3:30 Also wir haben zwei Schlüssel. Jeder kann unsere öffentlichen Schlüssel haben und den privaten, den behalten wir nur
3:36 bei uns. Der muss nicht zum Gesprächspartner.
3:39 Nun nimmst du meinen öffentlichen Schlüssel und verschlüsselst damit was, was nur ich entschlüsseln kann.
3:45 Denn ich bin der Einzige, der den privaten Schlüssel hat. Das heißt Verschlüsseln mit dem öffentlichen Schlüssel, Entschlüsseln mit meinem privaten.
3:54 Signaturen sind da ähnlich. Nur mit dem privaten Schlüssel lassen sich Unterschriften erstellen.
3:59 Das heißt, nur ich kann unterschreiben. Sollte ja auch so sein.
4:03 Jeder, der den öffentlichen Schlüssel hat, also du, kann die Signatur prüfen und damit verifizieren, dass ich das Dokument wirklich unterschrieben habe.
4:12 Es ist also asymmetrisch, weil die Schlüssel, die wir nutzen, andere sind. Du nimmst meinen öffentlichen, ich nehme meinen privaten.
4:20 Ich nehme deinen öffentlichen, du deinen privaten. Und hier kommen die Quantencomputer ins Spiel.
4:26 Jedes asymmetrische Verfahren basiert auf einem harten mathematischen Problem. Das prominenteste Beispiel wahrscheinlich die Faktorisierung von Zahlen.
4:39 Nehmen wir die Zahl 15. 5 mal 3 ist 15.
4:43 Das wissen wir. Ein Computer kann das aber nicht effizient berechnen.
4:47 Er muss jede einzelne Primzahl durchgehen und schauen, ob eine Division ohne Rest möglich ist.
4:53 Das heißt 15 durch 2. Ah shit.
4:56 Ist 7,5. Also nicht drin.
4:58 15 durch 3. Aha, das ist 5.
5:00 Also haben wir keinen Rest. Also haben wir den ersten Primfaktor gefunden.
5:05 Und so weiter und so fort. 5 kommt dann direkt danach.
5:08 Jetzt, deswegen ist natürlich das Beispiel ziemlich langweilig. Es sind ja nur zwei Primzahlen und dabei haben wir Primzahlen 2 und 3 dabei.
5:15 Also nicht wirklich spannend. Sind aber diese Primzahlen mal mehrere tausend Binärstellen lang, wird das auch für einen
5:23 Menschen echt ziemlich unmöglich. Logisch.
5:26 Quantencomputer haben jetzt allerdings ein Feature. Quantencomputer können das leider effizient machen.
5:32 Das heißt, es gibt einen ausführbaren Algorithmus, Shores Algorithmus, um genau aus solchen riesigen Zahlen die Primfaktoren auszulesen.
5:41 Und das zerstört unsere komplette Annahme. Denn wir sagen ja, wir müssen haben, dass das nicht möglich ist.
5:50 Und Quantencomputer machen es möglich. Denn die Primfaktoren sind bei RSA mein privater Schlüssel.
5:57 Das heißt, ich kenne 3 und 5. Und die große Zahl, also in unserem einfachen Beispiel 15, ist mein öffentlicher Schlüssel.
6:04 Das heißt, du kennst 15, ich kenne 3 und 5. Das heißt, ein Quantencomputer könnte technisch gesehen aus meinem öffentlichen Schlüssel
6:12 meinen privaten errechnen. Und damit können wir natürlich nicht mehr von Vertraulichkeit sprechen.
6:17 Denn man kann ja jetzt alles machen. Deswegen brauchen wir kryptografische Verfahren, die auf Annahmen basieren, die wir auch mit
6:25 Quantencomputern nicht brechen können. Und hier wird extrem viel geforscht.
6:30 Gibt es vielleicht einen Algorithmus, der das Diffie-Hellman-Problem bricht? Gibt es einen, der das Diffie-Hellman-Problem auf elliptischen Kurven bricht?
6:37 Was können Quantenrechner überhaupt? All das ist noch nicht ganz fertig erforscht und nicht ganz klar dementsprechend.
6:45 Bislang konnten für einige neue Verfahren keine Algorithmen gefunden werden, die deren Annahmen zerstören.
6:51 Und das gilt für zum Beispiel fehlerkorrigierende Codes, wie ich das zum Beispiel auch in dem Tutorial zum Mac-Elise-Kryptosystem vorgestellt habe.
7:00 Aber auch für kryptologische Hash-Funktionen, multivariate Polynome und supersinguläre elliptische Kurven.
7:07 Und für Gitter. Und genau darauf hat sich das Team hinter Crystals gestürzt.
7:12 Reden wir ganz kurz über den Wettbewerb. Dieser wurde von der amerikanischen Behörde NIST ausgerufen.
7:20 Das ist genau dasselbe Institut, das auch schon die Standardisierung von AES, dem Standard für symmetrische Verschlüsselung, veranstaltet hat.
7:28 Und auch das war ein historischer Prozess für die Kryptographie. Denn dieser Prozess war sehr lang und sehr gründlich.
7:37 2016 begann der Call for Papers, das heißt Forscher weltweit wurden aufgerufen, ihre quantensicheren Algorithmen einzureichen.
7:47 Egal ob jetzt digitale Signatur oder Verschlüsselung. 2017 hat die NIST mit dem Standardisierungsprozess begonnen, weil abzusehen war, dass ungefähr
7:57 im Jahr 2030 RSA ein Problem haben wird. Es wurden zu all den mathematischen Problemen, die ich oben genannt habe, Vorschläge eingereicht,
8:07 die die Forscher zu einem Paper formuliert hatten. Darunter zum Beispiel 22 asymmetrische Verschlüsselungsalgorithmen nur für das Gitterproblem.
8:16 Das Wunderschöne an diesem Wettbewerb, was ich hier allerdings noch mal kurz hervorheben möchte, beispielsweise Hela 5 und Round 2 wurden noch in der ersten Runde von den Forschern
8:28 zurückgezogen und mit dem Team hinter Round 5 haben die sich dann zusammengesetzt und gemeinsam daran gearbeitet, weil ihre Ideen so ähnlich waren.
8:38 Sie haben also ihre Köpfe zusammengesteckt und aus drei quasi eins gemacht, weil es eine ähnliche Sache war.
8:46 Ähnliches passierte mit den Code basierten Verfahren Lake, Locker und Uroboros R, die gemeinsam in Rollo flossen.
8:53 Nach der ersten Runde durften dann wieder Kryptografen der ganzen Welt ihren Zerstörungstrieb ausleben.
9:00 Jeder einzelne Algorithmus wurde nun auseinandergenommen und angegriffen. Es wurde nach Lücken gesucht und insgesamt wurden 13 Angriffe veröffentlicht.
9:10 Übrigens auch hier wieder, Forscher-Teams waren sowas von international und nur gemeinsam haben die schlauesten Köpfe der Kryptografie Angriffe an den Schemata gefunden.
9:20 Anschließend wurden einige Algorithmen zurückgezogen, angepasst, verbessert und überdacht und übrig blieb am 30. Januar 2019 eine Sammlung aus 17 Verschlüsselungsalgorithmen und 9 Signaturalgorithmen.
9:34 Die gelten als ziemlich sicher. Jetzt durften also wieder Angriffe gesucht werden, aber es wurden zusätzlich noch weitere
9:41 Kriterien beachtet. Vor allem der Overhead wird betrachtet.
9:45 Das heißt, wie groß sind die Schlüssel eigentlich? Immerhin müssen die ja jedes Mal, wenn man eine Website aufruft, übertragen werden.
9:53 Auch mobil. Ein paar Gigabyte an Schlüsseln wären da ziemlich unglücklich.
9:57 Auch wichtig ist, wie schnell die Berechnungen verlaufen. Klar, heutzutage spielt vieles nicht mehr so eine extreme Rolle wie früher, aber trotzdem
10:05 können Verschlüsselungen sehr viel Zeit in Anspruch nehmen. Jeder, der mal eine Datei in VeraCrypt verschoben hat, der weiß, dass das für ein paar Gigabyte
10:13 durchaus dauert. Laufzeit ist also ebenfalls essentiell.
10:18 Beides war ausschlaggebend dafür, dass Crystals Kaiba den Wettbewerb als einziges asymmetrisches Verfahren gewonnen hat.
10:27 Auch bei den Algorithmen zu digitalen Signaturen gewann Crystals Dilithium aufgrund derselben Kriterien.
10:33 Es sollen jedoch noch mehr Algorithmen als Standard festgehalten werden, denn darum ging es bei dem Wettbewerb.
10:40 Sie sollen überall verfügbar sein und leicht einsetzbar. Das ist quasi das, was den Standard ausmacht.
10:50 Zu den weiteren Algorithmen gehört auch Falcon, der kleinere Signaturen erzeugt, was in manchen Szenarien wichtig sein könnte.
10:57 Und zuletzt wird Sphinx Plus genannt, der zwar langsamer ist und mehr Platz braucht, aber dafür nicht wie die anderen Verfahren auf Gittern basiert, sondern auf Hash-Funktionen.
11:09 Das heißt, wird ein Quantenalgorithmus gefunden, der die Gitterannahme bricht, haben wir einen Fallback-Algorithmus für digitale Signaturen, den jeder auch einfach nutzen kann, ohne auch
11:20 nur irgendwas zu implementieren. Was ihr aber vielleicht gemerkt habt, sind Dilithium, Falcon und Sphinx alles nur Signature-Algorithmen.
11:32 Das heißt, für Verschlüsselungen wurde nur ein einziger Algorithmus standardisiert bislang, also auch nur auf Basis von Gittern.
11:40 Deswegen sollen in einer zusätzlichen vierten Runde noch vier weitere Verschlüsselungsalgorithmen standardisiert werden.
11:47 Beaker, klassischer Mac-Elise, und HQC, die alle auf Codes basieren. Und dann noch Psyche, der auf supersingulären elliptischen Kurven basiert.
11:58 Somit sind wir dann auch also da ganz gut aufgestellt. Die Standards sollen bis 2024 fertig sein, wenn es einen besonderen Durchbruch bei der
12:15 Quantencomputerforschung gibt, sogar noch früher. Jetzt wäre die nächste berechtigte Frage, die man haben kann, warum wurde eigentlich
12:23 kein neuer symmetrischer Verschlüsselungsalgorithmus gewählt? Machen wir alles in Zukunft asymmetrisch?
12:28 Und nein, das wird nicht der Fall sein. Tatsächlich hat AIS aber einfach immer noch keinen Angriff gegen sich.
12:36 Es gibt einen einzigen Algorithmus für Quantencomputer, der AIS ein kleines bisschen wehtut. Der Grover-Algorithmus.
12:42 Der Grover-Algorithmus schafft es, die AIS-Schlüssellänge in einem Angriff zu halbieren. Mehr geht aber nach der aktuellen Forschung noch immer nicht.
12:53 Deswegen passiert da einfach folgendes, AIS-Schlüssellänge wird verdoppelt. Selbst mit 256 Bits, die wir heute schon als Standard nutzen, ist also immer noch alles
13:03 sehr gut gesichert. Lediglich die 128 Bit werden mit dem Grover-Algorithmus ein bisschen eng, um noch sicher zu sein.
13:10 Da muss also kaum was passieren, außer dass wir halt den stärkeren Algorithmus benutzen, vielleicht noch einen stärkeren dann als Standard etablieren.
13:18 Und damit sind wir dann auch in der Lage weiterhin Chats, Nachrichten, Mails, Webtraffic und noch vieles mehr sicher zu verschlüsseln.
13:27 Völlig egal, ob es eines Tages Quantencomputer mit 50 Qubits oder 5 Millionen Qubits gibt. Wenn ihr euch für das Thema interessiert, zum McElies-Algorithmus, der ja auch in Zukunft
13:38 noch standardisiert werden soll, hab ich tatsächlich ein Tutorial schon gemacht. Gönnt es euch gerne, ich verlinke es euch in der Endcard.
13:45 Grundsätzlich empfehle ich euch aber erstmal meine Kryptografie-Playlist. Viel Spaß damit!
13:49 Und vor allem auch natürlich danke an die Forscher, die sich da so reingehängt haben. Ohne euch hätten wir wirklich ein Problem.
13:56 Bis zum nächsten Mal. Ciao!