Paper 2012/256

The myth of generic DPA...and the magic of learning

Carolyn Whitnall and Elisabeth Oswald and François-Xavier Standaert

Abstract

A prominent strand within the side-channel literature is the quest for generic attack strategies: methods by which data-dependent leakage measurements can be successfully analysed with `no' a priori knowledge about the leakage characteristics. In this paper, we introduce a well-reasoned definition for what it means to have `no' a priori insight (that is, to use a power model which approximates the device---up to nominality---by the equivalence classes associated with the target function), and use this to define generic DPA attacks. With these definitions we are able to clarify precise conditions (on the target function) under which generic attacks succeed. Doing so, we expose a rather limited range of vulnerable target functions, so that the `myth' of the potential power of generic DPA is somewhat dispelled. We then shift focus onto linear regression-based attacks: linear regression can operate generically (as we explain) by `fitting' the leakage measurements (differently for different key hypotheses) to a \emph{full basis} of polynomial terms in the targeted bits. Quite surprisingly, we show that even when the target function is not susceptible to generic DPA, applying some additional, non device-specific intuition to the different hypothesis-dependent models can in fact reveal the key. This intuition amounts to the idea that the estimated model coefficients associated with the correct key hypothesis ought to be `more orderly', in some sense, provided the target function is sufficiently nonlinear (as is typically the case for cryptographic S-Boxes used in block ciphers). To leverage this in a practical way we apply a model building technique called stepwise regression. Thus by `emulating' a generic technique we can `magically' produce successful attacks even when generic attacks applied in a conventional mode would fail.