Perfect Forward Secrecy

By Mick Ayzenberg

There comes a time in every security consultant's career when they must step up to the plate and rehash some old topics in a blog. It is a rite of passage to proudly share some insight into an interesting technical topic, often one that has already been covered to death, with hopes that their point of view will be just a tiny bit more interesting or understandable than the last article's.  Well this is that time for me and I've decided to write on the topical subject of Perfect Forward Secrecy.

I like the idea of discussing Perfect Forward Secrecy (PFS) for a few reasons. First, the term has become a very notable buzz word lately in relation to the recent government scandals we've all grown to love. Second, the math behind PFS is fairly simple to understand and  requires only a basic understanding of SSL and Public-key cryptography to be able to grasp of the ideas. Third, PFS is not supported nearly enough. Hopefully, when more people understand why PFS is  necessary, more organizations will decide it is important enough to require.

Perfect Forward Secrecy is a property of cryptography. It is implemented in certain cipher suites of SSL and offers tremendous privacy benefits. But before we go into what PFS accomplishes and how it works, lets talk about what we are trying to fix.

What is the problem?

We need the ability to communicate privately over the web. This fact is not debatable. A modern user of the web must have the ability to visit sites and communicate knowing that sensitive data (passwords, credit card numbers, etc) will arrive where it is intended to go without being viewed or tampered with. Right now SSL/TLS is primary protection for our browsers to prevent eavesdropping over the net. SSL/TLS uses a combination of asymmetric and symmetric cryptography to accomplish this.

When you visit a website and you see the little lock symbol next to the URL this informs you that your session is encrypted over SSL.  A lot of things are happening in the background during this communication.

Let's say, for example, you are visiting your bank's website that communicates over SSL.  A very simplified view of this connection is the following:

  1. Your browser asks for the bank's certificate, or public key, and verifies its legitimacy.
     
  2. Your browser creates a new, random, one-time, shared secret key.
     
  3. You encrypt this new secret with the bank's public key and send it to the bank over the internet.
     
  4. The bank uses the matching private key to decrypt the message and obtain the shared secret. Note that various properties of asymmetric cryptography prove the only way to decrypt a message encrypted with a public key is with the matching private key. The bank is the only entity with this matching private key
     
  5. All subsequent communications for the duration of the session are encrypted with the shared secret. Only you and the bank know this secret; only you and the bank can decrypt these messages.
     
  6. Once your session completes, the shared secret is discarded by both parties, never to use it again.

Now, this process contains many places where things can go drastically wrong. For example: 
•    The public key used in step 1 can be faked or compromised through various methods.
•    The secret/private keys might be small enough to discovered using brute force or crack.
•    The cryptographic functions used to encrypt and decrypt messages might be insecure.
•    The random number generators might be compromised.

 All of these are valid threat vectors for breaking SSL, but we are not going to focus on any of them today. We are going to assume that everything above just works.

Under our current assumptions we assume this methodology accomplishes what it set out to do.  You are choosing a secret that only your browser and your bank know and you are using it to encrypt all of your communication.  You are able to tell the bank, and only the bank, this secret because you encrypted it with their real public key and the only way they can decrypt it is with their real private key.

The threat we are going to explore here is around an attacker stealing the bank's private key. If an attacker obtains a private key, the key provides the ability to impersonate whomever the true owner is and the game is over. The attacker can trick your browser into thinking it is the bank in question and decrypt any messages you send to it without any warning.

Methods already exist to thwart this kind of breach in ways so that the attacker can't use old and stolen private keys, including revoking the certificate, and in some cases, shutting down the service altogether.

What makes this threat interesting is when an attacker stores all the encrypted internet traffic from across the planet in their colossal data centers until the end of time.  With the protocol defined above, an attacker would only need to obtain a private key, possibly months or even years later, and decrypt the message sent in step 3.  By decrypting that message, the attacker obtains the shared secret and can decrypt all the private communications of that session long after the fact.  

We are now aware that this is not only something that can be done, but something that is actively being done.

This is the problem that Perfect Forward Secrecy so elegantly solves.

What is PFS?

Perfect Forward Secrecy is a concept where communication between two parties is not only encrypted, but will remain encrypted even if their primary encryption keys are later stolen. In the context of SSL it is an exchange that allows a browser and a website to agree on a shared secret without ever needing to say what that secret is over the wire. This way even when private keys are stolen, they can not be used to decrypt the shared secret. Since the shared secret is needed to decrypt every subsequent message in the session the stored communication remains indecipherable.

The math behind this is surprisingly simple and intuitive.  It uses the Diffie-Hellman key exchange to create the shared secret using some simple properties of integers.

When simplified, Diffie-Hellman works something like this:

  1. Your browser comes up with two numbers that anyone can know, p and g. Let's say our numbers are p=5 and g=3.
  2. Your browser then picks a secret number that only it knows, a.  Let's say a=4
  3. Your browser sends the bank those two public numbers, p and g, along with (g^a) mod p.  
    • (3^4) mod 5 = 81 mod 5 = 1
    • The generalized form is (g^a) mod p = 1
  4. The bank then picks a secret number b, we'll say b=7, and sends back (g^b) mod p.
    • (3^7) mod 5 = 2187 mod 5 = 2
    • The generalized form is (g^b) mod p =2
  5. Since ( (g^a)^b) and ( (g^b)^a) are equal mod p, both parties can calculate ( (g^a)^b) mod p and agree that this value will be the shared secret.  
    • The bank can compute this because it knows bp, and (g^a) mod p:
      • ( ( (g^a) mod p) ^ b) mod p = ( (g^a)^b) mod p
      • ( (1) ^ 7) mod 5 = 1
      • Shared Secret = 1
    • The browser can compute this because it knows ap, and (g^b) mod p:
      • ( ( (g^b) mod p) ^ a) mod p = ( (g^a)^b) mod p
      • ( (2) ^ 4) mod 5 = 16 mod 5 = 1
      • Shared Secret = 1
    • Most interestingly, anyone who has intercepted the traffic will know pg(g^a) mod p, and (g^b) mod p, but there is no efficient way to generate ( (g^a)^b) mod p from those values. Thus an attacker who can see this traffic will still not know the shared secret.

    * Note: the algorithm above was highly simplified and used small numbers for clarity.  To ensure the shared secret is not cracked p must be prime,  must be primitive root mod p, and all integers must be much larger.

If you add this key exchange method into the graph from before it will look something like this:

  1. Your browser requests the bank's certificate, or public key, then verifies its legitimacy.
     
  2. Your browser creates "p", "g" and "a" for its side of the Diffie-Hellman exchange.
     
  3. You  encrypt the Diffie-Hellman
    parameters using the bank's public key and send it to the bank over the internet.
     
  4. The bank generates a value for "b" and responds in the clear with its Diffie-Hellman parameters.
     
  5. Both the browser and the bank now agree on a shared secret that was never explicitly stated. 
     
  6. All the rest of the communication is encrypted with that shared secret that only you and the bank know.
     
  7. Once your session has completed the shared secret, variable a, and variable b are discarded by both parties and never used again.

The server's public key is still used to guarantee authenticity of the web server. The new shared secret is freshly generated every session and once the Diffie-Hellman parameters have been deleted, the private key can not be used against stored traffic.

What's next?

We have to live with the fact that all encrypted internet traffic will be stored permanently.  We also have to live with the fact that the websites we trust so dearly may eventually have to surrender their private keys.  What we don't have to live with is that those private keys will be able to decrypt our session's data years later.  There are already SSL cipher suites that support PFS such as the following:

ECDHE-RSA-AES128-GCM-SHA256
ECDHE-RSA-RC4-SHA
DHE-RSA-AES256-SHA

You can identify suites with PFS look for either DHE (Ephemeral Diffie-Hellman) or ECDHE (Elliptic Curve Ephemeral Diffie-Hellman) in the name. In order to mitigate this threat these suites must be supported and prioritized by browsers and web servers by default.

Hopefully over time web servers will begin to support PFS suites by default in the same way that many sites are now migrating to SSL all the time. I'm crossing my fingers that this happens sooner than later.

Originally Posted at zuxsecurity.blogspot.com