1
$\begingroup$

Through repeated DH attempts, could Alice and Bob build a large random key for use as a one-time pad? My intuition is that this protocol would be as hard as breaking DH (discrete logarithm).

$\endgroup$
  • 1
    $\begingroup$ Not posting as an answer since I'm not 100% certain, but I'm pretty sure that DHE does not distribute evenly across the set underlying the group it is done over. In which case it would not be a valid random number generator. Stream ciphers are the common way to "build" a keystream that can be xor'd with the plaintext, but even assuming a perfect RNG for the seed their security becomes dependent on the security of CSPRNG they use to expand the keystream, so they are not "perfect" in the sense that a OTP is. $\endgroup$ – sju Nov 23 '14 at 15:18
  • $\begingroup$ You could run the exchange once and put the result in some CSPRNG, and use that for your stream cipher. DH is expensive. $\endgroup$ – rath Nov 23 '14 at 15:19
  • $\begingroup$ Samuel Judson, I am pretty sure DHE does in fact give you a key that is computationally indistinguishable from a uniformly random key (under the DDH assumption). So this scheme should work. However, as rath notes it would probably not be a very efficient scheme. $\endgroup$ – Guut Boy Nov 24 '14 at 9:18
  • $\begingroup$ @Guut Boy: when working modulus $p$, the $j$-th high bit of the outcome of DH key exchange has a bias, in the order of $2^{-j}$; so you need to ignore enough high bits (or use a post-processing like a hash) in order to get practical security even if you do not consider MiTM attacks. $\;$ And of course neither DH, nor the proposed system, is secure against MiTM attacks. $\;$ (Notice the use of @ so that you are notified of the comment). $\endgroup$ – fgrieu Nov 24 '14 at 10:11
  • $\begingroup$ @fgrieu really? Could you elaborate on the bias? (or point to explanation of it). My intuition says that the key should be computationally indistinguishable from random in the group we are working in (by the DDH assumption). Of course this will not be a random bit-string, instead you just do OTP in the particular group. $\endgroup$ – Guut Boy Nov 24 '14 at 11:10
1
$\begingroup$

Through repeated DH attempts, could Alice and Bob build a large random key for use as a one-time pad?

No, since that is not how a one time pad works. You can use your idea to create cryptographic material to encrypt plaintext using XOR, what you are describing is an asymmetric stream cipher of some sorts.

A one time pad requires an "offline" exchange of key material. A one time pad when used properly is unbreakable, whereas a DH exchange can be broken or potentially maliciously interfered with. Using this idea may potentially expose a weakness in the PRNG used to generate the private keys, but that same problem is applicable to whatever is generating a true OTP. I this case however, the public key exchange may expose this weakness much earlier than an offline key exchange, as no ciphertext would be needed.

This idea may be significantly faster than an offline key exchange, but that depends on how much key material needs to be created. In your example, the shared secret would generally be passed through a hash function to distribute entropy more evenly over the bits, or possibly reduce the size of the shared secret so the entropy per bit is higher.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I do not think it is correct to say that you could not do this. It is true that you would not get an encryption scheme that is as secure as OTP. However, that is not what is asked. The question explicitly says that the security would be that of the key exchange protocol, which is correct. $\endgroup$ – Guut Boy Nov 24 '14 at 8:44
  • $\begingroup$ I tried to say you would not be generating a one time pad, not that it could not be done. I thought that was clear, but I will edit my answer to make it more so $\endgroup$ – Richie Frame Nov 24 '14 at 9:18
  • $\begingroup$ @Guut Boy: The question states "protocol would be as hard as breaking DH (discrete logarithm)", which is wrong even if we ignore the minor issue that breaking the DH problem might be easier than breaking the discrete logarithm problem. The issue is that reference to "discrete logarithm" makes it clear "DH" means the DH problem, not the DH protocol (because there is no discrete logarithm protocol). And the proposed protocol (as well as the DH protocol) is trivially broken by MiTM, when the DH problem is not. $\endgroup$ – fgrieu Nov 24 '14 at 10:34
  • $\begingroup$ OTP does not necessarily require an offline key exchange. $\endgroup$ – mikeazo Nov 24 '14 at 12:18
  • $\begingroup$ @mikeazo not 100% sure, but would that not require an optical quantum key exchange system to be secure? $\endgroup$ – Richie Frame Nov 24 '14 at 20:12

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.