快速Dilithium 於Cortex-M4 平台實現的旁通道分析

Side-Channel Analysis of Faster Dilithium on Cortex-M4

李昇峰(Sheng-Fong Li)

指導教授 ： 陳君明

國立臺灣大學/理學院/應用數學科學研究所/碩士(2023年)

https://doi.org/10.6342/NTU202301181

摘要

隨者量子電腦的發展，後量子密碼演算法，將會取代現有的非對稱密碼系統。在2022 年七月，美國國家標準暨技術研究院，公布了標準化的後量子數位簽章法，Crystal-Dilithium 是三個標準的其中一個，也是三個之中可以在合理時間內，於Cortex-M4 上運行的後量子數位簽章。

2022 年一月，一種運行於 Cortex-M4 加速版本的 Dilthium 被研發出來，它在小係數多項式乘法有更快的運算，使得運行的時間被近一步地縮短，然而也使其對旁通道攻擊的弱點進一步地被放大。

本文使用了相關性能量分析攻擊(Correlation Power Analysis) 和 T 檢定(T-test)， 將這兩種分析的方式結合，成功的攻擊了 Dilithium-2 的小係數多項式乘法，並且準確地還原其私鑰。Correlation Power Analysis 可以在短時間內，從66049 種可能性中找出最有可能的私鑰組合，而 Profiling T-test，則可從少數的組合中找到正確的答案，形成一個快速又有效果的攻擊方式。如果沒有使用 masking 或shuffling 進行防護，Dilithium 對於旁通道攻擊的防護是非常脆弱的。

關鍵字

相關性能量分析攻擊 ； 電子簽章 ； 快速數論變換 ； 模板攻擊 ； 後量子密碼 ； 司徒頓t檢定

並列摘要

With the development of quantum computers, post-quantum cryptography (PQC) and its digital signatures will replace asymmetric cryptographic systems. In July 2022, the National Institute of Standards and Technology (NIST) announced the standardized Postquantum signatures. Crystal-Dilithium is one of the three digital signature standards, and it is also one of the three that can run on the Cortex-M4 in a reasonable time. In January 2022, a faster version of Dilithium was developed. It has faster operations in small coefficient polynomial multiplication, further shortening the running time and amplifying its vulnerability to side-channel attacks.

This article uses the combination of Correlation Power Analysis and Profiling T-test to successfully attack Dilithium-2’s small coefficient polynomial multiplication to recover its sensitive information $s_1$ and $s_2$. Correlation Power Analysis can find the most likely $s_1$ and $s_2$ coefficient pairs from 66049 possibilities quickly. In contrast, the Profiling T-test can find the correct answer from a few candidates, forming a fast and effective attack method. Without the countermeasure of masking or shuffling for protection, Dilithium will be very vulnerable to side-channel attacks.

並列關鍵字

Correlation Power Analysis ； Digital Signature ； Number Theoretic Transform ； Online Template Attack ； Post-quantum Cryptography ； Welch's T-test

參考文獻

[1] A. Abdulrahman, V. Hwang, M. J. Kannwischer, and A. Sprenkels. Faster kyber and dilithium on the cortex-m4. In Applied Cryptography and Network Security: 20th International Conference, ACNS 2022, Rome, Italy, June 20–23, 2022, Proceedings, pages 853–871. Springer, 2022.

[2] S. Bai, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé. Crystals-dilithium: Algorithm specifications and supporting documentation (version 3.1). NIST Post-Quantum Cryptography Standardization Round, 3, 2021.

[3] S. Bai and S. D. Galbraith. An improved compression technique for signatures based on learning with errors. In Topics in Cryptology–CT-RSA 2014: The Cryptographer＇s Track at the RSA Conference 2014, San Francisco, CA, USA, February 25-28, 2014. Proceedings, pages 28–47. Springer, 2014.

[4] L. Batina, Ł. Chmielewski, L. Papachristodoulou, P. Schwabe, and M. Tunstall. Online template attacks. Journal of Cryptographic Engineering, 9:21–36, 2019.

[5] Z. Chen, E. Karabulut, A. Aysu, Y. Ma, and J. Jing. An efficient non-profiled sidechannel attack on the crystals-dilithium post-quantum signature. In 2021 IEEE 39th International Conference on Computer Design (ICCD), pages 583–590. IEEE, 2021.