Does a key need to be signed if it is being used to decrypt a message that is already signed?

Question

I am trying to better understand authentication. Lets say I have posted my 128-bit AES symmetric key on some forum, encrypted asymmetrically to my friend using 256-bit ECC (25519). The forum isn't controlled by us so this key message could potentially be tampered with.

I then post a bunch of actual communication messages onto the forum that are encrypted with that AES key, and I sign them using a ECC 25519 signing key that my friend can safely use to verify the messages have not been tampered with.

Did I also need to sign my AES key message, or is it an adequate authentication check that the key decrypts my signed message correctly? If the key was tampered with it would fail to decrypt my message to something meaningful?

Answer 1

I am trying to better understand authentication. Lets say I have posted my 128-bit AES symmetric key on some forum, encrypted asymmetrically to my friend using 256-bit ECC (25519). The forum isn't controlled by us so this key message could potentially be tampered with.

Well first of all, note that encrypting with curve25519 isn't as trivial as encrypting with say RSA, you'll probably have to use ECIES or something along those lines. You usually see (and use) ECC used for digital signatures and key exchange, just so you're aware.

I then post a bunch of actual communication messages onto the forum that are encrypted with that AES key, and I sign them using a ECC 25519 signing key that my friend can safely use to verify the messages have not been tampered with.

Did I also need to sign my AES key message, or is it an adequate authentication check that the key decrypts my signed message correctly? If the key was tampered with it would fail to decrypt my message to something meaningful?

Let's consider what can happen if you don't sign your AES key. Worst case a malicious forum admin modifies your message and replaces your AES key with their own key (encrypted with your friend's public key). If they succeed and send messages to your friend encrypted with their own key one of three things can happen:

1. Your friend decrypts the message, sees e.g. some valid English text and says OK this message looks good, key must be fine.
2. Your friend does not decrypt the message because there is no signature on the message.
3. If the attacker did sign the message with their own key (since they can't forge your signature) your friend tries to verify the signature with your public key, which will fail (at which point your friend should discard the ciphertext).

In 2 out of 3 cases the attack will fail, but there is the chance that the attack will succeed if your friend is willing to decrypt ciphertexts without checking their integrity (known also as The Cryptographic Doom Principle). So it depends on what your friend does.

I recommend the a slightly different construction in this case. Assume you have private / public keypair $(sk_A, pk_A)$ and your friends is $(sk_B, pk_B)$, the notation $function_{key}$ means perform $function$ using the key $key$ and $||$ represents concatenation:

1. Generate two keys, one for AES ($k1$) and one for a MAC e.g. HMAC ($k2$)

2. Sign your generated keys ($sig = \text{Sign}_{sk_A}(k1 \text{ || } k2)$) and send the signature and keys encrypted to your friend: $\text{Encrypt}_{pk_B}(k1 \text{ || } k2 \text{ || } sig)$.

   • Your friend should decrypt, verify the signature, and then grab the keys.

3. To send a message $m$ to your friend encrypt it to yield $c = \text{AES}_{k1}(m)$ and then send the message $(c \text{ || } \text{HMAC}_{k2}(c))$. This is the "Encrypt-Then-Mac" construction, whose security you can read about more here.

   • Your friend should upon receipt of a message verify the MAC and if it is OK then decrypt the ciphertext.

Note that the authenticity of your messages is established from the MAC, which in turn is established by the fact that you used your private key to sign the key ($k2$) used when computing the MAC.

Answer 2

If the key is send beforehand it is not required but highly recommended to sign it. Otherwise anybody could post an AES key, encrypted using the public encryption key of your friend. In that case your friend may only find out after receiving the right messages. Furthermore, your friend may not be able to distinguish between an invalid key and an invalid message; in other words, your AES key would need be trusted implicitly instead of explicitly.

If you'd change the scheme so your friend can send messages as well then he'd encrypt those messages for the wrong person. Furthermore, it would let you use an authenticated cipher afterwards, where messages are send with a symmetric authentication tag. Symmetric authentication is much more efficient than signing primitives. It also removes the problems with sign-then-encrypt vs encrypt-then-sign.

Note that you may need to use a hybrid cryptosystem such as ECIES to encrypt using a EC public key. You need to trust the public keys in this scheme somehow. Finally, you need to keep in mind that anybody can re-sign the AES encrypted key or messages after stripping off the original signature.

Good programming practices and layered security are both good reasons not to get into an invalid state, which happens if you manage to trust the wrong AES key initially.