eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2018/671

A Systematic Study of the Impact of Graphical Models on Inference-based Attacks on AES

Joey Green, Elisabeth Oswald, and Arnab Roy


Belief propagation, or the sum-product algorithm, is a powerful and well known method for inference on probabilistic graphical models, which has been proposed for the specific use in side channel analysis by Veyrat-Charvillon et al. We define a novel metric to capture the importance of variable nodes in factor graphs, we propose two improvements to the sum-product algorithm for the specific use case in side channel analysis, and we explicitly define and examine different ways of combining information from multiple side channel traces. With these new considerations we systematically investigate a number of graphical models that "naturally" follow from an implementation of AES. Our results are unexpected: neither a larger graph (i.e. more side channel information) nor more connectedness necessarily lead to significantly better attacks. In fact our results demonstrate that in practice the (on balance) best choice is to utilise an acyclic graph in an independent graph combination setting, which gives us provable convergence to the correct key distribution. We provide evidence using both extensive simulations and a final confirmatory analysis on real trace data.

Note: Changed name order and added reference to CARDIS paper (currently in post-proceedings so DOI not known)

Available format(s)
Publication info
Published elsewhere. Minor revision. 17th Smart Card Research and Advanced Application Conference
Belief PropagationFactor GraphsAESInference Based AttacksSide Channel AttacksTemplate Attacks
Contact author(s)
joey green @ bristol ac uk
2018-12-11: last of 3 revisions
2018-07-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joey Green and Elisabeth Oswald and Arnab Roy},
      title = {A Systematic Study of the Impact of Graphical Models on Inference-based Attacks on AES},
      howpublished = {Cryptology ePrint Archive, Paper 2018/671},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/671}},
      url = {https://eprint.iacr.org/2018/671}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.