My custom handshake

Question

I designed a custom handshake between 2 entities $\rm C$ (client) and $\rm S$ (server) which should meet the following requirements:

Requirements:

The handshake should make:

• $\rm S$ know who is $\rm C$,
• $\rm C$ make sure that he is talking to $\rm S$,

... without letting anyone who is listening the communication line know:

• what is $\rm S$'s public key,
• what is $\rm C$'s public key,
• whether or not a specific $\rm C$ with a well known public key is in the contact list of a specific $\rm S$ with a well known public key.

My handshake:

1. $\rm C$ opens a connection to $\rm S$.

2. $\rm C$ sends a random cipher's symmetric key $K_1$ to $\rm S$, encrypted using $\rm S$'s public key. Then $\rm C$ uses $K_1$ in a symmetric cipher to encrypt all the following data:

   • timestamp,
   • 2 first bytes of $\rm C$'s public key.

   • $\rm C$'s signature, where the hash is computed from:

     • $K_1$,
     • timestamp,
     • $\rm S$'s public key.

3. $\rm S$ receives it and decodes it using his private key. If the timestamp is too far from now or If the signature cannot be verified then close the connection. Otherwise the message is considered valid, then $\rm S$ sends back the following concatenated message to $\rm C$, encrypted using $\rm C$'s public key:

   • a random cipher's symmetric key $K_2$.
   • a hash of $\rm C$'s signature from the previously received message.

4. $\rm C$ takes $K_2$ and verifies that the hash is from the signature that he previously sent. If it doesn't match he closes the connection.

5. Both $\rm C$ and $\rm S$ compute $K$ by combining $K_1$ and $K_2$ together. They now have a shared secret that they will use to encrypt and decrypt any further message via a symmetric encryption algorithm.

Notes:

• $\rm C$ and $\rm S$ know each other's public key.
• the handshake description is also available on this page.

Question: I would like to know if my handshake meets its requirements.

EDIT:

• The asymmetric encryption algorithm used is RSA with 4096 bits keys.
• The symmetric encryption algorithm used is AES-256.
• The shared secret algorithm used to combine $K_1$ and $K_2$ is Diffie-Hellman.

Answer 1

No, the handshake does not meet your requirements.

Nowhere do you state that the asymmetric encryption algorithm used does or must have the property that it not be possible to extract the particular public key used to encrypt a particular message. This doesn't violate any of the basic rules of an asymmetric encryption algorithm which only requires that that messages encrypted with the public key cannot be decrypted without the private key.

So, assume the implementation uses an algorithm that does have this property. An interceptor can then receive the encrypted key sent in the first step and extract S's public key from it. Oops.

You either need to specify the particular algorithms and data structures used or you need to impose appropriate constraints on the algorithms chosen to ensure the security requirements are met.

Answer 2

First off just use SSL. It has a client authentication scheme built in and is way better tested and thought out than things that anyone can come up with.

So there are a few things that just don't add up.

First you use diffie hellman to have two public keys that want to decide on a private key. In this instance you have two shared secrets you want to compute a third master secret. You could hash them, then make each one it's own DH key in some group and then combine them but it's way overkill for no reason. For your purposes probably use HMAC(K1,K2)

Next, If everythings a 4096 bit key, then they'll usually start out with the same number. 4096 bit means its around 2**4096 as such, your identifier is pretty much useless. I'd suggest hashing the key, and using that as an identifier.

Third there's an actual signature operation in public key cryptography. Use it. You also arguably have message confusion unless you fix the length of the timestamp.

Fourth- You need an iv somewhere. Else I can easily see who it is since the timestamp may not actually influence the public key identifier. As such an attacker listening on the wire can figure things out about who's talking.