I woke up to the news of a new form of timing-side-channel attack based on the dynamic frequency scaling of modern x86 processors. This is the Hertzbleed attack, which will be presented at the USENIX Security Symposium in Boston in August. The authors are Yingchen Wang and Hovav Shacham from the University of Texas at Austin, Riccardo Paccagnella and Elizabeth Tang He and Christopher Fletcher from the University of Illinois Urbana-Champaign, and David Kohlbrenner from the University of Washington.
Interestingly for this blog, they target the supersingular isogeny key exchange protocol SIKE. SIKE is implemented in constant-time using standard timing-attack countermeasures from traditional ECC, such as the Montgomery ladder. But the frequency scaling feature allows to mount the timing attack even against supposedly constant-time code. The attack is a form of “zero value attack“. See also Patrick Longa’s comments on the NIST PQC mailing list.
The key property of SIKE that is exploited is that the protocol message is a triple where is an elliptic curve and are points. The points are a troublesome aspect of SIDH/SIKE, and are the cause of the adaptive attack by Galbraith-Petit-Ti-Shani, the torsion point attacks by Petit and de Quehen-Kutas-Leonardi-Martindale-Panny-Petit-Stange, and so on. In certain contexts, these attacks are prevented by the Fujisaki-Okamoto transform, but this doesn’t help in the context of side-channel attacks.
The specific attack on SIKE given by the Hertzbleed authors is also of this form. It involves maliciously choosing the points in a key-dependent way to learn information. As explained by Patrick Longa in his post above, there is a countermeasure to such attacks.
What does this mean for ECC in general? At the moment the timing channel does not seem to be fine-grained enough to attack constant-time elliptic curve systems in use. The paper says:
“Despite its theoretical power, it is not obvious how to construct practical exploits through the frequency side channel. This is because DVFS updates depend on the aggregate power consumption over millions of CPU cycles and only reflect coarse-grained program behavior. Yet, we show … that some cryptographic primitives admit amplification of single key bit guesses into thousands of high- or low-power operations, enough to induce a measurable timing difference.”
But we know that attacks only get better. So it will be interesting and important to see if this approach can be used to attack current ECC systems in practice.
— Steven Galbraith