Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

We often want to send messages that are both (a) encrypted, so passive attackers can't discover the plaintext of the message, and (b) signed with a private-key digital signature, so active attackers can't trick Alice into thinking that some message came from Bob, when really the message is some (accidental or malicious) modification of a real message Bob sent, or a message that was forged out of whole cloth by an attacker.

Is it better to (a) generate the digital signature from the (hashed) plaintext, and then encrypt a file containing both the plaintext message and the digital signature? Or is it better to (b) encrypt the message first, and then generate a digital signature from the (hashed) encrypted file? Or (c) combine encryption and public-key digital signatures in some other way?

A closely related earlier question ( Should we MAC-then-encrypt or encrypt-then-MAC? ) seems to focus on symmetric-key MAC authentication. As Robert I. Jr. asked earlier, Do the same issues with (symmetric-key) MAC-then-encrypt apply to (public-key) sign-then-encrypt?

share|improve this question
3  
I'm for signing first, and then encrypting with symmetric authenticated encryption. –  CodesInChaos Nov 22 '12 at 18:27
    
@DavidCary, I suspect it might help if you clarified: when you mention encryption, are you talking about public-key encryption, or symmetric-key encryption? I think only the former makes sense. Or, to put it another way: Do you assume Alice and Bob have already shared a symmetric key known only to them, or not? If you assume they have a symmetric key, there'd typically be no reason to use a digital signature -- so I presume you must be starting from the assumption that they don't already have a shared key, in which case we're talking about public-key signatures + public-key encryption. –  D.W. Nov 23 '12 at 23:36

4 Answers 4

up vote 19 down vote accepted

Assuming you are asking about public-key signatures + public-key encryption:

Short answer: I recommend sign-then-encrypt, but prepend the recipient's name to the message first.

Long answer: When Alice wants to send an authenticated message to Bob, she should sign and encrypt the message. In particular, she prepends Bob's name to the message, signs this using her private key, appends her signature to the message, encrypts the whole thing under Bob's public key, and sends the resulting ciphertext to Bob. Bob can decrypt, verify the signature, and confirm that this indeed came from Alice (or someone she shared her private key with). Make sure you use an IND-CCA2-secure public-key encryption scheme and a UF-CMA-secure public-key signature scheme (i.e., one that is secure against existential forgery attack).

Justification: The reason to do this is to defeat some subtle attacks. These attacks are not necessarily a problem in all scenarios, but it's best to harden the approach as much as possible. A complete explanation would take more space than is available here, but see below for a sketch of the reasoning.

For a detailed analysis about whether to sign first or encrypt first, the following is a good resource: Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.

I don't recommend encrypt-then-sign. It could work, but it has some subtle pitfalls in some contexts, because the signature does not prove that the sender was aware of the context of the plaintext. For instance, suppose Alice's SSH client sends the message "Dear SSH server, please append my public key to /root/.ssh/authorized_keys -- and you can know that I am authorized because I know the root password is lk23jas0" (encrypted then signed with Alice's public key), and the SSH server acts on it if the root password is correct. Then Eve can eavesdrop, capture this message, strip off Alice's signature, sign the ciphertext with Eve's own key, and send it to the SSH server, obtaining root-level access even though Eve didn't know the root password.

share|improve this answer
    
I notice you write "IND-CCA2-secure public-key encryption". Is this as opposed to CCA2 SIM-NME' (www.iacr.org/archive/asiacrypt2007/48330522/48330522.pdf) or some other security notion against CCA2 attacks? –  Ricky Demer Nov 23 '12 at 23:59
1  
@RickyDemer, I don't know. This is the first time I've heard of SIM-NME', whatever that is. IND-CCA2 security is the standard notion of security for a public-key encryption scheme that is intended to be secure against chosen-ciphertext attacks. For a definition of IND-CCA2 security, see any good textbook on modern (theoretical) crypto ... or, if you're feeling brave, see Wikipedia. –  D.W. Nov 24 '12 at 1:15
1  
@RickyDemer, I've never heard of this "bounded-CCA2 non-malleable" until now; as far as I can tell, it has approximately zero practical relevance. Anyone can invent some crazy security notion, but that doesn't make it relevant. I stand by all of my recommendations and statements in my answer. To be honest, I'm not sure where you're going with your comments. If you have questions, you may want to raise them in a separate question -- I'm not sure if I understand what you are getting at, but they seem to be a bit of a tangent. –  D.W. Nov 24 '12 at 2:21
3  
@RickyDemer, s far as why your comments are being formatted funny, it appears to be because you are manually inserting LaTeX spacing commands (e.g., \;, \hspace, manual linebreaks, etc.) into your comment text. It has been suggested to you before that you avoid doing that, if you want to avoid the funny formatting of your comments. I think that remains valid advice. –  D.W. Nov 24 '12 at 2:21
1  
@louism, that's a separate question. This isn't a discussion forum -- questions should be posted separately (see the Ask Question on the upper right). But make sure to first read the help center, and do your research (try to answer the question on your own using Google, Wikipedia, search on this site, etc.) before asking. –  D.W. Nov 18 '13 at 4:41

It depends on your requirement,

  • If you Sign-then-encrypt then only receiver can decrypt and then
    verify .
  • If encrypt-then-sign then anybody can verify the
    authenticity and only receiver can decrypt it .

But in practice, both are not enough , ideally We have to sign-encrypt-sign , am not able to recollect the paper which discusses this

There is one more paper that is popular and discusses this issue in general

share|improve this answer
3  
"in practice, both are not enough" - False. Sign-the-encrypt is sufficient, if you include the prepend the identity of the recipient before signing. See my answer. (Sign-encrypt-sign is not necessary -- and indeed, in practice no deployed system that I'm familiar with uses sign-encrypt-sign.) –  D.W. Nov 23 '12 at 23:30
2  
@D.W , in encrypt-then-sign, If i encrypt with receivers public key and sign with my private key, then anybody knowing my public key ( say some auditor or a proxy agent) can first verify the signature for authenticity ( and drop it if does not match ) but only receiver can actually decrypt it –  sashank Nov 24 '12 at 0:44
1  
sashank, in my experience it is very rare for there to be any value in verifying that a signature is valid without being able to verify the contents of the message. (As far as auditing, in my experience any auditor is going to demand to see the contents of the message.) –  D.W. Nov 24 '12 at 1:12
1  
@D.W , There is possibility that an attacker could launch denial of service , if the message should be decrypted first in order to verify the signature. The attacker could simply pump in large amounts of garbage and make the decryptor deplete its resources, assuming the message is huge and signature is less in length. –  sashank Jul 18 '14 at 0:45
1  
I've recently came across "signcryption" that sign and encrypt in the same time (quicker). –  David 天宇 Wong Dec 8 '14 at 14:08

The only difference between this approaches is hiding information about sender. If you don't want attackers know who is signer, you need to sign-then-encrypt. In another case it doesn't matter.

share|improve this answer
    
There might be a successful chosen ciphertext attack against sign-then-encrypt. $\hspace{1.4 in}$ –  Ricky Demer Nov 23 '12 at 8:02
    
@Ricky Demer: How can attacker get a plain text? There are no conditions for chosen ciphertext model. –  Pavel Ognev Nov 23 '12 at 8:31
    
For example, it might be easy to come up with a ciphertext whose decryption is the result $\hspace{1 in}$ of setting the $n$th bit in the original plaintext to zero. $\:$ –  Ricky Demer Nov 23 '12 at 8:38
3  
@RickyDemer, regarding your comment "There might be a successful chosen ciphertext attack against sign-then-encrypt." - Not if you use a IND-CCA2-secure encryption scheme and a UF-CMA-secure signature scheme, and if you prepend the recipient's identity first. See my answer. (In general, the quality of technical analysis in this comment thread is low, and many comments seem to lack familiarity with the relevant technical literature, so I would caution by-standers to take what you read with a grain of salt.) –  D.W. Nov 23 '12 at 23:32
1  
@Ricky Demer: signature will be correct only if all decrypted text including padding is identical to the sender's source. So, attacker will take message "Signature is correct" in 2 cases: 1) he pass the message unchanged. 2) He changes ciphertext in some way so the decrypted text is the same as in correct message. The only way to do that is re-encrypting entire message with different IV. I don't think it's possible without knowing the key. –  Pavel Ognev Nov 24 '12 at 21:27

Should we sign-then-encrypt, or encrypt-then-sign? ... Do the same issues with (symmetric-key) MAC-then-encrypt apply to (public-key) sign-then-encrypt?

Yes. From a security engineering standpoint, you are consuming unauthenticated data during decryption if you mac-then-encrypt or sign-then-encrypt. A very relevant paper is Krawczyk's The Order of Encryption and Authentication for Protecting Communications.

The order may (or may not) be problematic in practice for you. But as the SSL/TLS folks have repeatedly shown, its problematic in practice.

Another important paper is cited by D.W. and Sashank: Don Davis' Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.

I think the primitive of sign vs mac is less important. With all things being equal (like security levels, key management and binding), then one of the top criteria is efficiency. Obviously, a symmetric cipher is more efficient than an asymmetric cipher.


Data authentication is a different property than entity authentication. You can use a MAC for data authentication and a signature for entity authentication.

But its not entirely clear to me if you want data authentication or entity authentication. The security goal you state in (b) begs for data authentication (a MAC), and not entity authentication (a signature).

I think that's why CodesInChaos said he signs then performs authenticated encryption. That's another way to say he signs-then-encrypts-then-macs. If the MAC is good, then he decrypts and verifies the signature to verify who sent the message. If the MAC is bad, then he does not bother decrypting - he just returns FAIL.

If you look at the link provided by Sashank, CodesInChaos' fix is effectively Sign/Encrypt/Sign from Section 5.2 of the paper. And D.W's solution is effectively Naming Repairs from Section 5.1.


There's a third option that's not readily apparent. It combines Encrypt-Then-MAC for bulk encryption with public key cryptography. Its also IND-CCA2 as D.W. suggested you strive for.

The option is an Integrated Encryption Scheme. There are two of them that I am aware. The first is Shoup's ECIES, which operates elliptic curves; the second is Abdalla, Bellare and Rogaway's DLIES, which operates over integers. Crypto++ provides both ECIES and DLIES. Bouncy Castle provides ECIES.

ECIES and DLIES combine a Key Encapsulation Mechanism (KEM) with a Data Encapsulation Mechanism (DEM). The system independently derives a symmetric cipher key and a MAC key from a common secret. Data is first encrypted under a symmetric cipher, and then the cipher text is MAC'd under an authentication scheme. Finally, the common secret is encrypted under the public part of a public/private key pair. The output of the encryption function is the tuple {K,C,T}, where K is the encrypted common secret, C is the ciphertext, and T is the authentication tag.

There's some hand waiving around the use of a symmetric cipher. The schemes use a stream cipher that XORs the plaintext with the output of the KDF. The design choice here was to avoid a block cipher with padding. You could use a block cipher in a streaming mode, like AES/CTR to the same effect.

There is some hand waiving around the "common secret" since its actually the result of applying a Key Agreement function and later digesting the shared secret with a KDF. The Key Agreement function uses the recipient's static public key and an ephemeral key pair. The ephemeral key pair is created by the person doing the encryption. The person performing the decrypt uses their public key to perform the other half of the key exchange to arrive at the "common secret".

The KEM and the DEM avoid padding, so padding oracles are not a concern. That's why a KDF is used to digest the large "common secret" under the KEM. Omitting the padding vastly simplifies the security proofs of the system.

share|improve this answer
    
The scheme described on the page you linked to does not provide public key authentication. $\hspace{.91 in}$ –  Ricky Demer May 4 at 3:19
    
@Ricky - the public key cryptography is used in the KEM, not the MAC/Signature. –  jww May 4 at 3:24
    
Yes. $\:$ Is there public key authentication in that? $\;\;\;\;$ –  Ricky Demer May 4 at 3:28
    
@Ricky - the public key cryptography is used in the KEM. Perhaps you should read up on the scheme and then we can talk about it. –  jww May 4 at 3:32
    
I might do that when I get back to my computer again, but there's one possibility that occurred to me. $\:$ Are you talking about a version in which $R$ is Alice's public key? $\:$ (That's not how it's described on the wikipedia page you linked to.) $\;\;\;\;$ –  Ricky Demer May 4 at 3:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.