Resending the Message as a Receipt

Consider an implementation of this protocol, with the additional feature of confirmation messages. Whenever Bob receives a message, he returns it as a confirmation of receipt.

(1)  Alice signs a message with her private key, encrypts it with Bob’s public key, and sends it to Bob.

E_B(S_A(M))

(2)  Bob decrypts the message with his private key and verifies the signature with Alice’s public key, thereby verifying that Alice signed the message and recovering the message.

V_A(D_B(E_B(S_A(M)))) = M

(3)  Bob signs the message with his private key, encrypts it with Alice’s public key, and sends it back to Alice.

E_A(S_B(M))

(4)  Alice decrypts the message with her private key and verifies the signature with Bob’s public key. If the resultant message is the same one she sent to Bob, she knows that Bob received the message accurately.

If the same algorithm is used for both encryption and digital-signature verification there is a possible attack [506]. In these cases, the digital signature operation is the inverse of the encryption operation: V_X = E_X and S_X = D_X.

Assume that Mallory is a legitimate system user with his own public and private key. Now, let’s watch as he reads Bob’s mail. First, he records Alice’s message to Bob in step (1). Then, at some later time, he sends that message to Bob, claiming that it came from him (Mallory). Bob thinks that it is a legitimate message from Mallory, so he decrypts the message with his private key and then tries to verify Mallory’s signature by decrypting it with Mallory’s public key. The resultant message, which is pure gibberish, is:

E_M(D_B(E_B(D_A(M)))) = E_M(D_A(M))

Even so, Bob goes on with the protocol and sends Mallory a receipt:

E_M(D_B(E_M(D_A M))))

Now, all Mallory has to do is decrypt the message with his private key, encrypt it with Bob’s public key, decrypt it again with his private key, and encrypt it with Alice’s public key. Voilà! Mallory has M.

It is not unreasonable to imagine that Bob may automatically send Mallory a receipt. This protocol may be embedded in his communications software, for example, and send receipts automatically. It is this willingness to acknowledge the receipt of gibberish that creates the insecurity. If Bob checked the message for comprehensibility before sending a receipt, he could avoid this security problem.

There are enhancements to this attack that allow Mallory to send Bob a different message from the one he eavesdropped on. Never sign arbitrary messages from other people or decrypt arbitrary messages and give the results to other people.

Foiling the Resend Attack

The attack just described works because the encrypting operation is the same as the signature-verifying operation and the decryption operation is the same as the signature operation. A secure protocol would use even a slightly different operation for encryption and digital signatures. Using different keys for each operation solves the problem, as does using different algorithms for each operation; as do timestamps, which make the incoming message and the outgoing message different; as do digital signatures with one-way hash functions (see Section 2.6).

In general, then, the following protocol is secure as the public-key algorithm used:

(1)  Alice signs a message.

(2)  Alice encrypts the message and signature with Bob’s public key (using a different encryption algorithm than for the signature) and sends it to Bob.

(3)  Bob decrypts the message with his private key.

(4)  Bob verifies Alice’s signature.

Attacks against Public-Key Cryptography

In all these public-key cryptography protocols, I glossed over how Alice gets Bob’s public key. Section 3.1 discusses this in detail, but it is worth mentioning here.

The easiest way to get someone’s public key is from a secure database somewhere. The database has to be public, so that anyone can get anyone else’s public key. The database also has to be protected from write-access by anyone except Trent; otherwise Mallory could substitute any public key for Bob’s. After he did that, Bob couldn’t read messages addressed to him, but Mallory could.

Even if the public keys are stored in a secure database, Mallory could still substitute one for another during transmission. To prevent this, Trent can sign each public key with his own private key. Trent, when used in this manner, is often known as a Key Certification Authority or Key Distribution Center (KDC). In practical implementations, the KDC signs a compound message consisting of the user’s name, his public key, and any other important information about the user. This signed compound message is stored in the KDC’s database. When Alice gets Bob’s key, she verifies the KDC’s signature to assure herself of the key’s validity.

In the final analysis, this is not making things impossible for Mallory, only more difficult. Alice still has the KDC’s public key stored somewhere. Mallory would have to substitute his own public key for that key, corrupt the database, and substitute his own keys for the valid keys (all signed with his private key as if he were the KDC), and then he’s in business. But, even paper-based signatures can be forged if Mallory goes to enough trouble. Key exchange will be discussed in minute detail in Section 3.1.

2.8 Random and Pseudo-Random-Sequence Generation

Why even bother with random-number generation in a book on cryptography? There’s already a random-number generator built into most every compiler, a mere function call away. Why not use that? Unfortunately, those random-number generators are almost definitely not secure enough for cryptography, and probably not even very random. Most of them are embarrassingly bad.