You guys seem to not be on the same wavelength - are you talking about theoretical cryptography, or real life security (which includes stuff like social engineering, trusted entities going rogue, etc..)? Clearly some things that are "secure" in one model are completely "insecure" in the other, and vice versa.

The answer is yes and no.

The third "friend" makes things a lot simplier. But it's not really needed.

You want to establish a secure connection between John & Jane? Make John meet Jane in a public bar (or make one go to the other's home/office), make them exchange USB keys with their public keys. Go back home.

Congratulations, now you can establish secure connections with your buddy.

It's not a joke. That's how it works really. "Third party friends" like Verizon are actually doing this, Jane (having a server) asks Verizon to sign his certificate, and Verizon asks for Jane proof of her identity (how strong the proof they ask may depend on the company); then agrees to sign it.

And you blindly believe in the root certificates that were installed in your system, which often you get them when installing your OS (i.e. Windows), because you blindly trust Microsoft. (I'm not using "blind trust" in a derogatory form).

This is why they advice not to install Windows OS downloaded from torrents (whether cracked/pirated or with a legit key). Because the root certificates (among other things) may have been tampered, and you will blindly believing in the root certificates that you downloaded from a torrent; you didn't get them from a Microsoft-approved store.

Trust is delicate issue. In our original example of John & Jane; if Jane convinced John she's a bank employee, do you really trust her? Exchanging usb with public keys will ensure a "secure connection" but it doesn't guarantee she's telling the truth.

Did you phone your bank to check Jane works there? Did you ensure your phone line was not tampered and routed to a fake bank? Did you visit the bank personally to verify this? Did you check with the Federal Government that the Bank has a valid license to operate? Are you sure this isn't a government conspiracy against you?

You have to draw the line somewhere; when are you willing to start trusting or not.

Is it even theoretically possible for two complete strangers to securely communicate without a mutual friend?

Yes, absolutely! Just exchange your keys in a private way (i.e. John & Jane example). The connection will be encrypted and no one else will see it. It's troublesome though, to do this every time with every person you expect to meet.

However if "Harold" already exchanged w/ Jane, and Jane tells John he's of trust, John & Harold may communicate securely too, providing John trusts Jane. This is what "mutual friend" firms do, they do all the hassle for us by making it a business & living of it.

If the two strangers have no trusted mutual friend, then they can't validate certificates with their trusted mutual friend, and thus can't be entirely sure there isn't a man in the middle.

That problem goes around a deeper problem not much related with code, but rather more philosophical: "what is trust?"

if you and your friend have both agreeded upon a cipher sure you can communicate securely, but that pre-supposes you already communicated before hand and was that secure?

So if the answer is "no, you need a trusted friend or a common secret", then I guess the real question of the thread is what are some practical ways of establishing a common secret or friend with a stranger?

If you're physically nearby, you can meet in person and be in close enough proximity that you can privately share some information without a MITM being able to intercept it. If that's not practical, are there other 'challenges' you can make which only the intended recipient can complete? e.g. something where the MITM would have to travel to the physical location of either party to know the answer, etc...?

you are once again putting words in my mouth

You missed the fact that the OP is asking about situations where you don't have a trusted 3rd party or a shared secret.
Samoth is putting words in your mouth because you're making suggestions that do require a shared secret, and he's assuming that you think these are valid in the OP's situation.

To decode Samoth's jab at you: One-time-pads are a shared secret. The OP's situation requires no shared secrets. Therefore sending a message encrypted with a one-time-pad is the same as sending random jibberish -- the recipient cannot possibly decode either.

@Samoth, stop picking at him, he obviously missed the bit where the OP wants to communicate without a shared secret, or alternatively, be more direct with your critique

The static background noise from radiowaves in space is also good and unless someone else recorded in the exact same direction as you, at the exact same time, with the exact same level of equipment, nobody else will ever have that key.

When I worked on gambling machines, this is what we used in order to ensure that no one could possibly guess the outcome of the games (along with ambient temperature, radiation, etc...). It's a genuine random number generator, instead of a PRNG.
It's impossible for someone outside the cabinet to take the exact same measurements, and the cabinet itself is secured with a pre-shared key -- literally, the government regulator is given a physical key in person.

If you're physically nearby, you can meet in person and be in close enough proximity that you can privately share some information without a MITM being able to intercept it.

It is still very hard to guarantee that the person you are meeting is, in fact, the person you intended to meet, and not a skilled impersonator.

Unless you known this person already, or are introduced (in person) by a trusted 3rd party, the man-in-the-middle vector remains...

If you're physically nearby, you can meet in person and be in close enough proximity that you can privately share some information without a MITM being able to intercept it.

It is still very hard to guarantee that the person you are meeting is, in fact, the person you intended to meet, and not a skilled impersonator.

Unless you known this person already, or are introduced (in person) by a trusted 3rd party, the man-in-the-middle vector remains...

Huh, yeah... if you ask someone to meet you at the town square to exchange keys, a MITM could intercept the message and change it to say that you want to meet at starbucks. They then meet you at the town-square, and meet 'the stranger' at starbucks, exchanging their own key with both of you, and gathering both of your own keys... They can then continue to act as a MITM, forwarding your messages to 'the stranger' via themselves.

Guys (and gals?), this has been an awesome thread to read. I'm wishing I hadn't posted it in the Lounge so that I could give upvotes galore! I just wanted to say thanks. Carry on :)