Bekannte AngriffeBekannte Angriffe

Zusammenfassung

Kyber wurde seit seiner Veröffentlichung im Jahr 2017 einer umfangreichen Kryptoanalyse unterzogen. Bis Juli 2026 ist kein Angriff bekannt, der die empfohlenen Parameter in praktischer Zeit bricht. Es existieren jedoch Angriffe, die die Kosten reduzieren, sowie offene Forschungslinien.

Klassische Angriffe

Gitterangriffe (BKZ + SVP)

Der bekannteste Angriff gegen LWE besteht darin, das zugrundeliegende Gitterproblem mit dem BKZ-Algorithmus (Block Korkine-Zolotarev) und einem SVP-Orakel (Shortest Vector Problem) zu lösen.

Geschätzte Kosten für ML-KEM-768:
  - BKZ mit Block β ≈ 500
  - Geschätzte Zeit: > 2²⁰⁷ Operationen
  - Speicher: mehrere TB

Die Komplexität wächst exponentiell mit der Blockgröße. Für Kyber sind die Parameter so gewählt, dass der benötigte Block jede vorhersehbare praktische Kapazität übersteigt.

Entscheidungsangriffe

Der Angreifer kann versuchen, LWE-Instanzen von zufälligen mit statistischen Techniken zu unterscheiden. Diese Angriffe stellen den Schlüssel nicht wieder her, können aber die semantische Sicherheit brechen.

Für Kyber sind die Parameter so gewählt, dass der Vorteil des Unterscheiders vernachlässigbar ist (< 2⁻¹⁴⁰).

Algebraische Angriffe

Einige Arbeiten haben algebraische Angriffe untersucht, die die Ringstruktur ausnutzen (z. B. mit Gröbner-Basen). Für Module-LWE mit den Parametern von Kyber wurde keine signifikante Kostenreduktion gefunden.

Quantenangriffe

Grover-Angriffe auf das Geheimnis

Grover kann das Geheimnis s im Raum O(2^(n/2)) suchen. Für Kyber:

Grover bietet eine quadratische Beschleunigung, bleibt aber für die Dimensionen von Kyber unbehandelbar.

Shors Algorithmus

Shor löst LWE nicht. Shor löst das Problem des diskreten Logarithmus und die Faktorisierung, indem er die Struktur der verborgenen abelschen Gruppe ausnutzt. LWE über Gittern hat diese Struktur nicht — es ist ein Gitterapproximationsproblem, kein Gruppenproblem.

Regevs Algorithmus (Quanten)

Regev (2023) schlug einen neuen Quantenalgorithmus vor, der LWE unter bestimmten Bedingungen in Zeit 2^(n/2) löst, vergleichbar mit dem klassischen BKZ-Angriff, aber mit Speichervorteilen. Bisher wurde nicht gezeigt, dass er die klassischen Angriffe für die Parameter von Kyber übertrifft.

Fourier-Angriffe

Quantenangriffe basierend auf der Fourier-Transformation über Gittern (wie Kuperbergs Algorithmus für Isogenien) haben kein bekanntes Analogon, das für Standard-LWE oder Module-LWE effizient wäre.

Seitenkanalangriffe

Timing

Die Referenzimplementierung von Kyber ist zeitkonstant. Allerdings können fehlerhafte Implementierungen preisgeben:

• Das Geheimnis s durch Variationen in der nicht-konstanten NTT-Multiplikation
• Den Wert m bei der Dekompression, wenn diese nicht sorgfältig implementiert ist

Gegenmaßnahme: Verwendung der verifizierten Referenzimplementierung oder geprüfter Bibliotheken (liboqs, AWS-LC, BoringSSL).

Stromverbrauch / EM

Leistungsanalyseangriffe (DPA/SPA) können s wiederherstellen, wenn das Gerät keine Gegenmaßnahmen hat. Kyber ist besonders anfällig in eingebetteten Geräten ohne Abschirmung.

Gegenmaßnahme: Blinding von Exponenten, Randomisierung von NTT-Operationen, Signalentkopplung.

Fehlerangriffe (Fault Attacks)

Das Induzieren von Fehlern in der NTT-Berechnung während der Entkapselung kann dazu führen, dass das fehlerhafte Ergebnis Informationen über s preisgibt.

Gegenmaßnahme: Redundante Verifizierung, Fehlererkennung in NTT.

Hybride Angriffe

Die NSA empfiehlt X25519Kyber768 gerade deshalb, weil niemand zu 100% nur Kyber vertraut. Ein Angriff, der Kyber bricht, aber nicht X25519, würde immer noch von der klassischen Schicht aufgehalten werden, und umgekehrt.

Offene Forschungslinien

Schlussfolgerung

Kyber ist sicher gegen alle bekannten Angriffe im Juli 2026. Sein größtes Risiko ist nicht kryptoanalytisch, sondern implementierungs- und protokollbedingt: Eine schlechte Implementierung oder ein schlecht entworfenes Protokoll kann die Sicherheit brechen, obwohl der zugrundeliegende Algorithmus solide ist.

Dies unterscheidet sich nicht von der klassischen Kryptographie. Die Neuheit ist, dass Kyber als neueres Schema weniger kumulative Audits hat als AES oder SHA-3.

Referenzen

• Albrecht, M. et al. (2022). "Estimate all the LWE, NTRU schemes!" — Kostenschätzungen von Angriffen.
• Regev, O. (2023). "An Efficient Quantum Algorithm for LWE?" — Preprint, offene Debatte.
• Bernstein, D. J. & Lange, T. (2020). "Post-quantum cryptography: handling the fallout."
• Xagawa, K. (2022). "Side-channel attacks on lattice-based KEMs." CHES 2022.