How to calculate the bit error rate of flush+reload on RSA

Question

I am learning to utilize flush+reload method to get private key of RSA. I read related papers flush+reload and found its open source code (flush+reloa flush+reloa). And I experimented according to the tutorial.

I am very grateful for these open source codes. But with these open source codes, I always have a very confusing question. It's just that they don't introduce what the correct result looks like (if I know the correct result, I can reproduce them faster, and better observe the impact of the paper's idea on the experiment).

For example, the experiment of Flush+Reload on RSA. The bottom image presents an optimized RSA implementation, known as CRT-RSA.

According to the introduction of the paper, as long as the Square-Reduce-Multiply in the encryption process is detected, the private key can also be restored.

The paper states:

Square-Reduce-Multiply-Reduce indicate a set bit. Sequences of Square-Reduce which are not followed by Multiply indicate a clear bit.

But according to the previous description this seems to restore dp and dq. Because the above code is calculating mp = c^dp mod p and mq = c^dq mod q.

The paper states:

Hence, knowing dp (and, symmetrically, dq) is sufficient for factoring n and breaking the encryption

By reading the paper and source code, I found that he always checks whether the following three cache lines are used when decrypting.

 probe 0x080f7607 S #mpih-mul.c:270 (First cache line in mpih_sqr_n())
    probe 0x080f6c45 r #mpih-div.c:329 (Loop in default case in mpihelp_divrem())
    probe 0x080f6fa8 M #mpih-mul.c:121 (First cache line of mul_n())

After that, the author directly gave the bit error rate. This feels suspicious. I measured the access latency of the three cache lines above during decryption. And restore them to 01 bits according to the following introduction.

Square-Reduce-Multiply-Reduce indicate a set bit. Sequences of Square-Reduce which are not followed by Multiply indicate a clear bit.

How can I calculate the bit error rate? Does this restore dp or dq? or something else? How to get the correct dp and dq for comparison?

Thanks!

Answer 1

What they leak

I don't know which example specifically you are talking about. If you clarify this (e.g., by adding a link) I may be able to edit this and provide a better answer.

When attacking RSA, it is usually assumed that N and e (the public modulus and exponent) are known.
To break RSA, we need to recover the private exponent d.
However, there are multiple ways to reconstruct d:
Since N = p * q, leaking either p or q will trivially recover p = N / q (or q = N / p respectively).
Knowing p and q, we can calculate d = e^(-1) mod phi(N) (where phi(N) = (p-1) * (q-1)).
Of course, leaking d itself will also suffice.
To break CRT-RSA, leaking either dq or dp can be used to calculate one of the primes p or q, thus recovering d.

Bit Error Rate

To get the bit error rate, you have to know the correct result, then you calculate it the following way:

number of incorrectly leaked bits / total bits of the secret

For example, if I leak the bits 10001, but the correct key is 10101, the bit error rate is:

1 / 5 = 20% 

Since one of the leaked bits is incorrect.