# 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. Jul 16, 2012 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? Jul 16, 2012 at 12:47
• @poncho The only thing the two parties have pre-shared is their locations, e.g. an IP address. Jul 16, 2012 at 12:49
• @Polynomial The question is too vague to answer usefully without knowing precisely what is pre-shared. If it's an IP address, then my answer is correct -- send the data in the clear and you have perfect security. It will only go to the intended recipient since the intended recipient is "whoever gets it when I send it to that IP address". Sep 23, 2017 at 17:07

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).

• Your answer uses the term "the receiver" to mean something other than "anyone who happens to receive the message". It is not clear what it means in the context where there is no pre-shared information. There can be no intended receiver without pre-shared information since the identity of the receiver would have to be shared, right? Sep 19, 2017 at 17:15

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. Jul 16, 2012 at 8:35
• Ahh, okay, I'll fix my answer. Jul 16, 2012 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. Jul 16, 2012 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.) Jul 16, 2012 at 9:23
• @David Schwartz: I understand your point, but you are pushing words and concepts for "ensure security" beyond reasonable and common definitions. Especially with "If literally all you know is the address, then nothing could provide any more security than simply sending to that address", when the later procedure (or "send the data in the clear") gives no confidentiality or integrity-with-origin at all under the question's hypothesis. I agree that without any pre-shared information, nothing does. But your answer, while correct, is too misleading for my taste.
– fgrieu
Sep 19, 2017 at 16:14

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. Jul 16, 2012 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. $\;\;$
– user991
Jul 16, 2012 at 10:01
• I have to agree with @CodeInChaos here. I don't even have software installed to read PPT files. Jul 16, 2012 at 12:49
• @RickyDemer.. ok, but that's just being overly picky on his words... Apr 4, 2014 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? Mar 12, 2016 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. Mar 12, 2016 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. Mar 12, 2016 at 20:46
• @poncho Do you agree ? Mar 13, 2016 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. Mar 14, 2016 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) Mar 14, 2016 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. Jul 6, 2016 at 10:47
• @dpdocs21 In your answer, R is pre-shared information. Both the sender and receiver know that there exists an R. The question specifically said there was no pre-shared information. Sep 19, 2017 at 17:16
• @DavidSchwartz R is the intended receiver or legitimate party and not the pre-shared information. Sep 21, 2017 at 6:27
• @dpdocs21 So the receiver doesn't know it's the intended receiver? Or the sender doesn't know R is the intended receiver? If both the sender and receiver know that R is the intended receiver, then that R is the intended receiver is pre-shared information. The problem is trivial to solve if the receiver's identity is pre-shared information and impossible to solve (arguably, it's not even coherent to ask) if it isn't. Without some pre-shared information (the identity of the intended receiver), the concept of an "intended receiver" is incoherent. Sep 21, 2017 at 18:38

Yes its possible. The technique was developed a while ago at Royal Holloway, University of London. Its called certificate-less Public Key Cryptography (CL-PKC). With no apriori interaction / knowledge (you just would need the identity or IP address in your case of your communicating partner. You will not need a PKI like structure nor the associated certificates and the inherent "key-escrow" associated with IBC will also not be a problem.

• Section 1.2 of the paper you linked defines a pre-shared key agreement between parties. Sep 19, 2017 at 16:09
• @Polynomial: No there is no pre-shared key agreement between the two communicating entities. Think of the KGC as the network deployer but its not a trusted one. Sep 20, 2017 at 16:35
• The KCG's key deployment presupposes a secure channel: "The process of supplying partial private keys should take place confidentially andauthentically: the KGC must ensure that the partial private keys are delivered securely to the correct entities." - you would then need to propose a way to develop such a secure channel without any pre-shared information, which is a catch 22. Sep 20, 2017 at 16:38
• @Polynomial: If the only pre-shared information is IP address then obviously it is an IP network. Right? If it is so, a network administrator needs to be there to deploy the network (i.e. allot the IP addresses). If that's the case (otherwise anybody can allot itself any address which leads to chaos only) then there is no catch 22 situation as mentioned by you. Oct 30, 2017 at 10:46
• The key point is that it's an untrusted IP network. The administrator may set up an IP range and DHCP, but the client connecting to that network has never connected to that network before and has no prior contact with the administrator, and there may be malicious people on that network at the same time (e.g. open WiFi at a café). But all of this is irrelevant - the paper you linked explicitly requires a pre-existing secure channel for the KCG's key deployment and it does not aim to solve that problem. Oct 30, 2017 at 19:15