1
$\begingroup$

We know that perfect secrecy in encryption is possible (one-time pad). Now, the concept of key exchange like Diffie-Hellman is that we can establish a shared key without an interceptor knowing, and with no previous communication.

Obviously, for Diffie-Hellman as such, an interceptor can actually find the shared key; it would just take them ridiculously long. But I'm wondering, is it possible to make it impossible for the interceptor to find out the shared key?

I know that no such key exchange currently exists, but is it proven that it's impossible for such a scheme to exist? Or is there a chance it could be invented?

Improve this question
$\endgroup$
1
$\begingroup$

Lets start with a set of basic assumptions.

  • The communication channel transmits a sequence of symbols with each symbol taken from a finite set, there is no weird quantum stuff going on.
  • The attacker can obtain a complete record of the symbols that were transmitted.
  • The end systems are finite sized computers fed from a finite sized random number generator and run for a finite amount of time.
  • The purpose of the key exchange algorithm is to establish a shared secret.
  • No secrets were known by the end points prior to the start of the key exchange process.

I believe that in this case an attacker with unlimited computing power can always crack the key exchange.

The attacker can simply enumerate all the possible outputs of the random number generator. Feed each one into the key exchange algorithm and compare the data that the algorithm generates with the data that was observed on the wire.

If the data exchanged on the wire matches then the shared secret must match.

Improve this answer
$\endgroup$
4
  • $\begingroup$ what if the algorithm requires certainly in a secret key generated by at least one party? similarly to how perfectly secret encryption cannot be brute forced; you have to first be certain that the key you're using is correct, and its correctness is unverifiable $\endgroup$
    – user2894959
    Jul 2 '18 at 0:32
  • $\begingroup$ No secrets were known by the end points prior to the start of the key exchange process does that mean neither side has a private key? I think to be fair you'd want to at least assume that each end point has each others public key already. $\endgroup$
    – Ella Rose
    Jul 2 '18 at 3:03
  • $\begingroup$ I was considering the unauthenticated key exchange case (hence why I talked about a passive attacker) but digital signatures fall to a similar argument if you have unlimited processing capability, just try all private keys until you find the one that matches the public key. $\endgroup$
    – Peter Green
    Jul 2 '18 at 3:12
  • $\begingroup$ Note: we are not discussing practical attacks here, we are discussing whether something can be information theoretically secure (secure if the attacker has unlimited computing power) or merely secure for feasible levels of computing power. $\endgroup$
    – Peter Green
    Jul 2 '18 at 3:13
0
$\begingroup$

Actually, there already exists such a key exchange scheme: Quantum key distribution.

It's proven to be 100% secure to exchange a key between two parties and a third party can never retrieve the key.

Improve this answer
$\endgroup$

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.