Defective Sign-and-Encrypt

Bob decrypts Alice's message, but uses Charlie's public key to reencrypt her signed plaintext, including the attachment, and forwards the message to Charlie with spoofed mail headers. Charlie believes Alice wrote to him directly and can't detect Bob's subterfuge. Being an honorable fellow, Charlie calls Alice's boss, and in the end, Alice gets blamed for exposing her company's secrets.

Indeed, the attack works because Charlie wrongly assumed that Alice's inner signature somehow authenticates the ciphertext envelope that Bob put on the message. It's mainly this false supposition, and not the unsigned recipient header, that misled Charlie to believe that the message was securely addressed to him. For this reason, surreptitious forwarding is a flaw only in signed-and-encrypted messaging, and doesn't really apply to signed cleartext messages: It's the presence of the encryption envelope that leads unsophisticated recipients to over-rely on the encrypting key's name.

To see that the cleartext recipient header is unimportant to Bob's attack, consider this scenario:

1. Bob's signed-and-encrypted message bears no cleartext "To" list, but is only a naked ciphertext.

2. Charlie is told verbally, by an anonymous telephone call, that the message was encrypted with his public key.

3. Charlie can then attempt the decryption, which will succeed.

4. Inside, Charlie finds a signed plaintext and (let's suppose) Alice's certificate.

5. Charlie verifies Alice's signature and finds it valid.

Then, Charlie tacitly, naturally, and incorrectly assumes that Alice encrypted the message for him to see. Charlie believes this — not because he trusts the anonymous phone call — because he's a sales executive (not a crypto expert) and blindly and uncritically trusts the cryptography.

As this example shows, simple sign-and-encrypt is, by itself, not very secure because it is vulnerable to surreptitious forwarding. Cryptographers well know this, but application programmers and standards authors still tend to put too much trust in the simple sign-and-encrypt methodology. In fact, every secure e-mail protocol — including S/MIME, PKCS#7, PGP, OpenPGP, PEM, and MOSS — has codified naive sign-and-encrypt as acceptable security practice. Likewise, the secure document protocols PKCS#7, XML-Signature, and XML-Encryption suffer from the same flaw. Although naive sign-and-encrypt techniques appear only in file- and mail-security applications, this narrow scope is becoming more important to the rapidly growing class of commercial users. With file and mail encryption enjoying widespread use, and with flawed encryption in play, you can expect widespread exposures.

At this writing, the XML-Signatures draft specification (http://www.w3.org/TR/xmldsig-core/) is nearing completion, and the allied XML-Encryption Working Group (http://www.w3.org/TR/2001/WD-xml-encryption-req-20010420) is just starting its work. Both groups have explicitly committed to producing low-level toolkit-like specifications, which will describe how to combine basic public-key operations with a rich array of XML document-structuring features. However, both groups are unwilling to stipulate any high-level security behavior, such as how to sign and encrypt messages with full security. To some extent, this is proper: These standards are intended to give low-level PKI support for as broad a class of XML applications as possible, including document preparation and handling, financial applications, wire protocols, and potentially even intricate cryptographic security protocols. But until higher level XML security specs explain how programmers should join signatures with encryption, XML programmers should be careful to avoid the naive sign-and-encrypt mistake.

Usability

Users and programmers prefer to think about security by analogy with familiar symmetric-key "secret codes." Mail-handling and file-handling security designers have relied heavily on simple, naively combined asymmetric encryption and signing. Naive sign-and-encrypt has surprisingly different security semantics from symmetric encryption, but the difference is subtle. Indeed, for senders, sign-and-encrypt guarantees the same security properties as symmetric-key cryptography gives. With both types of crypto, senders are sure that:

• The recipient knows who wrote the message.
• Only the recipient can decrypt the message.

The difference appears only in the recipient's security guarantees: The recipient of a symmetric-key ciphertext knows who sent it, but a simple sign-and-encrypt recipient knows only who wrote the message, and has no assurance about who encrypted it. This is because naive sign-and-encrypt is vulnerable to surreptitious forwarding, while symmetric-key encryption is not. Since users always assume that sign-and-encrypt is similar to symmetric-key secret codes, they tend to trust naive sign-and-encrypt too much.

Repair Options

Users in need of file and mail security require simple security semantics, and symmetric-key semantics are sufficient for most user and application needs. Furthermore, symmetric-key semantics are natural and easy for unsophisticated users to understand.

At first glance, naive sign-and-encrypt seems secure, because message-author Alice gets the security guarantees she needs — her signature proves her authorship and she knows who can read the message. However, the reader Bob doesn't get the same guarantees. He knows who wrote the message, but doesn't know who encrypted it, and therefore doesn't know who else besides Alice has read the message. Note the asymmetry:

• When A sends B a signed-and-encrypted message, A knows that only B can read it because A trusts B not to divulge the message, but...
• When B gets A's signed-and-encrypted message, B can't know how many hands it has passed through, even if B trusts A to be careful.

Seen this way, the flaw in naive sign-and-encrypt is that B gets no proof that it was A who encrypted the message. In hindsight, this is obvious — public-key algorithms usually don't automatically authenticate the encryptor of a message.

Certainly, in some applications, it's neither necessary nor feasible to give recipients any assurance that only the sender has seen the message plaintext. Thus, for example, mail-security applications need the flexibility to waive full end-to-end symmetric-key semantics. But whenever possible and by default, mail- and file-security applications should give end users easy-to-understand security guarantees.

In a nutshell, the messaging standards are flawed because they treat public-key encryption and digital signatures as if they were fully independent operations. This assumption is convenient for writing standards and software, but is cryptographically incorrect. When independent operations are applied one on top of another, the outermost crypto layer can undetectably be replaced, and security is weakened.

Martin Abadi and Catherine Meadows have offered rules-of-thumb for designing security protocols:

• Abadi: "If the identity of a principal is essential to the meaning of a message, it is prudent to mention the principal's name explicitly in the message." ("Prudent Engineering Practice for Cryptographic Protocols," Digital SRC Research Report #125, 1994.)

• Meadows: "In general, it's safer to include names explicitly inside crypto protocols' messages." ("Verification of Security Protocols," RSA Cryptographers' Colloquium, 1996.)

Five Approaches

I present here five independent and equivalently secure ways to fix the naive sign-and-encrypt problem.

The first method involves signing a recipient's name into plaintext. The easiest repair puts the decrypting recipient's name inside the signed plaintext message; see Example 2(a). This repair is straightforward for users or implementors, but hard for standards specifications to stipulate because it requires that different crypto operations must be tied together like this, without breaking the full generality of the content-transformation model. The presence of names under both crypto layers is crucial, but including both names is not strictly necessary. To use sign-and-encrypt safely, Alice needs only to enclose Bob's name, because this will link the outer crypto layer's key to the inner layer. If a naive sign-and-encrypt message arrives without proof that the signer and encryptor were the same person, then the application software should warn the recipient that the message's privacy and/or authenticity are suspect.

Even if Alice just signs and encrypts the text "Dear Bob, The deal is off. Regretfully, Alice," Alice's message is secure, albeit accidentally so.

The second way to fix the naive sign-and-encrypt problem is to encrypt the sender's name in plaintext. If Alice prefers to use the encrypt-and-sign method, then she should encrypt her own name along with her message, and sign her message plaintext outside the ciphertext, so as to block a plaintext-substitution attack, as in Example 2(b) (see "Robustness Principles for Public Key Protocols," by R. Anderson and R. Needham, Advances in Cryptology: CRYPTO '95, Springer-Verlag, 1995). Again, this links the outer layer's key pair to the inner layer, and prevents an attacker from replacing Alice's signature. Encrypting the sender's name works in a subtle way to prove that Alice performed the encryption: The enclosed name shows that the encryptor intends for the outer signature to carry the same name (Alice's). The outer signature, in turn, says that Alice did indeed touch the ciphertext. Therefore, Bob knows that Alice performed the encryption.

The third way is to incorporate both names in the message body. Alice can avoid having to pay attention to cryptographic choices early on by including both names in the message text in either of two ways, as in Example 2(c). These two-name formats might be suitable for a flexible standards specification like S/MIME, in which the layers of crypto can be applied in any order. Always enclosing both names with the message is simpler than judging on the fly which names to enclose, depending on the choice of cryptographic wrappings.

The fourth way to address the naive sign-and-encrypt problem is to sign again the signed-and-encrypted message. Surprisingly, you can get an effective repair for sign-and-encrypt if Alice signs and encrypts the plaintext, then signs the ciphertext; see Example 2(d), where #B means Alice hashes Bob's key, not his name. This message means: "Alice wrote the plaintext" (inner signature), "Only Bob can see the plaintext" (the encryption), and "Alice used key B to encrypt" (outer signature). Bob can conclude not only that Alice wrote the message, but that she also encrypted it. Seen another way, sign/encrypt/sign is a variation on including the sender's name inside the plaintext, which then is encrypted and signed; see Example 2(b). The inner signature's key links the encryption layer to the outer signature's layer. Alice signs Bob's key, so as to protect herself from the plaintext-substitution attack.

The fifth way to fix the problem is to use an encrypt/sign/encrypt approach. Conversely, Alice can get the same security guarantees by reencrypting her ciphertext's signature; see Example 2(e). This message means: "Only Bob sees the plaintext" (first encryption); "Alice wrote the plaintext and the ciphertext" (signature); "Only Bob can see that Alice wrote the plaintext and ciphertext" (second encryption). Bob cannot forward the message without invalidating Alice's signature. The outer encryption serves to prevent an attacker from replacing Alice's signature. As with sign/encrypt/sign, encrypt/sign/encrypt is a variant of including the recipient's name inside the plaintext, which is then signed and encrypted, as in Example 2(a). Alice signs her plaintext along with her ciphertext so as to protect herself from the plaintext-substitution attack. At the same time, Alice's signed plaintext gives Bob nonrepudiation.

In each aforementioned case, the signing layer and encryption layer become interdependent, binding the sender's name in one layer to the recipient's name in the other layer. Any of the five solutions establishes that Alice authored both the plaintext and the ciphertext.

Costs and Advantages

Of course, naming repairs and double-signed repairs have different trade-offs. Naming repairs bring no performance cost, but they do require new standards, and those standards would arguably be more intricate than the current standards (because interdependence of layers conflicts with arbitrary nesting of layers). Double-signed repairs are expensive in speed, but they have two virtues:

• Double signing is compatible with the existing CMS and S/MIME specifications. The only change double signing would bring is that the standard would have to require that the recipient check the innermost layer's key against the outermost layer's key.

• For some applications, double signing may be preferable to having to put names into message bodies or payloads.

Overall, it's clear that the simplest repair is to add the recipient's name, then sign-and-encrypt, as in Examples 2(a) and 2(c). The other solutions all require an extra hash of the message or of the encrypting key, so as to block the plaintext-substitution attack.

Conclusion

The weakness of naive sign-and-encrypt is subtle, but easily fixed. The repairs all show that signing and encryption should not be viewed as independent operations; the repairs presented here all rely on linking the outer operation's key to the inner operation's payload. This realization, that public-key operations are not necessarily so independent as they're commonly thought to be and that coupling two layers together is a profitable primitive, may prove to be a novel and useful axiom for beginning protocol designers and analysts.

References

A complete list of references and notes can be found at http://world.std.com/~dtd/sign_encrypt/sign_encrypt7.html.

Acknowledgments

Thanks to Martin Abadi, Ross Anderson, Marc Branchaud, Dave Carver, Dan Geer, Peter Gutmann, Philip Hallam-Baker, Paul Hoffman, Russ Housley, Steve Kent, Norbert Leser, John Linn, Ellen McDermott, Joseph Reagle, Ed Simon, Win Treese, Charlie Reitzel, Ralph Swick, and Henry Tumblin.

DDJ