Security aspects of the Authentication used in Quantum Cryptography

Die Arbeit zeigt auf, dass die Verwendung von teilweise kompromittierten Schlüsseln aus der Quantenkryptographie für die Authentifizierung in nachfolgenden Runden eine Sicherheitslücke erzeugt, da ein Angreifer über den Quantenkanal manipulierte Nachrichten mit seinem partiellen Schlüsselwissen ausnutzen kann, und schlägt eine einfache Gegenmaßnahme vor.

Das Wesentliche

Die Geschichte vom unsichtbaren Dieb und dem rostigen Schloss

Stellen Sie sich vor, Alice und Bob wollen geheime Nachrichten austauschen. Sie nutzen dafür eine magische Technologie namens Quantenkryptografie. Das Besondere daran: Wenn sich jemand (nennen wir sie Eve, die Lauscherin) dazwischendrängt, verändert sie die Nachrichten unweigerlich, und Alice und Bob merken sofort, dass etwas nicht stimmt. Es ist wie ein Brief, der sich von selbst in Asche verwandelt, wenn man ihn berührt.

Aber es gibt ein Problem: Alice und Bob brauchen einen Startschlüssel, um sich überhaupt erst sicher zu identifizieren. Sie nutzen diesen Schlüssel, um zu prüfen: „Ist das wirklich Bob, der mir schreibt, oder ist das Eve, die sich als Bob ausgibt?"

Das Problem: Der halb-leere Schlüsselbund

In der klassischen Welt nutzen Alice und Bob für diese Prüfung einen sehr cleveren Mechanismus (den Wegman-Carter-Algorithmus). Stellen Sie sich das wie einen Schlüsselbund vor.

• Alice hat einen Schlüsselbund mit Millionen von Schlüsseln.
• Sie wählt zufällig einen Schlüssel aus, um eine Nachricht zu „versiegeln" (einen Stempel zu drucken).
• Bob hat denselben Schlüsselbund. Er nimmt den gleichen Schlüssel, prüft den Stempel und sagt: „Alles klar, das ist echt."

Das Tolle an diesem System ist: Selbst wenn Eve den Stempel sieht, kann sie ihn nicht fälschen, weil sie nicht weiß, welcher der Millionen Schlüssel benutzt wurde. Es ist wie ein Würfelwurf: Sie können nicht vorhersagen, welche Zahl kommt, solange der Würfel fair ist.

Aber hier kommt der Haken aus dem Papier:
In der Quantenkryptografie ist der Schlüsselbund nie ganz neu. Eve hat in früheren Runden vielleicht ein winziges bisschen Information über den Schlüsselbund geschnappt (durch das Abhören der Quantenkanäle). Sie weiß also nicht genau, welcher Schlüssel benutzt wurde, aber sie kann sagen: „Okay, die Schlüssel 1 bis 1000 kommen sicher nicht infrage."

Der Schlüsselbund ist jetzt nicht mehr voll, sondern hat ein paar Lücken. Eve kennt die Lücken.

Der Trick: Eve spielt mit dem Inhalt der Nachricht

Bis hierhin dachten die Forscher: „Na ja, Eve kennt ein paar Lücken, aber das macht den Stempel immer noch fast unmöglich zu fälschen."

Aber dann haben sie einen genialen, bösen Trick entdeckt.

Stellen Sie sich vor, Eve ist nicht nur ein passiver Lauscher, sondern ein Kellner, der die Bestellung von Alice an die Küche (Bob) weiterleitet.

1. Alice schreibt eine Nachricht: „Ich habe heute 500 Euro überwiesen."
2. Eve fängt die Nachricht ab.
3. Eve weiß, dass Alice einen Schlüssel aus einem eingeschränkten Set benutzt (weil Eve einige Schlüssel ausschließen kann).
4. Eve verändert die Nachricht von Alice: „Ich habe heute 1.000.000 Euro überwiesen." (Sie nutzt die Quantenkanäle, um die Nachricht zu manipulieren, ohne dass Alice und Bob es sofort merken, solange die Fehlerquote nicht zu hoch ist).

Jetzt passiert das Magische:
Eve weiß, dass Alice die Nachricht „500 Euro" mit einem bestimmten Schlüssel gestempelt hat. Eve berechnet nun: „Wenn ich die Nachricht auf '1.000.000 Euro' ändere, welcher Schlüssel würde dann den gleichen Stempel ergeben?"

Da Eve einige Schlüssel schon ausschließen konnte, gibt es vielleicht nur noch einen einzigen Schlüssel im Rest des Bunds, der für ihre gefälschte Nachricht („1.000.000 Euro") den gleichen Stempel erzeugt wie für die echte Nachricht.

Das Ergebnis: Eve kann die Nachricht ändern, den Stempel berechnen und Bob schicken. Bob prüft den Stempel, sieht, dass er passt, und denkt: „Alles super!" Aber die Nachricht ist manipuliert. Eve hat das Schloss nicht geknackt, sie hat einfach den Inhalt des Briefes so verändert, dass der alte Stempel trotzdem passt.

Warum ist das so gefährlich?

Normalerweise ist es extrem unwahrscheinlich, dass ein zufälliger Schlüssel für eine andere Nachricht den gleichen Stempel ergibt. Aber weil Eve die Nachricht selbst verändern kann, wählt sie genau die Nachricht aus, bei der die Mathematik auf ihrer Seite steht. Sie nutzt ihre winzige Information über den Schlüsselbund, um die Nachricht so zu drehen, dass sie gewinnt.

Es ist wie beim Lotto: Normalerweise sind die Chancen 1 zu 100 Millionen. Aber Eve darf sich den Zettel selbst ausfüllen, solange sie weiß, welche Zahlen nicht gezogen werden können. Sie füllt dann genau die Zahlen ein, die übrig bleiben. Plötzlich sind ihre Chancen viel besser.

Die Lösung: Der „Salz"-Trick (Der Koch-Trick)

Wie verhindert man das? Die Autoren schlagen eine sehr einfache Lösung vor, die wie das Hinzufügen von Salz in einen Kochtopf funktioniert.

Statt dass Alice die Nachricht direkt versendet, passiert Folgendes:

1. Alice schickt ihre Nachricht: „500 Euro".
2. Bob (oder Eve, die dazwischen ist) schickt sofort eine zufällige Nummer zurück, nennen wir sie „Salz" (z. B. eine Zahl wie 7392).
3. Erst jetzt berechnet Alice den Stempel. Aber sie stempelt nicht die Nachricht allein, sondern die Nachricht plus das Salz: „500 Euro + Salz 7392".

Warum hilft das?
Eve kann die Nachricht von Alice ändern (z. B. auf „1.000.000 Euro"). Aber sie kennt das Salz von Bob noch nicht, wenn sie die Nachricht manipuliert!

• Wenn Eve die Nachricht ändert, muss sie auch das Salz ändern, damit der Stempel passt.
• Aber sie weiß nicht, welches Salz Bob gerade gewählt hat.
• Sie muss also beides raten: die neue Nachricht UND das Salz.

Da das Salz zufällig ist und Eve es nicht kennt, bevor sie die Nachricht ändert, kann sie nicht vorhersagen, welcher Stempel passen wird. Sie muss sich entscheiden, ob sie angreift, bevor sie weiß, ob sie gewinnt. Das macht den Angriff wieder extrem unwahrscheinlich.

Fazit für den Alltag

Die Botschaft des Papiers ist:
Selbst wenn ein Quanten-System theoretisch absolut sicher ist, gibt es eine kleine Schwachstelle, wenn man die Schlüssel wiederverwendet und der Angreifer die Nachrichten manipulieren darf. Es ist wie ein Schloss, das nur dann sicher ist, wenn niemand den Inhalt des Briefes ändern kann.

Die Lösung ist simpel: Fügen Sie einen zufälligen Faktor (das „Salz") hinzu, der erst nachdem die Nachricht gesendet wurde, bekannt wird. So zwingt man den Dieb, einen blinden Schuss zu tätigen, bevor er weiß, ob sein Trick funktioniert. Das macht das System wieder sicher, ohne dass man die ganze Technologie neu erfinden muss.

Technische Zusammenfassung

1. Problemstellung

Das Papier adressiert ein kritisches, oft übersehenes Sicherheitsproblem in der Quantenkryptographie (QC), genauer gesagt beim Quantenschlüsselwachstum (QKG).

• Kontext: QKG-Protokolle (wie BB84) nutzen Quantenkanäle, um einen geheimen Schlüssel zwischen Alice (Sender) und Bob (Empfänger) zu erzeugen. Um Manipulationen durch einen Lauscher (Eve) auf dem klassischen Kommunikationskanal zu verhindern, muss jeder Schritt des Protokolls authentifiziert werden.
• Standardverfahren: Als Standard für die Authentifizierung wird das Wegman-Carter-Schema (basierend auf universellen Hash-Familien, $\epsilon$-ASU2) verwendet. Dies bietet eine informationstheoretische Sicherheit, solange der verwendete Authentifizierungsschlüssel vollständig geheim ist.
• Das Problem: In einem QKG-System wird der für die Authentifizierung verwendete Schlüssel aus einem vorherigen QKG-Lauf gewonnen. Da Eve durch Abhören des Quantenkanals und durch die Notwendigkeit der Fehlerkorrektur/Privatsphärenverstärkung (Privacy Amplification) immer einen gewissen, wenn auch kleinen, Informationsgewinn über den Schlüssel hat, ist der Schlüssel für die Authentifizierung in späteren Runden nicht mehr perfekt geheim (partially known key).
• Die Annahme: Bisherige Analysen gingen davon aus, dass dieser geringe Informationsverlust die Sicherheit der Authentifizierung kaum beeinträchtigt, da die Wahrscheinlichkeit, einen gültigen Tag (Tag) zu erraten, nur geringfügig steigt.
• Die Lücke: Die Autoren zeigen, dass diese Annahme falsch ist, wenn man die Interaktion zwischen Eve, dem Quantenkanal und dem Authentifizierungsprozess berücksichtigt. Eve kann nicht nur den Schlüssel teilweise kennen, sondern auch die Nachricht ($m_A$), die authentifiziert werden soll, über den Quantenkanal beeinflussen. Diese Kombination aus teilweisem Schlüsselwissen und der Fähigkeit, die Nachricht zu manipulieren, führt zu einer signifikanten Sicherheitslücke.

2. Methodik und Analyse

Die Autoren analysieren die Sicherheit unter der Annahme, dass Eve über einen Teil des Schlüssels verfügt (dargestellt durch die Min-Entropie $H_\infty(K)$) und gleichzeitig Zugriff auf den Quantenkanal hat.

• Szenario 1: Passive Beobachtung (Standardannahme):
  Eve kennt den Schlüssel nicht perfekt, aber sie wartet auf eine Nachricht und einen Tag von Alice. Wenn sie die Nachricht $m_A$ und den Tag $t_A$ sieht, kann sie den Schlüsselraum einschränken. Die Analyse zeigt, dass die Wahrscheinlichkeit, einen gültigen Tag für eine gefälschte Nachricht $m_E$ zu erraten, zwar steigt, aber bei kleinen Informationsverlusten ($r \approx 1$) immer noch extrem gering ist (basierend auf der Chebyshev-Ungleichung).

• Szenario 2: Aktive Manipulation (Der kritische Angriff):
  Die Autoren identifizieren einen neuen Angriffsvektor:

  1. Eve manipuliert den Quantenkanal so, dass die resultierende Nachricht $m_A$ (die Bob empfängt) spezifische Eigenschaften aufweist.
  2. Durch die Manipulation kann Eve die Verteilung der verbleibenden Schlüssel in den Teilmengen (Subsets) beeinflussen, die durch das Paar $(m_A, t_A)$ definiert sind.
  3. Ziel ist es, die Schlüsselverteilung so zu verzerren, dass für bestimmte Nachrichten die Anzahl der verbleibenden Schlüssel in einer Teilmenge extrem klein wird (nämlich $\le \epsilon |H|/|T|$).
  4. Wenn Eve die Nachricht $m_A$ so wählt, dass alle verbleibenden Schlüssel denselben Tag $t_E$ für ihre gefälschte Nachricht $m_E$ erzeugen, kann sie den Tag mit Sicherheit erraten.
  5. Der entscheidende Punkt: Eve wartet, bis sie durch die Beobachtung von $m_A$ und $t_A$ sicher ist, dass ihr Angriff erfolgreich sein wird, bevor sie die Nachricht auf dem klassischen Kanal ersetzt. Da sie nur in den Fällen aktiv wird, in denen sie sicher ist, wird sie nicht entdeckt.

• Mathematische Herleitung:
  Die Autoren leiten eine neue Erfolgswahrscheinlichkeit her (Gleichung 25), die im Gegensatz zur passiven Analyse (Gleichung 21) nicht mehr von der Größe des Hash-Raums $|H|$ abhängt, sondern nur noch von den Parametern $\epsilon$ und dem Anteil des verlorenen Schlüssels.

  • Ergebnis: Die Erfolgswahrscheinlichkeit steigt drastisch von extrem kleinen Werten (z. B. $10^{-647}$) auf Werte in der Größenordnung von$10^{-11}$ an.
  • Konsequenz: Die erwartete Zeit, bis Eve das System bricht, sinkt von Jahrtausenden auf weniger als ein Jahr (bei 1000 Runden/Sekunde).

3. Wichtige Beiträge

1. Identifikation einer neuen Schwachstelle: Der Nachweis, dass Wegman-Carter-Authentifizierung mit einem teilweise bekannten Schlüssel nicht mehr die gleiche Sicherheit bietet wie mit einem perfekt geheimen Schlüssel, wenn der Angreifer die zu authentifizierende Nachricht beeinflussen kann.
2. Kritik an der aktuellen Praxis: Die Aufdeckung, dass die übliche Annahme „geringer Informationsverlust ist harmlos" in QKG-Systemen falsch ist, da Eve die Nachricht $m_A$ über den Quantenkanal steuern kann, um die Schlüsselverteilung zu ihrem Vorteil zu manipulieren.
3. Quantitative Analyse: Eine detaillierte mathematische Modellierung, die zeigt, wie Eve durch geschickte Wahl der Nachricht die Wahrscheinlichkeit eines erfolgreichen Angriffs massiv erhöht.

4. Ergebnisse und Lösungsvorschlag

Ergebnis:
Das Standard-Wegman-Carter-Verfahren ist in QKG-Umgebungen, in denen der Schlüssel aus vorherigen Runden stammt und Eve den Quantenkanal kontrolliert, nicht sicher. Eve kann das System in akzeptabler Zeit brechen, ohne entdeckt zu werden.

Lösung (Prävention):
Die Autoren schlagen eine einfache, generische und effiziente Gegenmaßnahme vor, die die Reihenfolge der Informationen ändert, um Eve die Möglichkeit zu nehmen, den Erfolg ihres Angriffs vorherzusagen:

• Einführung eines „Salts" (SALT):
  1. Alice sendet ihre Nachricht $m_A$.
  2. Bob generiert eine zufällige Zahl (Salt) $s_B$ und sendet sie an Alice.
  3. Alice berechnet den Tag basierend auf der Konkatination von Nachricht und Salt: $t_A = h_k(m_A + s_B)$.
  4. Alice sendet $t_A$ an Bob.

Warum dies funktioniert:
Eve muss entscheiden, ob sie die Nachricht (und das Salt) manipuliert, bevor sie den Tag $t_A$ sieht. Da der Salt zufällig und unbekannt ist, kann Eve nicht vorhersagen, welche Teilmengen von Schlüsseln durch die Kombination aus ihrer manipulierten Nachricht und dem Salt übrig bleiben. Sie kann also nicht warten, bis sie sicher ist, dass der Angriff funktioniert. Sie muss entweder sofort angreifen (mit geringer Erfolgswahrscheinlichkeit) oder gar nicht. Dies stellt die ursprüngliche Sicherheitsgarantie wieder her.

5. Bedeutung und Fazit

• Praktische Relevanz: Da QKG-Systeme oft auf der Annahme basieren, dass der Schlüssel durch Privacy Amplification „sauber" genug ist, könnte dieses Problem in realen Implementierungen zu einem totalen Sicherheitsversagen führen, ohne dass es bemerkt wird.
• Kosteneffizienz: Die vorgeschlagene Lösung (Salt) erfordert keine komplexen Änderungen am Quantenprotokoll oder eine drastische Erhöhung der Schlüssellänge (was die Datenrate senken würde). Sie ist leicht implementierbar.
• Empfehlung: Die Autoren raten dringend dazu, diese oder eine äquivalente Maßnahme in zukünftigen QKG-Systemen zu implementieren, um die Sicherheit gegen Angreifer mit teilweisem Schlüsselwissen und Kanalzugriff zu gewährleisten.

Zusammenfassend zeigt das Papier, dass die Sicherheit von QKG nicht nur von der Quantenphysik abhängt, sondern auch von der korrekten Kombination von Authentifizierungsmechanismen und Protokollabläufen, um Rückkopplungseffekte zwischen Schlüsselgewinnung und Nachrichtenmanipulation zu verhindern.