# Strangers cryptographically agree on secure video channel using information over insecure channel

Alice and Bob know nothing about one another, and talk for the first time on a video channel that they are not in control over and that might be compromised. They want to create a new secure channel, but can only transmit information about how to do so over the insecure channel. How can they exchange information to create a secure channel, without the potential man in the middle altering that information?

• Tell the public key bit by bit ( or, hex by hex). Is this a homework question? Commented Aug 6, 2020 at 13:31
• It is manipulable though. Simple things like that. The proof with the most hardness (most difficult to manipulate with video editing etc. ) is to generate a video proof before exchanging any other data. At that time, Alice and Bob have "information-theoretic anonymity", the social proof equivalent of perfect secrecy or information-theoretic security. Then, encrypt a hash of proof + public key for secure channel, encryptedProof = encrypt((videoHash, publicKey), encryptionKey), and exchange the encryptedProof. Then, wait a few minutes, and exchange encryptionKeys. Then create channel with pk. Commented Aug 6, 2020 at 13:56
• @kelalaka is correct. Without further defining the problem, I'll just assume I can verify that the public key is yours (has your name in it and signed by a trusted third party). The untrusted channel cannot manipulate that. If they truly know nothing about each other, the problem isn't privacy, it's authentication.
– Marc
Commented Aug 6, 2020 at 15:41
• A mitm can always intercept in this case. If A knows nothing about B, she has no way of determining if she established a connection with B vs a mitm. Commented Aug 6, 2020 at 15:52
• If Alice and Bob do not have any prior way to authenticate each other, then this is an unsolvable problem. If Alice negotiates with someone, how does she know that that someone is Bob, and not Carl (or the MITM)? Commented Aug 6, 2020 at 19:59

I asked for a pretty unique use-case. Authentication to who the person is socially is not an issue there, just that the two human Just saying or communicating the public key for a secure channel, like Kelalaka said in a comment, seems like it could work but that it is still manipulable by video editing.

The most secure proof I came up with is that Alice and Bob produce a video proof before exchanging any data to begin with. At that time, Alice and Bob have "information-theoretic anonymity", the social proof equivalent of perfect secrecy or information-theoretic security.

It seems very secure, as secure as it can get. Alice and Bob both encrypt a hash of their video proof and their public key, and exchange the encrypted proof. The attackers have no information about Bob or Alice at the time Bob and Alice exchange their proof. Then after a few minutes, they exchange the encryption keys, they analyse the video proof, and use the decrypted public key to create a secure channel where they expect to meet the person from the proof.

• Again: the public key must be verifiable through other means than the insecure channel. This can be done by using a public key repository (eg: for pgp) or by having the keys signed by a trusted third party (eg: the web of trust). This makes the public key verifiable and cannot be manipulated without breaking public key cryptography or "fooling" the third party. There is no need for a ad-hoc proof, this is a solved problem if you have a trusted third party. If not, a public key does no good whatsoever and a full MITM (read/write interceptor) will make secure communication impossible.
– Marc
Commented Aug 6, 2020 at 21:04
• You can't use an insecure channel to bootstrap a secure one. If you don't know who Bob is, you can't be sure that's him in the video. If you don't know who you are trying to talk to, what does it even mean to be sure that you are talking to them? Commented Aug 7, 2020 at 0:33
• @Marc the problem was just to know that the person you are talking to is controlling the keys to the secure channel. I think the approach with pre-committed video proofs is very secure. Commented Aug 7, 2020 at 19:37
• @bmm6o no need to know who Bob is, just that Bob is controlling the keys to the secure channel so that no one else is receiving the data on the way to him. (I asked for a pretty unique use-case. ) Commented Aug 7, 2020 at 19:38
• Just to clarify, the question clearly states "Strangers cryptographically agree on secure video channel using information over insecure channel", as in that Bob and Alice are strangers to one another. Commented Aug 7, 2020 at 19:39