Are the following asymmetric encryption schemes equivalent?

Question

Consider the scenario where you want a machine to be able to send daily encrypted backups to a storage server.

You'd prefer to not use simply a symmetric key for encryption, because if the machine was compromised then the symmetric key would enable the entire history of backups on the storage server to be decrypted.

Are the following two schemes equivalent?

In all schemes, the storage server only allows uploads, and not downloads or deletions. In all schemes, generate a permanent EC keypair (a,A) (where a is the private key and A is the corresponding public key). Store only A on the machine.

Scheme 1: Generate an ephemeral EC keypair (e, E) for each backup. Encrypt the data using an authenticated cypher (such as AES256-GCM or ChaCha-Poly1305) using the symmetric key H(eA), where H() produces uniformly distributed hashes (such as SHA2-256). The backup is decrypted using the symmetric key H(aE), and E is stored along with the backup. Successful decryption proves that only a machine that knew A could have created the backup. Backups would include timestamps, so it would be detected if the same observed backup was retransmitted by an attacker at a later date.

Scheme 2: In addition to the permanent encryption keypair (a,A), keep a permanent authentication keypair (b,B) on the machine. Then, Scheme 2 is the same as Scheme 1 except that prior to transmission, the encrypted backup is signed with b. On decryption, verify the signature first.

At first glance, it might seem that Scheme 2 is superior, because it prevents backups from being uploaded by an attacker that learns of the public key A. However, the authentication private key b is stored on the same machine, so both b and A are likely to be leaked together. There is no way I can see that anyone compromising the storage server could deduce the public key A that was used on each occasion when sending each backup.

Therefore, scheme 2 does not look superior to me, other than if it is suspected that the machine is compromised, the signing keypair (b,B) can be replaced without also having to replace the keypair (a,A).

Is this correct? Does use of the authentication keypair in scheme 2 have any other advantage? Does knowledge of A effectively authenticate the backup just as well as if the backup was signed with b?

Answer 1

Generally, you should try to keep to standard practices unless the situation prevents you to do otherwise. That would mean that sign-then-encrypt should probably be used using two different key pairs.

Public keys are designed to be public and you should keep that in mind. Even if your scheme is secure, the system may not be. Public key operations could for instance leak the public key through side channel attacks. There is no need to protect the key after all. Key stores may not be available to store the key securely or at the right access level. Maybe you want to replace the software implementation with a hardware module that securely stores the private key - public keys won't be protected by such hardware.

An advantage of sign-then-encrypt is that you could decrypt the backup, then check the correctness of the signature afterwards. This allows you to store the backup decrypted somewhere without losing integrity. It also allows you to re-encrypt the package using a different key / scheme if that's required. Or to sign using a more fine-grained structure where parts of the backup are protected separately. In other words, using a separate signing key will give you a lot more flexibility.