Secure encrypt-then-sign with RSA

Question

I understand that when you want to encrypt and sign data with RSA the generally recommended approach is sign-then-encrypt.

However, I have encrypted data that I need to sign, to prove the author of the encrypted data.

1. Encrypt wth recipient's public key
2. Sign with author's private key
3. Concatenate cipher text with signature

From reading papers such as this, it seems that the problems with sign-then-encrypt are quite subtle, but solutions are quite straightforwrd.

I haven't been able to turn up much on issues with encrypt-then-sign. I guess one problem is that someone could simply strip off the signature and replace it with their own. My first thought was to prefix the data with the author's public key before encrypting, but then the signature can only 'really' be verified by the recipient (public verification is more desirable for me).

What are the issues associated with encrypt-then-sign, and what solutions exist?

** Edit **

I thought of another potential solution to the problem of someone replacing the original signature with their own - using X.509 certificates. So in step 3 above we also concatenate the certificate of the author. When verifying the signature we check that the public key matches that of the certificate, and we also verify that the certificate was issued by a particular, trusted CA. With this scheme, not just anyone can replace the signature, only those who are issued a certificate from the trusted CA. Any issues with this approach?

Answer 1

The primary problem with encrypt-then-sign (signing the ciphertext) relates to the difference between signing for the purpose of assigning responsibility vs for the purpose of taking credit. Encrypt-then-sign is OK for the former but not for the latter. The issue is quite subtle.

In particular, in your protocol, the recipient has no reason to believe the sender (signer) was ever aware of the contents of the plaintext. The signer must have been aware of the contents of the ciphertext and approved signing the ciphertext, but this does not mean that the signer knows or created the original message.

For instance, suppose we're using this to log into a site. Suppose Alice, who is a system administrator, is going to authenticate to Sam, who is a server. Suppose that, to authenticate, Alice is going to use your scheme to send a copy of the root password to Sam (encrypted and then signed); if everything checks out, Sam will conclude that Alice knows the root password and should be granted full access to the server. Sounds reasonable, right? But now look what can go wrong. Mallet can intercept Alice's encrypted-and-then-signed packet, strip off Alice's signature, append her own signature, and forward it to Sam. Sam will receive it and everything will check out: Sam can see that this was signed by Mallet and decrypts to contain the correct root password, so Sam will conclude that Mallet should be granted full access to the server. That's bad.

The reason why an attack is possible in the latter example is that Alice and Sam were using the signature as a basis for taking credit: Alice was trying to take credit for knowledge of the root password, and Sam was willing to accept the signature as evidence for that. However, encrypt-then-sign does not provide a basis for allowing the sender to take credit for knowledge of the contents of the message.

So, whether this scheme is adequate will depend upon the particular application you have. Many applications only need authentication for the purpose of assigning responsibility: if something goes wrong, we know who to hold responsible (or, we know whose account to charge or whose quota to decrement), and encrypt-then-sign is fine for that. But a few applications (the password authentication example I mentioned; auctions; and some others) use authentication to additionally allow the parties to take credit for knowledge of a message. For those applications, vanilla encrypt-then-sign can be problematic.

There are ways to fix encrypt-then-sign so it doesn't have this shortcoming. See the research literature below for details.

For more details on all of this, including what can go wrong as well as how to avoid these problems, you can read the following detailed explanation in the research literature:

• Prudent engineering practice for cryptographic protocols. Martin Abadi and Roger Needham. See Section 5.2 (but the entire paper is fantastic and a classic).

• Security Protocols and their Properties. Martin Abadi. See Section 5.

Answer 2

Actually, Encrypt-then-MAC (EtM) is considered to be the most secure mechanism to achieve Authenticated Encryption (AE).
There is also a research paper by Mihir Bellare on this topic: https://cseweb.ucsd.edu/~mihir/papers/oem.pdf

This is another resource from Dan Boneh's crypto class where the exact same thing is discussed (slide 29). https://crypto.stanford.edu/~dabo/courses/OnlineCrypto/slides/07-authenc-v2-annotated.pptx

Also, another link on using the EtM paradigm: https://moxie.org/blog/the-cryptographic-doom-principle/