anonymous DH & MITM

[bear]

On Fri, 3 Oct 2003, Benja Fallenstein wrote:

>bear wrote:

>> Why should this not be applicable to chess?  There's nothing to
>> prevent the two contestants from making "nonce" transmissions twice a
>> move when it's not their turn.
>
>I.e., you would need a protocol extension to verify the nonces somehow--
>if that's possible at all-- or are you just faster than me, and have
>thought about a way to do that already?

Not "faster" per se, but I do happen to know the solution to that
problem.  :-)

Suppose Alice picks a nonce A(zero).  Then for n=one to a thousand
(presumably no chess game will last 1000 moves) she calculates A(n) =
hash (A(n-1)).  Note, this has to be a ONE WAY hash function rather
than any kind of encryption that can be decrypted.  I'd suggest
seventeenth-power mod K where K is prime, but lots of good
irreversible hashing functions that aren't so expensive in CPU cycles
are around.

Bob also picks a nonce B(zero) on his side, and produces the same kind
of sequence of B(one...one thousand) using the same hash function.

Now let the moves of the chess game be numbered from 1000 down to 0.
(ie, the first move they play will be move 1000, the second will be
move 999, etc.)

When it's Bob's turn, he sends his move padded with B(n), and Alice
sends a random move padded with A(n).  When it's Alice's turn, she
sends her move padded with A(n) and Bob sends a random move padded
with B(n).

Bob can rapidly check to make sure that the A(n) recieved with each
message has the right relation to the A(n+1) he recieved with the
previous move, but there is no way he (or Mitch) can possibly predict
A(n-1) to know what he'll get in the next move.

Likewise Alice can rapidly check to make sure that the B(n) recieved
with each move has the right relation to the B(n+1) she recieved with
the previous move, but there is no way she (or Mitch) can predict
B(n-1) to know what she'll get the next move.

The only change to the rules of chess this requires is that if they
ever exhaust the finite sequence of generated nonces, they have to
call that game a draw.  But a thousand moves, really, shouldn't be a
problem for chess, and if it is you can just make the sequence longer
and start a new game.

				Bear

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com