Side Channel Anaylsis

Side Channel Analysis¶

Smart Cards¶

RSA Side Channel attacks¶

RSA is biased on C = M^k

If the Byte of the RSA key is 0 then the algorithm uses the square() function
If the Byte of the RSA key is 1 then the algorithm uses the square() then the multiply() function.

Using the power analysis you can retrieve the binary data from the key

Example of RSA-CRT¶

Precompute:

\[ d_p \equiv d \pmod{p-1} d_q \equiv d \pmod{q-1} K \equiv p^{-1} \pmod{q} \]

Exponentiation:

\[ S_p = M^{d_p} \pmod{p} S_q = M^{d_q} \pmod{q} \]

Recombination:

\[ S = (((S_q - S_p) * K) \pmod{q}) * p + S_p \]

Injecting a fault that corrupts the S_q value

Fault Recombination:

\[ S' = (((S_q' - S_p) * K) \pmod{q}) * p + S_p \]

Calculate a Mutable of P:

\[ \begin{aligned} S - S' & = ((S_q - S_p) * K) \pmod{q}) * p - ((S_q' - S_p) * K) \pmod{q}) * p \\ & = (x_1 - x_2) * p \pmod{N} \\ & = x * p \pmod{N} \end{aligned} \]

Factor GCD:

\[ GCD(S - S', n) = GCD(x*p, p*q) = p \\ q = n/p \]

Example Differential Fault Analysis of RSA-CRT¶

With a single faulty signature the platintext and the public key

\[ S - S' = x * p \pmod{N} \\~\\ \begin{align*} M & = S^{e} \pmod{N} = (S' + x * p)^{e} \pmod{n} \\ & = \sum\limits_{i=0}^e \begin{pmatrix}e \\ i \end{pmatrix} * s ^{ie -i} (xp)^{i} \pmod{n} \\ & = s^{ie} + x * p * \sum\limits_{i=1}^e \begin{pmatrix}e \\ i \end{pmatrix} * s ^{ie -i} (xp)^{i-1} \pmod{n} \\ & = s^{ie} + x * p * k \pmod{n} \end{align*} \\~\\ M - S'^{e} = p * x * k GCD(M - S'^{e}, n) = GCD(p * x * k, p * q) = p \]

Differential Side Channel on RSA¶

Averaging all of the the power consumption of mutable encryptions creates a better power map. Then setting a threshold and taking all of the outputs that are above that data creates a map of the inputs for

Countermeasure¶

Do both square() and multiply() on every byte then take the proper output.