144
$\begingroup$

Frequently, we want to send messages that are (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 make Alice think that a message came from Bob when it didn't.

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?

$\endgroup$
5
  • 6
    $\begingroup$ I'm for signing first, and then encrypting with symmetric authenticated encryption. $\endgroup$ Nov 22, 2012 at 18:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Nov 23, 2012 at 23:36
  • 1
    $\begingroup$ @CodesInChaos In a hybrid scenario with the use of asymmetric encryption like RSA to exchange the key of a symmetric encryption like AES GCM so would you sign the plaintext message and then encrypt the pair (message, signature) with AES GCM? $\endgroup$
    – M-elman
    Dec 6, 2016 at 17:55
  • $\begingroup$ Good question indeed $\endgroup$
    – Peter
    Mar 27, 2019 at 13:07
  • 1
    $\begingroup$ Existing answers are dated. See github.com/rweather/arduinolibs/issues/… $\endgroup$
    – tejasvi88
    Dec 16, 2021 at 11:43

6 Answers 6

111
$\begingroup$

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.

$\endgroup$
15
  • 4
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Nov 24, 2012 at 1:15
  • 2
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Nov 24, 2012 at 2:21
  • 6
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Nov 24, 2012 at 2:21
  • 5
    $\begingroup$ And what effect does it have? As Bob, I receive the message, decrypt it, and then what it gives me, that the message is prepended with my identity? $\endgroup$
    – krzychu
    Nov 8, 2016 at 7:51
  • 5
    $\begingroup$ @M-elman I suppose one reason for prepending the name would be that a malicious Bob could pose as Alice by encrypting the exact same message + Alice's signature using Charlie's public key, and trick Charlie into believing that Alice sent him the message. $\endgroup$
    – bkjvbx
    Feb 28, 2017 at 14:40
24
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ The scheme described on the page you linked to does not provide public key authentication. $\hspace{.91 in}$ $\endgroup$
    – user991
    May 4, 2015 at 3:19
  • 1
    $\begingroup$ @Ricky - the public key cryptography is used in the KEM, not the MAC/Signature. $\endgroup$
    – user10496
    May 4, 2015 at 3:24
  • 1
    $\begingroup$ Yes. $\:$ Is there public key authentication in that? $\;\;\;\;$ $\endgroup$
    – user991
    May 4, 2015 at 3:28
  • 1
    $\begingroup$ @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. $\endgroup$
    – user10496
    May 4, 2015 at 3:32
  • 1
    $\begingroup$ 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.) $\;\;\;\;$ $\endgroup$
    – user991
    May 4, 2015 at 3:39
17
$\begingroup$

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

$\endgroup$
11
  • 9
    $\begingroup$ "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.) $\endgroup$
    – D.W.
    Nov 23, 2012 at 23:30
  • 8
    $\begingroup$ @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 $\endgroup$
    – sashank
    Nov 24, 2012 at 0:44
  • 2
    $\begingroup$ 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.) $\endgroup$
    – D.W.
    Nov 24, 2012 at 1:12
  • 8
    $\begingroup$ @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. $\endgroup$
    – sashank
    Jul 18, 2014 at 0:45
  • 3
    $\begingroup$ I've recently came across "signcryption" that sign and encrypt in the same time (quicker). $\endgroup$ Dec 8, 2014 at 14:08
2
$\begingroup$

How about having three different keys: $S_K1, C_K$ and $S_K2$.

  1. $S_K1$ is used to sign the cleartext message.
  2. $C_K$ is used to encrypt the concatenation of the signature generated in (1) and the cleartext.
  3. finally $S_K2$ is used to sign the encrypted output of (2). Then, the message to send is the concatenation of the output of (2) with the output of (3).

I think this is what is done by the milimail extension of Thunderbird.

$\endgroup$
1
  • 1
    $\begingroup$ Can you explain why 3 different keys, especially what's the advantage of using two different keys to sign? $\endgroup$
    – not2savvy
    Jul 9, 2019 at 16:22
0
$\begingroup$

For Authenticated Encryption, the best practice is "encrypt and then MAC". Encrypt and then MAC is always AE secure (assuming the encryption is CPA secure and the MAC is secure), but MAC then Encrypt is not always secure. The NIST AES-GCM AEAD scheme is based on "Encrypt then MAC". The SSL padding attack exploits the fact that its AE is based on "MAC and then Encrypt". Also, when you "MAC and then Encrypt" you operate encryption on a data that its entropy is decreased, due to the addition of the MAC, that is dependent on the data, and does not add entropy. So, for AEAD it is better to use encrypt and then MAC. Nevertheless, you are asking about digital signature, and intuitively I think that the same practice should be used (i.e. Encrypt and then sign), although I did not find a security prove.

$\endgroup$
-4
$\begingroup$

The only difference between these approaches has to do with hiding information about the sender. If you don't want attackers to know who the signer is, you need to sign-then-encrypt. In other cases it doesn't matter.

$\endgroup$
13
  • $\begingroup$ There might be a successful chosen ciphertext attack against sign-then-encrypt. $\hspace{1.4 in}$ $\endgroup$
    – user991
    Nov 23, 2012 at 8:02
  • $\begingroup$ @Ricky Demer: How can attacker get a plain text? There are no conditions for chosen ciphertext model. $\endgroup$ Nov 23, 2012 at 8:31
  • $\begingroup$ 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. $\:$ $\endgroup$
    – user991
    Nov 23, 2012 at 8:38
  • 5
    $\begingroup$ @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.) $\endgroup$
    – D.W.
    Nov 23, 2012 at 23:32
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 24, 2012 at 21:27

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