@article{Hermelink_Streit_Strieder_Thieme_2022, title={Adapting Belief Propagation to Counter Shuffling of NTTs}, volume={2023}, url={https://tches.iacr.org/index.php/TCHES/article/view/9947}, DOI={10.46586/tches.v2023.i1.60-88}, abstractNote={<p>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). Ravi et al. have recently proposed a number of countermeasures mitigating these attacks.<br>In 2021, Hamburg et al. presented a chosen-ciphertext enabled SCA improving noise-resistance, which we use as a starting point to state our findings. We introduce a pre-processing step as well as a new factor node which we call <em>shuffle</em> <em>node</em>. Shuffle nodes allow for a modified version of BP when included into a factor graph. The node iteratively learns the shuffling permutation of fine shuffling within a BP run.<br>We further 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.<br>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.<br>Our methods are not limited to the presented case but provide a toolkit to analyze and evaluate shuffling countermeasures in BP-based attack scenarios.</p>}, number={1}, journal={IACR Transactions on Cryptographic Hardware and Embedded Systems}, author={Hermelink, Julius and Streit, Silvan and Strieder, Emanuele and Thieme, Katharina}, year={2022}, month={Nov.}, pages={60–88} }