62
$\begingroup$

The diagram below illustrates the process of digitally signing a message with RSA:

Image

As diagram shows, the message is first hashed, and the signature is then computed on the hash, rather than on the full message.

Why hash the data before signing it? Why not sign the whole message? Of course, it'll save time if you sign just the hash value, but I've heard there are also security issues with directly signing the full message. If so, what are they?

$\endgroup$
1

4 Answers 4

41
$\begingroup$

In addition to the performance problems poncho already mentioned when using RSA signatures without hashing I just want to add on the security warning of poncho:

Reordering

If you have a message $m>N$ with $N$ being the RSA modulus, then you have to perform at least 2 RSA signatures as $m$ does not longer fit into $Z_N$. Let us assume that it requires $k$ such signatures and write the message $m=(m_1,\ldots,m_k)$ and the overall signature will be $\sigma=(\sigma_1,\ldots,\sigma_k)$, i.e., $k$ RSA signatures. Now without any additional measures, anyone getting to hold $(m,\sigma)$ can manipulate the message and adopt the signature by 1) swapping any pair of sub-message $m_i$, $1\leq i\leq k$ and corresponding sub-signature $\sigma_i$ or 2) dropping a sub-message and corresponding sub-signature.

As an example for swapping lets say we have $m=(m_1,m_2,m_3)$ and thus $\sigma=(\sigma_1,\sigma_2,\sigma_3)$, i.e., 3 indepenendet RSA signatures for a message consisting of 3 blocks, then an adversary who gets $(m,\sigma)$ can simply swap, for instance to $m'=(m_2,m_3,m_1)$ and $\sigma'=(\sigma_2,\sigma_3,\sigma_1)$, which is a forgery, as it clearly is a valid signature.

Existential forgery

If you do not use a redundancy scheme for messages prior to signing within RSA (textbook RSA signatures), they are susceptible to existential forgeries. Let $(e,N)$ be the public signature verification key of RSA, then one can randomly choose a signature $\sigma \in Z_N$ and compute the corresponding message as $m\equiv \sigma^e \pmod N$.

Note that given an RSA signature $\sigma$, a message $m$ and a public verification key $(e,N)$, the signature verification for the textbook RSA signature will be to check: $m\stackrel{?}{\equiv} \sigma^e \pmod N$.

Clearly, this check will hold for the forgery by construction. Observe, however, that the adversary can not control what the message $m$ will exactly be. In particular, it will be a random element of $Z_N$. However, this may be sufficient in some applications, e.g., when only signing random numbers when issuing some tokens. Applying a redundancy scheme to messages, i.e., hashing and padding prior to signing renders so computed forged signatures useless in practice.

Final Remarks

Consequently, textbook RSA signatures must not be used and instead standardized padding methods for RSA involving hashing and padding the message must be used. Then, RSA signatures provide strong security guarantees (UF-CMA security).

$\endgroup$
1
  • $\begingroup$ Also the purpose of signature is authenticity rather than confidentiality so encrypting a hash of whole message is sufficient. $\endgroup$ Commented Jul 19, 2021 at 15:49
24
$\begingroup$

Well, one reason to hash the data before signing it is because RSA can handle only so much data; we might want to sign messages longer than that.

For example, suppose we are using a 2k RSA key; that means that the RSA operation can handle messages up to 2047 bits; or 255 bytes. We often want to sign messages longer than 255 bytes. By hashing the message to something small, and then signing the hash, we get around the problem of message length. Now, we could also solve this problem by breaking up the message to smaller chunks, and signing each chunk; however this adds a great deal of complexity and expense for no particularly good reason.

I would like to add a warning not directly related to your question: that image you showed is simplified, and is missing an important piece of the RSA signature process. After you perform the hash, it is essential that you pad the hash out before you give it to what they have labeled the 'encrypt hash with the signer's private key' step. Conversely, after the signature verifier has used the signer's public key, they need to verify that the padding in the 'decrypted' message looks valid (in addition to the hash being the expected value). There are known weaknesses that result by not performing the padding correctly.

$\endgroup$
1
  • 4
    $\begingroup$ Addition: If one hashes then apply the naked RSA signature function $x\mapsto x^d\bmod N$ without padding, one stands vulnerable to multiplicative forgeries in a chosen-message setup using an attack devised by Desmedt and Odlyzko, combining signature of messages which hashes are smooth into the signature of another such message. Even with proper padding on the signing side, implementations of signature verification have been vulnerable to incorrect verification of the padding; here's an example. $\endgroup$
    – fgrieu
    Commented Jan 8, 2014 at 8:16
0
$\begingroup$

I am answering this in the context of Digital Signatures. Digital Signatures offer - Authenticity (that the message was sent by the person whom the message claims to be sent by) and Data Integrity (that the message was not altered in transit).

Suppose, you encrypt the entire message using private key and send it out. Now, any body will be able to decrypt using the public key but won't be able to encrypt again (since private key is held by sender only). Instead say, the encrypted message itself is altered in transit. A receiver will proceed to decrypt using public key and will probably get an entirely different message. Now the intended audience will know who sent this message in the first place but cannot tell if the message was altered. So Data Integrity is clearly lost.

Instead you generate a hash (using a publicly known algorithm) and then encrypt this hash using private key and send the data + encrypted hash to intended audience. Now, in transit, someone may modify the encrypted hash or the message. In either case, validation on receiver side (decrypt hash using public key, generate hash from actual data (that was sent in clear text) and comparing decrypted hash with generated hash) will fail if the message was edited. Thus we retain data integrity and authenticity.

$\endgroup$
2
  • $\begingroup$ I find it hard to understand this answer and the down votes, it would be great if someone can explain it to me what KM Raghava meant and why the down votes $\endgroup$
    – Ulkoma
    Commented Mar 26, 2016 at 18:43
  • 2
    $\begingroup$ He mixed signing and encryption. When signing you already have the message that was signed, hence data integrity is irrelevant in the context that he put it in. It is relevant for encryption, though when encrypting you do not hash of course.. $\endgroup$
    – SatA
    Commented Oct 16, 2017 at 8:46
0
$\begingroup$

It is not secure if not hashed.

Recap that the main security requirement of signature is to be resistant to "forgery". That is, with public key, attacker is unable to produce a new pair of valid message and signature (m,s), even if the attacker has seen many other valid pairs.

Here is the attack if hash is not being applied.

  1. Attacker randomly chooses a sequence and call it s.
  2. Attacker uses the public key to decrypt s and obtain m.
  3. Attacker output (m,s).

Note that (m,s) is a valid pair. In other words, the attackers succeeds in forgery.

$\endgroup$
1
  • $\begingroup$ Actually, this explains why you need padding with RSA, not hashing... $\endgroup$
    – poncho
    Commented Apr 19 at 14:07

Your Answer

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

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