Friday, March 28, 2014

Something is leaking in the state of Denmark

A recent study group brought about a micro-preview of this year's Eurocrypt, as we visited one of the 'Best Paper' nominated submissions, Unifying leakage models: from probing attacks to noisy leakage [by A. Duc, S. Dziembowski and S. Faust]. Speaking of Eurocypt, Susan's (who is now part of our Bristol Crypto group) and her co-authors' paper is also on this year's programme.

Side-channel attacks target implementation-specific characteristics of algorithms deployed on physical devices, such as power consumption, running time and so on. Sure, this information is "observed" with specific pieces of hardware (e.g., an oscilloscope), but since such equipment is relatively cheap, it is plausible to assume that even a not-so-experienced attacker can gain access to sensitive information. There is a significant number of papers describing scenarios in which and methods by which the then attacker walks successful (at least in theory), even when side-channel information is incomplete or erroneous. This is a highly optimistic perspective, perhaps a more realistic one would be the cat-and-mouse game, where deployers constantly develop countermeasures and attackers/evaluators strive to come up with ingenious ways around them, both tasks being equally hard. And let's not forget that the attackers may not have it easy to begin with: alas, although in theory there may be no difference between theory and practice, in practice, there always is [fact]. In particular, the two shortcomings mentioned above hold base for the most common paradigms in leakage modelling: there's only so much information which is actually available (bounded leakage) and physical measurments will always reflect some degree of intrinsic noise (noisy leakage).

The paper that we have visited aims at unifying leakage models, and of course does so by introducing a new leakage model. Moreover, it extends the previous work of Prouff and Rivain presented at last year's Eurocrypt [paper]. In particular, the latter paper analyzed the security of a block-cipher implementation protected with additive masking, but had some shortcomings, namely 1. some components were assumed leak-free, 2. the security was guaranteed against random (i.e., not chosen) messages 3. it had limited application.

Duc et al. make their argument based on simulation. Clearly, the first issue will then be how to model noise. Basically, noise is regarded as a randomized function over a finite set of values, independent for all elementary operations, bounded by some parameter, δ (δ-noisy), and is as such a statistical distance from the "ideal" leakage.

Three models for adversaries are studied, the noisy, the random probing and the t-threshold-probing model. In this third example, the adversary can learn the value of t intermediate values that are processed during the computation. A random probing adversary recovers an intermediate value with probability e and obtains a special symbol ⊥ with probability 1−e. Quite intuitively, it is possible to change from this model to the t-threshold-probing adversary, the intuition being accompanied by a formal proof and examples.

On the other hand, in order to address the topic of the noise-resilience of cryptographic computations, a model for arithmetic circuits over a finite field is presented. A (stateful arithmetic) circuit Γ over a field F is an oriented graph. The nodes are called gates, and belong to a pre-determined set (e.g., input/output gates, multiplication/addition, random/constant, memory and so on). A black-box circuit adversary A is a machine that adaptively interacts with a circuit Γ via the input and output interface. Given two stateful circuits Γ and Γ′ over some field F, Γ′ is said to be a (δ, ξ)-noise resilient implementation of a circuit Γ with respect to some (encryption) function f, if the output of Γ with some chosen key k and input is equally likely observed as the output of Γ' with the f(k) and same input, and for every δ-noisy adversary A there exists a black-box circuit adversary S such that the distance between the output of A after interacting with Γ with key k and the output of S after interacting with Γ' with key f(k)  is bounded by ξ. Finally, security in the probing model and resilience to leakage are addressed and a comparison to the previous work is given.

No comments:

Post a Comment