Paper 2024/135

A Closer Look at the Belief Propagation Algorithm in Side-Channel-Assisted Chosen-Ciphertext Attacks

Kexin Qiao, Beijing Institute of Technology, Beijing 100081, China
Zhaoyang Wang, Beijing Institute of Technology, Beijing 100081, China
Heng Chang, Beijing Institute of Technology, Beijing 100081, China
Siwei Sun, University of Chinese Academy of Sciences, Beijing 100089, China
Zehan Wu, Beijing Institute of Technology, Beijing 100081, China
Junjie Cheng, Beijing Institute of Technology, Beijing 100081, China
Changhai Ou, Wuhan University, Wuhan 430072, China
An Wang, Beijing Institute of Technology, Beijing 100081, China
Liehuang Zhu, Beijing Institute of Technology, Beijing 100081, China
Abstract

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 Kyber 1024, 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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. Major revision. SCIENCE CHINA Information Sciences
DOI
10.1007/s11432-024-4150-3
Keywords
KyberCCAbelief propagationcontraction strategymachine learning
Contact author(s)
qiaokexin0327 @ 163 com
wangzhaoyang1 @ bit edu cn
2226234745 @ qq com
sunsiwei @ ucas ac cn
zehanwu @ bit edu cn
junjiecheng @ bit edu cn
ouchanghai @ whu edu cn
wanganl @ bit edu cn
liehuangz @ bit edu cn
History
2024-11-19: revised
2024-01-31: received
See all versions
Short URL
https://ia.cr/2024/135
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/135,
      author = {Kexin Qiao and Zhaoyang Wang and Heng Chang and Siwei Sun and Zehan Wu and Junjie Cheng and Changhai Ou and An Wang and Liehuang Zhu},
      title = {A Closer Look at the Belief Propagation Algorithm in Side-Channel-Assisted Chosen-Ciphertext Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/135},
      year = {2024},
      doi = {10.1007/s11432-024-4150-3},
      url = {https://eprint.iacr.org/2024/135}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.