Paper 2014/357

Making and Breaking Leakage Simulators

Jake Longo Galea and Daniel Martin and Elisabeth Oswald and Daniel Page and Martijn Stam

Abstract

Recently, Standaert et al. (Crypto'13) advocated the notion of simulatable leakage as a means to connect theoretical leakage resilience to practice. They argued that using simulators based on actual physical devices, the assumptions underlying their proofs of side channel resistance become empirically `verifiable' as evaluation labs can scrutinise the indistinguishability of the simulator by actually `playing' the games that involve real versus simulated leakage. Standaert \emph{et al.} proposed a concrete, block cipher based instantiation of a leakage resilient pseudorandom generator. They provided a high level definition of a simulator based on splicing two partial traces, and included detailed reasoning why their simulator (for AES-128) would resist state-of-the-art side channel attacks. We exhibit a distinguisher against their simulator, thereby falsifying their hypothesis. We demonstrate the efficacy of our distinguishing technique by experimental validation using concrete implementations of the Standaert \emph{et al.} simulator on several different platforms. Our successful analysis is based on `tracking' consistency (and likewise spotting simulator inconsistencies) in leakage traces by means of cross correlation. By taking the cross correlation between trace points, we can estimate real-or-simulated based either on a single key that is used multiple times, or based on multiple runs of Standaert's \emph{et al.} security game with varying keys each used only once. Since the game hybridizes (in the number of keys used), the latter implies that theoretically our distinguisher already wins when a single key is used with a single trace of side channel leakage! Finally, we propose several alternative simulators, based on splitting traces at points of low intrinsic cross-correlation, which are more promising w.r.t.~the cross-correlation distinguisher. Unfortunately, these new simulators come with significant caveats, and we conclude that the most natural way of producing simulated leakage is by using the underlying construction `as is' (but with a random key). Provided the actual implementation has a low signal-to-noise ratio, we believe it practically infeasible to distinguish between real and simulated traces: when only a few very noisy leakages are made available to an attacker, signal processing techniques that rely on having sufficient observations are not applicable.