The way Applied cryptography 2ED explains the puzzle is as follows (I paraphrase it):
Bob generates 2^20 messages of the form
x,y
wherex
is a puzzle number andy
is the secret key. Bothx
andy
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.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
y
she just recovered (using symmetric cipher). Her message will containx
, the puzzle number.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?