HIC Is All You Need: Post-Quantum-PAPKE erklärt

Passwörter gelten oft als der alte Teil der Sicherheit: nützlich, vertraut und fragil. Public-Key-Verschlüsselung gilt als der moderne Teil: leistungsfähig, asynchron und abhängig von authentischen öffentlichen Schlüsseln.

Password-Authenticated Public-Key Encryption verbindet diese beiden Ideen. Dieser Artikel erklärt das ursprüngliche PAPKE-Primitiv, warum es nicht dasselbe ist wie eine Datei mit einem Passwort zu verschlüsseln, und wie dieses Paper, HIC Is All You Need, die Konstruktion in Richtung praktischer postquanten-sicherer Instanzen bewegt.

Das Problem: Öffentliche Schlüssel müssen trotzdem authentifiziert werden

Public-Key-Verschlüsselung löst ein Problem: Ein Sender kann an den öffentlichen Schlüssel eines Empfängers verschlüsseln. Sie lässt aber ein anderes Problem offen: Woher weiß der Sender, dass dies wirklich der öffentliche Schlüssel des Empfängers ist?

In realen Systemen kommt diese Authentizität meist von PKI, Zertifikaten, einem vertrauenswürdigen Verzeichnis, einem Messaging-Anbieter oder einem manuellen Fingerprint-Vergleich. Diese Mechanismen sind nützlich, aber nicht immer verfügbar, einfach oder wünschenswert.

Password-Authenticated Public-Key Encryption, kurz PAPKE, fragt, ob ein kurzes gemeinsames Passwort einen öffentlichen Schlüssel authentifizieren kann, ohne den öffentlichen Schlüssel oder spätere Chiffrate in ein Offline-Werkzeug zum Prüfen von Passwortversuchen zu verwandeln.

Was PAPKE ergänzt

Das ursprüngliche PAPKE-Paper von Bradley, Camenisch, Jarecki, Lehmann, Neven und Xu führte Password-Authenticated Public-Key Encryption als Primitiv ein, das Public-Key-Verschlüsselung mit Passwortauthentifizierung kombiniert.

Auf hoher Ebene erlaubt PAPKE dem Empfänger, einen wiederverwendbaren öffentlichen Schlüssel zu veröffentlichen, der durch ein gemeinsames, merkbares Passwort authentifiziert ist. Ein Sender, der das Passwort kennt, kann diesen passwortauthentifizierten öffentlichen Schlüssel verwenden und asynchron eine Nachricht verschlüsseln.

Ein Angreifer, der diesen öffentlichen Schlüssel ersetzt oder manipuliert, sollte keinen Man-in-the-Middle-Angriff durchführen können, außer er kann das Passwort online erraten. Gleichzeitig sollte das bloße Beobachten des authentifizierten öffentlichen Schlüssels oder der Chiffrate keine Offline-Prüfung von Passwortversuchen erlauben.

Die Einschränkung ist wichtig: die Authentifizierung des öffentlichen Schlüssels ist nur so stark wie das gemeinsame Passwort. PAPKE ist keine Wunderlösung für schwache oder wiederverwendete Passwörter. Wenn das Passwort später offengelegt wird, kann ein Angreifer möglicherweise den authentifizierten öffentlichen Schlüssel erkennen und neue verschlüsselte Nachrichten an den Empfänger senden. Bereits verschlüsselte Nachrichten werden dadurch aber nicht automatisch entschlüsselt; sie hängen weiterhin vom geheimen Schlüssel des Empfängers und von der Sicherheit des zugrunde liegenden Public-Key-Verfahrens ab.

• Wiederverwendbarer öffentlicher Schlüssel: Der Empfänger kann einmal einen passwortauthentifizierten öffentlichen Schlüssel veröffentlichen und später verschlüsselte Nachrichten empfangen.
• Asynchrone Kommunikation: Der Sender kann verschlüsseln, ohne vorher ein interaktives Schlüsselaustauschprotokoll mit dem Empfänger auszuführen.
• Passwortauthentifizierung: Das Passwort authentifiziert, welcher öffentliche Schlüssel akzeptiert wird; es wird nicht als hochentropischer Verschlüsselungsschlüssel behandelt.
• Resistenz gegen Offline-Wörterbuchangriffe: Der authentifizierte öffentliche Schlüssel und die Chiffrate dürfen nicht zu billigen Passwortprüfern werden.

Wie PAPKE auf hoher Ebene funktioniert

Ein hilfreiches Modell trennt PAPKE in Einrichtung und Verschlüsselung.

Bei der Einrichtung erzeugt der Empfänger ein Public-Key-Schlüsselpaar. Der öffentliche Schlüssel wird anschließend mit dem gemeinsamen Passwort transformiert oder geschützt, sodass ein Sender, der das Passwort kennt, den richtigen öffentlichen Schlüssel wiederherstellen oder validieren kann.

Bei der Verschlüsselung verwendet der Sender das Passwort, um den passwortauthentifizierten öffentlichen Schlüssel zu verarbeiten. Ist das Passwort korrekt, erhält der Sender den echten öffentlichen Verschlüsselungsschlüssel und verschlüsselt normal. Ist das Passwort falsch, sollte der Prozess nicht genug Information preisgeben, um Passwortversuche offline zu testen.

Das unterscheidet sich von gewöhnlicher passwortbasierter symmetrischer Verschlüsselung. Wenn ein Angreifer ein passwortverschlüsseltes Chiffrat erhält, kann er ein geratenes Passwort ausprobieren, einen Schlüssel ableiten, entschlüsseln und prüfen, ob das Ergebnis wie normaler Klartext aussieht. Das ist ein Offline-Wörterbuchtest. PAPKE behält die Struktur der Public-Key-Verschlüsselung bei, nutzt das Passwort aber zur Authentifizierung des öffentlichen Schlüssels und verhindert, dass der authentifizierte öffentliche Schlüssel oder die Chiffrate zu einem billigen Passwortprüforakel werden.

Warum die ursprüngliche Konstruktion eine ideale Chiffre verwendete

Die generische PAPKE-Konstruktion aus dem ursprünglichen Paper verwendet ein CCA-sicheres, anonymes Public-Key-Verschlüsselungsverfahren zusammen mit einer idealen Chiffre über dem öffentlichen Schlüsselraum.

Das erzeugt eine ungewöhnliche Spannung. In normaler Public-Key-Verschlüsselung soll der öffentliche Schlüssel öffentlich sein: Jeder darf ihn kennen, kopieren und an ihn verschlüsseln. In PAPKE spielt der echte öffentliche Schlüssel nach der Authentifizierung weiterhin diese Rolle, aber der passwortauthentifizierte öffentliche Schlüssel darf nicht genug Struktur offenlegen, damit ein Angreifer Passwortversuche prüfen kann.

Die Intuition ist, dass das Passwort den öffentlichen Schlüssel versteckt oder transformiert, sodass er für jemanden ohne Passwort zufällig aussieht. Das Modell der idealen Chiffre ist dafür eine saubere theoretische Abstraktion.

Diese Abstraktion ist in einem Beweis nützlich, aber in der Implementierung unbequem. Standard-Blockchiffren arbeiten über feste Blockgrößen wie 128 Bit, während moderne öffentliche Schlüssel, besonders postquanten-sichere Schlüssel, viel größere strukturierte Objekte sind.

Warum postquanten-sicheres PAPKE schwieriger ist

Viele klassische PAPKE- und PAKE-artige Konstruktionen beruhen auf Diffie-Hellman-ähnlicher Algebra. Große fehlertolerante Quantencomputer würden die Annahmen hinter diesen klassischen Gruppen brechen, und neue Ressourcenschätzungen machen den Migrationsdruck konkreter. Ein Whitepaper von Google Quantum AI schätzt, dass Shors Algorithmus gegen diskrete Logarithmen auf 256-Bit-Elliptischen Kurven auf bestimmten zukünftigen Architekturen mit schnellem Takt und weniger als einer halben Million physischer Qubits in Minuten laufen könnte. Ein separates Oratomic/Caltech-Preprint argumentiert, dass hochratige Fehlerkorrekturcodes und rekonfigurierbare atomare Qubits kryptographisch relevante Shor-Instanzen in den Bereich von 10.000 bis 100.000 Qubits bringen könnten, allerdings mit längeren Laufzeiten. Das sind Ressourcenschätzungen, keine heutigen Angriffe, aber sie erklären, warum die postquanten-sichere Migration dringlich behandelt wird.

Eine natürliche Idee ist, die zugrunde liegende Public-Key-Verschlüsselung durch ein postquanten-sicheres PKE oder KEM zu ersetzen. Das ist aber kein einfacher Austausch. Die Konstruktion braucht weiterhin eine Möglichkeit, öffentliche Schlüssel mit einem Passwort zu authentifizieren, ohne Struktur preiszugeben oder Offline-Wörterbuchangriffe zu ermöglichen.

Hier werden Größe und Struktur postquanten-sicherer Schlüssel wichtig. Wenn die Konstruktion eine ideale Chiffre über dem öffentlichen Schlüsselraum erwartet und die Schlüssel große gitter- oder codebasierte Objekte sind, wird die effiziente Instanziierung dieser Chiffre zum zentralen Hindernis.

HIC Is All You Need

In diesem Paper schlagen Arriaga, Mestel, Oupicky, Ronne, Skrobot et al. einen Weg um dieses Hindernis vor.

Statt einer vollständigen idealen Chiffre über dem öffentlichen Schlüsselraum verwendet die Konstruktion einen Half-Ideal Cipher, kurz HIC. HIC wurde in einer früheren EUROCRYPT-2023-Arbeit als Abschwächung einer idealen Chiffre eingeführt, die für bestimmte passwortauthentifizierte Protokolle trotzdem ausreichen kann.

Der Punkt ist pragmatisch: Man sollte kein stärkeres idealisiertes Objekt instanziieren, als der Beweis tatsächlich benötigt. Wenn ein schwächeres und effizienter realisierbares Objekt ausreicht, wird die postquanten-sichere Konstruktion deutlich plausibler.

Die resultierende Konstruktion, PAPKE-HIC, wird als UC-sicheres PAPKE-Schema beschrieben, das aus einem Public-Key-Verschlüsselungsverfahren und einem HIC aufgebaut ist.

Was die postquanten-sichere Variante benötigt

Das HIC-Paper behauptet nicht, dass jedes beliebige postquanten-sichere Verschlüsselungsverfahren blind eingesetzt werden kann. Es behält die ursprüngliche Anforderung an CCA-sichere anonyme Public-Key-Verschlüsselung bei und präzisiert einen Punkt im PAPKE-IC-Beweis.

Auf hoher Ebene muss sich das Verschlüsselungsverfahren so verhalten, dass passwortauthentifizierte öffentliche Schlüssel und Chiffrate weder die falsche Art von Information preisgeben noch mehrdeutiges Entschlüsselungsverhalten erzeugen.

• CCA-Sicherheit: Das zugrunde liegende PKE muss auch gegen adaptive Chosen-Ciphertext-Angriffe vertraulich bleiben. Das ist stärker und präziser als nur zu sagen, dass Chiffrate schwer zu invertieren sind.
• Chiffrat-Anonymität: Ein Chiffrat sollte nicht verraten, unter welchem öffentlichen Schlüssel es erzeugt wurde, selbst wenn der Angreifer die Kandidatenschlüssel kennt.
• Pseudo-uniforme öffentliche Schlüssel: Erzeugte öffentliche Schlüssel sollten rechnerisch schwer von der Schlüsselverteilung zu unterscheiden sein, die die HIC-basierte Konstruktion manipuliert.
• Entschlüsselungsrobustheit: Ein Chiffrat sollte nicht unter verschiedenen geheimen Schlüsseln gültig zu widersprüchlichen Nachrichten entschlüsseln, sodass der Protokollbeweis bricht. Das Paper erfasst die benötigte Version als DROB-CCA und setzt sie zu stärkeren Robustheitsbegriffen in Beziehung.

Konkrete Instanziierungen

Das Paper macht die Konstruktion anschließend konkret. Es untersucht PAPKE-HIC auf Basis einer Standard-KEM+DEM-Public-Key-Verschlüsselungsschicht mit ML-KEM, FrodoKEM und Classic McEliece. ML-KEM und FrodoKEM passen über die prefix-hashing Fujisaki-Okamoto-Transformation in die Analyse, die einen direkten Weg zur benötigten Entschlüsselungsrobustheit gibt. Classic McEliece ist schwieriger: Das Paper diskutiert eine modifizierte Variante und eine Hashed-Public-Key-Transformation als stärker Black-Box-artigen Weg zur nötigen Robustheit. Der Benchmark-Code ist öffentlich im PAPKE-HIC-Benchmark-Repository, implementiert in C++ mit Botan für kryptographische Primitive und Catch2 für Messungen. Die Benchmarks zeigen den praktischen Nutzen von HIC: Für ML-KEM benötigt PAPKE-HIC eine Hash-to-Group-Operation, während PAPKE-IC mehrere benötigt; für Classic-McEliece-Verschlüsselung wird die HIC-Variante mit etwa 0,26x der Zeit der 8-Runden-Feistel-PAPKE-IC-Variante angegeben.

Die praktische Bedeutung

Das Versprechen von PAPKE ist asynchrone, PKI-freie Verschlüsselung auf Basis eines gemeinsamen Passworts. Das passt zu Situationen, in denen zwei Personen ein Passwort vereinbaren können, aber nicht auf Zertifikate, Kontoanbieter oder manuelle Fingerprint-Vergleiche angewiesen sein möchten.

Das Versprechen von PAPKE-HIC ist, dieselbe Idee in die postquanten-sichere Welt zu verschieben. Statt auf Diffie-Hellman-Annahmen zu beruhen, kann die Konstruktion mit geeigneten postquanten-sicheren Public-Key-Werkzeugen instanziiert werden.

Die Einschränkung ist, dass dies kryptographisches Protokolldesign ist, keine einfache Anwendungsfunktion. Die Sicherheit entsteht nicht dadurch, dass man ein Passwort mit einem öffentlichen Schlüssel vermischt. Sie entsteht aus einem präzise spezifizierten Primitiv, einem Beweismodell und klaren Anforderungen an das zugrunde liegende Verschlüsselungsverfahren und die HIC-basierte Transformation des öffentlichen Schlüssels.

Die Kernaussage

PAPKE ist nützlich, weil es Passwörter als Werkzeug zur Authentifizierung öffentlicher Schlüssel behandelt und gleichzeitig Offline-Wörterbuchangriffe verhindern will.

Die ursprüngliche PAPKE-Arbeit definiert das Primitiv und seine Beziehung zu PAKE. HIC Is All You Need zeigt, wie die generische PAPKE-Idee in postquanten-sicherer Richtung praktisch werden kann, indem eine schwierige ideale Chiffre durch eine Half-Ideal-Cipher-Konstruktion ersetzt wird.

Einfach gesagt: Passwörter können öffentliche Schlüssel authentifizieren, Public-Key-Verschlüsselung kann asynchrone Nachrichten unterstützen, und postquanten-sichere Varianten werden realistisch, wenn die Transformation des öffentlichen Schlüssels mit der richtigen kryptographischen Abstraktion entworfen wird.

Referenzen

• Bradley et al.: Password-Authenticated Public-Key Encryption
• Arriaga, Mestel, Oupicky, Ronne, Skrobot: HIC Is All You Need
• Freitas Dos Santos, Gu, Jarecki: Randomized Half-Ideal Cipher on Groups
• Babbush et al.: Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities
• Cain et al.: Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits
• PAPKE-HIC benchmark implementation repository