[Cryptography] Silly Diffie-Hellman question using XOR

[Stuart Longland]

Hi all,

I'm not sure if this is the right "forum" to ask this, I stumbled on this 
mailing list whilst looking through the newsgroups on my NNTP server; I 
see this list is one of a couple that pop up (via gmane).

I was doing some thinking about ways of establishing shared secrets over 
a public medium.

The use case here that I'm thinking of is for allowing authentication of 
individuals over a medium that prohibits encryption.  Examples of this 
would be some countries (i.e. in the past France prohibited encryption, 
China at best frowns upon it), and also amateur radio.  My intent here is 
to have some means of proving that the other person is who they say they 
are by means of the web-of-trust.

GPG seems a good fit here, but public key crypto is expensive: good for 
that initial contact and negotiating a shared secret, but expensive to 
keep on with indefinitely.  The thought is that the initial shared-key 
exchange is signed using asymmetric crypto (i.e. GPG, and using its web-
of-trust feature to authenticate), to negotiate a session key which can 
be used as a HMAC key for verifying traffic.

Thinking about the problem, it seems Diffie-Hellman is one to achieve 
this.  From what I see, D-H key exchange normally works using modulo 
arithmetic and prime numbers (big ones).  I wondered if simple XOR (which 
is commutative) could work.

Conventional D-H relies on having a common secret: this won't work with 
XOR... it takes two inputs and produces an output, you need to know any 
two pieces to produce the third piece of data.  The thought is to do away 
with the common secret altogether.

i.e. two parties, Alice and Bob wish to establish a shared key.

1. Alice generates two keys: A1 and A2.
   Bob generates two keys: B1 and B2.
2. Alice signs A2 and sends A2 + signature to Bob.
   Bob signs B2 and sends B2 + signature to Alice.
3. Alice verifies B2+signature, then generates
      A3 = A1 ^ A2 ^ B2.  Alice signs A3 and sends to Bob.
   Bob verifies A2+signature, then generates
      B3 = B1 ^ B2 ^ A2.  Bob signs B3 and sends to Alice.
4. Alice verifies B3+signature, then generates
      A4 = B3 ^ A1 = B1 ^ B2 ^ A2 ^ A1
   Bob verifies A3+signature, then generates
      B4 = A3 ^ B1 = A1 ^ A2 ^ B2 ^ B1

Since XOR is commutative; A4 and B4 should be identical.  A1 and B1 are 
never revealed in public.  XOR is computationally inexpensive, not the 
strongest, and probably wouldn't stop a determined (i.e. state-backed) 
cracker.  Information theory would be useless as the keys would be random.

The keys in my case would be used with keyed hashes, but the same scheme 
could generate crypto keys too.

I'm guessing that, if done frequently enough (and it's simple enough it 
should be computationally inexpensive to negotiate new secrets) it'd be 
nearly impossible to guess A1 and B1 fast enough before the session 
became invalid with today's technology.

Anyone here have any thoughts on this?  Did I overlook something 
fundamental?

Regards,
Stuart Longland