The way Applied cryptography 2ED explains the puzzle is as follows (I paraphrase it):
Bob generates 2^20 messages of the form
xis a puzzle number and
yis the secret key. Both
yare 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.
Alice picks one at random and brute force it. She should be able to recover x and y.
Alice encrypts her message to Bob by using
yshe just recovered (using symmetric cipher). Her message will contain
x, the puzzle number.
Bob looks up the secret key for puzzle
xand 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
x is encrypted in Alice response, then Bob have to brute force like Eve too, no?