1
$\begingroup$

Context

I recently came across a video on the net showing the process of key exchange in Diffie Hellmann.

Alice and Bob want to communicate. Eve is the (wo)man in the middle.

This video is the basis of my question http://youtu.be/YEBfamv-_do?t=6m22s

Question

Alice sends the modulo and the prefix to bob. Eve gets that.

What prevents Eve to have a giant table of all the calculations possible given a prefix and a modulo and the public value and intersect thos possibilities with the public value from bob ?

Yes the table would be very big but you can then iterate over the intersecting possibilities and try the numbers on the message up to the point to get something right.

i may miss something, but it is not that hard, even with very big numbers.

So what did I miss ?

Thanks

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ You're underestimating what "very big" means. No conventional computer will ever be able to count to $2^{256}$ and that doesn't even consider storing that much. $\endgroup$
    – CodesInChaos
    Commented Nov 19, 2014 at 8:55
  • 3
    $\begingroup$ the "giant table" would be as large or larger than the observable universe for the key sizes currently used (4096-bits), and take more energy to search than was released by the big bang $\endgroup$
    – Richie Frame
    Commented Nov 19, 2014 at 9:09
  • $\begingroup$ What "prefix" does Alice send to Bob? $\;$ $\endgroup$
    – user991
    Commented Nov 19, 2014 at 10:30

2 Answers 2

Reset to default
4
$\begingroup$

A lot of modern cryptography is based on some mathematical assumptions and aims to achieve what is called Computational Security. That means that the adversary (Eve) could get some information about the plaintext with a negligible probability and the adversary is modeled as someone with bounded computational power, storage and bounded time. So all the (encryption) schemes are dimensioned in sort to achieve such level of security: that means that all mathematical elements are chosen to be large enough to make the best known attack feasible in a reasonable amount of time.

Even if this is a weaker notion of security, this assumption on the adversary is easy to accept in practice.

Other approach exists: Information theoretic Security or Perfect Security

So coming back to your solution based on a big table, if the scheme is correctly dimensioned the table you are supposed to use to attack the scheme would be so large that it cannot be stored in a (very very) large disk or to be (too) long to be generated.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I think it is time for me to write a paper. $\endgroup$
    – Larry
    Commented Nov 19, 2014 at 8:33
  • $\begingroup$ What do you mean? $\endgroup$
    – ddddavidee
    Commented Nov 19, 2014 at 8:34
  • 7
    $\begingroup$ @Larry I look forward to your paper where you ridicule the entire cryptographic community. Please jot me down as the idiot that ridiculed you before you proved that the crypto community is a bunch of asses :) $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 19, 2014 at 10:10
  • 1
    $\begingroup$ @Larry if you are somehow able to find a solution to storing $4.4*10^{598}$ times the total amount of storage in the world then I believe you will become far too rich to worry about breaking Diffie-Hellman. $\endgroup$
    – flashbang
    Commented Nov 19, 2014 at 21:32
  • 1
    $\begingroup$ Humans are so bad at understanding exponential growth... Best example is the question "How often can you fold a paper, and guess how thick it will be" -> typical are 6 or 7, record is at 12 atm $\endgroup$
    – tylo
    Commented Nov 24, 2014 at 14:54
1
$\begingroup$

Guess the catch in the video is in how the participants exchange details 'publicly'.

If the Man-In-The-Middle can intercept and manipulate what is being 'publicly' shared, then the attempt to eavesdrop would still be successful.

Improve this answer
$\endgroup$

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.