Paper 2022/555

Adapting Belief Propagation to Counter Shuffling of NTTs

Julius Hermelink, Silvan Streit, Emanuele Strieder, and Katharina Thieme

Abstract

The Number Theoretic Transform (NTT) is a major building block in recently introduced lattice based post-quantum (PQ) cryptography. The NTT was target of a number of recently proposed Belief Propagation (BP)-based Side Channel Attacks (SCAs) . These attacks exploit the known structure of the NTT to reduce the guessing entropy after a profiled SCA by modeling the algorithm as a factor graph. Ravi et al. have proposed a number of countermeasures mitigating these attacks. They introduced three shuffling levels and one configurable masking step to counter the influence of the known structure of the NTT. In 2021, Hamburg et al. presented a chosen-ciphertext enabled SCA improving noise-resistance. Exemplarily, using their setting, we introduce a set of tools, which reveal that a subset of the proposed shuffling countermeasures could lead to a false security perception. Firstly, we analyze fine shuffling. We introduce a pre-processing step as well as a new factor node which we call shuffle node. Shuffle nodes allow for a modified version of belief propagation when included into a factor graph. The node iteratively learns the shuffling permutation of fine shuffling within a BP run. This allows a more noise resistant inference in the presences of mixed leakage distributions, which model the uncertainty of shuffled input or output nodes of a NTT butterfly. Secondly, we introduce a set of tools targeting the coarse shuffling countermeasure. We expand our attacker model and describe several matching algorithms to find inter-layer connections based on shuffled measurements. Our matching algorithm allows for either mixing prior distributions according to a doubly stochastic mix matrix or to extract permutations and perform an exact un-matching of layers. We additionally discuss the usage of sub-graph inference to reduce uncertainty and improve un-shuffling of butterflies. Based on our results, we conclude that the proposed countermeasures of Ravi et al. are powerful and counter Hamburg et al., yet could lead to a false security perception -- a powerful adversary could still launch successful attacks. We discuss on the capabilities needed to defeat shuffling in the setting of Hamburg et al. using our expanded attacker model.