What use is the signature without the message under RSA?

Question

Using RSA for signing & verification, is there a way to take a valid signature for an unknown message, and for someone else to generate a valid signature using a different key against the valid signature, given knowledge of the original public key?

First, let me describe how I understand signing/verification with RSA:

You start with a keypair with modulous $N$ that is the product of two large primes, along with integers $e$ and $d$ such that $e d ≡ 1 \pmod {\varphi(N)}$, where $\varphi$ is the Euler phi-function. The signer's public key consists of $N$ and $e$, and the signer's secret key contains $d$.

To sign something, the signer computes $\sigma ≡ m^d \pmod {N}$. To verify, the receiver checks that $\sigma^e ≡ m \pmod N$.

( http://en.wikipedia.org/wiki/Digital_signature#How_they_work )

What are the risks to making $\sigma$ public, if $m$ is kept secret, along with the signers private key, $d$?

The public key, $N$ and $e$, is public, as is $\sigma$, the signature.

$\sigma^e$ is easily calculatable, which gets us $m \pmod N$, but not $m$ itself.

Given $m \pmod N$ but an unknown $m$, what can we do with it?

Can a second signer, with public key $N^{\prime}$ and $e^{\prime}$, and private key $d^{\prime}$ be used to generate $\sigma^{\prime} = m^{d^{\prime}} \pmod {N^{\prime}}$?

How resistant to brute forcing is that? How about if some sort of verification oracle is available?

Since $m \pmod N$ is lossy, without $m$ (or more likely $\text{pad}(\text{hash}(m))$ in practice), is anything about $m$ recoverable?

Is there another system for signing whose signatures are of less use without the message?

Answer 1

Caution: the question assumes that the message $m$ can be larger than the public modulus $N$ and sent separately from the signature (perhaps, encrypted), contrary to textbook RSA as in the original article. The answer makes that assumption unless otherwise specified.

---

If we signed a secret message $m$ by publishing its signature $σ$ computed as $m^d\bmod N$, at least two very bad things would happen:

1. The message would not be so secret anymore
   That's because anyone knows the public key $(N,e)$, and thus from $σ$ can compute $σ^e\bmod N$, which is $m\bmod N$. This reveals a lot of information about $m$, which goes straight against the requirement to keep $m$ secret. In modern cryptography, the adversary succeeds if she learns anything about a secret message (except its length), and $m\bmod N$ qualifies. For example:

• $m\bmod N$ allows (with overwhelming odds) to recognize $m$ among a moderate list of arbitrary messages.
• If $m$ is shorter than $N$ then $m\bmod N$ is $m$ and thus $m$ is no longer secret at all (this occurs when $m$ is less than $256$ bytes for $2048$-bit $N$, a common size).
• If (as in the question) it is computed and published the signature $σ'$ of the same $m$ according to a different RSA key $(N',e')$, then this reveals $m\bmod N'$. By the Chineese Remainder Theorem we can efficiently compute $m\bmod(N\;N')$, and this reveals $m$ if it's size is less than the sum of the size of $N$ and $N'$, extending the above to longer messages than was possible with a single signature.
• If $m$ is known except for a segment shorter than $N$ (that is $m=m_0\mathbin\|m_1\mathbin\|m_2$ with $m_0$ and $m_2$ known, and $m_1$ shorter than $N$), from $m\bmod N$ it is easy to find $m_1$, thus $m$, as follows: if $|m_i|$ is the number of bits in each segment of $m$, we have $m\bmod N=\big((m_0 2^{|m_1|}+m_1)2^{|m_2|}+m_2\big)\bmod N$ thus $m_1=\big((m\bmod N)-m_0 2^{|m_1|+|m_2|}-m_2\big)2^{-|m_1|}\bmod N$ where $2^{-|m_1|}$ is the multiplicative inverse of $2^{|m_1|}$ modulo $N$, which is easily computed using the Extended Euclidian algorithm.

2. It would be easy to make forgeries
   In particular, it would be possible to forge a large class of messages, including C strings showing as anything desired. For any $m_0$, $N$ and $e$, it is easy to exhibit $m_1$ such that $m=m_0\mathbin\|m_1$ verifies $\sigma^e \equiv m \pmod N$. Just choose $m_0$ ending with a terminating 0x00 bytes, decide a size $b$ of $m_1$ with $b$ multiple of 8 and $2^b>N$, pick any $\sigma$, compute $m\gets m_0\,2^b+((\sigma^e-m_0\,2^b)\bmod N)$ ).

Note: in common textbook RSA, $m$ is not sent separately and is recovered as $m\gets\sigma^e\bmod N$, hence $0\le m<N$. This makes the attack more difficult. However for small $e$, and when $|m_0|$ is small enough (roughly up to $\log_2(N/e)/e$ bit including terminating 0x00), we find $b\gets8\,\lfloor \log_2(N/(m_0+1))/8\rfloor$, compute $σ\gets\left\lceil\sqrt[e]{m_0\,2^b}\right\rceil$ and $m\gets σ^e$. This $σ$ verifies as the signature for this $m$, and prints the same as $m_0$.

---

Rather, good and common practice in order to RSA-sign a confidential message is to:

1. Encrypt and sign (or sign and encrypt)
   Encipher the message (typically using a symmetric algorithm such as AES in CTR mode with random IV), then RSA-sign the cryptogram (ciphertext, rather than the plaintext), e.g. as in 2 below; or transform the message into a signed message (again e.g. as in 2 below), then encipher that whole signed message.
   Note: if possible, use encrypt-then-sign. If for some reason sign-then-encrypt must be used, make sure to encrypt the signature even if it is randomized; pay care that deciphering of any invalid ciphertext can not trigger undesirable behavior on the receiver side; and pay care that signature verification of partially invalid messages does not leak information about the message.

2. (and) Use a signature scheme with hash-based padding
   In order to RSA-sign a message $m$ (confidential or not), signature must NOT be computed as $σ=m^d\bmod N$, which would be an unsafe use of textbook RSA. Rather, one might (there are other secure ways)

   1. compute $h=H(m)$ for some hash function $H$ like SHA-256, with $h$ what will actually be signed (albeit still not using textbook RSA, as it could be vulnerable to forgery if the adversary could obtain the signature of chosen messages)
   2. appropriately pad $h$ into a so-called message-representative $r$ with $0<r<N$ by some method (possibly involving adding randomness), the most common such methods being RSASSA-PSS and RSASSA-PKCS1-v1_5 in PKCS#1;
   3. compute the signature as $σ=r^d\bmod N$
   4. build the signed message as $m\|σ$ (that is, append the signature); the verifier will extract $m$ and $σ$ from $m\|σ$, compute $h=H(m)$, compute $r=σ^e\bmod N$, and check $r$ against $h$ according to the padding method.