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

Kexin Qiao; Siwei Sun; Zhaoyang Wang; Zehan Wu; Junjie Cheng; An Wang; Liehuang Zhu

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

Siwei Sun, University of Chinese Academy of Sciences, Beijing 100089, China

Zhaoyang Wang, Beijing Institute of Technology, Beijing 100081, China

Zehan Wu, Beijing Institute of Technology, Beijing 100081, China

Junjie Cheng, Beijing Institute of Technology, Beijing 100081, 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 Kyber512 as a study case to construct bilateral inequalities on key variables with substantially narrower intervals using a side-channel-assisted oracle. The number of such inequalities required to recover the key with probability 1 utilizing the BP algorithm is reduced relative to previous unilateral inequalities. Furthermore, we introduce strategies aimed at further refining the interval of inequalities. Diving into the BP algorithm, we discover a measure metric named JSD-metric that can gauge the tightness of an inequality. We then develop a heuristic strategy and a machine learning-based strategy to utilize the JSD-metrics to contract boundaries of inequalities even with fewer inequalities given, thus improving the information 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: Preprint.
Keywords: Kyber CCA belief propagation contraction strategy machine learning
Contact author(s): qiao kexin @ bit edu cn
sunsiwei @ ucas ac cn
wangzhaoyang1 @ bit edu cn
zehanwu @ bit edu cn
junjiecheng @ bit edu cn
wanganl @ bit edu cn
liehuangz @ bit edu cn
History: 2024-01-31: approved; 2024-01-31: received; See all versions
Short URL: https://ia.cr/2024/135
License: CC BY

BibTeX

@misc{cryptoeprint:2024/135,
      author = {Kexin Qiao and Siwei Sun and Zhaoyang Wang and Zehan Wu and Junjie Cheng 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},
      url = {https://eprint.iacr.org/2024/135}
}