# Is it possible to ensure security with zero pre-shared information?

Is it possible to secure a communications channel against both passive (sniffing) and active (injecting / MitM) attackers without either legitimate party knowing any pre-shared information?

I know that this isn't possible using "traditional" asymmetric crypto, since an active attacker could create its own public keys and relay the information on both sides. A trusted third party implies pre-shared information, since at least one party must provide their public key to the third party.

Are there any schemes that make this viable, or is it completely impossible?

Update: By "zero information", I mean other than the "address" of the other person, e.g. their computer's IP address, or even their mailing address.

-
It's obviously impossible. You need to know at least something. For example you could have the public key double as address. – CodesInChaos Jul 16 '12 at 9:44
Is IBE (where there's a third party that provides to each party the system parameters and the private key corresponding to that party's address, but no one need give a public key to a third party) also out of bounds? – poncho Jul 16 '12 at 12:47
@poncho The only thing the two parties have pre-shared is their locations, e.g. an IP address. – Polynomial Jul 16 '12 at 12:49

Yes. Simply send the data in the clear.

Passive attacks are not possible. For a passive attack to work, the data must be intercepted by someone other than the intended recipient. But by your definition of "pre-shared information" the existence of an intended recipient would count as "pre-shared information" (since both sides would know this). So anyone who receives the traffic is just as much the recipient as anyone else.

Active attacks are not possible. Active attacks involve someone other than the person the other side expects to be sending the data to be able to influence the data or receive the data. Since neither side has any expectations as to who is originating or receiving the data (such an expectation would be "pre-shared information" since both sides would need to have it), such an attack cannot, by definition, exist.

The idea of a "secure channel" to nobody in particular simply isn't coherent. And if both sides knew who they wanted to speak to or hear from, that would be "pre-shared information" by your expansive definition.

So this is not a coherent thing to want.

Consider two people considering such a scheme, Alice and Bill. If Bill knows who Bill is, Alice cannot know who Bill is as that would be pre-shared information. If Alice knows who Alice is, then Bill cannot know who Alice is, as that would be pre-shared information. Thus Bill could not distinguish a secure link to Alice from a secure link to Fred. To Bill, either is just as good. So it matters not if Fred intercepts or distorts the data. Fred is no less the intended recipient.

Update: If literally all you know is the address, then nothing could provide any more security than simply sending to that address. Since the address is all you know, whoever can receive something sent to that address is the intended recipient, right? And it doesn't matter what that person receives, since you are no different from an attacker, they wouldn't care whether they received what you sent or what someone else sent -- they don't know who you are.

-
Certificate authorities, as I mentioned, count as pre-shared information. They have to give their certificate to a trusted third party. – Polynomial Jul 16 '12 at 8:35
Ahh, okay, I'll fix my answer. – David Schwartz Jul 16 '12 at 8:37
I think your edit went too far the other way. Alice knows Bob, Bob knows Alice, let's say by IP address on a LAN. I'm not sure whether you misunderstood me, or if you're just being pedantic with the aim of making a point. – Polynomial Jul 16 '12 at 8:48
If all Bob knows is Alice's IP address, then the best Bob can do is communicate with that IP address. Whoever gets it is the intended recipient, since that person meets the only criterion Bob knows or cares about. (Unless you're asking a totally different question like "Can someone prove they are 'entitled' to a particular IP address?" If that's the case, you should ask a more specific question.) – David Schwartz Jul 16 '12 at 9:23

No. Consider using encryption to protect against a passive adversary. In this case, encryption needs to hold from the sender to the receiver. The sender can verify that the message leaves them encrypted but they have no guarantee that it is not decrypted before the receiver unless if they can authenticate the receiver. Authentication requires knowledge of some secret which would constitute preshared information in your definition.

The closest I believe you could come to a secure channel in this setting would be what is called Secure Message Transmission Protocols. The basic idea is that the sender would split up the message into shares (say 10 shares) such that some threshold (7 shares) are required to reconstruct the message. The sender would send the 10 shares over different channels. This is not secure against an adversary that is one all channels (which your question implies, which is why the answer is still likely "no") but if the adversary is on 6 or less, you get passive security. Active security is possible but the adversary is bounded to less than a third of the channels (byzantine agreement). Anyways, you could also argue that knowing the algorithm to reconstruct the message from the shares is pre-shared information (although not a secret).

-

Yes, one needs a manual channel. $\:$ That is, some channel which allows
the parties to compare a short string held by each of them for equality.

www.wisdom.weizmann.ac.il/~naor/COURSE/fc0607_lect7.ppt

-
You should post a summary of your source. Your post is utterly useless without the linked material. – CodesInChaos Jul 16 '12 at 9:53
I'll concede that it wasn't very helpful without the linked material, but I say it was far from "utterly useless" without the linked material. $\:$ It provided the term "manual channel", which is the term that's needed to look up further information on this subject. $\;\;$ – Ricky Demer Jul 16 '12 at 10:01
I have to agree with @CodeInChaos here. I don't even have software installed to read PPT files. – Polynomial Jul 16 '12 at 12:49
@RickyDemer.. ok, but that's just being overly picky on his words... – Pacerier Apr 4 '14 at 23:50

Yes it would really hard to avoid MITM attacks without any pre-shared information which essentially helps us establish the identity of the parties involved. However, I feel it is still possible to come up with a secure protocol which can avoid MITM attacks(both passive and active).

There is a lot of research being done to perform Zero human interaction authentication, which specifically address this issue of not having a pre-shared secret information.

The idea is usually to use a fuzzy commitment scheme, with some context. Now the catch here is that there exists some information which is uniquely know to both parties but never pre-shared. (for e.g. ambient context - luminosity).

• MITM attack - Since there is no PKI infrastructure/Digital Certicates being used it may be vulnerable to MITM attack. However, it can be overcome if key exchange is designed in a secure fashion and would work in certain use-cases, such as below.[here RS -> reed solomon code, FP -> fingerprint]

Ex. Lets assume A and B wan't to communicate, so
1. A selects a random key K and performs an operation FPa XOR RSencode(K) [Can pass Hash of K for future verification at B]
2. sends the resultant to B.
3. At B, we would perform FPb XOR FPa XOR RSencode(K)
4. Since FPb would be similar to FPa , it might introduce some error in RS(K)
5. However since it is a fuzzy commitment scheme, it is able to tolerate error and thus we are able to reproduce the symmetric key K by performing RSdecode. [Verify K using Hash]

Now, in this scenario, lets assume there is an active eavesdropper E . Even if he/she is able to sniff the data , he won't be able to derive the key, unless he also has a similar fingerprint. So now this brings us to the question, can E sniff/eavesdrop on sensor data too. If the sensors are chosen in a manner that eavesdropping is not feasable/extremely hard then this could be avoided too.

Secondly, if we consider active MITM, the attacker would need to know the FP to even perform an active attack. With the data E has acquired, it should be practically infeasable for E to deduce FP.

Also they use a key-evolution approach to further strenghten there security properties.[details in the paper]

So overall, yes pre-shared information makes it quie easy to do away with MITM attacks, however recent research have shown potential methods achieve a certain sense of security without using any pre-shared information .

For completness, E could definitely corrupt/modify packets sent from A to B and thereby prevent A from authenticating to B (Denial of Service).

Hope this answer was useful and provided some points to ponder about :)

-
"Now the catch here is that there exists some information which is uniquely know[n] to both parties but never pre-shared." How is this secret data exchanged between the two parties? In the specific protocol you gave, if Alice never shares her fingerprint with Bob, how does Bob learn it? – poncho Mar 12 at 20:19
Hi @poncho, thanks for the question. This type of authentication is based on proof-of-co-presence. So, here if the devices are co-present they percieve similar fingerprint and therefore need not perform any pre-exchange of information. This is possible due to the fact that recreating exact/~ fingerprints is extremely hard(infeasable) if fingerprinting is done properly. – FunnyPanda Mar 12 at 20:46
[contd]So here, A and B , both being benign would be co-present and thus have access to valid fingerprint , however E being malicious would have to guess the fingerprint (which is generally hard and obviously assuming physical security) .Hope it clarifies. – FunnyPanda Mar 12 at 20:46
@poncho Do you agree ? – FunnyPanda Mar 13 at 23:14
So, A would preshare his fingerprint with B (and his fingerprint would be secret), and B would similarly share his fingerprint with A, and so having these shared secrets is how you propose getting around the requirement for having preshared secrets. – poncho Mar 14 at 2:45

It is not completely impossible. There are cases when it is possible and it depends on your adversary model.
Consider a Distributed network, in which a sender S want to send a message M to a receiver R. They are connected through a network on which they don't trust or you can say is corrupted by adversary. The question is whether secure communication is possible or not in this case.
If the adversary is passive and static, Then the necessary and sufficient condition for secure communication is that there should be at least t+1 vertex disjoint path from S to R, where t is the number of players that can be corrupted by an adversary i.e. Adversary can only eavesdrop on those t nodes in the network. I have also proved that if the Adversary is passive as well as dynamic, t+1 is sufficient for this communication assuming the adversary is changing it's position from one node to another in the channel with time greater than the maximum_time(sending a message between two arbitrary adjacent node).
Similarly, the 2t+1 vertex disjoint path is required in case of active and static adversary. Moreover, it has also been been proved that it is sufficient for dynamic active adversary.

Hope this helps.

-
Actually, if we limit ourselves to passive attackers (who can listen in to the messages exchanged by the two valid parties, but cannot modify or inject messages), then it's fairly easy, even if we allow the adversary to listen in to all messages - just have the two parties perform an unauthenticated DH operation; in this case, we don't need the authentication, because when either party receives a message, they know that it's from the other party (as we don't allow the adversary to generate anything) – poncho Mar 14 at 3:17
In unauthenticated DH, there is some sort of sharing information just before the message is being sent. I was trying for a solution in which there will not be any key establishment process. I was trying to impose the restriction on the topology of the network itself. – dpdocs21 Jul 6 at 10:47