2
$\begingroup$

The way Applied cryptography 2ED explains the puzzle is as follows (I paraphrase it):

  1. Bob generates 2^20 messages of the form x,y where x is a puzzle number and y is the secret key. Both x and y are different for each of the one million message. Encrypt each message using symmetric cipher with a different 20-bit key. Send all messages to Alice.

  2. Alice picks one at random and brute force it. She should be able to recover x and y.

  3. Alice encrypts her message to Bob by using y she just recovered (using symmetric cipher). Her message will contain x, the puzzle number.

  4. Bob looks up the secret key for puzzle x and decrypts the message.

According to the book and many Internet sources, Eve would have to do theta(n^2) work to brute force the communication.

The book doesn't seem to say much about how x is included in Alice's response to Bob. It must be not be encrypted right? Because Bob has to do a O(1) look up. That is, Alice would have to send x+E(private message, y) to Bob.

Then why can't Eve just wait for Alice's response to Bob and compute that puzzle?

This is the brute force algorithm I think would satisfy 2^n if x is encrypted in Alice's response as well.

for y in 2^20:
   for x in 2^20:
       c = symmetric_enc(y, x)
       if c == c_from_alice:
           return yes, c, x, y
return no, none, none, none

But if x is encrypted in Alice response, then Bob have to brute force like Eve too, no?

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

$x$ is not encrypted in Alice’s response. The point is that, even though Eve knows the puzzle number $x$, she has no way to tell which of the puzzles Bob sent is the one with this number, unless she solves all of them (or at any rate half of them, on average).

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks. If x is encrypted in Alice's response, how is Bob able to tell which x in constant time? Now that I think about it, Bob might only need to do n encryption to find out which x. In other words, since Bob has a table with x and key as columns, he can do 2^20 encryptions to find out. So this is the difference and my assumption that Bob does only O(1) is wrong right? Otherwise, Eve can do O(1) as well. Am I correct? Does x really have to be encrypted in Alice's response? $\endgroup$ – CppLearner Oct 28 '13 at 10:57
  • $\begingroup$ @CppLearner Sorry, I should have been clearer: $x$ is not encrypted in Alice’s response. I have edited the answer to make it clearer, I hope. $\endgroup$ – Robin Houston Oct 28 '13 at 11:55
  • $\begingroup$ @CppLearner By the way, if you haven't read it Merkle’s original paper on Merkle puzzles explains the whole process pretty clearly (though apparently no one at the time understood it: I guess secure key exchange over an insecure channel was just too radical an idea for the cryptographers of the early ’70s!) $\endgroup$ – Robin Houston Oct 28 '13 at 12:00
  • $\begingroup$ Thanks. I will read that paper later this week. I am not convinced. Each message corresponds to a different x. x is just an index for looking up the secret key for Bob to reply back to Alice. So if x is known to Eve, that is, Eve knows exactly which one to try, then she just needs to brute force the initial message x. In other words, if Bob sends [1,2,3] and Alice brute forced 2 and sends (2, message) to bob, then Eve just brute force 2 like Alice does and that's only 2^20 bits of secret keys trial (because different key produce different ciphertext). $\endgroup$ – CppLearner Oct 28 '13 at 14:17
  • $\begingroup$ @CppLearner The part it sounds like you’re missing is that the mapping from x to y is a secret known only to Bob. Even though Eve knows the value of x, she doesn’t know the secret key. $\endgroup$ – Robin Houston Oct 30 '13 at 19:45

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.