Meet a New Cybersecurity Threat … Frequency Scaling

Meet a New Cybersecurity Threat … Frequency Scaling

And so, the darling of the post-quantum cryptography world … isogenies … is facing a new threat. It involves the SIKE (Supersingular Isogeny Key Exchange) key exchange method, and which has been attacked through the dynamic frequency scaling of x86 processors — known as dynamic voltage and frequency scaling (DVFS). The threat was discovered by researchers at the University of Texas at Austin, the University of Illinois Urbana-Champaign, and the University of Washington, and will be presented at the 31st USENIX Security Symposium in Boston [1]:

It relates to timing-related attacks and which normally involves discovering one or more bits of a key by measuring the time it takes to perform a given task.

Timing attack

A classical timing attack is with the square and multiply method, and where we use an exponential cipher of M^e (such as in RSA), and a ‘1’ in an encryption key, will cause extra computation, as opposed to a ‘0’. This allows an adversary the opportunity to observe how long it takes to perform the encryption operations. In the following case, we see that the SM (Square and Multiply) method takes longer than the S (Square method) [here]:

With this, we can then just read of the bits: 0 (S), 1(SM), 1(SM), 0(S), 1SM , 0(S), 0(S), 1(SM), 1(SM), 1(SM), 0(S), and 1(SM), and will revealed virtually all of the bits in the key. Some theory on the Montgomery method is here:

https://asecuritysite.com/ecc/ecc_kr2

Frequency scaling attack on SIKE

Robustness against timing attacks was actually one of SIKE’s strengths for its implementation, in that it uses timing-attack countermeasures. These are ones that ECC (Elliptic Curve Cryptography) generally uses. But, the frequency scaling method overcomes this and attacks with a zero value technique [2]:

Hertzbleed now adds a frequency side channel attack. With this, the x86 processor can do dynamic frequency scaling of the data that is being processed. Generally more extensive code will run the process up to its turbo mode, but will then fall back after a while. This will change the wall time of the code as it runs.

The range of processors — and their turbo modes — used in the experiments in the paper were:

In an x86 we define then p-states, and where the processor clock varies between two levels (a base frequency and a max turbo frequency). The base frequency will generally save battery power and run the processor cooler. Overall, the faster the clock, the more power will be consumed and the higher the workload. This higher frequency state, though, can only be sustained for so long before the processor will fall back to a lower frequency state (and thus consume less power). An example of running different workloads on the same machine is (and where int32-float is a more intensive process than int32):

We can see from Figure 2, that the speed of execution varies for the different work loads. In this case, int32-float is the more intensive task, and will thus run the processor at a faster rate for a while, and thus have a higher level of power consumption. As we see in (a) the power is higher for int32-float, but the frequency is then dropped quicker than in the case with the less intensive task. This happens around 6 seconds in for test (a), and around 9 seconds for test (b). The drop is from a full throttle of around 4.5GHz to around a base frequenc of 3.9GHz. This drop will then leak information about the intensity of the process, and which can link to the encryption key being used in SIKE.

Scope

The researchers have confirmed that every Intel processor is affected, and several AMD processors (including for AMD Ryzen, Zen 2 and Zen 3). It has been published as CVE-2022–24436 with a threat level of 6.3:

Conclusions

There’s no known patch for this, and no one quite knows how this attack can scale to other methods. So, interesting times!

Reference

[1] Hertzbleed: Turning Power Side-Channel Attacks Into Remote Timing Attacks on x86, 31st USENIX Security Symposium (Boston, 10–12 August 2022). Preprint.

[2] De Feo, L., El Mrabet, N., Genêt, A., Kaluđerovi, N., de Guertechin, N. L., Pontié, S., & Tasso, É. (2022). SIKE Channels: Zero-Value Side-Channel Attacks on SIKE. IACR Transactions on Cryptographic Hardware and Embedded Systems, 264–289.