Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I'm looking for ways to send private messages over a public channel, and in doing this I stumbled in asymmetric encryption, which is just perfect for what I was looking for at first - A and B communicate directly, over a public channel.

However, it is now my concern that the security of the message might be compromised by man-in-the-middle attacks of this kind.

Alice and Bernard are computer users connected to the Internet. Alice uses a proxy, Paul, to connect to the Internet and send messages to Alice.
Paul wishes to read communications between Alice and Bernard. So, when Alice attempts to send Bernard her public key, Paul stores it and forges a new one, also from "Alice", and sends it to Bernard. He does the same with Bernard.
When Alice wants to send Bernard a message, she's actually sending it to Paul, who decrypts it, modifies it and sends it to Bernard.

share|improve this question

5 Answers 5

up vote 3 down vote accepted

Asymmetric encryption provides security for messages exchanged between Alice and Bob only insofar as Alice knows Bob's public key and Bob knows Alice's public key. Otherwise, attackers could publish fake public keys and, in effect, pose as Alice when talking to Bob and vice versa.

An historical view of the issue is the following: in older times (say, 50 years ago), Alice and Bob could have talked "securely" only if they knew an initial shared secret. If both Alice and Bob know a shared secret K, then they can use it to encrypt their messages and also to check their integrity (with a MAC). Encryption is against passive attackers (who try to learn the message contents) and MAC is against active attackers (who try to alter the message contents). For a complete secure flow, Alice and Bob would also have to include some sort of numbering in the messages, so that dropped, duplicated or reordered messages are detected.

An initial shared secret is usually hard to establish. Especially when there are more than two Alices and Bobs. If there are n people who must securely talk to each other (securely against external attackers but also against the n-2 other users), then there will be a need for n(n-1)/2 shared secrets, and each user will have to store n-1 secret values (one for each other user to which he may want to talk to).

Asymmetric cryptography makes the problem easier (but not easy). With public/private key pairs, each user stores one private key, and just needs to know the public keys of the other n-1 participants. Public keys are, as the name says, public. They can be shown to the whole world without any ill effect. Presumably, distributing public elements is easier than distributing secrets, because only active attackers are to be feared.


The analogy is that of the Wall. Imagine that there is, in some specific place (say, the central plaza of a town), a big wall made of marble. Everybody can come and look at the wall. On the wall are engraved the public keys of Alice, Bob, Charlie, Dave, Ebenezer,... so that everybody can learn these keys without fear of interference. The whole is guarded and only the official town engraver can add or remove or modify a public key on the wall; and he will engrave, say, Fred's public key only if Fred himself shows him the said key and some valid ID (driver's licence...).

A big wall can be inconvenient, especially for users who do not live in the town where the Wall is located. To allow for remote operation, a nice scheme has been designed: the official engraver is also given a camera, a printer, and a stamp. When the engraver has finished engraving a new public key, he takes a photo of it, prints it a few times, and signs them (with the official stamp). Now, if Alice sends to Bob such a photo, Bob may trust that he has a genuine copy of the part of the Wall which contains Alice's public key: we assume, here, that the engraver's stamp cannot be counterfeited. It is not a problem if some bad guy opens letters and sees that photo: it is public anyway. Making sure that the stamp cannot be counterfeited may prove troublesome, though.

Here comes the really nifty part, which turns this photo business into a complete public-key infrastructure. Instead of a stamp, the official engraver will use a digital signature: the engraver also has a public key, engraved on the Wall too. If Bob knows the engraver's public key, then he can verify any signature computed by the engraver over any photo. That way, by knowing a priori a single public key (the engraver's public key), he can make sure whether any given photo is genuine or not, allowing him to learn the public key of just any other user.

In normal PKI terminology, the photos are the certificates and the engraver is the Certification Authority. Bob must still start somewhere, i.e. know a public key, but only one (the "root") and for an unlimited number of users; it will even work for user's public which do not exist yet. In a full-blown PKI, there may be too many users for a single engraver to manage them all, in which case we can extend the principle with a Master of all Engravers who signs the public keys of subordinate engravers. The Master is then the "root CA" or "trust anchor", and the subordinate engravers are "intermediate CA". To avoid abuse, the photo of the public key for a subordinate engraver is duly marked as "this is the public key of someone who can act as engraver".

Ultimately, once the system with photos works, nobody actually comes to look at the Wall anymore. Only the photos and the signatures are used, and they are sufficient. We may then avoid building the Wall itself (marble is expensive, after all); the "engraver" simply writes down the public key on a piece of paper, duplicates it, and signs the copies directly.


The PKI model explained above is what is done on the Web, with X.509 certificates. Each Web browser (or operating system) knows a priori a few dozens of root public keys, from which the validity of the certificates for the millions of existing HTTPS-powered Web site can be ascertained by verifying the signatures on them. This is a very centralized model; it is called a hierarchical PKI.

Other models exist, in particular the Web of Trust. In the WoT, everybody can act as an "engraver". Since Bob cannot assume that every single user is as trustworthy and reliable as an official engraver, Bob will accept a given public key as being Alice's only if Alice can show many certificates for that key; i.e. Alice could convince Charlie, Dave and Ebenezer that a given key was indeed hers, and Bob happens to know the public keys of these three guys. In that sense, the WoT is more heuristic in nature than a hierarchical PKI. In fact, this is a matter of a definition of identity: in the Wall model, Alice is Alice because she was given an ID card from some "authority" (say, a central state); in the WoT, Alice is Alice because sufficiently many other people know her as "Alice".


The definition of identity is crucial. What does it mean, that Alice and Bob want to "talk securely" ? Bob wants to talk to the "real Bob" which means that she has a preexisting notion of who Bob is, and what makes Bob distinct from, say, Charlie. If Bob is a complete stranger, then it makes no sense to want to talk to Bob exclusively; there is no "Bob" distinct from "Charlie". This notion of identity is what will dictate what kind of PKI you need. If identities come from a centralized structure, then a hierarchical PKI is appropriate. If identities come from mob approval, then a WoT is the right model.

Or maybe you don't want a PKI at all, after all. For instance, Bob may be, from Alice point of view, "the guy who knows the secret password P". Then we are back to the historical setup which predates asymmetric cryptography. We can still do some advanced science, though. Passwords are poor keys because they tend to be guessable through what is known as a dictionary attack. If Alice and Bob just use P as encryption key, then spies may record the message, then try to decrypt them with potential passwords. In order to fix that issue, Password Authenticated Key Exchange algorithm can be used. With a PAKE protocol, Alice and Bob authenticate each other with regards to their common knowledge of P, but a sufficient amount of asymmetric cryptography was injected in the protocol to prevent spies from learning any data which they could use to test a potential password. If Charlie wants to try a potential password P', then he will have to talk to Alice (posing as a fake Bob) or to Bob (posing as a fake Alice), and he will have to do it again for each P' he wants to test. Surely, after a few such failed attempts, Alice and/or Bob will notice that something is amiss. This is how PAKE protocols allow the secure use of low-entropy secrets (i.e. passwords) without needing any kind of PKI.

share|improve this answer

Alice and Bernard need to do at least one of three things:

  1. Exchange keys using another secure channel (perhaps they might have to meet in person)
  2. Exchange keys over the insecure channel, but use a web of trust to verify the keys (they each need to sufficiently trust someone else's keys who trusts someone else's keys, ad nauseum until it forms a path between Alice and Bernard)
  3. Exchange keys over the insecure channel, and then transmit an unforgeable message over the insecure channel verifying each others' keys (in practice this may be done by reading a short nonce number out loud over a voice connection on that insecure channel, and checking if both ends have the same nonce, but this only works if you consider human voices to be unforgeable, which may not be true)

This is not really a limitation of asymmetric encryption, just a limitation on security. You can't really hold a secure conversation with someone without "meeting" them first, or meeting someone that they trust. Otherwise you could be having an encrypted conversation with anybody, which really defeats the purpose of encryption.

share|improve this answer

Asymetric encryption is the basis for approximately all secret communication. Specifically, it's the basis for SSL/TLS, as well as a few similar-but-incompatible protocols such as SSH and a few other proprietary variants. You're definitely on a winner, but you're not done yet.

First of all, if you have any plans of building your own new standard in cryptography, don't do it. This problem has been solved, and the solutions have been examined and tested and improved, and re-examined, and improved some more, and so on for literally decades. This can be done, and done correctly, with common everyday tools. There's no need to build anything.

The aforementioned SSL/TLS is the simplest solution; its purpose is to turn a public channel (often TCP) into a private one, and it does so extremely well.

If instead of a simple network connection you want to secure a chat session, such as IRC or or a number of instant-messaging services, then you want OTR ("Off The Record"). It's a message-oriented encryption system that rides on top of almost any existing IM system. It's about 10 years old and is pretty solid.

Either way, you'll need to properly identify the two parties to eachother. This step is the critical one, and the one most susceptible to interference. It's best, therefore, to exchange keys in person, or have them signed by a trusted third party or exchange them over a known-secure channel. If you have enough participants, you may have to build a key infrastructure ("PKI") to handle key distribution, but if it's just a handful of you, then key distribution can happen manually, in person.

But as long as your keys are trusted, and as long as you're properly using the underlying software, then your security is guaranteed.

share|improve this answer

Yes, asymmetric encryption in the naive implementation you describe is indeed vulnerable to MITM attacks. To resolve this problem, you need to involve a form of public-key infrastructure.

There are two forms of PKI that are widely used.

The first form involves a Certificate Authority (CA) signing a X.509 certificate belonging to Bernard. If Alice trusts this particular CA, she can trust that the certificate indeed belongs to Bernard. This is the model that is used in SSL/TLS.

The second form involves GnuPG keys. If Alice and Bernard can meet up in real life at least once to exchange GnuPG public keys, the entire MITM attack scenario will be averted. If this is not possible, Alice and Bernard can use the Web of Trust model. This essentially involves having many different people sign Bernard's public key. If enough people does so, Alice can be reasonably confident that the public key indeed belongs to Bernard and not someone trying to impersonate him.

share|improve this answer

Alice should send Bernard her certificate instead. The certificate contains her public key and should have a certificate common name that Bernard recognizes. E.g. Her website URL or ip address etc. It can either be signed by a certificate authority like in tls or used in a web of trust method like in pgp. This prevents Bernard from spoofing a certificate.

Also, Bernard can send Alice in a similar way for mutual authentication. So that Alice and Bernard are assured that they are really talking to each other.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.