Cryptology ePrint Archive: Report 2018/671

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

Joey Green and Elisabeth Oswald and Arnab Roy

Abstract: 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.

Category / Keywords: Belief Propagation, Factor Graphs, AES, Inference Based Attacks, Side Channel Attacks, Template Attacks

Original Publication (with minor differences): 17th Smart Card Research and Advanced Application Conference

Date: received 11 Jul 2018, last revised 11 Dec 2018

Contact author: joey green at bristol ac uk

Available format(s): PDF | BibTeX Citation

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

Version: 20181211:152225 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]