The necessity of authentication in public-key systems
It would appear that public-key cryptography is an ideal system, not requiring a secure channel to pass the encryption key. This would imply that two entities could communicate over an unsecured channel without ever having met to exchange keys. Unfortunately, this is not the case. Figure 1.13 illustrates how an active adversary can defeat the system (decrypt messages intended for a second entity) without breaking the encryption system. This is a type of impersonation and is an example of protocol failure (see §1.10). In this scenario the adversary' impersonates entity В by sending entity A a public key e' which A assumes (incorrectly) to be the public key of B. The adversary intercepts encrypted messages from A to B, decrypts with its own private key cl', re-encrypts the message under B’s public key e, and sends it on to B. This highlights the necessity to authenticate public keys to achieve data origin authentication of the public keys themselves. A must be convinced that she is encrypting under the legitimate public key of B. Fortunately, public-key techniques also allow an elegant solution to this problem (see §1.11).
Figure 1.13: An impersonation attack on a rwo-party communication.
Digital signatures from reversible public-key encryption
This section considers a class of digital signature schemes which is based on public-key encryption systems of a particular type.
Suppose Ee is a public-key encryption transformation with message space M and ciphertext space C. Suppose further that M = C. If Dd is the decryption transformation corresponding to E, then since Ee and Dd are both permutations, one has
A public-key encryption scheme of this type is called reversible,u Note that it is essential that M = C for this to be a valid equality for all m e M; otherwise, Dd(m) will be meaningless for m £ C.
''There is a broader class of digital signatures which can be informally described as ansmg from irreversible cryptographic algorithms. These are described in §11.2.
Construction for a digital signature scheme
- 1. Let M be the message space for the signature scheme.
- 2. Let C = Л4 be the signature space S.
- 3. Let (e, d) be a key pair for the public-key encryption scheme.
- 4. Define the signing function 5'д to be Д/. That is, the signature for a message m e M
is s = Dd(m).
5. Define the verification function VA by
The signature scheme can be simplified further if A only signs messages having a special structure, and this structure is publicly known. Let M' be a subset of M where elements of M' have a well-defined special structure, such that M! contains only a negligible fraction of messages from the set. For example, suppose that M consists of all binary strings of length 21 for some positive integer t. Let M' be the subset of M consisting of all strings where the first t bits are replicated in the last t positions (e.g., 101101 would be in M' for t = 3). If A only signs messages within the subset M', these are easily recognized by a verifier.
Redefine the verification function VA as
Under this new scenario A only needs to transmit the signature s since the message m = E,. (s) can be recovered by applying the verification function. Such a scheme is called a digital signature scheme with message recovery’. Figure 1.14 illustrates how this signature function is used. The feature of selecting messages of special structure is referred to as selecting messages with redundancy.
Figure 1.14: A digital signature scheme with message recovery.
The modification presented above is more than a simplification; it is absolutely crucial if one hopes to meet the requirement of property (b) of signing and verification functions (see page 23). To see why this is the case, note that any entity В can select a random element s 6 S as a signature and apply Ee to get и = Ee(s), since S = M and Ee is public knowledge. В may then take the message m = и and the signature on m to be .s and transmits (m, s). It is easy to check that s will verify as a signature created by A for m but in which A has had no pari. In this case В has forged a signature of A. This is an example of what is called existential forgery. (B has produced A’s signature on some message likely not of J5’s choosing.)
If M' contains only a negligible fraction of messages from M, then the probability of some entity forging a signature of A in this manner is negligibly small.
1.52 Remark (digital signatures vs. confidentiality) Although digital signature schemes based on reversible public-key encryption are attractive, they require an encryption method as a primitive. There are situations where a digital signature mechanism is required but encryption is forbidden. In such cases these digital signature schemes are inappropriate.
Digital signatures in practice
For digital signatures to be useful in practice, concrete realizations of the preceding concepts should have certain additional properties. A digital signature must
- 1. be easy to compute by the signer (the signing function should be easy to apply);
- 2. be easy to verify by anyone (the verification function should be easy to apply); and
- 3. have an appropriate lifespan, i.e., be computationally secure from forgery until the signature is no longer necessary for its original purpose.
Resolution of disputes
The purpose of a digital signature (or any signature method) is to permit the resolution of disputes. For example, an entity A could at some point deny having signed a message or some other entity В could falsely claim that a signature on a message was produced by A. In order to overcome such problems a trusted third partу (TTP) or judge is required. The TTP must be some entity which all parties involved agree upon in advance.
If A denies that a message m held by В was signed by A, then В should be able to present the signature sa for m to the TTP along with m. The TTP rales in favor of В if VA (m, sa) = true and in favor of A otherwise. В will accept the decision if В is confident that the TTP has the same verifying transformation VA as A does. A will accept the decision if A is confident that the TTP used VA and that SA has not been compromised. Therefore, fair resolution of disputes requires that the following criteria are met.
Requirements for resolution of disputed signatures
- 1. SA and VA have properties (a) and (b) of page 23.
- 2. The TTP has an authentic copy of VA.
- 3. The signing transformation SA has been kept secret and remains secure.
These properties are necessary but in practice it might not be possible to guarantee them. For example, the assumption that SA and VA have the desired characteristics given in property 1 might turn out to be false for a particular signature scheme. Another possibility is that A claims falsely that SA was compromised. To overcome these problems requires an agreed method to validate the time period for which A will accept responsibility for the verification transformation. An analogue of this situation can be made with credit card revocation. The holder of a card is responsible until the holder notifies the card issuing company that the card has been lost or stolen. §13.8.2 gives a more indepth discussion of these problems and possible solutions.