How is it possible that people observing an HTTPS connection being established wouldn't know how to decrypt it?

Question

I've often heard it said that if you're logging in to a website - a bank, GMail, whatever - via HTTPS, that the information you transmit is safe from snooping by 3rd parties. I've always been a little confused as to how this could be possible.

Sure, I understand fairly well (I think) the idea of encryption, and that without knowing the encryption key people would have a hard time breaking the encryption. However, my understanding is that when an HTTPS connection is established, the encryption key is "discussed" between the various computers involved before the encrypted connection is established. There may be many factors involved in choosing an encryption key, and I know it has to do with an SSL certificate which may come from some other server. I do not know the exact mechanism.

However, it seems to me that if the encryption key must be negotiated between the server and the client before the encryption process can begin, then any attacker with access to the network traffic would also be able to monitor the negotiation for the key, and would therefore know the key used to establish the encryption. This would make the encryption useless if it were true.

It's obvious that this isn't the case, because HTTPS would have no value if it were, and it's widely accepted that HTTPS is a fairly effective security measure. However, I don't get why it isn't true. In short: how is it possible for a client and server to establish an encrypted connection over HTTPS without revealing the encryption key to any observers?

Answer 1

It is the magic of public-key cryptography. Mathematics are involved.

The asymmetric key exchange scheme which is easiest to understand is asymmetric encryption with RSA. Here is an oversimplified description:

Let n be a big integer (say 300 digits); n is chosen such that it is a product of two prime numbers of similar sizes (let's call them p and q). We will then compute things "modulo n": this means that whenever we add or multiply together two integers, we divide the result by n and we keep the remainder (which is between 0 and n-1, necessarily).

Given x, computing x³ modulo n is easy: you multiply x with x and then again with x, and then you divide by n and keep the remainder. Everybody can do that. On the other hand, given x³ modulo n, recovering x seems overly difficult (the best known methods being far too expensive for existing technology) -- unless you know p and q, in which case it becomes easy again. But computing p and q from n seems hard, too (it is the problem known as integer factorization).

So here is what the server and client do:

• The server has a n and knows the corresponding p and q (it generated them). The server sends n to the client.
• The client chooses a random x and computes x³ modulo n.
• The client sends x³ modulo n to the server.
• The server uses its knowledge of p and q to recover x.

At that point, both client and server know x. But an eavesdropper saw only n and x³ modulo n; he cannot recompute p, q and/or x from that information. So x is a shared secret between the client and the server. After that this is pretty straightforward symmetric encryption, using x as key.

The certificate is a vessel for the server public key (n). It is used to thwart active attackers who would want to impersonate the server: such an attacker intercepts the communication and sends its value n instead of the server's n. The certificate is signed by a certification authority, so that the client may know that a given n is really the genuine n from the server he wants to talk with. Digital signatures also use asymmetric cryptography, although in a distinct way (for instance, there is also a variant of RSA for digital signatures).

Answer 2

Here's a really simplified version:

1. When a client and a server negotiate HTTPS, the server sends its public key to the client.
2. The client encrypts the session encryption key that it wants to use using the server's public key, and sends that encrypted data to the server.
3. The server decrypts that session encryption key using its private key, and starts using it.
4. The session is protected now, because only the client and the server can know the session encryption key. It was never transmitted in the clear, or in any way an attacker could decrypt, so only they know it.

Voilà, anyone can see the public key, but that doesn't allow them to decrypt the "hey-let's-encrypt-using-this-from-now-on" packet that's encrypted with that public key. Only the server can decrypt that, because only the server has that private key. Attackers could try to forge the response containing an encrypted key, but if the server sets up the session with that, the true client won't speak it because it isn't the key that the true client set.

It's all the magic of asymmetric key encryption. Fascinating stuff.

P.S. "really simplified" means "mangled details to make it easier to understand". Wikipedia "Transport Layer Security" gives an answer more correct in technical particulars, but I was aiming for "easy to grok".

Answer 3

The other answers are good, but here's a physical analogy that may be easier to grasp:

Imagine a lock-box, the kind with a metal flap that you put a padlock on to secure. Imagine that the loop where you put the padlock is large enough to fit two padlocks. To securely exchange send something to another party without sharing padlock keys, you would

1. put the "Thing" in the box, and lock it with your padlock.
2. send the locked box to the other party.
3. they put their padlock on the loop also (so that there are two locks on it), and return the double-locked box to you
4. You remove your padlock, and return the now singly-locked box to them
5. they remove their own lock and open the box.

With encryption the locks and keys are math, but the general concept is vaguely like this.

Answer 4

A lot of the answers already provided are overlooking the interception capability of the ISP or NSA. Take a look at Room 641A in the AT&T datacenter. There are an estimated 10 to 20 such facilities that have been installed throughout the United States. Also take a look at the One Wilshire building where 260 ISP's connections converge into one building. That location is a prime location for an interception facility.

The fact is an ISP (or the equipment installed by the NSA in the ISP) can intercept and MITM attack an SSL connection and they can do it quite easily actually.

• Your web browser or operating system has over 500 trusted certificates installed in it. This means that you implicitly trust any website whose certificate has been signed by this certificate.
• The NSA via secret FISA court order can force any Certificate Authority operating in the United States to give them their root certificate. The court order includes a special non disclosure clause which forces the CA to keep their mouth shut under penalty of jail time if they speak out about it. They may not even need to do this however, they only need to convince the browser vendors to accept one NSA owned certificate as trusted in the browser.
• As your traffic passes through the ISP they swap out the website's true public key with the NSA's own public key signed by the compromised certificate authority thus performing the MITM attack.
• Your web browser accepts this false certificate as trusted and you communicate the symmetric encryption key for the exchange back to the NSA/ISP who keep a copy of it and also pass the same key onto the website.
• Your session with the website is decrypted in real-time with the compromised symmetric key.
• The decrypted data is sent via fibre optic line to the NSA's headquarters and data center in the basement of Fort Meade. This scans the data for hundreds or thousands of keywords that may indicate various types of threats. Any keywords are red-flagged for an analyst to view and prioritize further action if any. The final data is sent to one of the NSA's data storage facilities in the US. The new storage facility is the Utah datacenter which is likely online already as it was scheduled to be online at the end of last month.

Here's a diagram from nsawatch.org:

Answer 5

In simple words: There are two different encryptions taking place:

• First there is the public/private key encryption. The client uses the public key of the server (which is included in the certificate) to encrypt some information that only the server can decrypt using it's private key.

• Based on this information a session key is derived, that is only known to the server and the client. This session key is used to encrypt that data.

This is a very rough summary.

There is a lot more taking place to prevent various kinds of attack:

• For example the client tries to validate the certificate of the server to ensure that he is not talking to a man in the middle.
• There are different algorithms and key lengths for the session keys that have to be negotiated
• Random numbers that are only used once are used to prevent replay attacks.
• The Diffie-Hellman key exchange protocol can be used to generate a session key that cannot be reconstructed by someone who recorded the encrypted data transmission and gets access to the private key of the server at a later time (Perfect forward secrecy).
• ...

Answer 6

I think of the six answers already up, gowenfawr's explains it best. Read that first as this is simply an addendum.

On Diffie-Hellman

Several answers mention Diffie-Hellman exchanges. These are implemented in a minority of exchanges. A DH exchange is signed by the server's key to prevent a MITM attack. Because the key is not encrypted to a public key, it cannot be recovered by using a captured private key against captured traffic of a key exchange. This is the idea of Perfect Foward Secrecy. OpenSSL provides for both "regular" and DH key exchanges depending on configuration.

On MITM / Signature chains

Both public-key and DH exchanges prevent somebody from observing the connection and deriving the key. This is based on a whole bunch of math problems that you can research / look at Thomas' answer to understand. The problem with either is the MITM attack. For public key cryptography, this is fixed by either knowing the public key beforehand (even if the exchange is observed) or by way of a certificate chain. Examples: I trust Alice, and Alice signed Bob's key certifying it really is his. Also known as Google is certified by... err, Google. It appears they're in Firefox as their own CA. So, random_bank's_ssl is signed by Verisign, and my browser trusts Verisign to only issue legitimate certs.

Problems do exist with this model when you run into things like a certificate authority being compromised. In that case, an MITM attack becomes possible.

Answer 7

SSL relies on public key cryptography. A server that participates in SSL has a keypair, which has public and private components.

Imagine you have a special lockbox with two keys: one key can lock the box, and another can unlock the box. If your friend wants to send you a secret message, he only needs the locking key, and you can keep the unlocking key private.

In fact, you can freely give out your locking key to everyone. You decide to leave out copies of your special lockboxes and locking keys on your front porch so anyone can have a copy. Soon, everyone in your whole town can send you secret messages in mail. You've made your locking key public.

If your friend Alice wants to send you a secret message, she puts her message inside a lockbox and locks it with a copy of your public locking key. The postmaster of your town is very suspicious of you and Alice, but -- even though he, too, has access to your public key -- he cannot open the lockbox. Only you, the sole owner of the private unlocking key, can open the box that Alice locked.

Thus, your ISP (here, the postmaster) has access to your public key, but that doesn't help them decrypt messages encrypted with your public key. Your public key only encrypts, and only your private key decrypts. Thus, your private key never leaves your possession, so no has access to it except you, and therefore no one can eavesdrop on your messages.

There's a bit more protection that SSL gives you (e.g., suppose the postmaster throws away Alice's box and sends a new message to you pretending to be Alice), but this should clarify why your ISP can't simply decrypt your messages.

Answer 8

Look at Diffie Hellman : http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

For performances reasons, the connection is encrypted with symmetric key. But the symmetric key is generated during connection establishment and never exchanged in clear, but using asymmetric cryptography.

Asymmetric cryptography is a technique were two key are needed : a public one and a private one. What is crypted with the public key has to be decrypted with the private key and the other way around. So both computer can exchange data based on each other public keys. But only the owner of the corresponding private key can decrypt it. The private key is never exchanged, so, even if you have sniffed everything, you cannot decrypt anything. Those technics are expansive, so are used to exchange the key for symmetric cryptography's key and not data themselves.

Answer 9

Transport Layer Security (which is what Secure Sockets Layer is now called) involves methods of securely exchanging cryptographic keys over an insecure communications channel (like the internet).

Yes, this means that the ISP can see the key exchange information as it passes back and forth, and yet still has insufficient information to read the message stream once a secure connection has been established.

A very strange concept, and it's quite a new bit of work. The most common example of this is called Diffie-Hellman Key Exchange, and was only invented in the 1970's.

The Wikipedia article has all the delicious mathematical detail, but I find the image below (from Wikimedia) illustrates the concept perfectly. Look at it, think about it, even try it out for yourself, and you'll find that there is no way for an opponent to derive the private key from the publicly viewable information.

Answer 10

If I put my black hat on (not this black hat... actually that hat also works):

An ISP can simply perform a man-in-the-middle-attack on any of your HTTP downloads of applications or their patches and thus update the browser trust chain directly or update it indirectly with a self-destructing trojan.

Microsoft only requires drivers to be code-signed; digital signatures for applications and application-equivalent executable data are not enforced by default*. Most consumer operating systems are no better if simply because mandatory application code-signing (and identity verification) would cost just enough to drastically shrink the size of their software ecology.

_{* I make a point of not linking to Microsoft Answers unless I have to. Their trained monkeys are obviously using broken typewriters.}

Answer 11

The key thing there is asymmetrical, or public key encryption. It means you have two pieces of key, public and private, and a mathematical function that is easy to calculate to one direction but very, very hard to calculate to the other.

So, when servers sends its public key, we can use the public key to easily encrypt our stuff, but only with the another key of the pair, private key in this case, you can easily decrypt it.

Answer 12

The EcoParty Conference announced a tool called BEAST that reportedly decrypts SSL3/TLS1.0 traffic and lower, presumably by observing it.

Here is a link to the news report

I'm sure over the coming days we will hear more about this, the workarounds and limitations.

This section below will be updated as more information is discovered

This hack assumes the attacker can somehow see your network traffic; though spyware or through a network capture. Poorly administered machines, and Wifi users are the most likely the usual suspects… though not limited to that use-case.

There are reports that we can mitigate this risk by changing the SSL*/TLS 1.0 cipher list to RC4, and not supporting older combinations. Another mitigation is to increase the length of the authentication token, which would slow down the attack. Modifying the Siteminder and ASP.net membership authentication cookie configuration may help here.

Just so you know this vulnerability is exposed by the same people who announced the “Padding Attack on ASP.NET” last year. That old issue puts every IIS webserver at risk just by being turned on, which appears to be more serious than this attack.

Do share any links you find that mention or confirm these vulnerable scenarios, or mitigations here. As it stands now, some of this is speculation and not vetted by Cryptology experts.

Answer 13

No, they wouldn't hold the key as the connection you are making is between you and the target site (e.g. Amazon) so the ISP would have no knowledge of the key.

The more general question of how SSL/TLS works is answered here.

Answer 14

There are lots of great answers here, especially the ones that talk about the issues beyond performing DH or ECDH (e.g. client side corruption/cert installation/cert hijacking, et cetera.)

If you're ignoring the local machine itself and simply worried about MITM - you need DH/ECDH AND SSL pinning. SSL pinning is becoming more common, but is still not ubiquitous today. This means that your ISP can simply pretend to be your server as long as it has a valid SSL in your root chain of trust. SSL pinning ensures that the SSL cert used by the server you connected to IS the cert of the server you're trying to get to.

Again, if you're looking to be safe from the government or hackers - this is not enough. If you're looking to keep your ISP from looking through your data - this is probably enough.