Was bedeuten Quantencomputer für die Sicherheit im Internet?

Hanno Böck

hboeck.de

@hanno

Vorstellung / Über mich

• Journalismus und IT-Sicherheit
• Schreibe regelmäßig für Golem.de und verfasse den monatlichen Bulletproof TLS Newsletter
• Habe schon mehrfach Sicherheitslücken aufgedeckt, u.a. in TLS-Implementierungen (ROBOT)

Wir reden über ein Thema an der Schnittstelle von Physik und Kryptographie

Full Disclosure:

Ich kenne mich mit Kryptographie besser aus als mit Physik

Quantencomputer

Quanteneffekte könnten sich ausnutzen lassen, um bestimmte Berechnungen schnell durchzuführen, die ansonsten nicht praktikabel durchführbar sind, da sie zu lange dauern

Quantum Supremacy

Bild: Google

Google hat im Oktober mit dem Sycamore-Chip Quantum Supremacy gezeigt*

* oder auch nicht, sagt IBM

Was bedeutet Quantum Supremacy überhaupt?

Ein Quantencomputer ist in der Lage, eine Berechnung durchzuführen, die kein gewöhnlicher Computer praktisch durchführen kann

Anders ausgedrückt: Man kann zeigen, dass Quantencomputer tatsächlich funktionieren und nicht nur in der Theorie

Was bedeutet Quantum Supremacy nicht?

Quantum Supremacy bedeutet nicht,

• dass ein Quantencomputer etwas nützliches berechnet hat
• dass unsere Laptops bald Quantencomputer sein werden
• dass alle Verschlüsselung kaputt ist

Was hat Google Berechnet?

Die Simulation einer zufälligen Quanten-Schaltung

Anders ausgedrückt: Sie haben ein Problem konstruiert das sich auf einem Quantencomputer besonders gut berechnen lässt

Die Kritik von IBM

Kurz nach der geleakten Veröffentlichung haben Wissenschaftler von IBM darauf hingewiesen, dass sich der berechnete Algorithmus doch auf einem Supercomputer mit viel Speicherplatz berechnen lässt

Streng genommen hat Google also Quantum Supremacy nicht wirklich erreicht, aber es ändert nichts an der Grundaussage des Experiments: Quantencomputer funktionieren prinzipiell und nicht nur in der Theorie

Hype

Es gab in den letzten Jahren einen enormen Hype um Quantencomputer und haufenweise unrealistische Versprechungen

Fastcompany

"Das Amazon des Cloud-basierten Quantumcomputing"

Bisher hat noch niemand irgendetwas sinnvolles auf einem Quantencomputer berechnet

VW

VW behauptet, mit einem Quantencomputer von D-Wave Verkehrsströme berechnen zu können

Anders als bei Googles Sycamore ist es D-Wave bisher nicht gelungen, zu zeigen, dass sie mit ihrem sogenannten Quantum-Annealer Berechnungen schneller als auf klassischen Computern durchführen zu können

Was auch immer VW hier berechnet - sie brauchen dafür keinen Quantencomputer

"Quantum Supremacy" klingt toll, aber wenn man versteht was es bedeutet zeigt es eigentlich wo wir stehen - noch weit weg von praktischen Anwendungen

Große, leistungsfähige Quantencomputer gibt es selbst nach optimistischen Schätzungen frühestens in 10-20 Jahren

Manche glauben auch, dass die Quantencomputer-Zukunft komplett unrealistisch ist

IEEE Spectrum, The Case Against Quantum Computing

Selbst wenn leistungsfähige Quantencomputer Realität werden ist unklar, ob sie für Alltagsanwendungen überhaupt relevant sind

Quantencomputer, Kryptographie und IT-Sicherheit

HTTPS

Zertifikate, Signaturen, Schlüsselaustausch, Verschlüsselung

Public-Key-Kryptographie

• Signaturen: RSA, ECDSA
• Schlüsselaustausch: Diffie Hellman, Elliptic Curve Diffie Hellman

Alle diese Mechanismen basieren darauf, dass bestimmte mathematische Probleme schwer zu lösen sind

Mathematische Probleme, auf denen Public-Key-Kryptographie basiert:

• Faktorisierung
• Diskreter Logarithmus in endlichen Körpern
• Diskreter Logarithmus in Elliptischen Kurven

Alle üblicherweise verwendeten Public-Key-Verschlüsselungsverfahren, Schlüsselaustauschverfahren und Signaturen basieren auf einem dieser drei Probleme

Faktorisierung

Eine Zahl in ein Produkt von Primzahlen zerlegen

15 = 3 ⋅ 5

3927 = 3 ⋅ 7 ⋅ 11 ⋅ 17

449231 = 983 ⋅ 457

Wer diese Zahl faktorisieren kann, der kann HTTPS-Verbindungen zu www.google.com angreifen

Peter Shor konnte 1994 zeigen, dass man mit einem leistungsfähigen Quantencomputer große Zahlen effizient faktorisieren kann

Auch diskrete Logarithmen könnten mit Quantencomputern effizient gelöst werden

Wenn Quantencomputer kommen ist die heute verwendete Public-Key-Kryptographie kaputt

Noch besitzt niemand einen leistungsfähigen Quantencomputer

Post-Quanten-Kryptographie

Als Post-Quanten-Kryptographie bezeichnet man kryptographischen Verfahren, bei denen man davon ausgeht, dass sie mit einem Quantencomputer nicht angegriffen werden können

Der einfache Teil: Symmetrische Verschlüsselung

Es gibt theoretische Quantenangriffe, welche die Stärke einer symmetrischen Verschlüsselung auf die Quadratwurzel reduzieren

AES-256 statt AES-128

Signaturen, Schlüsselaustauschverfahren, Public-Key-Verschlüsselung

Hier benötigen wir komplett andere Algorithmen

Prinzipiell sind Post-Quanten-Verfahren verfügbar, es gibt aber verschiedene Herausforderungen

Sicherheit

McEliece

Verfahren ist seit 1978 bekannt, sehr gut untersucht und gilt bei entsprechend großen Schlüsseln als sehr sicher

Bei hohem Sicherheitslevel Schlüsselgröße etwa ein Megabyte

SPHINCS+

Signaturverfahren, das auf Hashfunktionen basiert und beweisbar so sicher ist wie die verwendete Hashfunktion

Bei hohem Sicherheitslevel Signaturgröße 30 Kilobyte

Klingt nach nicht so viel?

Ein TLS-Handshake beinhaltet circa 6 Signaturen

Wenn man weniger Bytes haben will muss man auf Verfahren zurückgreifen, die weniger gut untersucht sind, trotzdem muss man auf jeden Fall damit rechnen, dass mehr Daten anfallen

Am aussichtsreichsten sind hier verschiedene Gitter- oder Lattice-basierte Verfahren

Die kleinsten Datenmengen erreicht man mit Verfahren auf Basis sogenannter Supersingulärer Isogenien, diese gelten aber als sehr experimentell und sind sehr langsam, außerdem nicht für Signaturen geeignet

Bytes Verschlüsselung / Key Exchange

https://pqc-wiki.fau.edu/w/Special:DatabaseHome

Bytes Signaturverfahren (Byte)

Die US-Standardisierungsbehörde NIST hat 2017 dazu aufgerufen, Vorschläge für künftige Post-Quanten-Kryptographiestandards einzureichen

Das NIST hat schon mehrfach derartige Wettbewerbe ausgerichtet und diese haben einen sehr guten Ruf - hohes Maß an Transparenz und Kryptographen werden dazu animiert, gegenseitig die Sicherheit ihrer Vorschläge zu prüfen

Runde 1: 69 Vorschläge

Darunter einige eher ungewöhnliche Einreichungen, die nach kurzer Zeit vollständig gebrochen wurden

Runde 2: 26 Vorschläge

17 Verschlüsselungs-/Schlüsselaustauschverfahren

9 Signaturverfahren

Resultate werden zwischen 2022 und 2024 erwartet

Quantencomputer sind noch weit weg, es besteht also keine Eile?

Problem: Angreifer mit großen Festplatten

Daten heute aufzeichnen und in ferner Zukunft mit Quantencomputern knacken

Es kann also durchaus Sinn machen, bereits heute Post-Quanten-Verfahren einzusetzen, insbesondere für Verschlüsselung

Google und Cloudflare testen zur Zeit Post-Quanten-Verfahren für HTTPS-Verbindungen

CECQ2: X25519 + HRSS-SXY (Lattice)

CECQ2b: X25519 + SIKE (Supersinguläre Isogenien)

Kombination aus bewährtem Verfahren mit elliptischen Kurven und neuem Verfahren

Erste Resultate: Lattice sieht besser aus

Adam Langley's Weblog

Post-Quanten-Kryptographie kommt, es dauert aber noch ein paar Jahre und es gibt Herausforderungen

Zum Abschluss noch ein Hype-Thema

Quantenkryptographie oder Quantenschlüsselaustausch

Vielleicht habt ihr schon mal etwas in der Form gehört:

"Quantencomputer bedrohen die heute verwendete Verschlüsselung, aber wir können auch Quantentechnologie nutzen, um neue, absolut sichere Verschlüsselung zu entwickeln"

Völliger Quatsch!

Quantenschlüsselaustausch

Man versendet polarisierte Teilchen (bspw. Photonen) und der Empfänger misst diese mit Polarisationsfiltern, damit kann man ein Verfahren konstruieren, das aufgrund der Heisenbergschen Unschärferelation theoretisch absolut sicher ist

Das funktioniert nur

• wenn man in der Lage ist, einzelne Teilchen kontrolliert zu verschicken
• auf kurze Distanzen (einige Duzend Kilometer, evtl. auf einige Hundert erweiterbar)
• wenn man in der Lage ist Teilchen vom Sender zum Empfänger ungestört zu schicken (kein WLAN/Mobile Internet)
• wenn man bereits einen sicher authentifizierten Kanal hat

Quantenschlüsselaustausch ist ein nettes Gedankenspiel, aber praktisch nutzlos

Aber für Hype - und Fördergelder - reicht es

Takeaways

• Quantencomputer machen Fortschritte in der Forschung, sind aber von praktischer Nutzbarkeit noch weit entfernt
• Quantencomputer könnten die heutige Kryptographie weitgehend brechen, Alternativen sind aber auf dem Weg
• Quantenschlüsselaustausch (oder Quantenkryptographie, Quanteninternet) ist praktisch nutzlos