Fault attack on RSA-CRT

Question

I am trying to understand fault attack on RSA-CRT, and I found some example, which I don't know how to solve it.

I know public modulus $N$, public exponent $e$, a value of faulty signature (where one of the two partial signatures was incorrect) and the value of correct signature. The message $m$ is signed by RSASSA-PKCS1-v1_5 (signature transformation is RSASP1).

I have already read the documentation of RSASSA and RSASP1, and I have also read some articles about how to attack this problem. However, I don't understand how to get a message which I need for calculating $p$, because I should get $p = \operatorname{gcd}(\text{faultySignature}^{exponent} - m, N)$

Could someone help me?

Answer 1

In order to have a successful fault attack on RSA-CRT, you need to work with known values of $e, N$ and of the message $m$, but you should be knowing them already, since you cannot verify the signature without knowing these values.

So, at first you should be knowing the public key of the signer: $(e,N)$. Then the signer signs a message $m$, which you should know in order to verify it. But if the signer instead issues a faulty signature, you can try and recover its private key as you said using the following method.

You can first recover the value $p$ as you mentioned using $$p = \operatorname{gcd}(\text{faultySignature}^{e} - m, N)$$ once this is done, you can get the second prime $q$ by dividing $N$ by $p$: $$q=\frac{N}{p}$$ and you can finally compute the value $d$ by computing $\phi(N)=(p-1)(q-1)$ (assuming we are working with a 2 prime factors RSA modulus) and by finally computing $$d=e^{-1}\mod{\phi(N)}$$

Now, when using RSASSA-PKCS1-v1_5, what you are signing is not directly the message, to avoid the malleability issues and such, but instead the padded hash thereof. You can see the exact process of deriving the signed hash from the message in RFC3447 section 8.2.1 and following. But basically, what you need to do is to:

1. Convert the message M into its encoded form of length k octets EM = EMSA-PKCS1-V1_5-ENCODE (M, k).

2. Convert the encoded message EM to an integer which can be used with RSA: m = OS2IP (EM)

3. Use this integer value m as being your value $m$ in your computations.

Answer 2

A little late, but for anyone else interested:
There is an even easier way to recover $p$ if you know both a correct signature $S$ and a faulty signature $\hat{S}$. Assume - without loss of generality - that an error occured during calculation of $ S_q $, with $$ S_q = m_q^{d_q} \operatorname{mod} q $$ and $$ m_q = m \operatorname{mod} q~~;~~d_q = d \operatorname{mod} q-1$$

The signature is calculated as follows: $$ S = S_p \cdot (q^{-1} \operatorname{mod} p) \cdot q + S_q \cdot (p^{-1} \operatorname{mod} q) \cdot p $$ which leads to the following equation for the faulty signature: $$ \hat{S} = S_p \cdot (q^{-1} \operatorname{mod} p) \cdot q + \hat{S_q} \cdot (p^{-1} \operatorname{mod} q) \cdot p $$ Let's take a look at the difference of both signatures: $$ S - \hat{S} = (S_q - \hat{S_q}) \cdot (p^{-1} \operatorname{mod} q) \cdot p $$ Now we know that $p |(S - \hat{S})$ which implies that $ p = \operatorname{gcd}(N,(S - \hat{S})) $

Everything else works the same way as @Lery already explained. Both ways are stated in the original paper by Boneh, DeMillo and Lipton which is worth a read and can be found here.