11
$\begingroup$

Given enough RSA signature values, is it possible to determine which public key is required to verify the values?

Could there be enough information to establish which key is required? Is there anything in the RSA scheme to retrieve the modulus, assuming the public exponent can be guessed?

Only padded RSA for signature generation with PKCS#1 v1.5 padding or PSS padding may be considered, not raw/textbook RSA.


This question is related to this one asking about the same question for RSA encryption.

$\endgroup$
  • $\begingroup$ Is deterministic padding allowed? Do you know the (unpadded) plaintexts corresponding to the signatures? $\endgroup$ – SEJPM Mar 12 '16 at 15:48
  • $\begingroup$ Yes, PKCS#1 v1.5 padding is deterministic. As for the plaintext, yes, that could be considered (just back after a WHEA_UNRECOVERABLE_ERROR, sorry about the delay). $\endgroup$ – Maarten Bodewes Mar 12 '16 at 16:02
  • $\begingroup$ I had a friend who kept signing his emails and then asking me to import his public key therefrom. Nevertheless it isn't (I believe) necessary to have the public key in order to verify a signature; I thought it was possible to, given one signature, be able to verify that all subsequent signed communication is signed with the same signature. Considering that signatures involve the use of checksums, by computing the checksum for the communication yourself I can envisage how it would be possible to do this. $\endgroup$ – Micheal Johnson Mar 12 '16 at 21:03
  • $\begingroup$ @MichealJohnson Be aware that PGP and CMS are container formats that include more information than just a raw signature. It may include the signing certificate for example. As long as you can verify that the message is indeed from your friend the request may not be that outlandish. $\endgroup$ – Maarten Bodewes Mar 12 '16 at 21:06
  • $\begingroup$ I'm pretty sure it does include the certificate, for that matter. Thought that was used as part of the "plaintext" of the RSA signature in addition to the checksum. $\endgroup$ – Micheal Johnson Mar 12 '16 at 21:08
8
$\begingroup$

First, assuming any padding, the answer given by fgrieu to your related question still holds. You can associate public keys with signatures by looking at which signatures are consistenly (minimally) smaller than the modulus.


The second method, as suggested by poncho in the comments of your related question and the comments of this post cleverly uses small prime factoring to find $N$. I put this here, so it doesn't look "tagged-on" at the end of the post. The idea is the same as in the third method below, but with a clever twist. Where I collect enough samples to get a decent probability that there's on coprime pair of $t_i$ values, he suggested to take much less pairs and calculate the GCD of all $t_i$. This is $\gcd(t_1,...,t_k)=\gcd(r_1N,...,r_kN)=N*\gcd(r_1,...,r_k)$, where $\gcd(r_1,...,r_k)$ is likely to be a factor which is small enough ($<2^{128}$) to be factored out by methods which can find small primes efficiently, like ECM, yielding the desired $N$, as the largest factor.


The third method is a bit more specialized. It's basically a re-statement of my previous answer to a similar question and goes into a little more detail than poncho's answer to your related question, while standing on similar feet.

Assumptions

It needs to be assumed that you have a set of message-signature pairs, it needs to be assumed that the padding is deterministic (i.e. something like PKCS#1 v1.5) and that the public exponent is known or can be brute-forced easily.

Method

Assume you're given the public RSA exponent $e$, the set of message-signature pairs $\mathcal S = \{(m_1,\sigma_1),...,(m_k,\sigma_k)\}$ with $|\mathcal S|=k$ and the padding function $\operatorname{Pad}(m)$. Note that knowledge of the padding function implies knowledge or a good estimate of the size of the modulus.

The first step is to reduce this problem from one with a complex padding scheme to one of simple raw RSA signatures. For this, we apply $\operatorname{Pad}(m)$ to each message $m_i$ in $\mathcal S$ and and replace the unpadded $m_i$ with the padded $m_i'$ for the set $\mathcal S'$.

Now observe, that as per the normal verification process, $(m_i')^e \equiv \sigma_i \pmod N \forall 0<i\leq k$. This can be rewritten as $(m_i')^e = \sigma_i + r_i * N$. As we know $m_i', e, \sigma_i$, we can calculate $t_i=(m_i')^e-\sigma_i=r_i * N$. Now we observe that all $t_i$ share one common factor: $N$, which we can recover (with a given probability) by calculating the pair-wise greatest common divisor of all $t_i$. The smallest result is likely our $N$. The fancy writing for this would be: $N=\gcd(t_1,...,t_k)$. Once we have a guess for $N$, we can confirm it by checking if all signatures are valid, i.e. if all equations $(m_i')^e\equiv \sigma_i\pmod N$ hold.

Success Probability

The first thing to observe or assume is that the values of $r_i$ are random non-zero integers. Due to their large size (beyond $2^{100,000,000}$), we will model them as randomly distributed numbers. Next, we observe that we found the modulus, if $\gcd(r_1,...,r_k)=1$ holds, i.e. if the set is co-prime. As we modeled the integers randomly, we can use the standard approximation for the probability that $k$ random integers are co-prime which is $1/\zeta(k)$ where $\zeta(x)$ is the riemann zeta function. So the probability that our guess $N'$ for $N$ is correct, is equal to the probability that all $r_i$ are co-prime and thereby:

$$\Pr[N'=N]=1/\zeta(k)$$

This formula can be used to retrieve the number of pairs neccessary to get a good probability for finding the correct $N$. The probability is at $99.99%$ with $k\geq 14$.

$\endgroup$
  • $\begingroup$ The same comments as in the original answer still apply. $\endgroup$ – SEJPM Mar 12 '16 at 16:42
  • 3
    $\begingroup$ Actually, we don't necessarily require that all the pairs be coprime; if we derive the value $kN$, where (say) $k < 2^{128}$, it's easy enough to factor out $k$ (ECM works quite well here), and recover $N$. I believe that the probability that $k < 2^{128}$ is quite good even with only 2 signatures. $\endgroup$ – poncho Mar 12 '16 at 17:36
  • $\begingroup$ Instead of computing the min of the pairwise gcd's, it's better to compute $\gcd(t_1,t_2,\dots,t_k)$. You'll get a significant improved success probability. $\endgroup$ – D.W. Mar 12 '16 at 19:06
  • $\begingroup$ @D.W., the success probability of $\gcd(t_1,...,t_k)$ actually is $1/\zeta(k)$ which approaches $1$ slower than $1-(1-6/\pi^2)^{k/2(k-1)}$ if I want to believe my GeoGebra plot. $\endgroup$ – SEJPM Mar 12 '16 at 20:09
  • 2
    $\begingroup$ I don't believe it. There's something wrong with your math if it suggests that $\min_{i,j} \gcd(t_i,t_j)$ is better than $\gcd(t_1,\dots,t_k)$. It's easy to prove that $\gcd(t_1,\dots,t_k) \mid \min_{i,j} \gcd(t_i,t_j)$, so if pairwise min works, then $\gcd(t_1,\dots,t_k)$ definitely works -- and one can also find cases where $\gcd(t_1,\dots,t_k)$ works but pairwise min doesn't. In other words, $\gcd(t_1,\dots,t_k)$ is strictly better. Double-check the math? $\endgroup$ – D.W. Mar 12 '16 at 20:11
2
$\begingroup$

Note: This is a late answer, and uses the same principle as methods 2 and 3 in that other answer. The only difference is use of just two (message, signature) pairs, and demo code in Java within the answer's text to illustrate that this is enough for practical parameters.


With only one (message, signature) pair $(m,\sigma)$, it is not known how to recover the public key $(N,e)$. However, that can be done in practice with just two distinct pairs $(m_1,\sigma_1)$ and $(m_2,\sigma_2)$, assuming a known deterministic RSA signature padding scheme with appendix, including textbook RSA, hash-then-textbook-RSA, RSASSA-PKCS1-V1_5 (which is believed safe), and a few others (but not standard RSASSA-PSS, because the random padding gets in the way).

In a deterministic RSA signature padding scheme, the signature of message $m$ is computed by transforming it into a padded message representative $\text{Pad}(m)$, then computing the signature $\sigma={(\text{Pad}(m))}^d\bmod N$. The verification of alleged $m'$ against $\sigma$ computes $\text{Pad}(m')$ and checks $\sigma^e\bmod N=\text{Pad}(m')$. Textbook RSA has $\text{Pad}(m)=m$, secure padding scheme typically involve hashing.


The attack needs to guess $e$, but that's typically a small integer, often $e=F_i=2^{(2^i)}+1$ with $0\le i\le4$, or $e=37$, with $e=F_4=65537$ common in practice. We need to pad the two messages $m_i$ into their message representatives per the padding algorithm used by the signature scheme, giving $\text{Pad}(m_i)$ (for RSASSA-PKCS1-V1_5, we need the size of $N$ in octets, which is the same as that of the $\sigma_i$ if expressed as fixed-size octet strings, or typically given by the highest $\sigma_i$ otherwise).

We are now trying to solve a system of two equations $\sigma_i^e\bmod N=\text{Pad}(m_i)$ with only unknown $N$. In each, if we got $e$ right, $N$ is a divisor of $\sigma_i^e-\text{Pad}(m_i)$. It follows that $N$ divides the quantity $x$, that we can compute $$x=\gcd(\sigma_1^e-\text{Pad}(m_1),\sigma_2^e-\text{Pad}(m_2))$$

$N$ is $x$ with probability about $\frac6{\pi^2}\approx0.61$, by the argument on probability of coprimality of large random integers.

And in most of the remaining cases, pulling out a few small factors from $x$ by trial division of small primes will reveal $N$. It seems that for $k$ much less wide than $N$, we'd have to pull a factor larger than $k$ with probability about $$1-\frac6{\pi^2\displaystyle\prod_{\mathrm{primes}\ p\le k}\left(1-\frac1{p^2}\right)}$$ and that probability is only $\approx2^{-13.0}$ (resp. $\approx2^{-23.9}$) if we test divisibility by the 172 (resp. 82025) primes at most 10-bit (resp. 20-bit). Even better options pull the small factors using Pollard's rho or ECM (as in GMP-ECM).

For practical parameters, this almost always works. The only implementation difficulty stems from the size of $\sigma^e$, especially for $e=F_4=65537$ (Java's BigInteger gets impractically slow; GMP shines). Much larger $e$ would make the attack difficult.

If we make a wrong guess of $e$, the method fails (typically yielding a much too small $x$), we can detect that and try another $e$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.