13

I realize something like this would be the holy grail of communications security and have never heard anything to suggest it has been done.

Am just wondering. A lot of mathematicians and computer scientists spend time doing proofs for theoretical situations. Has anyone done a proof to rule out the possibility of ever doing a key-exchange (or some other encryption setup) over an open or already compromised line?

To be clear I mean : A and B are communicating while C has the potential to be listening (ideally C is not listening in real time and is only logging A&B for action later). Is it impossible for A and B to ever exchange information over the compromised line to setup a new encrypted line that C can't immediately crack?

Last Clarification : I'm realizing public key may technically satisfy the problem by not transferring the whole method of encryption over the line. Is there anything else you do, even if only theoretical? This feels like more of a loophole than directly solving things.

Vigilant
  • 287
  • 2
  • 6
  • 4
    ...PKI is built to solve this exact problem. – ztk Jul 21 '15 at 01:44
  • 1
    PKI needs pre-distributed keys and pre-established trust in a common root, which is not always possible. – Mike Ounsworth Jul 21 '15 at 01:46
  • 11
    PKI only solves the problem if there is a second, trusted communication channel available (though this channel can be highly indirect or temporally separated). It can't function if the only available channel is compromised. – Mark Jul 21 '15 at 01:51
  • 3
    Is there a reason why public key cryptography is a "loophole"? It fulfils the requirement of enabling confidential exchange of secret information over a line subject to eavesdropping. – Soron Jul 21 '15 at 02:20
  • 6
    @MikeOunsworth - in the case of active modification of the communications channel, I agree, you're hosed without a previously exchanged key. But it sounds like this question is about passive eavesdropping, rather than active modification of the data stream. – Soron Jul 21 '15 at 02:43
  • +1 to Ethan. @MikeOunsworth The asker is very clear about Eve's (or C's) MO here. They're only logging the communication for later analysis - not actively interfering. As such, public key cryptography fully satisfies the threat model here. If Eve *was* modifying traffic in real-time, then you'd have to worry more about authenticity. Public key cryptography still serves this, but there needs to be a certain amount of data exchanged securely in advance. (Either the public keys themselves, or the public key of a trusted signing authority.) – Iszi Jul 21 '15 at 16:12
  • @Mark See above. – Iszi Jul 21 '15 at 16:21
  • I think this is too pedantic. The problem is authenticating the other end, and having secure computers on both ends. Key exchange is a solved problem, and authentication mostly so. In the worst case, get into a video chat to authenticate. Do the DH key exchange with your eyes open (verify the key exchange) from your secure computer. – Rob Jul 22 '15 at 02:15

6 Answers6

70

If the attacker is only passively listening to the connection then Diffie Hellman Key Exchange can be done to create a common key known only to the communication peers.

But, if the attacker can not only listen to the connection but also actively modify the transferred data, then the attacker might mount a man-in-the-middle attack and claim to be the expected communication partner for both A and B. This can only be prevented if A can identify B before starting the encrypted communication and thus knows that it exchanged the key with the expected partner. For this it needs a secure way to verify the identity even if the line is compromised. This can be done by public-key cryptography. But of of course it needs some kind of prior knowledge about the expected identity of B, i.e. either A knows B already (direct trust) or it knows somebody who knows B etc (trust chain).

You'll find an implementation for all of this with SSL/TLS and the associated PKI. This is used with https in the browsers and the necessary trust anchors for building the trust chain are the public certificate agencies which are either known by the operating system or by the browser. For more information see How does SSL/TLS work?.

Community
  • 1
Steffen Ullrich
  • 190,458
  • 29
  • 381
  • 434
  • "A and B are communicating while C has the potential to be listening (ideally C is not listening in real time and is only logging A&B for action later)." seems to indicate a passive adversary, which would rule out MITM. Regardless, good answer. – puzzlepalace Jul 21 '15 at 06:09
  • 5
    @puzzlepalace Steffen is just covering all bases. Well done. – Mindwin Remember Monica Jul 21 '15 at 14:28
  • 5
    @danielAzuelos FWIW, It is mentioned in the linked wiki article. In the context of this answer, the history doesn't add anything useful. – Dev Jul 21 '15 at 16:10
  • 2
    @danielAzuelos I doubt the entire industry is going to change the name of a long-standing cryptographic standard, solely for the sake of historical accuracy. And making special notation about that history in an answer here, where such history is irrelevant to the question at hand, is really pretty pointless. A more appropriate place to raise such concern would be on the linked Wikipedia article. However, it seems there's no point in that either since the second paragraph already addresses it. – Iszi Jul 21 '15 at 16:18
  • 11
    @danielAzuelos, for purposes of intellectual credit, the scientific community has a long-standing tradition of giving credit to the first person to discover *and* publish the result. If X discovers an idea first but doesn't tell anyone about it, X doesn't get the credit in the scientific literature. There are good reasons for this: it doesn't do anyone any good if you don't tell the world about your discovery. So, our naming convention for Diffie-Hellman *is* consistent with standard practices in the scientific community; this is not intellectually dishonest. – D.W. Jul 21 '15 at 17:58
  • To tack on to D.W.'s observation and deepen the tangent, the fact that it's NOT called "CEW (Cocks Ellis Williamson) Key Exchange" is the professional JOY of OPSEC professionals, not their regret. To remain hidden so that others don't even know what question to ask/what to look for is ideal. – Smithers Jul 21 '15 at 18:04
  • 1
    @danielAzuelos: If you work for parties that are actively compromising the public's security rather than publishing your new findings in cryptography, losing the chance to be recognized for your work seems pretty fair... – R.. GitHub STOP HELPING ICE Jul 21 '15 at 23:34
  • 2
    Amanda and Neil get on video chat and sharpie themselves with DH key exchanges, then resume the connection under the new key. They know each other well, so don't expect real-time video manipulation by the man in the middle to fool them. If you try to authenticate with somebody you don't actually know, you haven't really authenticated no matter what tech you used; as your new friend is an NSA employee. – Rob Jul 22 '15 at 02:31
  • → D.W.: thank you :). I didn't see it under this light. Fully agree. ⇒ will remove my comment. – dan Jul 22 '15 at 07:28
9

There is indeed a solution to this problem! It's called the Diffie-Hellman Key Exchange protocol.

You can read a good description at the wikipedia link, but the basic idea is that Alice and Bob each have their private keys and corresponding public keys. From the magic of the Diffie-Hellman math, 

PublicKey_Alice + PrivateKey_Bob = SharedSecret

and

PublicKey_Bob + PrivateKey_Alice = SharedSecret

both parties end up with the same shared secret. Thus A) only public keys were exchanged over the insecure network, and B) in order to crack the shared secret, you need to know either Alice's private key or Bob's private key. (You can find the details of the math by a quick Google, so I won't go into them here.)

So yes, Diffie-Hellman is considered a secure way for two parties to establish a shared symmetric encryption key, even over an insecure network where Charlie is listening to everything they exchange.

Mike Ounsworth
  • 58,107
  • 21
  • 154
  • 209
  • I'm not sure this works @MikeOunsworth. DH allows secure communication but don't you need PKI or similar tech to know that you're communicating with your intended partner and not a MiTM. – Neil Smithline Jul 21 '15 at 03:29
  • Ah. @SteffanUllrich's [answer](http://security.stackexchange.com/a/94508/10885) mentions that PKI is needed. – Neil Smithline Jul 21 '15 at 03:30
  • 2
    @NeilSmithline With DH key exchange you can consider $g^a$ to be a public key. This can be either shared through a PKI or generated on the fly and communicated over the line. When not using PKI it is secure against passive attacks but vulnerable to active attacks. – kasperd Jul 21 '15 at 12:16
6

It's possible if and only if, at some point in the past, a trust chain was established that allowed you to authenticate your second party. It should be common sense that if A never had any idea how to identify B (or how to identify anyone else who could indirectly identify B), then, by definition, A simply doesn't have enough information to distinguish between B and some other entity, C.

Math is not magic. If you never knew how to identify someone directly or indirectly, math doesn't magically give you that piece of information.

user541686
  • 2,522
  • 2
  • 22
  • 28
1

It is not just not proven impossible, and not just practically possible with a sufficient level of security. There also exists a provably secure method ("secure" in a sense of being able to choose the highest possible likelihood arbitrarily).

As mentioned in other answers, Diffie-Hellman key exchange with PKI is a reasonably secure way of establishing a shared key that cannot (not easily, anyway) be eavesdropped. Obviously, as long as you do not fully control your own very private PKI, a malicious CA can (and they presently do) subvert this system. However, it is reasonably secure against most attackers.

Apart from PKI, approaches like for example the forced latency interlock protocol or the station to station protocol, or DH-EKE derivates (such as described in RFC5247), while not unbreakable, can successfully prevent most man in the middle attacks with a reasonably good probability, even without PKI.
If the likelihood that an attacker can "guess" correctly is low enough, that may very well pass as "secure" in practice.

Quantum key distribution is not yet ready for the general public, but it already works for a decade or so. Not in theory, but in practice.

Unlike the other approaches, it guarantees that you have a shared key that nobody else knows about (or rather, you can set an arbitrarily low threshold for the likelihood that someone might know your key, but that is as good as "guaranteed").
I expect that this might make it to mainstream some time after large-scale quantum computers are being deployed to attack DH (or maybe not, because all you need to do in order to defeat the magical quantum powers is double your key length, so it's not really all that scary).

Bruno Rohée
  • 5,351
  • 28
  • 39
Damon
  • 5,211
  • 1
  • 20
  • 26
  • This answer is incorrect. Quantum key distribution is not secure against a man-in-the-middle, any more than Diffie-Hellman is. Think of it this way: if you want to be sure you're talking to Alice but you have no way to identify it's her, how are you possibly going to know whether it's Alice you're talking to or Alice-imposter? Quantum crypto isn't magic; it doesn't change this fact. – D.W. Jul 21 '15 at 18:01
  • @D.W.: You should look at Jorgen Cederlof's thesis for that, although I believe that it is even a lot easier than that. You can MITM, yes. But you cannot make the other two believe that they talk to each other, not you. While they have no way of verifying where their photons come from, they both know the bases (both sent and matching). B can send a hash back to A prior to committing. What will MITM do? He knows what bases he sent to B, and he knows the ones he matched with A (but not the ones A sent and he didn't match, nor which ones B matched). He cannot produce a convincing message on 50%. – Damon Jul 21 '15 at 23:38
  • In either case, MITM only knows 50% of the bits (having matched 50% of the ones A sent, and knowing 100% of the ones sent to B, but being unaware which 50% of these B has matched). So, he needs to commit on something he doesn't know. If more than just 10 or 20 bits are exchanged (say, e.g. 256) the likelihood of being "lucky" is practically zero (1/2 chance per bit, so that's 2^128). – Damon Jul 21 '15 at 23:43
  • 1
    *"B can send a hash back to A"* - but the MITM can replace that, too. Again, Quantum key distribution is only secure against MITM attack if you have a separate out-of-band channel that is not subject to tampering (in which case you could just do Diffie-Hellman over that channel), or if you have some other way to authenticate the other party (e.g., a PKI). Bottom line: I think you have a fundamental misconception of the security properties that quantum key exchange provides. – D.W. Jul 22 '15 at 04:52
  • The only way to determine the veracity of the public key, is to employ the law of large numbers, over multiple information channels, which is what 2FA etc is all about. – munchkin Jul 22 '15 at 07:12
1

I spent a long time trying to reason this one out. I found a real solution, but not one that can be packaged up and made into a product. You see, a passive listener will be absolutely foiled by Diffie-Hellman with big-enough key size. But if the guy is willing to MITM it falls down flat.

If we know the topology we can know how long any packet should take down the wire, and if we are willing to build ASIC boards for DH all the way down to gate level so that we know that any potential MITM attacker cannot make a faster DH and cannot process messages in flight without being caught by timing measures, then we know it was secure. But in general, you can't do this as the internet does not have a fixed topology.

There's some nasties for things like SSH subject to the halting problem, like asking the remote side to run programs and including the session key in the environment but this has the same downside. If you made a product out of it it would fall.

Joshua
  • 1,090
  • 7
  • 11
0

Defcon 22 talk by Phil Zimmerman promoting his phone company (SilentCircle) as wiretap-free https://www.youtube.com/watch?v=HuHm1vzzm1g

His idea is to get rid of Public Key Infrastructure by verbally comparing session key hashes, he also gives interesting examples of PKI failures, the audience asks many questions that are in my opinion acurate and relevant.

He says this method is tamper-proof, because in case of a man in the middle attack, the session key hashes would be different between the users communicating and they would know it right away. He mentions the key is being exchanged over the media layer, instead of entrusting whoever owns the line with "doing the security".

Vilican
  • 2,723
  • 8
  • 22
  • 35
mwoa
  • 101
  • 1