Forward Secrecy posted December 2014

I was asked during an interview how to build a system where Alice could send encrypted messages to Bob. And I was asked to think outloud.

So I imagined a system where both Alice and Bob would have a set of (public key, private key). I thought of RSA as they all use RSA but ECIES (Elliptic Curve Integrated Encryption Scheme) would be more secure for smaller keys. Although here ECIES is not a "pure" asymmetric encryption scheme and Elgamal with ECs might be better.

Once one wants to communicate he could send a "hello" request and a handshake protocol could take place (to generate a symmetric encryption key (called a session key in this case)).

I imagined that two session keys would be generated by each end. Different set of keys depending on the direction. One for encrypting the messages and one for making the MAC (that would be then appended to the encrypted message. So we EtM (Encrypt-then-Mac)).

Then those keys would be encrypted with the public signature of the other one and sent over the wire like this. And Let's add a signature so we can get authentication and they also won't get tampered. Let's use ECDSA (Elliptic Curve Digital Signature Algorithm) for that.

Although I'm wondering if two symmetric keys for encrypting messages according to the direction is really useful.

I was then asked to think about renewal of keys. Well, the public keys of Alice and Bob are long term keys so I didn't bother with that. About the symmetric keys? What about their TTL (Time To Live)?

My interviewer was nice enough to give me some clues: "It depends on the quantity of messages you encrypt in that time also."

So I thought. Why not using AES in CTR mode. So that after a certain number of iteration we would just regenerate the symmetric keys.

I was then asked to think about Forward Secrecy.

Well I knew the problem it was solving but didn't know it was solving it.

Mark Stamp (a professor of cryptography in California (how many awesome cryptography professors are in California? Seriously?)) kindly uploaded this video of one of his class on "Perfect Forward Secrecy".

So here the trick would be to do an Ephemeral Diffie-Hellman to use a different session key everytime we send something.

This EDH would of course be encrypted as well by our public key system so the attacker would first need to get the private keys to see that EDH.