11
$\begingroup$

It there any way to, given a unidirectional channel, say a UDP messaging protocol, to derive a secret key and transmit information securely without prior knowledge of the other party? It sounds impossible, but maybe I am overlooking something.

What if the sender was to construct some kind of non-interactive proof of something and send it with the message?

Or if we relax the requirement that the sender knows nothing about the recipient, and say, is allowed to store a UUID or other very small piece of non-secret information that may be baked into firmware, is there any way of achieving an ephermal key-exchange process, over a one-way channel?

$\endgroup$
1

1 Answer 1

22
$\begingroup$

Let me reformulate your initial question. Bob wants to send a message to Alice such that Eve cannot know the content of the message. Bob has no prior knowledge about Alice.

This is impossible. Proof: suppose a valid protocol exists. Apply the exact same protocol, but with “Alice” and “Eve” swapped. Since Bob has no prior knowledge of Alice, “Alice” cannot appear anywhere in the protocol, so the resulting message from Bob is the same. But now Eve is the one who can decrypt the message, which is a contradiction with the validity of the protocol which states that only Alice can decrypt.

The same consideration applies to a bidirectional channel, by the way. There needs to be some way for Bob to distinguish between Alice and Eve. If Eve can snoop but not inject messages, then Alice's ability to send a message to Bob is what makes the problem solvable. The classic solution is Diffie-Hellman, but many other key encapsulation methods work. All have in common that Alice sends some form of public key.

If Bob knows Alice's public key, then Bob just needs to encrypt the message with Alice's public key. In fact, the problem is exactly public-key encryption: Bob needs to send information that only Alice can obtain, after having shared only public information with Alice, and with Alice allowed to choose what that public information is and to maintain secret information of her own. Public-key encryption is a well-known problem, so the question becomes how small the public key can get.

The smallest protocol I know of would be something based on ECC, for which the standard would be some variant of ECIES. The de facto standard minimum size for an ECC public key is 257 bits (using the compressed representation consisting of one 256-bit coordinate and one “sign” bit). It might be acceptable to go slightly below that. I think NIST still allows secp224r1 (225-bit public key). OpenSSL supports smaller curves, going as far down as secp112r1 but such a small size is definitely broken. Breaking encryption with an $n$-bit curve takes about as much work as brute-forcing an $n/2$-bit symmetric key.

It is possible to shave some bits off a public key by deciding that the first, or last, $c$ bits of the public key are some constant. This requires extra work when generating the key pair: you have to keep retrying the generation until the public key is within the desired range.

$\endgroup$
4
  • $\begingroup$ What if there exists publicly know unauthenticated pieces of information that all parties knew and could not modify, and a an intermediate trusted party Dave; such that Alice and Bob trust Dave. Alice can not interact with dave but Bob can. So Alice sends a message M to Bob, Bob asks Dave interactively to solve the problem so that Bob can the decrypt the payload sent by Alice. Imagine a Botnet with a data exfiltration protocol that can be embedded in one way protocols like NTP lookups, where it's better for Alice to not have to receive anything and allow an external party to do the work. $\endgroup$ Commented May 4 at 18:02
  • $\begingroup$ @WesleyJones I’m not sure how the new hypo is any better than the old one. Anything Dave does is something Alice could have done in Gilles’s scenario (note that you swapped the roles of Alice and Bob: Gilles had B sending to A, while you have A sending to B). Even if there’s trusted public information, if neither A nor B (nor, presumably, D) can influence it then there’s no advantage B has over E. E could read A’s message, then follow the algorithms both B and D use in order to learn everything B can learn. $\endgroup$
    – cpast
    Commented May 4 at 19:38
  • $\begingroup$ Since OP is talking about protocol design, it is probably worth noting that thure are existing protocols for one directional encrypted messages using public keys shared in advance, that could be stored in firmware or something. For example, PGP. $\endgroup$
    – Ben
    Commented May 5 at 14:25
  • $\begingroup$ Thanks for the help. I think what I will do is build the protocol to have two phases. 1. nodes will greet each other using ECDH and mutually authenticate. 2. nodes will use the peers public key (which they now know) and use it with ECDH deriving a key to encrypt the payload. No need to send the public keys with the message, because any node can be uniquely identified by public IP address. Active attacks are not pertinent, and so AES-256-CTR can be used. 96-bit IVs will be used and the protocol with have 12 bytes of overhead per message. Every byte counts. $\endgroup$ Commented May 6 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.