[Cryptography] Silly Diffie-Hellman question using XOR

Stuart Longland stuartl at longlandclan.yi.org
Wed Mar 5 09:26:28 EST 2014

```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

```

More information about the cryptography mailing list