Digital Signature

Setting

Fig 1. Setting of digital signature schemes

A signer publishes a public key \( pk \). As usual, we assume that everyone has a correct copy of \( pk \).
To sign a message \( M \), the signer uses its private key to generate a signature \( \sigma \).
Anyone can verify that \( \sigma \) is a valid signature on \( M \) with respect to the signer's public key \( pk \).
Since only the signer knows the corresponding private key, we take this to mean the signer has "certified" \( M \).
A digital signature scheme is secure if no one should be able to generate a valid signature other than the legitimate signer.

Syntax

A digital signature scheme consists of three algorithms \( ({\sf SGen}, {\sf Sign} , {\sf Vrfy}) \):

The key-generation algorithm \( {\sf SGen} \) takes as input a security parameter \( n \) and outputs a pair of keys \((pk,sk) \). These are called the public key and the private key, respectively. We write this procedure as \( (pk, sk) \leftarrow {\sf SGen}(n) \).
The signing algorithm \( {\sf Sign} \) takes as input a private key \( sk \) and a message \( M \). It outputs a signature \( \sigma \), and we write this as \( \sigma \leftarrow {\sf Sign}_{sk}(M) \).
The verification algorithm \( {\sf Vrfy} \) takes as input a public key \( pk \), a message \( M \), and a signature \( \sigma \). It outputs a bit \( b \), with \( b = 1 \) meaning valid and \( b = 0 \) meaning invalid. We write this as \( b \leftarrow {\sf Vrfy}_{pk}(M, \sigma) \).

We require that for every \( n \), every \( (pk,sk) \) output by \( {\sf SGen(n)} \), and every message \( M \) in the legitimate message space, it holds that

\( {\sf Vrfy}_{pk}(M, {\sf Sign}_{sk}(M) ) = 1 \).

We say \( \sigma \) is a valid signature on a message \( M \) (with respect to some public key \( pk \) that is understood form the context) if \( {\sf Vrfy}_{pk}(M, \sigma) = 1 \).

Security

Fig 2. EU-CMA security of a digital signature scheme

Given a public key \( pk \) generated by a signer \( S \), we say an adversary outputs a forgery if it outputs a message \( M \) along with a valid signature \( \sigma \) on \( M \) such that \( M \) was not previously signed by \( S \).

As in the case of message authentication codes, security of a digital signature scheme means that an adversary cannot output a forgery even if the adversary is allowed to obtain signatures on many other messages of its choice.

Example Application: Software Patch

Consider a software company that wants to disseminate software patches in an authenticated manner: that is, when the company needs to release a software patch it should be possible for any of its clients to recognize that this patch is authentic, and a malicious third party should never be able to fool a client into accepting a patch that was not actually released by the company. To do this:

The company can generate a public key \( pk \) along with a private key \( sk \), and then distribute \( pk \) in some reliable manner to its clients while keeping \( sk \) secret. (We assume that this initial distribution of the public key is carried out correctly so that all clients have a correct copy of \( pk \). In this example, \( pk \) can be included with the original software purchased by a client.)
When releasing a software patch \( M \), the company can then compute a digital signature \( \sigma \) on \( M \) using its private key \( sk \); the pair \( (M, \sigma) \) is then sent to every client.
Each client can verify the authenticity of \( M \) by checking that \( \sigma \) is a legitimate signature on \( M \) with respect to the public key \( pk \). Note that the same public key \( pk \) is used by all clients, and so only a single signature needs to be computed by the company and sent to everyone.

Digital Signatures vs Message Authentication Codes

Both message authentication codes and digital signature schemes are used to ensure the integrity (or authenticity) of transmitted messages. Here, we compare them.

Multiple receivers: one signature vs multiple MACs: Using digital signatures rather than message authentication codes simplifies key management in the case when a sender needs to communicate with multiple receivers. In particular, by using a digital signature scheme the sender can avoid having to establish a distinct secret key with each potential receiver, and avoid having to compute a separate message authentication code with respect to each such key; instead, the sender need only compute only a single signature that can be verified by all recipients.
Public verifiability: if a receiver verifies the signature on a given message as being legitimate, then it is assured that all other parties who receive this signed message will verify it as legitimate, too.
This feature is not achieved by message authentication codes since a signer has to share a different key with each different receiver.
- A malicious sender might compute a correct MAC tag with respect to receiver Alice's shared key.
- However, the malicious sender might send an incorrect MAC tag with respect to a different user Bob's shared key.
- In this case, Alice knows that she received an authentic message from the sender but has no guarantee that other recipients will agree.
Transferability: A signature \( \sigma \) on a message \( M \) by a particular signer \( S \) can be shown to a third party, who can then verify herself that \( \sigma \) is a legitimate signature on \( M \) with respect to S's public key. By making a copy of the signature, this third party can then show the signature to another party and convince them that \( S \) authenticated \( M \), and so on. Transferability and public verifiability are essential for the application of digital signatures to certificates and public-key infrastructures.
Non-repudiation: Assuming a signer \( S \) widely publicizes his public key in the first place, once \( S \) signs a message he cannot later deny having done so. This aspect of digital signatures is crucial for situations where a recipient needs to prove to a third party (say, a judge) that a signer did indeed "certify" a particular message (e.g., a contract): assuming \( S \)'s public key is known to the judge (or is publicly available), a valid signature on a message is enough to convince the judge that \( S \) indeed signed this message.
Message authentication codes cannot provide this functionality.
- To see this, say users \( S \) and \( R \) share a MAC key \( k \), and \( S \) sends a message \( M \) to \( R \) along with a (valid) MAC tag tag computed using \( k \).
- Note that since the judge does not know \( k \), there is no way for the judge to determine whether tag is valid or not. If \( R \) were to reveal the key \( k \) to the judge, there would be no way for the judge to know whether:
  - this is the actual key that \( S \) and \( R \) shared
  - or it is some fake key manufactured by \( R \).
- Even if we assume that the judge is given the actual key \( k \), there is no way for \( R \) to prove that \( S \) generated tag rather than \( R \) himself. The very fact that message authentication codes are symmetric (so that anything \( S \) can do, \( R \) can also do) implies that there is no way for the judge to distinguish between actions of the two parties.
Speed: MAC is 1000 times faster. If you don't need above features, use MAC.

Digital Signature By Reversing Plain RSA

Many books still say that a digital signature scheme can be obtained by reversing the roles of public-key encryption/decryption algorithms. This is unfounded. As an example, recall the plain RSA encryption scheme \(({\sf Gen}, {\sf Enc}, {\sf Dec})\). From this, consider the following digital signature scheme.

\( {\sf SGen} = {\sf Gen} \).
\( {\sf Sign}_{sk}(M) = {\sf Dec}_{sk}(M) \).
\( {\sf Vrfy}_{pk}(M, \sigma) \): Check if \( M = {\sf Enc}_{pk}(\sigma) \).

In other words, the signature is \( \sigma = M^d \bmod N \), and it can be verified by checking \( \sigma^e \bmod N \stackrel{?}{=} M \). This seems rational since it holds \( (M^d)^e \bmod N = M \).

Attacks

However, the above scheme is not secure. One can easily come up with forgeries.

Forging a signature on a random message:
1. Choose a random number \( \sigma \) at random from \( \mathbb{Z}_{N}^* \)
2. Compute \( M = \sigma^e \bmod N \).
3. The forgery is \( (M, \sigma) \).
In other words, by first choosing the signature and then compute the message depending on the signature, the attacker can easily forge a valid message-signature pair. Check that the pair easily passes the verification algorithm.
Forging a signature on a combined message: Recall the security definition (existential unforgeability under the chosen message attack).
1. The adversary obtains two message-signature pairs \( (M_1, \sigma_1) \) and \( (M_2, \sigma_2) \) from the box.
2. The forgery is \( ( M, \sigma )\) with \( M = M_1 \cdot M_2 \bmod N, \sigma = \sigma_1 \cdot \sigma_2 \bmod N \).
We know the following holds:
\( \sigma_1 \equiv M_1^d \pmod N, \sigma_2 \equiv M_2^d \pmod N\). Therefore, we know
\( \sigma \equiv \sigma_1 \cdot \sigma_2 \equiv M_1^d \cdot M_2^d \equiv (M_1 \cdot M_2)^d \equiv M^d \pmod N \), which means \( \sigma \) is a valid signature on \( M \).

Fix: Hashed RSA (aka Full Domain Hash)

The fix is to first apply hash to the message, and then sign on the hash.

\( {\sf SGen} = {\sf Gen} \).
\( {\sf Sign}_{sk}(M) \).
1. Parse \( sk = (N, d) \).
2. Output \( H(M)^d \bmod N \).
\( {\sf Vrfy}_{pk}(M, \sigma) \):
1. Parse \( pk = (N, e) \).
2. Check if \( H(M) \stackrel{?}{=} \sigma^e \bmod N \). If so, output 1; otherwise 0.

Security

Now, the first attack becomes infeasible. The adversary will choose \( \sigma \) and compute \( \sigma^e \), but now it has to find \( M \) that hashes to \( \sigma^e \). From pre-image resistance, this task is computationally infeasible.
For the second attack, the adversary needs to three messages such that \( H(M) = H(M_1) \cdot H(M_2) \). From pre-image resistance, this task is computationally infeasible again.
One additional concern arises when we change the scheme. In particular, the adversary try to find another message \(M_1\) such that \[H(M_1) = H(M).\] Then, if \((M, \sigma)\) is a good message-signature pair, so is \((M_1, \sigma)\); the adverary has made a successful forgery attack! However, from collision resistance, this task is also computationally infeasible.

Hashed RSA is EU-CMA secure under the RSA assumption, if the hash is modeled as an ideal random function.

Hash and Sign Paradigm: Long Messages Can Be Signed Too

In addition to (possibly) offering some protection against certain attacks, the hashed RSA signature scheme has another advantage over textbook RSA:

Thanks to the hash function, the scheme can be used to sign arbitrary-length data, rather than just elements of \( \mathbb{Z}_N^* \).

This feature is useful in general, and the approach of hashing a message and then signing the result (using some underlying signature scheme) is a standard way to achieve it.

Other Signature Schemes

There are digital signature schemes based on hardness of discrete logarithm such as the Digital Signature Algorithm (DSA). NIST provides a standard, called Digital Signature Standard (DSS), which gives various digital signature schemes.