Pp. 65–78 of the Proceedings

Defective Sign & Encrypt in S/MIME,
PKCS#7, MOSS, PEM, PGP, and XML

Don Davis¹

Abstract

In this paper, we analyze the naïve Sign & Encrypt flaw,we review the defective sign/encrypt standards,and we describe a comprehensive set of simple repairs.The various repairs all have a common feature:when signing and encryption are combined,the inner crypto layer must somehow depend on the outer layer,so as to reveal any tampering with the outer layer.

1  Introduction

Users and programmers prefer to think about securityby analogy with familiar symmetric-key ``secret codes.''For mail-handling and file-handling,security designers have relied heavily on simpleasymmetric encryption and signing,rather naïvely combined.Naïve sign & encrypt has surprisingly differentsecurity semantics from symmetric encryption,but the difference is subtle, perhaps too subtlefor non-specialist users and programmers to grasp.Indeed, for senders, sign-and-encrypt guarantees thesame security properties as symmetric-key cryptography gives.With both types of crypto, the sender is sure that:

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

The difference appears only in the recipient'ssecurity guarantees: the recipient of a symmetric-keyciphertext knows who sent it to him,but a ``simple sign & encrypt'' recipient knows onlywho wrote the message, and has no assurance aboutwho encrypted it.This is because naïve sign & encryptis vulnerable to ``surreptitious forwarding,''but symmetric-key encryption is not.Since users always will assume that sign & encryptis similar to symmetric-key ``secret codes,''they will tend to trust naïve sign & encrypt too much.

The standards that exist for simple file-encryption,chiefly PKCS#7 [23] and S/MIME [20],tend to allow secure Sign & Encrypt implementations(i.e., such as would prevent surreptitious forwarding),but surprisingly, these file-security standardsdon't require fully-secure implementation and operation.Similarly, some important new security standards,such as the XML ²security specifications [6,26],offer only low-level ``toolbox'' APIs.Too often, both the established standards and the new onesallow insecure yet compliant implementations.Application programmers need more security guidancethan these ``toolbox'' APIs offer,in order to build effective security into their applications.Without such guidance, programmers tend to supposeincorrectly that simply signing and then encrypting a messageor a file will give good security.

The limitations of naïve sign & encrypt probably werewell-known to the designers of all of the standards we discusshere (see § 4.6).The standards authors assumed, sometimes explicitly and sometimesimplicitly, that applications programmers and end-users wouldunderstand that naïve sign & encrypt is not a completesecurity solution.Application programmers were expected to knowhow to bolster each standard's sign & encrypt feature withother protocol elements.At the same time, end-users were expected to make carefulsecurity judgments about any application they might use,so as to use the application's security features correctly,and so as not to over-rely on a product that offers onlylimited security.The standards authors' expectations may have been realisticten years ago, before Everyman and the Acme Boot-Button Co.began using the Internet.It seems unfair to fault the standards designers forinsufficient prescience,but now, these expectations are hopelessly outdated,and those standards cannot serve end-users well.

1.1  Surreptitious Forwarding

Further, when Alice signs a message to Bob,Alice may be willing to let Charlie see that message,but not to sign the same message for Charlie:

1.2  Don't Sign Ciphertexts

Interestingly, naïve Encrypt-then-Sign isn't any betterthan Sign & Encrypt.In this case, it's easy for any eavesdropper to replacethe sender's signature with his own,so as to claim authorship for the encrypted plaintext:

Another problem with Encrypt-then-Sign arises, whenAlice uses RSA or El Gamal encryption.In a sequel to Abadi's ``Robustness Principles'' paper [1],Anderson showed that Encrypt&Sign is dramatically weakerthan had been thought [2].Suppose Alice uses RSA keys to send Bob an E&S message:

Anderson's attack has two minor limitations:

• Each modulus factor must be short enough (~120 digits, or ~400 bits)to allow a discrete-log calculation [13];
• Bob's new public exponent xB will be obviously unusual,in that it will be a full-length bitstring, instead of theusual small integer value.

So, it might seem that Alice should be safe from this attack,as long as Bob's public key B is substantially longer than240 digits (800 bits). Unfortunately, Alice cannot tell,without factoring Bob's RSA key-modulus, whether Bob usedthree or more prime factors to prepare his RSA key-pair [22].If Bob has a large-modulus key-pair made up from several small factors,then Alice's naïve use of Encrypt & Sign would stillleave her vulnerable to Bob's substituted-ciphertext attack.

Thus, whenever we want to sign a ciphertext,Anderson's attack forces Alice to sign, along with her ciphertext,either the plaintext itself or Bob's public key B:

Of course, Encrypt-then-Sign isn't very useful anyway, because only the illegible ciphertext, not the plaintext,would be non-repudiable. In what follows, for simplicity, we'll mostly ignoreEncrypt & Sign, and we'll concentrate on analyzingand fixing Sign & Encrypt's defects.

1.3  Purpose of the Paper

• Section 2 describes the problem's technical and social scope,
• Section 3 analyzes the problem cryptographically,
• Section 4 reviews several standards that accept naïveSign / Encrypt as secure, and
• Section 5 presents a comprehensive variety of simple solutions.

Our goal is to help security standards offera variety of secure ways to sign and encrypt messages.Application programmers should not be constrainedby ``one size fits all'' protocols,but they also shouldn't have to understand the nuancesof cryptographic design.

2  Problem Scope

2.1  Technical Scope

Thus, naïve Sign & Encrypt has come to characterizefile-handling and e-mail security applications.PKCS#7 [23], CMS ⁴ [9],S/MIME [20], and PGP ⁵ [29],all suffer from this defect.Further, the W3C's ⁶XML-Signature & XML-Encryption Working Groupshave explicitly set themselves the task of supplying XMLwith S/MIME-style security.The demand for simple file-security and message-security isbig and growing, so widespread use of these naïve Sign & Encryptsecurity models will lead to widespread exposures.

2.2  Social Scope

• Commercial PKI is in widespread deployment;
• Secure networking standards don't address file-encryption;
• Demand for cryptographers greatly exceeds the supply.

So, when application programmers need file-encryption help,they can seek help from crypto vendors and from crypto standards.Unfortunately, the vendors and the standards both offereither high-level secure connections,or low-level ``toolkit'' mechanisms.Neither offering makes file-encryption easy.The available standards specifications for file-encryptionintend to support security applications, but the specifications tend to standardize only low-level APIs for cryptographic primitives, so as to leave designersas much flexibility as possible.

3  Defective Standards

• Zimmermann described a naïve RSA-based Sign & Encrypt protocol, which later became PGP;
• X.509v1 codified a flawed, naïve Encrypt & Sign, independently of PGP;
• Burrows et al. and I'Anson described a workable Sign & Encrypt protocol for X.509;
• PEM applied X.509's cryptography to e-mail transport, using naïve S&E instead of I'Anson's repaired S&E;
• Three standards extended and generalized PEM:

  1. MOSS extended PEM to support MIME-encoded e-mail, by adding naïve Sign & Encrypt for e-mail attachments;
  2. PKCS#7 generalized PEM to non-mail file-handling applications, but preserved the S&E flaw intact;
  3. CMS and S/MIME carried PKCS#7's generality and the flawed S&E back to the e-mail community.

• Today, the nascent XML security standards expressly intend to support naïve Sign & Encrypt.

These relationships aren't as complicated as they look,because MOSS, PKCS#7, and S/MIME are all descended fromPEM, and through PEM from X.509, while PGP and XML arecompletely independent efforts.

In the rest of this section, we discuss the defective standardsin the chronological order listed above.

3.1  PGP and OpenPGP

PGP's message-format had several similarities withlater features of PEM and S/MIME:

• symmetric-key encryption for message bodies;
• unformatted message-bodies;
• independent crypto layers.

In our discussion, we'll omit PGP's use of symmetric-key ciphersfor bulk encryption,because it is irrelevant to our surreptitious forwarding attack.

PGP's strongest security option is naïve Sign & Encrypt,so PGP is vulnerable to surreptitious forwarding:

Note that PGP's plaintext message-bodies are unformatted,containing no names for the sender or recipient.Because PGP doesn't allow formatted message bodies,an extra signature layer, or signed attributes,PGP doesn't admit any of the protocol repairs we describe belowfor S/MIME and PKCS#7 (see §§ 23, 3.6, & 5.1).

3.2  X.509, Version 1

This modification involves no additional effort as far as token construction is concerned, and it is simply to require that the encryption of enc-Data is done after the signature operation instead of before.

I'Anson's text incorrectly implied thathe had only replaced E&S with S&E.In fact, his repair worked only because he madeAlice sign her recipient's name, Bob,along with her message.This signed name proved Alice's intent to write for Bob.If Alice's signature hadn't included Bob's name, thenI'Anson's new token would have been just a naïve Sign & Encrypt,fully vulnerable to surreptitious forwarding.

Clearly, I'Anson's paper influenced the early PKI standardscommunity, because PKCS#1 and various later RFCs cited the paper.Though PEM and later mail standards didn't cite I'Anson,they followed his paper's advice:PEM, PKCS#7, and CMS provided Sign & Encrypt as a basic operation,and S/MIME explicitly deprecated Encrypt & Sign.We suggest that had I'Anson explained the necessity of signing the recipient's name, the later standards would haveused Sign & Encrypt correctly.

Note that X.509's originalEncrypt & Sign token (cf. Eqn. 16, above)could have been fixed without signing first,by the simple addition of the sender's name,similar to I'Anson's signed recipient-name:

3.3  PEM

For our purposes, PEM provides essentially only two variantsof mail security; a message can be signed only, or it can besigned and then encrypted.Like PGP, and like PEM's descendants PKCS#7, CMS, and S/MIME, PEMapplies its signature and encryption steps to the message-body,i.e., not to the SMTP header, the ``From: / To:'' header,or to the ``encapsulated header,''which carries a PEM message's keys and names.PEM has no notion of signing or authenticating ancillary attributes,and also doesn't support extra crypto layers,so the repairs we discuss below for S/MIME and PKCS#7(see §§ 23 & 3.6) won't work for PEM.To prevent surreptitious forwarding, a PEM message's authorwould have to include the recipient's name directly in themessage-body. Of course, it could be very difficult forthe receiving PEM mail-client to find the recipient's namein the body, so as to check automatically for surreptitious forwarding.

Today, PEM is not widely used, and PEM's vulnerability to surreptitiousforwarding is mostly just a matter of historical interest.But PEM's accomplishment and influence were great, becausePEM successfully achieved platform-independent cryptographicinteroperation, at a time when the still-new Internet was amuch more heterogenous affair than it is today.

3.4  MOSS

1. By adding cryptographic support for MIME-formatted multipart messages (popularly known as attachments);
2. By allowing encryptions and signatures to be applied in any order, like S/MIME;
3. By decoupling secure mail from the monolithic X.500 public-key infrastructure, which had failed by the mid-1990's.

Like PEM, MOSS was eclipsed by S/MIME and by PGP, and is littleheard-of today.

MOSS had another feature, one very valuable for ourpurposes: unlike the other secure e-mail protocols, MOSSexplicitly provided by default for a sender Alice to beable to sign her message-header, along with her message-body.MOSS is the only e-mail standard that gives users such anout-of-the-box mechanism for signing the recipient-list.(S/MIME's ESS feature did allow header-signing, but this wasexplicitly intended as a link-oriented security featurefor military mail servers. See the discussion of ESS,in the last half of §3.6.)

Header-signing was easy for MOSS to provide, because MOSStreated the header as just another ``part'' in the message. If Alice's MOSS message carried her signatureand encryption on both the message-body and themessage-header, Alice's MOSS message and her recipientswould be fairly well-protected against surreptitious forwarding. Unfortunately, MOSS made header-signing an optional feature,and the MOSS RFCs don't discuss why header-signing is valuable. As specified, MOSS is as vulnerable to our attackas the other e-mail protocols are.

It's worth noting that even when Alice does choose to sign MOSS'sheader, MOSS's cryptography still relies too much on Bob'ssophistication about e-mail security:

• When Bob receives Alice's MOSS message, he does have to read Alice's signed header, so as to make sure that Alice intended to send the message to him.
• Further, when Alice's cc-list is long, Bob still has to read the signed header, but this step is neither as automatic nor as reliable as onewould like.
• Finally, if Alice's mail-client doesn't bother to sign her mail-headers, Bob probably won't notice, so he'll still be vulnerable to surreptitiously-forwarded messages.

All of these issues would vanish, if MOSS had made header-signingmandatory. Bob's e-mail reader presumably would automaticallyscan the header, looking for Bob's decryption-key's ``name form,''and if this search were to fail, the MOSS mail-reader would raisean error-message warning Bob.

3.5  PKCS#7

In order to bolster PKCS#7's Sign & Encrypt security,how might a PKCS#7 author securely attach names to a fileor message?Each PKCS#7 message has SignerInfo and RecipientInfofields, but the specification does not allow these fieldsto be signed or encrypted.PKCS#7 does provide for application-defined``authenticated attributes,'' though,so a PKCS#7 application could create a signed ``To-List'' attribute,so as to prove to recipients that they are the author'sintended recipients.But crucially, PKCS#7 does not require or even suggestthat for effective security,such a signed ``To-list'' should accompany the message.Further, PKCS#9 [24], which defines various attributes forPKCS#7 messages, similarly fails to provide any attributesfor holding senders' or recipients' names.

Note also that in order to use authenticated attributesfor repairing PKCS#7 Sign and Envelope,one must separately apply the signature and encryption steps,instead of using the Signed-and-Enveloped construct.This is because the combined construct doesn't supportattributes at all [23]:

Note. The signed-and-enveloped-data content type providescryptographic enhancements similar to those resultingfrom the sequential combination of signed-data andenveloped-data content types. However, since thesigned-and-enveloped-data content type does not haveauthenticated or unauthenticated attributes, nor doesit provide enveloping of signer information other thanthe signature, the sequential combination of signed-dataand enveloped-data content types is gnerally preferableto the SignedAndEnvelopedData content type, except whencompatibility with the ENCRYPTED process type inPrivacy-Enhanced Mail is intended.

Thus, for PKCS#7's simple Signed-and-Enveloped message,the protocol affords no cryptographically secure naming. The only way a Signed-and-Enveloped recipient can knowthat he is intended to see the message,and that no surreptitious forwarding has occurred,is for the sender to includethe recipient's name within the message-body.

3.6  S/MIME and CMS

The S/MIME specification itself acknowledges that CMS'Sign & Encrypt isn't very secure,but the S/MIME specification fails to discuss the main defect.Further, the document tells implementors nothingabout how to shore up Sign & Encrypt.Instead, the S/MIME specification merely cautions users andimplementors not to over-rely on a message's security:

1. ``An S/MIME implementation MUST be able to receive and processarbitrarily nested S/MIME within reasonable resource limitsof the recipient computer.

2. ``It is possible to either sign a message first, or toenvelope⁸ the message first.It is up to the implementor and the user to choose.When signing first, the signatories are then securely obscuredby the enveloping.When enveloping first, the signatories are exposed, but it ispossible to verify signatures without removing the enveloping.This may be useful in an environment where automatic signatureverification is desired, as no private key material is requiredto verify a signature.

3. ``There are security ramifications to choosing whether to signfirst or to encrypt first.A recipient of a message that is encrypted and then signed canvalidate that the encrypted block was unaltered, but cannotdetermine any relationship between the signer and the unencryptedcontents of the message.A recipient of a message that is signed-then-encrypted can assumethat the signed message itself has not been altered, but thata careful attacker may have changed the unauthenticated portionof the encrypted message'' [sic].

- [20] Sec. 3.5, ``Signing and Encrypting.''

• Paragraph 2 presents the security issues asa tradeoff between confidentiality and ease of verification;
• Paragraph 3 hints that an attacker can replacethe external signature in an encrypted-then-signed message,
• But there's no mention that sign-then-encrypt isvulnerable to surreptitious forwarding, by replacementof the outermost encryption layer.(In paragraph 3, ``unauthenticated portion'' seems torefer not to the unauthenticated ciphertext, but tounauthenticated plaintext.)
• The excerpt presents only the choice betweensigning first and encrypting first. There's no mentionof repairing either option's defects.

S/MIME is flexible enough to allowthe Sign & Encrypt defect to be repaired.In the specification excerpt above,the first paragraph provides that every S/MIME applicationmust be able to process Sign/Encrypt/Signed messages andEncrypt/Sign/Encrypted messages. Either S/E/S or E/S/Esuffices to reveal any alteration of the sender's cryptolayers, as long as the receiving client knows how to detectthe alterations (See §§ 5.2 & 5.3, below).

Note that our S/E/S double-signing only superficially resembles S/MIME's optional ``triple-wrapping'' feature;the two are different in mechanism and in purpose.S/MIME's Enhanced Security Services specification [7]provides specializedsecurity-related message-attributes, in support of certainfeatures such as signed receipts and secure mailing-lists.In order to support the ESS features, some mail serverswill apply an extra signature to the ciphertext of an end-user'sSigned-and-Encrypted message:

1.1 Triple Wrapping Some of the features of each service use the concept of a "triple wrapped" message. A triple wrapped message is one that has been signed, then encrypted, then signed again. The signers of the inner and outer signatures may be different entities or the same entity. Note that the S/MIME specification does not limit the number of nested encapsulations, so there may be more than three wrappings.

1.1.1 Purpose of Triple Wrapping Not all messages need to be triple wrapped. Triple wrapping is used when a message must be signed, then encrypted, and then have signed attributes bound to the encrypted body. Outer attributes may be added or removed by the message originator or intermediate agents, and may be signed by intermediate agents or the final recipient. [...]

The outside signature provides authentication and integrity for information that is processed hop-by-hop, where each hop is an intermediate entity such as a mail list agent. The outer signature binds attributes (such as a security label) to the encrypted body. These attributes can be used for access control and routing decisions.

Triple-wrapping allows mail servers tosecurely annotate messages on-the-fly (``hop-by-hop''),primarily for the benefit of other mail-servers.In contrast, in our S/E/S repair, Alice applies her outer signature,without any extra attributes, to her own Signed & Encrypted message,as the basic CMS specification allows.Similarly, only Alice's intended S/E/S recipient Bob would validateher inner and outer signatures.In sum, our S/E/S is an end-to-end security feature, whileESS uses triple-wrapping to support link-oriented security features.

Further, ESS triple-wrapping and S/E/S serve different purposes.Though the first two ESS paragraphs do mention that an end-userlike our Alice might apply an outer signature herself,the ESS document gives no reason that she might do so,except to attach signed attributes to the ciphertext.The ESS document nowhere suggests that triple-wrappingmight be necessary to repair a security defect inSign & Encrypt.In fact, the ESS specification committee did not intendtriple-wrapping to be a repair for the surreptitious-forwardingdefect. Instead, the ESS specification was written to fulfillthe U.S. Dept. of Defense's purchasing criteria for secure e-mail,which demanded server-oriented security features [8].

Besides S/E/S,another S/MIME repair option comes from the CMS specification,which is a core piece of the S/MIME standards suite.Like PKCS#7, CMS provides for ``signed attributes,''which offer a different way to prevent crypto alterations.Suppose the sender includes a signed ``To-List'' attribute,and suppose the recipient knows how to process and interpretsuch an attribute.Then the recipient can identify who intended him to receivethe message, and no attacker can profit by replacing theouter crypto layers.Unfortunately, like the PKCS#7 specification,the CMS specification does notstipulate or even suggest such naming attributes,though the specification does suggest other signed attributes.

These S/MIME repairs are cumbersome, and they only barelymeet the e-mail industry's needs.Crucially, because the specification neither requires any repair,nor even mentions that some features can serve as repairs,the repairs' interpretations aren't standardized, anddifferent vendors' S/MIME applications can't readilyinteroprate with full Sign & Encrypt security.

3.7  XML Security

To some extent, this is proper: these standards are intendedto support as broad a class of applications as possible,including document preparation and handling, financialapplications, wire protocols, and potentially evenintricate cryptographic security protocols.The Secure XML Working Groups say that they don't want torequire secure high-level behavior in their specifications,because they don't want to constrain how low-levelapplications will use XML's security features.The WGs explicitly hope that a higher-level XML securityspecification, with out-of-the-box ``idiot-proof'' security,will be built somedayto follow on the current WGs' specifications.But for now, certainly, the XML-Signatures draft specificationis most suitablefor use only by experienced security engineers and cryptographers,and not for application programmers who don't want to specializein security.

4  Analysis

In this section, we present three overlapping views of what'swrong with naïve Sign & Encrypt.Then, we summarize and discuss several arguments in defense ofthe naïve Sign & Encrypt standards.Finally, we discuss how this flaw survived severalstandards-review committees' deliberations.

4.1  Asymmetric Security Guarantees

• When A sends B a signed & encrypted message, A knows that only B can read it, because A trusts B not to divulge the message, but -
• When B receives A's signed & 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 naïve Sign & Encrypt is thatB gets no proof that it was A who encrypted the message.In hindsight, this is obvious:public key algorithms usually don't automaticallyauthenticate the encryptor of a message.

Certainly, in some applications, it's neither necessarynor feasible to give a recipient any assurance thatonly the sender has seen the message-plaintext.Thus, for example, mail-security applications do needthe flexibility to waive full end-to-end symmetric-keysemantics.But, whenever possible, and by default,mail- and file-security applications should give end-userseasy-to-understand security guarantees.

4.2  Symmetric-Key Semantics

• A sent the message,
• No-one else has seen the plaintext,
• A intended B to receive the plaintext.

With naïve Sign & Encrypt, these assumptions can break down,because the recipient may have to rely on the crypto layer tosupply the intended recipient's names.That is, the problem arises when:

• The message plaintexts don't mention the sender's and target's names;
• The sender's and recipient's names are important for understanding the message or its security import;
• The recipient assumes that the signer encrypted the message.

Under these conditions, an attacker can successfullyand surreptitiously forward a naïvely signed andencrypted message.

4.3  Sign & Encrypt Must Cross-Refer

We suggest that the messaging standards all erred by treatingpublic-key encryption and digital signatures as ifthey were fully independent operations.This independence assumption is convienient for writingstandards and for writing software, but it is cryptographicallyincorrect.When independent operations are applied one on top of another,then the outermost crypto layer can undetectably be replaced,and security is weakened.

In [1], Abadi and Needham presented a simplebest-practice rule for protocol design:

When a principal signs material thathas already been encrypted, it should not be inferred thatthe principal knows the content of the message.On the other hand, it is proper to infer that the principalthat signs a message and then encrypts it for privacyknows the content of the message.

In [2], Anderson and Needham presented theirplaintext-substitution attack against Encrypt-then-Sign(see § 1.2), and they strengthened Abadi's prescription:

Sign before encrypting. If a signature is affixed toencrypted data, then ... a third party certainly cannot assumethat the signature is authentic, so nonrepudiation is lost.

These principles were well-understood soon after X.509's defectwas discovered (if not before),and to be fair, they were published after the early versionsof PEM, PKCS#7 and S/MIME were published.But PKCS#7 and S/MIME have been revised sinceAbadi's and Anderson's papers became well-known,so the updated standards could have been repaired.Nevertheless, the e-mail standards still treat the Sign & Encryptproblem as a user-interface issue:``There are security ramifications to choosing whether tosign first or encrypt first...'' [20].

Though signing and encryption are not independent of one another,the defective standards treated crypto operations as independentcontent-transformations, converting ``content'' to ``content.''Conceptually, this makes it easy for users and programmers to layercrypto operations in arbitrary depth and in arbitrary order.By this device, the standards authors sought to avoid constrainingapplication developers' designs.

With such independent operations, though, it's hard to fulfill therecipient's security expectations.In order to work properly together,the signature layer and the encryption layer actuallymust refer to one another,so as to achieve basic symmetric-key security guaranteesthat users expect.The recipient needs proof that the signer and the encryptorwere the same person, which necessarily entails eithersigning the recipient's identifier (in Sign & Encrypt),or encrypting the signer's identifier (in Encrypt & Sign).Once such cross-references are in place,an attacker can't remove and replace the outermost layer,because the inner layer's reference will reveal the alteration.

In Section 5, ``Repair Options,''we present five ways to give the recipientthis cross-referenced proof of the encryptor's identity.In each of these five repairs, the sender identifies the outermostoperation's key-holder, inside the innermost content,so as to bind the sender's and recipients' names together.For example, one repair for Sign & Encrypt puts the decrypting recipient's name inside the signed plaintext message:

4.4  Trust and Risk

B has no way to gauge the risk that the messagehas been divulged to people unknown to A and B.To gauge the risk, B would have to know how trustworthyare the people who have surreptitiously forwardedthe message along from A towards B.Thus, in general, one can't assess the privacy of adecrypted plaintext, and shouldn't trust its privacy,unless one knows who encrypted it.In sum: if we accept the Trust and Risk argument, thenthe encryption step of Sign & Encrypt is quitepointless from the receiver's point-of-view.

4.5  Security and Ease-of-Use

It's unrealistic to expect today's users to catchsuch a subtle point.When X.509, PEM, and S/MIME were designed,PKI users were expected to be system administrators and otherfairly sophisticated users;now, though, with the modern Internet and withelectronic commerce in play, we can't expect most usersto understand any cryptographic nuances at all.

A similar defense of the defective secure mail standards is thatthe specifications aren't actually broken, because``Applications can and should put names into the content,if that's what they want.''This argument assumes that application programmersshouldn't try to incorporate cryptographic securityinto programs in the first place,unless they understand security andcryptography well enough to design security protocols.Further, the argument insists that no security standardcan be so complete as to prevent ignorant programmersfrom ``shooting themselvers in the foot.''

A ready answer to this argument is ``SSL.''The SSL specification gives fairly complete security, out-of-the-box.Further, non-specialist programmers are able to set up secureSSL connections for their applications, without havingto patch the SSL protocol on their own.

4.6  How Did This Happen?

• Optional Coverage: All of the specifications allow senders to put the recipient's name, or the whole mail header, into the message-body before signing. In addition, some protocols explicitly provide an optional mechanism for signing the mail header or the recipient-list.
• Contextual Repair: In the same way, the PEM committee's discussion explicitly decided that the message's context would usually solve the problem. For example, Alice's signed ``Dear Bob'' salutation would reveal any re-encryption.
• Out of Scope: The PEM committee noted that surreptitious forwarding is a type of replay, and that no e-mail mechanism can prevent e-mail replay. Thus, to the PEM committee, it seemed inappropriate to worry about surreptitious forwarding of signed-and-encrypted mail.

More recently, the XML-Signature and XML-Encryption workinggroups explicitly decided, from the outset of their work,to emulate S/MIME's security. Both groups decided not toaddress S/MIME's and PKCS#7's vulnerability to surreptitiousforwarding, for three related reasons:

1. XML-Signature and XML-Encryption are explicitly low-level protocols. Thus, the XML-security standards mustn't force higher-level protocols to follow a particular cryptographic model.
2. The W3C intends that for XML documents, format specifications and semantics specifications should generally be kept separate. Accordingly, surreptitious forwarding, being an issue of Sign & Encrypt ``semantics,'' should be treated in a separate XML Security Semantics specification.
3. A document-format working group shouldn't try to resolve questions about minute details of cryptographic implementation, because such discussions invariably become time-wasting ``ratholes.''

Thus, the XML-Security working groups seem to intend theirspecifications to be accepted as strictly ``low-level''cryptographic primitives. It's hard, though, to reconcile this``low-level'' label with these working groups' early proposalto emulate S/MIME, since S/MIME claims to offer high-level,comprehensive, and secure messaging.

It's hard to blame the secure-mail standards groups for havingmade a cryptographic mistake. Clearly, they all worked in goodfaith to promote secure and usable technologies. Further, it's important to acknowledge how hard it is to write networkingstandards in general, and mail-related standards in particular.As hard as it is to design cryptographic security protocols,cryptographic difficulty is only a formal or mathematical affair,and is very different from the difficulty of designing workablenetworking protocols for real-world deployment. In any designof a concrete security protocol, many hard problems have to besolved simultaneously, including:

• Flexibility for application programmers;
• Flexibility for network admins and sys-admins;
• Interoperation with other protocols;
• OS platform differences;
• Scaling;
• Server statelessness;
• Exportability;
• Time-to-market.

Clearly, each of the secure e-mail standards committeestried to codify a cryptographically correct protocol.The worst that can be said of these working groups is thatthey underestimated the subtlety of adding cryptography totheir already-burdened portfolio.

5  Repair Options

1. Sign the recipient's name into the plaintext, or
2. Encrypt the sender's name into the plaintext, or
3. Incorporate both names; or
4. Sign again the signed-&-encrypted message; or
5. Encrypt again the signed ciphertext.

In each case,the signing layer and the encryptionlayer become interdependent,binding the sender's name, in one layer,to the recipient's name in the other layer.Any one of these alternatives suffices to establish thatAlice authored both the plaintext and the ciphertext.Note though that an effective security standard should requirenot only that the author must provide one of these five proofs,but also that the recipient must demand some such proof as well.That is, if a naïve Sign & Encrypt message arrives withoutproof that the signer and encryptor were the same person,then the application software should warn the recipientthat the message's privacy and/or authenticity are suspect.

5.1  Naming Repairs

1. If Alice wants to use Sign & Encrypt, then she needs to enclose only Bob's name, because this will link the outer layer's key to the inner layer.

   A ---> B : {{Bob, msg}a}B (21)

   By signing Bob's name into her message, Alice explicitly identifies him as her intended recipient. This is equivalent to I'Anson's repair for X.509v1, as discussed above in Section 3.1.
2. If Alice prefers instead to use Encrypt & Sign, then she should encrypt her own name along with her message, and should sign her message-plaintext outside the ciphertext, so as to block Anderson's plaintext-replacement attack:

   A ---> B : {{Alice, msg}B, #msg}a< /sup> (22)

   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.
3. If Alice encloses both names in the message-body, she can avoid having to pay attention to cryptographic choices early on, while she's formatting her message text. She can send to Bob in either of two ways:

   A ---> B : {{``A ---> B¢¢,  msg}B, #msg}a A ---> B : {{``A ---> B¢¢,  msg}a}B (23)

   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.

These repairs are rational examples of Martín Abadi'sand Catherine Meadows' rule-of-thumb for designing securityprotocols:

• Abadi: ``If the identity of a principal is essential to the meaningof a message, it is prudent to mention the principal's name explicitly in the message.'' (Principle 3 in [1])
• Meadows: ``In general, it's safer to include names explicitlyinside crypto protocols' messages.'' [18]

5.2  Sign/Encrypt/Sign

• Inner Signature: ``Alice wrote the plaintext;''
• Encryption: ``Only Bob can see the plaintext;''
• Outer Signature: ``Alice used key B to encrypt.''

Bob can conclude not only that Alice wrote the message, but that she also encrypted it.Seen another way, S/E/S is a variation on including the sender's name inside the plaintext, which then is encrypted and signed (see Sec. 5.1, bullet 2).The inner signature's key links the encryption-layerto the outer signature's layer.Alice signs Bob's key, so as to protect herself from Anderson'splaintext-substitution attack.

5.3  Encrypt/Sign/Encrypt

• First Encryption: ``Only Bob sees the plaintext;''
• Signature: ``Alice wrote the plaintext and the ciphertext;''
• Outer Encryption: ``Only Bob can see that Alice wrote the plaintext and ciphertext.''

Bob cannot forward the message without invalidating Alice'ssignature.The outer encryption serves to prevent an attackerfrom replacing Alice's signature.As with S/E/S, E/S/E is a variant of including the recipient'sname inside the plaintext, which is then signed and encrypted (see Sec. 5.1, bullet 1).Alice signs her plaintext along with her ciphertext [27],so as to protect herself from Anderson's plaintext-substitution attack.At the same time, Alice's signed plaintext gives Bob non-repudiation.

5.4  Costs and Advantages

• Double-signing is quite 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 therecipient's name, then Sign & Encrypt(§ 5.1, bullets 1 and 3).The other solutions all require an extra hash of themessage or of the encrypting key, so as to block Anderson's plaintext-replacement attack.

6  Conclusions

The weakness of naïve Sign & Encrypt is somewhat subtle,but it is easily fixed in several ways.The repairs all show that Signing and Encryption shouldnot be viewed as independent operations;the repairs presented here all rely on linkingthe outer operation's key to the inner operation's payload.This realization, that public-key operations are notnecessarily so independent as they're commonly thought to be, and that coupling two layers together is a profitableprimitive, may prove to be a novel and useful axiom forbeginning protocol designers and analysts.

7  Acknowledgements

References

[1]

M. Abadi and R. Needham,``Prudent Engineering Practice for Cryptographic Protocols,''Digital SRC Research Report #125 (June 1, 1994).

[2]

R. Anderson and R. Needham,``Robustness Principles for Public Key Protocols,''in Lecture Notes in Computer Science 963,Don Coppersmith (Ed.), Advances in Cryptology -CRYPTO '95, pp. 236-247. Springer-Verlag, 1995.

[3]

S. Crocker, N. Freed, J. Galvin, S. Murphy,Internet RFC 1848 ``MIME Object Security Services,'' October 1995.http://www.faqs.org/rfcs/rfc1848.html

[4]

M. Burrows, M. Abadi, and R. Needham,``A Logic of Authentication,''Proc. R. Soc. Lond. A 426(1989) pp. 233-271.

[5]

T. Dierks and C. Allen, Internet RFC 2246``The TLS Protocol Version 1.0,'' January 1999.ftp://ftp.isi.edu/in-notes/rfc2246.txt

[6]

D. Eastlake, J. Reagle, and D. Solo (Editors),``XML-Signature Syntax and Processing: W3C Working Draft 18-September-2000,''http://www.w3.org/TR/xmldsig-core/

[7]

P. Hoffman, Internet RFC 2634 ``Enhanced SecurityServices for S/MIME,'' June 1999. ftp://ftp.isi.edu/in-notes/rfc2634.txt

[8]

Paul Hoffman, personal communication.

[9]

R. Housley, Internet RFC 2630 ``Cryptographic Message Syntax,'' June 1999. ftp://ftp.isi.edu/in-notes/rfc2630.txt

[10]

Russ Housley, personal communication.

[11]

C. I'Anson and C. Mitchell,``Security Defects in CCITT Recommendation X.509 - TheDirectory Authentication Framework,''ACM Comp. Comm. Rev., (Apr '90), pp. 30-34.

[12]

B. Fraser, T.Y. Ts'o, J. Schiller, M. Leech,``IP Security Protocol (IPSEC) Charter,''http://www.ietf.org/html.charters/ipsec-char- ter.html

[13]

A. Joux and R. Lercier,``Discrete logarithms in GF(p)'', April 17 2001.Announcement on the Number Theory Mailing List NMBRTHRY.http://www.medicis.polytechnique.fr/~lercier/talk/ecc99.ps.gz .

[14]

International Telegraph and Telephone Consultative Committee (CCITT).Recommendation X.509: The Directory - Authentication Framework.In Data Communications Network Directory, Recommendations X.500-X.521,pp. 48-81. Vol. 8, Fascicle 8.8 of CCITT Blue Book.Geneva: International Telecommunication Union, 1989.

[15]

J. Linn, Internet RFCs 989, 1040, 1113, 1421,``Privacy Enhancements for Internet Electronic Mail:Part 1: Message Encryption and Authentication Procedures,''February 1987, January 1988, August 1989, February 1993.ftp://ftp.isi.edu/in-notes/rfc{989,1040}.txtftp://ftp.isi.edu/in-notes/rf c{1113,1421}.txt

[16]

John Linn, personal communication.

[17]

Stephen Kent, personal communication.

[18]

C. Meadows,``Verification of Security Protocols,'' lecture at1996 RSA Cryptographers' Colloquium, Palo Alto, CA.

[19]

C. Neuman and J. Kohl, Internet RFC 1510``The Kerberos Network Authentication Service (V5)'',September 1993.ftp://ftp.isi.edu/in-notes/rfc1510.txt

[20]

B. Ramsdell, Internet RFC 2633``S/MIME Version 3 Message Specification,'' June 1999. ftp://ftp.isi.edu/in-notes/rfc2633.txt

[21]

R. Rivest, A, Shamir, L. Adleman,``A Method for Obtaining Digital Signatures and Public-KeyCryptosystems,'' Comm. ACM, v. 21, 2, Feb. '78, pp. 120-126.

[22]

RSA Laboratories,``PKCS#1: RSA Crypto- graphy Standard,'' version 2.0.Amendment 1: ``Multi-Prime RSA.''http://www.rsasecurity. com/rsalabs/pkcs/pkcs-1/

[23]

RSA Laboratories,``PKCS#7: Cryptographic Message Syntax Standard,''Version 12.5, Nov. 1, 1993.http://www.rsasecurity.com/rsalabs/ pkcs/pkcs-7/

[24]

RSA Laboratories,``PKCS#9 v2.0: Selected Object Classes and Attribute Types,''February 25, 2000. http://www.rsasecurity.com/rsalabs/ pkcs/pkcs-9/

[25]

Joseph Reagle, personal communication.

[26]

J. Reagle,``XML Encryption Requirements,'' W3C Working Draft 2001-April-20,http://www.w3.org/TR/2001/WD-xml-encryption-req-20010420 .

[27]

Ed Simon, personal communication.

[28]

Visa International and MasterCard,``Secure Electronic Transactions Protocol Specification,''http://www.setco.org/set_specifications.html .

[29]

P. Zimmermann,``The Official PGP User's Guide,''MIT Press (1995).

[30]

P. Zimmermann,``A Proposed Standard Format for RSA Cryptosystems,''IEEE Computer 19(9): 21-34 (1986).

Footnotes:

¹ Affiliations: Shym Technology,75 Second Ave. Suite 610 Needham, MA 02494;Curl Corp., 400 Technology Sq., Cambridge, MA 02139;ddavis@curl.com, don@mit.edu

² Extended Markup Language

³ Notation: ``A'' is Alice's public key, and ``a'' is her private key.Thus, {msg} ^A is an encrypted ciphertext, and{msg} ^a is a signed message.We assume that the asymmetric-key cryptosystem behaves similarlyto RSA [21], so that a signature is a private-key encryption.

⁴ Cryptographic Message Syntax.

⁵ Pretty Good Privacy

⁶ The World Wide Web Consortium, seehttp://w3.org .

⁷ In Eqn.16, we've simplified the X.509 token's structure,by leaving out various nonces and other parameters.

⁸ The S/MIME, CMS, and PKCS specification documentsuse the verbs ``encrypt'' and ``envelope'' interchangeably.

⁹ For notational simplicity, we represent these signaturesas {stuff} ^a,instead of as stuff, {#stuff} ^a .