Understanding Genkin-Pipman-Tromer's ground potential, side channel attack on RSA

Question

I'm pretty sure that by now folks might have come across this research from Genkin-Pipman-Tromer (GPT) on extracting the RSA key used by GnuPG (GPG) just by measuring the ground potential. I'm going to call it the GPT attack on GPG for short. I have done work on extracting informational content of a processor core by studying it's high frequency current draw at power supply source but this is cool because it's a low frequency analysis (i.e. easier to perform).

Their work is at http://www.tau.ac.il/~tromer/handsoff/ and I got lost at Q13, where they point to the frequency components as an indicator of when the exponentiation with the secret primes p and q happen. The spectrograph is sideways (time is vertical and frequency is horizontal) and the 12 yellow arrows show 12 RSA decryption captures where the algorithm switches from the exponentiation of p to the exponentiation of q. I get that.

But then the question (Q14) they immediately have a lovely analog wave showing the final private key bytes (basically p and q)! Here it is:

I recall that a 0 bit in the base to be exponentiated, simplifies the modular exponentiation but that still doesn't explain the jump to the final image showing the secret bits in all their glory.

Question: How did they jump from the spectrogram showing the RSA exponentiation timings straight to the secret bits? I expect that jump is highly dependent on GnuPG's RSA implementation. If you can supplement with the math (informal math ok), bonus points!

PS: Yes, I know they did similar low frequency analysis with the spectrum of acoustic signals emanating from the decrypting chassis. I also suspect this might be due to RSA being partially homomorphic ...

Answer 1

How did they jump from the spectrogram showing the RSA exponentiation timings straight to the secret bits?

Actually, they're jumping to secret bits; however those aren't the secret bits you're thinking of.

The bits displayed above are not the actual bits of $p$ and $q$. Instead, those are the bits from the secret exponent; because GnuPG uses CRT (and apparently binary exponentiation), those bits are of $d_q = d \bmod p-1$ and $d_q = d \bmod q-1$ (where $d$ is the private exponent).

With the CRT optimization of RSA, we take our message $M$, and divide it into $M_p = M \bmod p$ and $M_q = M \bmod q$. We then compute $C_p = M_p ^{d_p} \bmod p$ and $C_q = M_q ^{d_q} \bmod q$ separately, and then recompute $C_p$ and $C_q$. This attack looks at the computation of $M_p ^{d_p} \bmod p$ and $M_q ^{d_q} \bmod q$, and attempts to recover $d_p$ and $d_q$

So, what good are those bits? Well, those are as good as the actual values $p$ and $q$; with the knowledge of those values (actually, we only need one of the two), and the public key, we can factor.

The actual technique to factor using $d_p$ does use some simple number theory; I'll sketch it out for you: with your known value $d_p = d \bmod p-1$ and the public exponent $e$; because of how RSA works, we have the property that $x^{e \cdot d_p} = x \pmod p$ (for any $x$), while no such relation holds $\pmod q$. So, what you do is select a random value $r$, and compute $r^{e \cdot d_p} - r \bmod n$. This value is 0 mod p, and (with high probability) nonzero mod q; hence doing a simple gcd with that value and $n$ gives you the value $p$

I expect that jump is highly dependent on GnuPG's RSA implementation.

Yes; this sort of attack won't work with more recent implementations (such as OpenSSL), which disguise these sorts of simple side channel attacks.