Weil ich schon wieder viel zu viel uninformierte Panik bzgl. dem Impact auf Verschlüsselung lese: nein, Quantencomputer sind nicht das Ende sicherer Verschlüsselung, nichtmal theoretisch und wenn sie perfekt funktionieren.
Anlass für diesen Beitrag: Microsoft's Ankündigung zu Quantencomputern
Die relevanten Quantenalgorithmen
Bei der Betrachtung sind vor allem zwei Quantenalgorithmen relevant, die wir jetzt schon kennen, aber mangels brauchbarem Quantencomputer nicht praktisch einsetzen können:
- Shors Algorithmus
- Grovers Algorithmus
1) Shors Algorithmus
Dieser löst effektiv das Faktorisierungsproblem von Zahlen. Relevant daher, weil die aktuell üblichen asymmetrischen Verschlüsselungsverfahren (d.h. unterschiedlicher Schlüssel zum ver- und entschlüsseln) wie RSA, DSA und ECDSA damit gebrochen werden können, sowie Diffie-Hellmann Schlüsselaustausch.
2) Grovers Algorithmus
Kann effektiv in ungeordneten Daten suchen. Damit lassen sich symmetrische Verschlüsselungsverfahren wie AES angreifen, ABER anders als Shors Algorithmus ist er hier keine "magic bullet" sondern beschleunigt den Angriff nur. Lässt sich banal mit längeren Schlüsseln lösen.
Post-Quantum-Kryptographie
Die wesentlichen Probleme bleiben dann:
- asymmetrische Verschlüsselung
- Schlüsseltauschverfahren
Für beides gibt es bereits bekannte "post quantum" Algorithmen, also welche nicht mit Shors Algorithmus angreifbar sind.
Angenehmerweise "fallen" die nicht nur gemeinsam sondern können auch die selben mathematischen Konstrukte ersetzen. Das sind:
- gitterbasierte Verfahren
- codebasierte Verfahren
Warum werden diese nicht schon breit eingesetzt?
Weil sie natürlich auch Nachteile haben:
Gitterbasierte Verfahren
Diese sind insbesondere in der Entschlüsselung deutlich langsamer als klassische Algorithmen. Das ist nicht so schlimm, da asymmetrische Verfahren meist nur zur Verschlüsselung eines symmetrischen Schlüssels eingesetzt werden.
Codebasierte Verfahren
Diese haben den Nachteil riesige Schlüssel zu brauchen im Bereich von hunderten KB. (Zum Vergleich: bei RSA sind z.B. 4096 bit Schlüssel üblich, 100KB wäre fast 200mal so groß). Nervig, aber kein Blocker auf heutiger Hardware.
Der wichtigste Grund
Diese Verfahren sind erheblich jünger und in der Praxis bisher wenig eingesetzt, genießen also weniger Vertrauen als bewährte Algorithmen solange es keinen brauchbaren Quantencomputer gibt.
Ein verfrühter Umstieg birgt die Gefahr Probleme zu übersehen und vergeudet die Möglichkeit diese Algorithmen weiter zu verbessern bevor sie durch Implementierungen "zementiert" werden.
Bonus: Wäre Bitcoin betroffen?
Kurz: ja...
...aber
Bitcoin verwendet zwei prinzipiell gefährdete Algorithmen:
- ECDSA für Signaturen
- SHA256 für Proof-of-Work
Das SHA256 für PoW ist meines Erachtens dann völlig unkritisch wenn Quantencomputer allgemein verfügbar sind - jeder Miner kann sie einsetzen.
ECDSA wiederum ist futsch mit Shors. Bitcoin ist aber jetzt schon resilient nutzbar:
Shors braucht den Public Key um den Private Key zu ermitteln. Der Public Key wird bei Bitcoin mit P2PKH erst mit der ersten Zahlung von einem Wallet offenbart (vorher ist nur ein Hash bekannt).
Wenn eine Wallet Adresse stets nur einmalig verwendet wird ist das Risiko weitgehend minimiert.
Dennoch sollte Bitcoin wenn brauchbare Quantencomputer am Horizont sind das Signaturverfahren austauschen. Glücklicherweise gibt es bereits konkrete Vorschläge, z.B. BIP-360: QuBit - Pay to Quantum Resistant Hash.
Der Worst Case
Dieser Artikel beleuchtet den "worst case" - einen gut funktionierenden Quantencomputer der Shors und Grovers Algorithmus für große Eingaben fehlerfrei ausführen kann.
Was Microsoft und andere konkret ankündigen ist sehr sehr wahrscheinlich eher Marketingspuk als ein echter Durchbruch der diese Anforderungen erfüllt.
Fazit
Quantencomputer sind eine technologische Herausforderung für bestimmte kryptographische Verfahren, aber keineswegs das Ende der Verschlüsselung. Die Kryptographie-Community hat bereits Lösungen entwickelt und arbeitet kontinuierlich an deren Verbesserung. Ein überstürzter Umstieg wäre kontraproduktiv - wir haben Zeit, diese neuen Verfahren zu testen und zu härten, bevor praktisch nutzbare Quantencomputer Realität werden.
