Horizontal Attacks and Variants

An interesting class of side-channel attacks is the Horizontal Analysis attack, where a single trace is used to recover the secret scalar. The main characteristic of the traces that makes horizontal attacks possible lies in the fact that the operation sequences of doubling-adding and doubling-doubling can be distinguished. The attacker applies the classical correlation analysis using different parts of time samples in the same side-channel trace to recover the secret scalar bit-by-bit. This technique can be useful to attack protected implementations, where the secret value or unknown input is blinded. The first horizontal attacks were applied to RSA implementations; extension of those to ECC implementations is straight-forward, since scalar multiplication and exponentiation algorithms have the same operation steps.

The so-called Big Mac attack from Walter [38] is the first attack of this kind, where squarings (S) are distinguished from multiplications (M) and the secret exponent of an RSA exponentiation can be recovered from a single execution curve. The distinction is possible by averaging and comparing the cycles performed in the multiplier of the device during long-integer multiplication, since more cycles are needed for SM than for SS. This attack can be directly applied to ECC implementations.

The term horizontal was first introduced by Clavier et al. in [46], where the authors performed a horizontal correlation analysis to compute the correlation factor on several segments extracted from a single execution curve of a known message RSA encryption. More specifically, their proposed method starts by finding a sequence of elementary calculations (C) j (with i, j e Z indicating the sequence of the calculation and the order of the execution respectively) that processes the same mathematical operation (e.g., field multiplication) and depends on the same part of the secret scalar. The outputs Oij of the calculations C (X) that depend on the same input value X will give high correlation results and in this way, they can be distinguished from outputs of computations with different input values. Horizontal correlation analysis was performed on RSA using the Pearson correlation coefficient in [46] and triangular trace analysis of the exponent in [49].

The most recent attack, proposed by Bauer et al. in [41], is a type of horizontal collision correlation attack on ECC, which combines atomicity and randomization techniques. Based on the basic assumption of collision attacks that an adversary is able to distinguish when two field multiplications have at least one common operand, their attack consists of the following steps:

  • • Identify two elementary calculations C1, C2 that are processed N times with inputs from the same distribution. The correlation between the random output values O1, O2 must depend on the same secret sub-part s.
  • • For each of the N processings of C get an observation V-, with j e {1,..., N}.
  • • Compute the Pearson correlation coefficient on the two samples of observations P = P((l)) j , (2)j).
  • • Deduce information on the secret scalar from p using an appropriate distinguisher that shows which observation is more similar to the real secret value.

The horizontal collision correlation attack is shown by simulated traces to be applicable to atomic implementations and to implementations based on unified addition formulas over Edwards curves.

Two recent publications on blinded asymmetric algorithms propose the combination of horizontal and vertical techniques, in an attempt to provide more practical attacks against blinded implementations and avoid the complex signal processing phase. Bauer et al. [50] at Indocrypt 2013, presented an attack on RSA blinded exponentiation based on this approach. They took advantage of the side-channel leakage of the entire long-integer modular multiplication without splitting the trace into parts of single precision multiplications. However, their attack requires a small public exponent (no greater than 216 + 1) and an exponent blinding factor smaller than 32 bits. Their observation that the scalar blinding does not mask a large part of the secret value, led Feix et al. [51] a year later to exploit this vulnerability vertically on a ECC implementation. The most significant part of the blinded scalar can be recovered with a horizontal attack. The least significant part of the scalar is retrieved using vertical analysis (several execution traces) and the information leaked in the previous steps of the attack.

 
Source
< Prev   CONTENTS   Source   Next >