Can a key exchange protocol exchange a one time pad instead of a key?

Question

As I understand key exchange, two parties can agree on a fixed number of secret bits in the presence of a listening adversary. That set of bits forms a cryptographic key which is then used to encrypt data using a standard cryptographic algorithm. And that key is repetitively used over and over, perhaps for an AES session.

What if instead of a key for cryptographic algorithms, a one time key was exchanged for use with a one time pad construct? My system would then exchange another pad for the next message. Could you realistically securely exchange 1280 bits /160 bytes for a Twitter length message?

Note. A true random number generator is available.

EDIT. From initial comments, it seems that the security of the OTP key would be contingent on the security of the key exchange mechanism, say Diffie-Hellman, RSA or similar. So I guess a fundamental part of my cunning scheme would be the ability to use a key exchange mechanism that provided > (160*8) bits of security. Wouldn't that then mean the security proof of the OTP was still maintained? This is a theoretical exercise, so performance is not a consideration (unless we're talking of geological timescales that make it de facto impossible). Could it be done for example as one message per 24 hrs using a modern desktop machine? An SOE agent might only send one message per week in WW2. Just some temporal context.

Answer 1

In theory it could work, if you can ensure that the resulting key is actually generated uniformly from the full range, as long as one party chooses its input uniformly.

A rough sketch for a proof: Consider the inputs $x$ and $y$ to the key exchange $f(x,y)$. Then if you consider one input fixed the key exchange has to be a bijection. You need to proof that for every $x$, $f$ is a bijection between $y$ and $f(x,y)$.

But on the practical side, I can't think of any realization of this, where we can actually prove that. The obvious candidate is the DH key exchange. But if we use a generator $g$ for the full group, then we can't prove the above property: Assuming any fixed $x$, then $g^{xy}$ is not always a bijection, there is the counter example $x = 2$. If $g$ is a generator of a prime order group, then this property would hold. However, in this case you can only reach the elements of this particular subgroup and not all group elements. You would need a bijective mapping from the subgroup with $k$ elements to $\{0,1,\dots,k-1\}$ or similar. And that should be difficult, unless you assume you are able to calculate the DLOG. And this problem exists for both classical and EC-based Diffie-Hellman key exchange.

Answer 2

I think there's a problem here in that you're not specifying an attack model—what does the adversary see, and what powers do they have? For example, in the case of the one-time pad a standard analysis would assume that the adversary sees the ciphertexts but neither the keys nor the plaintexts.

But now in your hybrid key exchange + OTP proposal, what do you assume that the adversary sees? I would say that the reasonable assumption is that they get to see the participants' public keys, the transcripts of the key exchanges and the OTP ciphertexts, but not the private keys, the plaintexts or the pads.

But for a computationally unbounded adversary that's clearly enough to break the key exchanges, which in turn allows them to recover the pads and everything else. The security of the composition can't be better than its weakest link—the key exchange. (And, incidentally, key exchange algorithms in common use have a security level smaller than their key and transcript lengths, and the values involved have mathematical structure and relationships that can be used to attack them.)

The one-time pad encryption scheme has proofs of "unconditional" security, but those proofs are still carried out in a model whose assumptions your scenario doesn't fit. So those proofs don't transfer over.

Answer 3

An AES key should ideally be uniformly random just like an One-Time-Pad (OTP) key. So if your key exchange protocol can be used to generate an AES key, the same key can be used for OTP (obviously the key should not be used for both though).

However, such a system would likely be impractical as you would have to run the key-exchange protocol rather often. Additionally, if you care about things like malleability of your ciphertext, OTP might not be a great choice.

Addition: As I write in the comments above, you should of course also be aware that the security of the overall scheme would rely on the security of the key-exchange protocol. If that is broken, the key will obviously not be good.