0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ (Not a down voter): How can you exchange a key while retaining the security benefits of a OTP? (assuming you don't mean "physical distribution of a CD" by "key exchange". If you use RSA or DH or lattices or whatever to establish a key, even assuming it did produce properly distributed output, your key is only as strong as the number theoretic problem that backs the public key operation. Symmetric options like a shared seed with hashing are clearly a stream cipher and not a OTP, so that can't be what you want either. $\endgroup$ – Ella Rose Nov 14 '17 at 17:47
  • $\begingroup$ @EllaRose you could say the same of an AES key. In this case you reduce the security of your OTP system to the hardness assumption of the key-exchange protocol. But the key should still be good given that assumption. $\endgroup$ – Guut Boy Nov 14 '17 at 17:50
  • 2
    $\begingroup$ @GuutBoy That's true regarding an AES key, but the problem I see is how it can still be considered a OTP in that the only way to recover the plaintext from the ciphertext is to know which key. It's easy (in an information-theoretic sense) to know which key was used without being Alice or Bob - just factor the modulus or take a discrete log or solve LWE, and you have demonstrably violated the security guarantee of a OTP. $\endgroup$ – Ella Rose Nov 14 '17 at 18:25
  • 1
    $\begingroup$ @EllaRose sure, you do not get information theoretic security. Still, you could make a similar argument for AES, which is also not based the RSA or LWE assumptions. $\endgroup$ – Guut Boy Nov 14 '17 at 19:56
  • $\begingroup$ On your edit I think a lot of key exchange protocols 'pop' open, I didn't google the actual cryptography term but I mean you can deduct when you have the right private key. For example with RSA if you brute force it (or if someone tells you the private key) you know as you have the only two prime factors possible. If your key was passed hand to hand then an attack has no feedback that they have the right key. $\endgroup$ – daniel Nov 15 '17 at 12:00
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I expect to run the key exchange protocol for every single message. That's the point. Impractical perhaps, but possible? $\endgroup$ – Paul Uszak Nov 15 '17 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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