anonymous DH & MITM

[Zooko O'Whielacronx]

 Bear wrote:
>
> DH is an "open" protocol; it doesn't rely on an initial shared
> secret or a Trusted Authority.
> 
> There is a simple proof that an open protocol between anonymous
> parties is _always_ vulnerable to MITM.
> 
> Put simply, in an anonymous protocol, Alice has no way of knowing
> whether she is communicating with Bob or Mallory, and Bob has no way
> of knowing whether an incoming communication is from Mallory or from
> Alice.  (that's what anonymous means).  If there is no shared secret
> and no Trent, then nothing prevents Mallory from being the MITM.
> 
> You can have anonymous protocols that aren't open be immune to MITM
> And you can have open protocols that aren't anonymous be immune to
> MITM.  But you can't have both.

I'd like to see the proof.

I think it depends on what you mean by "MITM".  Take the Chess Grandmaster 
Problem: can Alice and Bob play a game of chess against one another while 
preventing Mitch (the Man In The CHannel) from "proxying" their moves to one 
another while taking the credit for being a good chess player?

To make it concrete, suppose we limit it to the first two moves of a chess 
game.  One player is going to make the first move for White, and the other 
player is going to make the first move for Black.

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.

Mitch wins if the first player accepts the second player's move (the first 
move for Black).  The players win if the first player accepts a different move 
that the second player didn't make.  (This is the case where Mitch is no 
longer doing the Chess Grandmaster Attack, but is instead just playing two 
games of chess, one game with the first player and another game with the 
second player.)

If the players reject a message and end the protocol, then neither Mitch nor 
the players win -- it is a tie.  (A denial-of-service situation.)

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.

The funny thing is that all of these published protocols seem to require a 
constraint on the game of chess.  For example, the Interlock Protocol works 
only with "full duplex" games where both sides are making a move at the same 
time.  You can't obviously apply it to chess, although you *could* apply it to 
a full-duplex game like chess variant "Bughouse", or, um, children's card 
game "War".  Or a "Real-Time Strategy" computer game where both players are 
sending moves to one another simultaneously.

Now, you might go back to the beginning of this message and say "Well, Chess 
Grandmaster isn't MITM!".  In that case, I would like to see a definition of 
what exactly is this "MITM" which can't be countered in the no- shared-trust 
setting.  I'm not saying that there isn't such a thing -- indeed I can think 
of a definition of "MITM" which satisfies that requirement, but I'm not sure 
it is the same definition that other people are thinking of.

Anyway, it is a funny and underappreciated niche in cryptography, IMO.  AFAIK 
nobody has yet spelled out in the open literature what the actual theoretical 
limitations are.


Regards,

Zooko

http://zooko.com/log.html

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