0

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!

enter image description here

Gerrie
  • 736
  • 3
  • 18
  • 1
    I think the most important tag for this would be [cryptography], you might want to replace [hardware] maybe (I'm not sure you want to, so I didn't). Also this touches so lightly on software development that I think this might be more suitable for [Crypto SE](https://crypto.stackexchange.com). – Gabor Lengyel Nov 04 '22 at 10:27

1 Answers1

0

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.

Lorenz Hetterich
  • 296
  • 5
  • thank you! But I don't know if the above method detects dp or dq? And is there a command or website that can decompose the RSA private key directly into dp or dq? – Gerrie Nov 12 '22 at 13:16
  • If you know p and q (as well as the public key component e and n), you can calculate d = e^(-1) mod (p-1)*(q-1) and then dp = d mod (p - 1) (and dq respectively) – Lorenz Hetterich Nov 15 '22 at 20:58