Paper 2018/498

Modeling Soft Analytical Side-Channel Attacks from a Coding Theory Viewpoint

Qian Guo and Vincent Grosso and François-Xavier Standaert

Abstract

One important open question in the field of side-channel analysis is to find out whether all the leakage samples in an implementation can be exploited by an adversary, as suggested by masking security proofs. For concrete attacks exploiting a divide-and-conquer strategy, the answer is negative (i.e., only the leakages corresponding to the first/last rounds of a block cipher can be exploited). Soft Analytical Side-Channel Attacks (SASCA) have been introduced as a powerful solution to mitigate this limitation. They represent the target implementation and its leakages as a code (similar to a Low Density Parity Check code) that is then decoded thanks to belief propagation. Previous works have shown the low data complexities that SASCA can reach in practice (at the cost of a higher time complexity). In this work, we revisit these attacks by modeling them with a variation of the Random Probing Model used in masking security proofs, that we denote as the Local Random Probing Model (LRPM). Our study establishes interesting connections between this model and the erasure channel used in coding theory, leading to the following benefits. First, the LRPM allows assessing the security of concrete implementations against SASCA in a fast and intuitive manner. We use it to confirm that the leakage of any operation in a block cipher can be exploited, although the leakages of external operations dominate in known-plaintext/ciphertext attack scenarios. Second, we show that the LRPM is a tool of choice for the (nearly worst-case) analysis of masked implementations in the noisy leakage model, taking advantage of all the operations performed, and leading to new possibilities of tradeoffs between their amount of randomness and physical noise level.