Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / leakage resilience, side channels

Date: received 21 May 2014, last revised 22 May 2014

Contact author: Elisabeth Oswald at bristol ac uk

Available format(s): PDF | BibTeX Citation

Version: 20140522:071754 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]