Post-Quanten-Kryptografie: Verschlüsselung mit Isogenien ist unsicher

Ein Angriff auf den Schlüsselaustausch SIDH zeigt erneut, wie riskant experimentelle kryptografische Algorithmen sein können.

Artikel veröffentlicht am 31. Juli 2022, 11:24 Uhr, Hanno Böck

Keine sichere Verschlüsselung: Die Algorithmen SIDH und SIKE sind angreifbar. (Bild: Poulpy/Wikimedia Commons/CC-BY-SA 3.0)

Zwei Kryptografen der KU Leuven haben in einem Preprint einen Angriff auf den Schlüsselaustauschalgorithmus SIDH veröffentlicht. Dabei handelt es sich um ein Verfahren auf Basis von Isogenien über supersingulären elliptischen Kurven. Das galt bislang als vielversprechende Möglichkeit, um die Verschlüsselung vor Angriffen durch Quantencomputer abzusichern.

Eine Variante des SIDH-Algorithmus namens SIKE ist Teil eines Wettbewerbs der US-Standardisierungsbehörde Nist (National Institute of Standards and Technology). Durch diesen Wettbewerb will die Behörde Post-Quanten-Kryptografie standardisieren, also Verschlüsselungs- und Signaturalgorithmen, die nicht durch Quantencomputer angegriffen werden können.

Das Nist hat dort kürzlich die ersten Gewinner bekanntgegeben. Der jetzt gebrochene Algorithmus SIKE war nicht dabei. Allerdings hat das Nist angekündigt, mehrere Algorithmen, darunter SIKE, weiter zu untersuchen und möglicherweise in Zukunft zu standardisieren. Das wird jetzt wohl nicht passieren.

Die Forscher konnten zeigen, dass sie SIKE auf dem niedrigsten Sicherheitslevel innerhalb von weniger als einer Stunde mit einem Core eines handelsüblichen Intel-Prozessors knacken konnten.

Schlüsselaustauschverfahren mit Isogenien galten vor allem deshalb als attraktiv, da die ausgetauschten Schlüsseldaten relativ klein sind. Viele andere Post-Quanten-Algorithmen haben eher große Schlüssel- oder Signaturlängen. Kryptografen hatten zwar gewarnt, dass diese Form von Algorithmen bisher noch wenig untersucht sei. Mit einem solch gravierenden Angriff hatte aber kaum jemand gerechnet.

Der Kryptograf Chris Peikert schreibt auf Twitter, dass es bei Angriffen auf SIDH über zwölf Jahre lang kaum Fortschritte gab - "und nun scheint es total gebrochen zu sein."

Erst vor kurzem gab es einen ähnlich fatalen Angriff auf ein Post-Quanten-Signaturverfahren namens Rainbow. Beide Fälle zeigen wohl: Wer neue Kryptografie entwickelt, muss mit Überraschungen und gravierenden Angriffen rechnen. Erst nachdem Verfahren ausführlich und über längere Zeiträume untersucht wurden, sollte man sie in der Praxis einsetzen.