** Side-Channel Attack:**

## Acoustic Cryptanalysis Attack:

- Find key-dependent instruction.
- Record emanations using high-bandwidth equipment.
- Obtain traces.
- Analyze the recordings and "guess" or "recover" the key.

### Implementation of the attack:

In the paper, they attack GnuPG (a software that implements RSA
encryption). To use GnuPG, we send “*adaptive cipher-texts”* to
the victim machine which uses Enigmail, which decrypts the massages as soon it
receives them.

The amplifier and digitizer are used to record acoustic
emancipations and graph them in this way. The vertical axis is a time axis and the horizontal axis is the frequency axis.

In the paper, they describe that all operations performed by the
computer emit different acoustic emancipations which allow us to identify
different operations. They find out the correlation of acoustic emancipations
with a basic code( For this purpose they wrote a simple program that executes
(partially unrolled) loops containing one of the following x86 instructions:
HLT (CPU sleep), MUL (integer multiplication), FMUL (floating-point
multiplication), main memory access (forcing L1 and L2 cache misses), and REP
NOP (short-term idle) ).

### How does RSA decrypt the message?

At the heart of RSA decryption is a modular exponentiation m = c^{d} mod N where N = pq is the RSA modulus, d is the private decryption exponent,
and c is the ciphertext is decrypted. The key-dependent steps of the
GnuPG’s implementation of RSA is – Chinese Remainder Theorem and Multiplication (Karatsuba vs Normal).

GnuPG uses the Chinese Remainder Theorem (CRT) to perform this
exponentiation. With Chinese remaindering, the function m = cd mod N is
computed in two steps. First, evaluate m1 = c^{d1} mod
p and m2 = c^{d2} mod q (where
d1 and d2 are precomputed from d). Then, combine m1 and m2 using CRT to yield
m. This speeds up the process by a factor of four. For further optimization, RSA
also implements square and multiply and sliding window.

GnuPG uses Karatsuba multiplication when multiplying two numbers
with an equal number of words. GnuPG uses normal multiplication, which runs
in time O(nm) when multiplying two numbers with an unequal number of words of
size n and m. This step depends highly on the input.

To learn in detail about RSA implementation, watch a video lecture here.

### Obtaining the traces:

Since GnuPG represents large numbers in arrays of 32-bit
limbs, GnuPG optimizes the number of modulo reductions by always checking (at
the end of every multiplication and squaring) whether the number of limbs in
the partially computed result exceeds the number of limbs in the modulus. If
so, a modular reduction operation is performed. If not, the reduction will not
decrease the limb count, and thus is not performed. This implementation of RSA
still uses the same Karatsuba vs Normal multiplication which we exploit.

One problem with the acoustic attack is that the emanation is very low and quick for us to analyze. Hence the idea is to use "*adaptive cipher-texts*" to target the 6inner-most loops which will create a ripple big enough for us to analyze.

On running a sample RSA decryption, we find out that we can
differentiate mod p and mod q of the algorithm. Here, in the image, the arrow
points to the time difference between mod p
and mod q denoting that we can differentiate them.

### "Guessing" the key:

The attacker just needs to jot down half the bits of the key and can generate the whole private key, without ever even touching the victim machine.

## 0 Comments