Hardware Hacking: Breaking Post-Quantum Encryption Using Side-Channel Analysis
Hello! A little more than a year ago I got the opportunity to work on a very exciting Thesis subject for my Master's in Embedded Systems at the University of Twente. I got to attack a post-quantum cryptographic algorithm with a hardware attack that I designed. In this article explain in layman terms why we care about post-quantum cryptography and how such an attack would work.
What is Post-Quantum Cryptography?
Quantum computer's are becoming an ever more prevalent threat to our current cryptographic standards. I'll spare you the details of exactly how quantum computer's are able to break most of our current-day encryption. Just know, that our cryptographic algorithms are based on mathematical problems which are hard for classical computer's to solve. But some of these problem's can relatively easy be solved using quantum algorithms, effectively breaking or severely weakening current cryptographic standards. A prime example of this would be Shor's algorithm, which is able to solve the prime factorization problem. This would mean that suddenly those numbers on your bank account might fade into non-existence, when somebody with a quantum computer decides that they are of their interest.
So to answer the question "What is post-quantum cryptography?". Post-quantum cryptography are cryptographic algorithms which are based upon problems on which we have convincing evidence that they are difficult problems for quantum computers as well. NIST (National Institute of Standards and Technology) has started a public competition for finding and standardizing post-quantum cryptography algorithms. All with the goal to prevent our digital infrastructure from collapsing when quantum computer's become powerful enough to break current-day cryptography. I designed a custom attack that targetted one of the competition's winners: CRYSTALS-Kyber.
Hardware Hacking Using Side-Channel Analysis
Hardware hacking is an unconvential technique where the underlying hardware of a system is part of the attack vector. The nature of these attacks often require physical access to the victim device. Back in the day, hardware attacks where not considered much of a concern as computers where scarce and not easily accessible. However with the ever increasing number of embedded devices, these attacks are becoming more and more relevant. A theoretical unbreakable cryptographic algorithm could still be exploited, not by focussing on the algorithm itself, but instead by focussing on the underlying hardware itself.
To illustrate such a technique, I would like to introduce you to side-channel analysis. Side-channel analysis is a technique where the side-channels of hardware is analyzed to recover secret information. On a very basic level, when a processor is working with (possibly secret) data it is unintentially releasing extra information that sometimes is linked to the underlying data. We call the channels that such information is leaked through, side-channels. Typical examples of side-channels are electricity consumption, heat, temperature, sound and electromagnetic radiation.
In context of cryptographic algorithms operating on secret data, it is sometimes possible to use this source of extra information to infer things about the secret data. This in turn can then be used by attackers to play outside of the box and break cryptographic algorithms by observing the hardware the algorithm is operating on.
My custom side-channel attack on CRYSTALS-Kyber
Finding a vulnerable critical-section
To perform a side-channel attack, we need to identify critical sections where operations are performed on the secret data. One of the last steps of the algorithm is to multiply coefficients by a constant followed by montgomery reduction (modulo operation). This is done in a function called fqmul(a,b). Where the result is a times b followed by modulo 3329. In the last step b is a constant and a is data that contains information about the secret key.
This therefore, could be a prime target for a side-channel analysis attack! In my attack I focused on the power side-channel. This is power consumption of the chip while it is performing operations. With a clever oscilloscope and a shunt-resistor it is possible to measure the power as the chip performs its operations. By cross-referencing the power measurements the operations that the chip performs, we might learn something about the data that is being operated on. In side-channel analysis the hamming-weight is often used to model the power leakage of an intermediate variable. The hamming-weight is the number of bits which are set to '1's. So the hamming-weight of 0001 would be 1 and the hamming weight of 1011 would be 3. The assumption for this model, is that the power leakage of is proportional to the number of set bits.
During my research, I analyzed the fqmul function and found that the hamming-weight of the function's output had a relation to the power leakage. In the Figure 1 you can see that the lower the hamming-weight the lower power consumption (Note: the more negative the value on the y-axis, the higher the power consumption). This makes fqmul a prime target for a side-channel analysis attack.
Correlation power analysis (CPA)
The primary technique used in this attack is Correlation Power Analysis (CPA). CPA is a clever technique making use of Pearsons' correlation coefficient.
First step, we have to define a theoretical leakage model. This is a model that relates the secret (sub)key to the power consumption. In many cases, the hamming-weight is used as part of this model. Alternative more complex techniques use deep-learning to obtain a leakage model. And many more method exist.
Second step, with the model defined, we can then perform many side-channel measurements of the chip performing its operation. We do many measurements for different input values where the chip operates on the secret data.
Third and most important step, we perform Correlation Power Analysis. The power measurements we have obtained, are generally very noisy and impossible to analyze by simple techniques. We take all power samples and our model, then we compute the Pearson's correlation coefficient for all samples related to our leakage-model. We do this for every possible value of (sub)key. We are effectively, guessing for all keys what the right key should be. Figure 2 shows a power trace with the computed Pearson's correlation coefficients next to it. Notice that the coefficients indicate a strong negative correlation between samples 100 and 120.
Now we have many correlation values, how does this help us with determing the secret (sub)key. Remember, that we have a model which loosely reflects the power consumption of different (sub)key values. If our model is correct, then we would expect the power measurements on average to be higher when our model also outputs higher values. We feed our model with a guess for a (sub)key value, and then use the correlation coefficient to check whether it is correlated to the power measurements. If our guess for the (sub)key is wrong, we would expect to see no correlation. But the opposite is also true, if our (sub)key guess was correct, we would expect to see some correlation. And as a result, we know that we guessed the correct (sub)key!
Performing the attack
Now with all steps in place, we can perform the attack. We take our ChipWhisperer-Lite setup to measure power leakage accurately. We let the chip perform the operation and capture a power trace. Next we use our model together with the measurements to obtain the correlation coefficients. Finally pick the guess which showed to have the strongest correlation. And now we are done!... well in an ideal world.
Because of noise in the power consumption and general non-determinism of mcu operations, we have to measure many times. From hundreds to million of traces. A side-channel analysis attack's effectiveness, is generally measured in the number of traces required to obtain the secret key. The partial guessing entropy (PGE), is the distance that we are from the actual key during an attack. The higher the PGE, the further away we are from the true key. If this value is 0, then we have found the true key. We can plot the PGE against the number of traces. Doing this, we can hopefully see the PGE get lower as we obtain and analyze more traces. In Figure 3 you can see a graph of the PGE as function of number of traces for my attack. After less than 50 power traces the full secret key has been recovered. Showing experimentally, that the attack indeed is capable of obtaining the secret key for CRYSTALS-Kyber by means of power side-channel analysis.
Conclusion
Even though retrieving the secret key within 50 traces is impressive, keep in mind that we are dealing with a simplified attack scenario. The attack was only performed on two different chips with different chipsets. (ARM and RISCV). In practice, the environment is less ideal and there may be specific conditions required to perform the attack. The hardware or algorithm may have been specialized to counteract side-channel attacks. Furthermore, an attacker requires physical access to the device with specialized measuring equipment. This already makes the attack hard to execute in practice. This however, does not take away from the importance of analyzing side-channel security of prospective cryptographic algorithms. Attack's like this might very help in shaping countermeasures which ensure robustness of post-quantum cryptography.
I hope that you enjoyed my very simplified write-up about my research on side-channel analysis on CRYSTALS-Kyber. If you want a more structured detailed explanation, feel free to read read my Master's Thesis.