anonymous DH & MITM

[Zooko O'Whielacronx]

 Bear wrote:
>
> If it's an anonymous protocol, then "credit" for being a good chess
> player is a misnomer at best; the channel cannot provide credit to
> any particular person.

I understand the objection, which is why I made the notion concrete by saying 
that Mitch wins if he gets the first player to accept the second player's 
move.  (I actually think that you can have some notion of "credit" -- for 
example a persistent pseudonym linked to a longer-term public key, but that 
isn't necessary to appreciate the current challenge.)


> > Now, obviously Mitch could always act as a passive proxy, forwarding
> > exactly the bits he receives, but in that case he can be defeated by
> > e.g. DH.  To make it concrete, suppose that the first player
> > includes both his move and his public key (or his public DH
> > parameters) in his message, and the second player encrypts his
> > message with the public key that arrived in the first message.
> 
> Public key? I thought we were talking about an open protocol between
> anonymous entities.  If Alice and Bob can identify each other's public
> keys, we're not talking about anonymous entities.

Right.  I proposed that the first player send a public key even though the 
second player has no way to authenticate it.  The effect of this is that Mitch 
can no longer act as a purely passive proxy (i.e., he can't act like an Eve), 
because if he does the second move will be encrypted so that he can't read 
it.  Oh -- whoops!  This doesn't suffice to deter Mitch from acting as a 
passive proxy, since we didn't specify that he had to actually see the second 
move in order to win.  Maybe we should add the requirement that for Mitch to 
win he has to know what the second player's move was.

Sorry about the incorrect detail.


> > Now, you might intuitively believe that this is one of those
> > situations where Mitch can't lose.  But there are several protocols
> > published in the literature that can help the players against Mitch,
> > starting with Rivest & Shamir's Interlock Protocol from 1984.
> 
> Hmmm.  I'll go read, and thanks for the pointer.  But I'm confident
> that if Mitch can be kept out, then either it's not fully anonymous
> participants, or it's not a fully open protocol.

I understand where you are coming from.  Your intuition about this is usually 
right (i.e., for pretty much all protocols that you have ever actually 
encountered), and it is an intuition that you share with most thinkers, even 
those who are brilliant and well-read cryptographers.  However the Interlock 
Protocol provides a counter-example to that intuition!  (Not for Chess 
Grandmaster, but for a full-duplex protocol such as Bughouse Grandmaster).

There are other counter-examples in the literature, which I would be happy to 
enumerate.  :-)


Please let me know if you find an on-line copy of Rivest & Shamir Interlock 
Protocol 1984.  I had to walk down to a library to read it.

Regards,

Zooko

http://zooko.com/log.html

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