A novel timing Side-Channel assisted key-recovery attack against HQC

Abstract

Kürzlich wurden mehrere Rechenzeitseitenkanäle in der HQC-Implementierung gefunden. Sie ermöglichen drei Angriffe, welche es alle ermöglichen den geheimen Schlüssel mittels Seitenkanalinformationen wiederherzustellen. Zwei von ihnen nutzen aus, dass ein nicht-konstantzeit BCH-Dekodierer verwendet wird. Der Verbleibende nutzt die Verwendung eines nicht-konstantzeit Vergleichs aus. Wir zeigen, dass ein weiterer kritischer Rechenzeitseitenkanal in der HQC-Implementierung verborgen ist. Der Seitenkanal ist der Verwendung von Werten, welche sich aus Geheimnissen ableiten, als Seed einer Verwerfungsmethode verschuldet. Wir schmiedenmehrere Angriffe, die den Seitenkanal ausnutzen. Wir bewerten diese und verbessern ihre Komplexität und Erfolgswahrscheinlichkeit. Der schnellste Angriff erfordert nur 19.942 Entkapselungsorakelaufrufe und gelingt mit einer empirisch ermittelten Wahrscheinlichkeitvon ≈ 96, 7%. Unsere Forschung zeigt, dass Rechenzeitseitenkanalangriffe noch lange nicht weg zudenken sind – auch in der Post-Quanten-Kryptographie können so selbst klassische Angreifer die Sicherheit eines Systems fundamental erschüttern. Glücklicherweise sinddie in dieser Arbeit identifizierten Probleme kein Todesurteil für das Kryptosystem, undkönnen mit den von uns vorgeschlagenen Gegenmaßnahmen behoben werden. Während unsere Hauptgegenmaßnahme einen starken Einfluss auf die gesamte Entkapselungszeit (+41%) hat zeigen wir, dass wir unter Anwendung der Gegenmaßnahmen keine statistisch signifikanten Zeitvariationen feststellen können.

Recently, multiple timing side-channels have been found in the Hamming Quasi-Cyclic (HQC) implementation. These enable three attacks that enable an attacker to recover the secret key from timing leakage. Two of them exploit an issue with the use of a non-constant time BCH decoder. The remaining one stems from using a non-constant time comparison.We demonstrate that another critical timing side-channel vulnerability exists in theHQC implementation. The timing side-channel is rooted in the use of values derived from secrets as a seed in a rejection sampling procedure. We forge multiple attacks exploiting the timing side-channel. We evaluate and improve their complexity and success probability. The fastest attack requires only 19,942 decapsulation oracle calls and succeeds with an empirically determined probability of ≈ 96.7%. Our research demonstrates that timing attacks are long from gone – in post-quantum cryptography they can shatter the security of a system even in the face of a classical attacker. Luckily, the issues identified in this thesis are not a death-sentence for the cryptosystem, and can be remedied using the countermeasures we proposed. While our main countermeasure has a heavy impact on total decapsulation time (+41%) we demonstrate that we cannot detect any statistically significant residual timing-variationin the patched version.