Now Machines Attack Post Quantum Cryptography: Kyber Has Been Cracked — Not The Algorithm, Though

NIST has recently standardized post quantum cryptograpy (PQC) standards, and have focused on CRYSTALS-Kyber for key exchange. And, so…
Photo by Alex Knight on Unsplash

Now Machine Learning Attacks Post Quantum Cryptography: Kyber Has Been Cracked — Not The Algorithm, Though

NIST has recently standardized post quantum cryptograpy (PQC) standards, and have focused on CRYSTALS-Kyber for key exchange. And, so, many researchers have been attacking it, and this new paper present a way to crack it [here][1]:

It should be noted that it is not the method itself that has been cracked, it is the usage of side channels. Overall, the usage of machine learning for side-channel analysis is fairly common, and has also been used to crack AES implementations. For the Kyber attack, the research team took thousands of power traces and used machine learning to crack.

Diagrams (a) and (b) show examples of the power traces, while (c), (d) and (e) show the Neural network training:

It is an interesting paper and focuses on a bug that the authors actually introduced. Overall, the side channel was discovered in the re-encryption phase of Kyber, and which is difficult to hide its operation — and thus exposing the potential for a side-channel attack. The neural network learning method used in the paper has already been applied to a number of side-channel attacks on encryption, but this seems to be the first that applies directly to Post Quantum Cryptography.

In 2019, Das et al, outlined how X-DeepSCA (Cross-device Deep Learning Side Channel Attack) uses a Deep Neural Network to provide an accuracy of more than 99.9%. Overall the model only took a few seconds to run compared with many minutes for the standard CPA (Correlation Power Analysis) technique [3]:

Then, in 2021, Wany and Dubrova also used a neural network classifier to discover the AES symmetric key [2]:

If you are interested, here is some of the work we did on side channels a few years ago:

And published here:

https://www.tandfonline.com/doi/full/10.1080/23742917.2016.1231523

Conclusions

And, so, the rise of machine learning continues, and it has the leakage of information in the encryption process in its sights. For Kyber, everything is fine with the method, we just need to find better ways to mask its operation. Luckily, it is not quite in full production, yet, so it’s not a major problem. If you are interested in side channels, here’s some background:

References

[1] Dubrova, E., Ngo, K., & Gärtner, J. (2022). Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste. Cryptology ePrint Archive.

[2] Wang, H., & Dubrova, E. (2021). Tandem Deep Learning Side-Channel Attack on FPGA Implementation of AES. SN Computer Science, 2, 1–12.

[3] Das, D., Golder, A., Danial, J., Ghosh, S., Raychowdhury, A., & Sen, S. (2019, June). X-DeepSCA: Cross-device deep learning side channel attack. In Proceedings of the 56th Annual Design Automation Conference 2019 (pp. 1–6).