Why the symmetric key is added to the message?

Question

Yesterday in my class we learnt how to send a message from Alice to Bob with the achieved goals of confidentiality, integrity and authenticity. In order to have a better performance we use a hybrid method with a symmetric and an asymmetric key.

Alice's and Bob's private Keys are signed by a Certification Authority (CA) -> Authenticity

The goal of integrity is assured thanks to the hash:

h = hash(M)

Confidentiality is used assured thanks to the usage of a symmetric key only known to Alice and Bob which was exchanged thanks to their asymmetric keys.

This all results in the following message - which Alice sends to Bob:

# public keys    
K_A_E = public_key_Alice
K_B_E = public_key_Bob

K_B_E and K_A_E are signed by a CA.

# private keys
K_A_D = private_key_Alice


M = "our secret message"
h = hash(M)

K_AB = the_symmetric_key

this results in the message:
{K_AB}**K_B_E {{h}**K_A_D, M}**K_AB

I don't understand why it is necessary to start the message with {K_AB}**K_B_E.

* Why it is necessary to prepend the symmetric key K_AB at the beginning of the message?

* Is this symmetric key added to every message sent between Alice and Bob?

* Our lecturer mentioned that this way of encryption is used in OpenPGP. So does OpenPGP create a new symmetric key for every message?

Answer 1

To answer your questions:

{K_AB}**K_B_E is prepended to the message so that the receiver has the symmetric key to decrypt the message. Because the key K_B_E is used only Bob can decrypt the symmetric key and only he can therefore read the message.

The next is the hash {h} which is encrypted/signed by the key K_A_D. I assume that K_A_D is the private key of Alice, so this is the signature of the message.

The symmetric key is created newly for each message by the sender. And the sender has to send the key for decryption purposes to the receiver. Therefore the key is prepended (asymmetrically encrypted) to each message.

Yes, GPG and OpenPGP use this scheme.

As an extension:

I can prepend multiple (asymmetrically) encrypted keys to the message so that I can send the message to multiple receivers.

If I use a pre-shared key then I have to send the message either multiple times or have to share the symmetric key with multiple persons. This would make this scheme insecure. That's the reason why I create a new symmetric key for each message.

Also note that GPG/OpenPGP do not use a CA but create a Web of Trust to authenticate all other participants.

Answer 2

Your notation seems to relate to hybrid encryption. The message is encrypted with a symmetric key K_AB; that key was probably generated randomly by the sender. For the recipient to know it, it is necessary to send it along with the message, but not as clear text, of course: K_AB is encrypted with the recipient's (Bob's) public key.

Thus, Alice does the following:

1. Generate K_AB with some strong PRNG.
2. Encrypt the message symmetrically with K_AB as key; this is what {{h}**K_A_D, M}**K_AB means (I take "**" to mean "encrypt with").
3. Encrypt K_AB with Bob's public key: {K_AB}**K_B_E
4. Send both encrypted blobs to Bob.

Then Bob does this:

1. Decrypt {K_AB}**K_B_E with his private key, thus recovering K_AB.
2. Using K_AB, decrypt {{h}**K_A_D, M}**K_AB, yielding the message M.

This process with two encryptions is made necessary by the fact that asymmetric encryption algorithms (like RSA) cannot handle bulk data (people usually say that the problem is one of performance -- symmetric encryption like AES being much faster than asymmetric encryption like RSA -- but that's a semi-myth; the real problem is that RSA cannot encrypt messages longer than a hundred bytes or so).

---

Your description also shows something with a hash value and some sort of encryption with a key K_A_D. I suppose this is an attempt at talking about either a MAC or a digital signature. Many people try to explain signatures as being some kind of "encryption in reverse". This is a widespread but awful explanation that spreads only confusion.

Answer 3

Only the last line is the actual message sent.

Symmetric encryption is generally much faster and potentially more future proof than asymmetric cryptography. It requires far shorter key lengths for security. Since it is the intent to share the entire message with Bob, Alice doesn't have to encrypt the entire message (long) with Bob's public key.

Instead, she encrypts the entire message with a fresh symmetric key that she has generated. This makes the encryption and decryption of the message fast, but she needs a way to share the key with Bob, who doesn't have it.

To share the key, she takes the public key of Bob and encrypts the message symmetric key (short) with it. She adds this to the message as additional data.

When Bob gets the message, it is a simple and quick matter to use his private key to unlock the symmetric key (which only he can do since only he has the private key for it) and can then use that symmetric key to decrypt the entire message.

The hash of the message (which is then signed by Alice's private key which can be tested with Alice's public key) is added so that Bob can know that Alice is actually the sender of the message and it wasn't altered in transit, though a slightly faster variant would be to hash the symmetric key itself and sign that (or simply encrypt the symmetric key with Alice's private key to minimize message size).

As long as the security of the symmetric key is preserved until Bob gets the message, it still proves to Bob that Alice's message wasn't altered as nobody else could have encrypted a new message since nobody else knew the key. It is faster since it has a much shorter thing to hash (or even requires no hash if just encrypting with the private key), however it also doesn't provide quite as much authentication.

It proves to Bob that the message came from Alice and isn't altered, but after Bob has the key, it can't be used to prove to a third party that Bob hasn't altered the message. If the message must be able to be proved to be from Alice to additional people besides Bob, then Alice must sign the entire (plaintext) message.

Answer 4

Took a while to wrap my head around the bizarre syntax your lecturer is using, but basically the symmetric key is a "session" key generated per message and not reused. Hence the need to include an encrypted copy of it in the final message.

I'm assuming H**K_A_D is Alice encrypting the message digest with her private key.