# Cryptographic Challenge: How to Say Something Confidentially to Snowden?

The Snowden situation raises an intereting cryptograpic problem. At present, how can something be sent confidentially to Snowden?

Claim:

I have no particular political orientation. The above question is merely a cryptographic challenge. The meta assumption is…

1. You trust someone, denoted as Snowden, but Snowden does not trust anyone and you do not know any further information about Snowden, except his name or identity.
2. You should be careful that someone, say FBI, might impersonate Snowden to you.

Objective:

1. How to build a global and secure communication channel between you and Snowden from scratch, without resorting to trusting any third party?

2. Snowden does not trust anyone at the beginning, but he wants to find someone whom he can trust, via the secure channel built (if possible) in Step 1. How is this done?

Is this possible to do by using cryptography?

For convenience, let us call this challenge the Snowden challenge. How do we model the security objectives for Snowden and you?

-
Interesting question. Cryptography usually emphasizes on securing communication between parties who know they are going to communicate with one another. In your game does getting tricked by an imposter give you any penalty? Anyway I don't think it's possible because there is no way to verify you're talking with Snowden, or for Snowden to verify that he can trust you. – rath Jul 4 '13 at 0:45
For example, you can ask someone who introduces himself as Snowden to verify his claim by asking him to give you the documents he leaked. An FBI agent can do the same thing. I suppose you can always ask people to join a video chat room and say 'will the real Snowden please stand up!' and then somehow eliminate the dopplegangers. Now that I think about it you could be an FBI agent having ran out of ideas. – rath Jul 4 '13 at 0:47
Isn't objective #2 self-contradictory? – Thomas Jul 4 '13 at 2:08
My meaning is that at the beginning, Snowden does not trust anyone. But after building such a secure channel, if possible, then you can confidentially prove you to Snowden that you are trustable. – Pigmann Jul 4 '13 at 5:09
You must have some way, in principle, to identify Snowden. If you have such a way, we must know what it is. If you do not, then it is provably impossible -- anything that identifies the Snowden you have in mind could also identify someone else. – David Schwartz Jul 4 '13 at 6:19

1. Generate a file of cryptographically strong random data at least as long as the message to be sent. This will allow communicating the secret using the random data as a one-time-pad. I.e., produce the ciphertext by using a bit-by-bit combining function such as XOR.

2. Purchase a plane ticket for an international flight connecting through Sheremetyevo airport.

3. Burn a copy of the OTP data onto a CD-ROM. Label it "Lady Gaga" and lock it in a briefcase handcuffed to yourself.

4. Take the flight. During your layover, locate Snowden in the international travel area.

5. Whisper the secret to Snowden.

7. Drop the CD-ROM in the trash so the spooks don't have to report home empty-handed.

8. (Optional) exchange public keys with Snowden to secure your future communications.

EDIT: OK, I felt bad about leaving a response that might be interpreted as just trolling. But in all seriousness, this is a classic identity bootstrapping problem.

Once we have identity authentication worked out, message integrity and confidentiality are basically solved by standard encryption systems. There's no magic bullet for bootstrapping identity, but here are the questions I ask myself when trying to approach the problem:

First: Precisely what facts are being authenticated?

For example, do you have a public key which claims to be Snowden's and you're trying to prove that it is genuine? Authentication has a cost, why would he go out of his way to prove that to you?

An easier problem to solve may be "If Snowden wanted to receive a message from me how could he do so securely?"

Second: To whom are these facts being authenticated?

Are you trying to prove to Snowden that a message you sent is genuinely from you? Or is some unknown party claiming to be Snowden expected to prove to you that a message you received is from the authentic Snowden?

Third: Who has what to lose from a successful attack?

Perhaps you are sending something to Snowden and then relying on him to do a perfect job of authenticating what he receives (i.e., proving the absence of an active man-in-the-middle attacker). But if he doesn't care at least as much as you do about the security of the message, he might do a halfhearted job of it you might continue on transmitting messages insecurely.

Fourth: How far do these credentials extend?

In other words, will your actions allow Snowden to do more than just verify you? For example, would he be able to impersonate you to a 3rd party? How about the other way around?

In summary:

A cipher is a device for converting a plaintext confidentiality problem into a key distribution problem.

An ephemeral key agreement algorithm is a device for converting a key distribution problem into an authentication problem.

A signature algorithm is a device for converting a message authentication problem into an identity problem.

If you can somehow establish trust for authentication credentials in one or both directions, the rest is mostly a solved problem. But this can only be built on top of human systems: What will it take for you and/or Snowden to believe that the other party is authentic?

-
I do not agree with (parts of) your last paragraph. Just raw plaintext has authentication issues as well - these are not "created" by using a cipher or ephemeral key agreement algorithm. – orlp Jul 5 '13 at 16:23
Yes, I did not mean to imply that plaintext was free of authentication problems, just that if we could solve the identity and authentication problems we have well established solutions for message confidentiality and integrity. – Marsh Ray Jul 5 '13 at 19:59
There is no reliable substitution for meeting someone in person and exchanging a private key which contains message and identity authentication bits ( I would use 128 bits for each, 256 if you are paranoid and/or smoke weed), in a OTP system or a stream cipher with a known cryptographically secure psuedorandom generator. – William Hird Jul 12 '13 at 20:24

First up, I think your question is less something for crypto.SE and would fit better in the security.SE corner. Nevertheless, here goes:

...except his name or identity...

That's in itself already describes your problems when it comes to security and cryptography.

1. Problem due to lack of verification options.

Currently, world news outlets (example: Reuters) as well as US governments confirm that Mr. Snowden's passport has been revoked by the US government. As a result, you don't have the option to verify if the person you are talking to is indeed Mr. Snowden, as there are no official documents that could indeed verify the identify in a trustworthy way.

2. Problem due to lack of knowledge.

As you have never met Mr. Snowden in person either, you can't tell if a person you meet is indeed Mr. Snowden and not someone who looks “just like him”. Remember that the only "knowledge" you currently have is a name and a small pack of pictures posted by news outlets. Keeping it short: since you both have no "common knowledge" which could be used to establish "trust", you can not trust the person you talk to.

Now... security is based on knowing, doing, or owning something that no one else can. This is especially true when thinking about cryptography for communication purposes. Since you don't even know Mr. Snowden and he does not know you, there is no way to establish a secure connection and/or communication.

In fact, you both represent "untrusted endpoints" for each other. You can't establish a secure connection when one or more endpoints are untrusted. To give you an every-day example: that's like trusting an invalid certificate when visiting an SSL protected website.

Keeping it short: symmetric key cryptography is not an option.

The alternative would be using public key cryptography instead. BUT: to avoid that everyone can decrypt the message, the decryption key would need to be passed to Mr. Snowden confidentially instead of publically... which does not satisfy the definition of "public key cryptography" anymore. Also, you can not establish a secure connection to an untrusted endpoint which means you can't securely pass the decription key. This practically closes the loop.

Wrapping it up: Humans are often the weakest link in a security protocol. This is one of such cases.

EDIT

Recently found some nice, reality-checking perspectives on the discussions that came up in the comments to my reply...

1. Can you trust a “public video”?

2. Even if you can trust the public video to transport a key, and even when you ignore the endpoint you can't verify with certainty... the “trust problem” remains due to “untrusted transport channels”. As said: in this case humans are the weakest link when trying to find a secure way of doing this.

(images via http://xkcd.com/, licensed CC BY-NC 2.5)

As the discussion in the comments boils down to thinking that public key crypto is the way to go, here are some additional thoughts why it won't work in this case:

In a public-key cryptography system, the private key is kept secret by the owner. Owner then publishes his public key through a certificate authority (CA). The CA essentially provides (identity, public key) pairs and signs this with the CA's private key so it can be checked using the “well-known” corresponding CA public key.

Now, to look up someone’s public key, you send the CA a request, which CA answers with a signed message which you then check the signature of.

This provides at least two weaknesses in Mr. Snowden's case, centered on the fact that the CA may be compromised:

1. If an attacker learns the CA’s private key, he can forge signed (identity, public key) pairs which will look like they are signed by the CA, and thus spread false public key records.

2. If an attacker somehow makes the CA change the public key record for entity XYZ to “forged key” whose private key is compromised, he can use “forged key” to impersonate entity XYZ ; this is essentially the same result as the above attack except that the CA may have a record of the forged key.

So, to communicate securely with someone like Mr. Snowden, you would need to make sure you can establish a trusted, verifiable direct connection to him, or you would need a CA which you both trust. But you won't be able to agree upon a commonly trusted CA since you can not establish a verifiable communication with Mr. Snowden in the first place.

We can discuss this back and forth, fact is: trust is a problem and verification practically not possible without having to rely on another non-verifiable intermediate party. Wrapping it up: you can not “say Something Confidentially to Snowden” (in the current situation described in the question) as the “confidential” part can not be proven from a cryptographic standpoint due to a key-exchange problem which rules the situation described in the question.

To wrap all this up:

How to Say Something Confidentially to Snowden?

-
Yes, you pin down the core of my question. I know that current knowing concepts of cryptography is insufficient for solving Snowden Chanllenge. I true meaning is to ask: Can we find some NEW CONCEPT or some NEW PRIMITIVES to solve this chanllenge. – Pigmann Jul 5 '13 at 2:18
@Pigmann Two-letter-answer: no. As I noted in my reply, you can't establish a secure connection when one or more endpoints are untrusted. Key to cryptography is that A and B trust each other and exchange data using a common secret so if C intercepts the exchanged, encrypted data, C can't use it. If A can't be sure if B is trustworthy, A has to treat B as if B is like C. The "trust" requirement has been like that for several centuries, so I wouldn't bet on finding a "new concept" anytime soon. That is, unless you can prove the untrusted to be trustworthy — which you can't, since it's a paradox. – e-sushi Jul 5 '13 at 7:09
It's identity. Who is Snowden? Is he real? I've only seen evidence of him on this same screen I'm typing this on. Via news reports, mostly @ggreenwald. This is a valuable clue. The only way forward is for Snowden to authenticate a key exchange using what we have: media reports. But it would have to be an activity that was hard to forge. For example consider the news headline: "In rare appearance at airport Snowden performs interpretive dance spelling out the letters 546215007a39af41a445812170f41142238e62bf (Video on Youtube)". – Marsh Ray Jul 5 '13 at 19:53
@MarshRay Yep, and then you would have to ask yourself if YouTube (a Google company) doesn't distribute a "fake" video. After all, they are now known to share data with the NSA so who knows how much they cooperate and who could have an interest in a faked video. I already see it before me: a video shot from long distance, partly blurry, with a glimpse of what could be Snowden. Again, it's all a matter of trust. 99.999% of the people on the internet don't know Snowden in person. For what it's worth, he could as well be a non-existent ghost character which acts as a setup to "catch them all". ;) – e-sushi Jul 5 '13 at 23:06
Well the point is to make it as little "about trust" as possible. Is it possible that someone could replace the President of \$country with a very similar-looking actor and get away with it for awhile on TV? Saddam tried but I don't think he fooled any experts for long. You could impose a short time window on the attacker to forge a convincing video. Next to having Poitras and Greenwald as trusted introducers (ruled out in question), I suspect high resolution video is probably still the best you can get. – Marsh Ray Jul 6 '13 at 0:19

The other answers cover it quite elaborately, but in short: No.

But let's consider this to be a game, with the following assumptions:

• There is a person called "Snowden". Somewhere. In the world. And he has no way to authenticate himself.
• Snowden initially trusts no one.
• There is no trustworthy way to authenticate anyone.

What is the attackers probability to win this game? It doesn't matter, because it is impossible for the "good guys" to win this game:

• Snowden does not trust anyone.
• He does not trust any verification means.
• If he only communicates with trustworthy (authenticated) people, then he is stuck alone.
• Of course Snowden could post his public key.... but since you have no way to verify it, you can not distinguish between the real "Snowden public key" and the "Fake FBI public Key". In the game you only know the name of Snowden and that he exists. That's it.

The real problem is, that you assume a system without any initial trust relations or "game changing condition" , which distinguishes honest parties and attackers. There is no cryptographic solution to this.

-