A closer look at the belief propagation algorithm in side-channel attack on CCA-secure PQC KEM  

作　　者：Kexin QIAO Zhaoyang WANG Heng CHANG Siwei SUN Zehan WU Junjie CHENG Changhai OU An WANG Liehuang ZHU 

机构地区：[1]School of Cyberspace Science and Technology,Beijing Institute of Technology,Beijing 100081,China [2]State Key Laboratory of Cryptology,P.O.Box 5159,Beijing 100878,China [3]School of Cryptology,University of Chinese Academy of Sciences,Beijing 100089,China [4]School of Cyber Science and Engineering,Wuhan University,Wuhan 430072,China

出　　处：《Science China(Information Sciences)》2024年第11期313-330,共18页中国科学（信息科学）（英文版）

基　　金：supported by National Key Research and Development Program of China(Grant No.2022YFB3103800);National Natural Science Foundation of China(Grant No.62102025);Beijing Natural Science Foundation(Grant No.4222035);Open Project Program of the State Key Laboratory of Cryptology(Grant No.MMKFKT202212)。

摘　　要：The implementation security of post-quantum cryptography(PQC)algorithms has emerged as a critical concern with the PQC standardization process reaching its end.In a side-channel-assisted chosen-ciphertext attack,the attacker builds linear inequalities on secret key components and uses the belief propagation(BP)algorithm to solve.The number of inequalities leverages the query complexity of the attack,so the fewer the better.In this paper,we use the PQC standard algorithm CRYSTALS-KYBER as a study case to construct bilateral inequalities on key variables with substantially narrower intervals using a side-channel-assisted oracle.For KYBER512,KYBER768,and KYBER1024,the average Shannon entropy carried by such inequality is improved from the previous 0.6094,0.4734,and 0.8544 to 0.6418,0.4777,and 1.2007.The number of such inequalities required to recover the key utilizing the BP algorithm for KYBER512 and KYBER1024 is reduced by 5.32%and 40.53%in theory and experimentally the reduction is even better.The query complexity is reduced by 43%,37%,and 48%for KYBER512,768,and 1024 assuming reasonably perfect reliability.Furthermore,we introduce a strategy aimed at further refining the interval of inequalities.Diving into the BP algorithm,we discover a measure metric named JSD(Jensen-Shannon distance)-metric that can gauge the tightness of an inequality.We then develop a machine learning-based strategy to utilize the JSD-metrics to contract boundaries of inequalities even with fewer inequalities given,thus improving the entropy carried by the system of linear inequalities.This contraction strategy is at the algorithmic level and has the potential to be employed in all attacks endeavoring to establish a system of inequalities concerning key variables.

关 键 词：KYBER chosen-ciphertext attack side-channel belief propagation contraction strategy machine learning 

分 类 号：O413[理学—理论物理] TN918.4[理学—物理]