I am learning to utilize flush+reload method to get private key of CRT-RSA.

CRT-RSA calculates two parts separately: mp = c^dp mod p and mq = c^dq mod q

x = b^e mod m is calculated by the code below.

[![enter image description here][1]][1]

There is a loophole in this method, that is, the execution of Square-Reduce-Multiply-Reduce in the code can be detected, and the exponent can be inferred.

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

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.

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.

For gnupg, flush+reload detects the execution of the following three lines of code.

    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())
  1. I'm confused, does the execution of the above three lines of code restore dp or dq?

  2. For Gnupg, I am able to export the private key by command gpg --output mike.secret.gpg --armor --export-secret-key [email protected], but how do I figure out what dp and dq are?

I've been trying for weeks and I still can't figure it out. Can anyone help? thank you very much!!!

  • $\begingroup$ The hint seems to be in the "detection" part. Detecting if specific code is executed according to input values can lead to side channel attacks. $\endgroup$
    – Maarten Bodewes
    Commented Nov 4, 2022 at 13:18
  • $\begingroup$ Do you know how to get dp and dq based on the RSA private key? Thanks! $\endgroup$
    – Gerrie
    Commented Nov 4, 2022 at 13:21
  • $\begingroup$ $d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$ $\endgroup$
    – user94293
    Commented Nov 4, 2022 at 14:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.