# Key exchange problem

I've found the following problem in one of my courses. Any tips on how to solve this would be appreciated!

Alice has the key pair $(pka,ska)$. Bob has the pair keys $(pkb,skb)$. They want to establish a secret common key $k$ for a fast encryption (using $AES$).

1. How?
2. How if both want to participate in choosing the key (none of them trusts the other)
• What can they both do with the keypairs (sign / encrypt)? Do both parties know each other's public key in advance? May 14, 2016 at 18:33
• "none of them trusts the other" You don't share secrets or keys with parties you don't trust. I'd throw away the public key from the trust store if it is in there. Moronic questions deserve moronic answers. I understand that they probably mean Diffie Hellman, but come on... May 14, 2016 at 22:56
• Just saying that neither side trusts the other doesn't really provide enough info; this is more of a political question than a crypto one. Does Alice think Bob has a bad CSPRNG, but otherwises trusts his character? Does she think his computer is compromised? Does she think Bob is secretly evil and is going to send her key to an attacker? Or does she think Bob is going to send her plaintext to an attacker (why is she sending it to him in that case)? There is always going to be some amount of trust when dealing with secrets.
– user40185
Nov 11, 2016 at 15:13

Depends how secure you want it to be. Do you want to be safe against MITM, against passive attackers, against active attackers, against replay attacks, ... and so on.

Even though that posting links is not that good, I would strongly suggest to read that paper: http://cs.unc.edu/~fabian/course_papers/needham.pdf "Using Encryption for Authentication in Large Networks of Computers" - Needham, 1978.

On the second page it has a nice description of quite a secure protocol for that. ("Protocol 2. With Public-Key Algorithms "), though you would have to modify it since you don't have a CA which both parties trust. (and, as a result, be vulnerable to some attacks)

Also, take a look on TLS. TLS could be with server authentication, client authentication, or both present or both missing. Option 4 is for you, since you do not have any CA's mentioned in your question.

Here is such a protocol.

Alice chooses a random AES key $K_a$, encrypts it using Bob's public key to get $C_a = \mathrm{Enc}_{pk_b}(K_a)$, and sends $C_a$ to Bob. Likewise, Bob sends $C_b = \mathrm{Enc}_{pk_a}(K_b)$ for a random AES key $K_b$.

Upon receiving $C_a$, Bob recovers $K_a = \mathrm{Dec}_{sk_b}(C_a)$ and computes the shared AES key $K_{ab} = K_a \oplus K_b$. Similarly, Alice computes the shared AES key $K_{ab} = K_a \oplus K_b$ from $K_a$ and $K_b = \mathrm{Dec}_{sk_b}(C_a)$.

Alice and Bob can now use the shared AES key $K_{ab}$.

Remark 1: It is important that both Alice and Bob participate in the generation of the shared AES key.

Remark 2: To authenticate the communication, one may also require Alice and Bob to sign their exchanged values.

• If Bob receives $C_a$ before he sends out $C_b$, he can select any key he wants, by selecting $K_b = K_a \oplus K_{evil}$. If you want to make sure that Alice participates in the key exchange, this is a problem. One easy solution is a) to have Alice and Bob exchange $Hash(K_a), Hash(K_b)$ values first, and b) prohibit $K_a = K_b$; this allows both sides that the other side selected their values before seeing the other. May 15, 2016 at 2:56
• @poncho: Assuming that Alice and Bob follow the protocol, the goal here was to make sure that the randomness of both Alice and Bob was incorporated in the shared key. For example, if Alice's random number generator is poor, the output will be good provided that Bob's random number generator is good. May 15, 2016 at 14:40
• @poncho: What do mean by $K_{evil}$? For example, if the key $K_{ab} = 0$ is a evil key, this can be checked by Alice at the end of the protocol. The same is true for other types of evil keys. May 15, 2016 at 14:52
• I would disagree that the goal of the protocol is, assuming that we trust both parties to be honest, would work even if the rng on one of sides is weak. Instead, the question specifically states "neither side trusts the other" - allowing Bob total control of the key (should he choose to) doesn't do this. As for what $K_{evil}$ is, that is a preselected value that Bob aims the key to be. Perhaps that's a value that he has shared with a confederate outside of the protocol; Alice cannot check this type of evil key. May 15, 2016 at 17:14
• Meh, you could just leak the shared key after performing the encryption. I don't see that as a huge hurdle for Bob or anybody he collaborates with. Jul 14, 2016 at 17:00