[Cryptography] Silly Diffie-Hellman question using XOR

realcr realcr at gmail.com
Wed Mar 5 14:01:07 EST 2014

Hey, Sorry for posting twice, I think I have now understood what you wrote.

Let us assume that Mallory is listening to the wire.
In your proposed protocol, in step 2 Alice sends A2, so A2 is known to
Mallory. Also Bob sends B2, so B2 is known to Mallory.

In step 3, Alice sends A1 ^ A2 ^ B2. As A2 and B2 are already known to
Mallory, it means that A1 is known to mallory.
In the same way, we get that B1 will be known to mallory.

Eventually, In the end of step 3 Mallory knows A1,A2,B1,B2. Thus she could
infer every secret that might be created in step 4.


On Wed, Mar 5, 2014 at 4:26 PM, Stuart Longland <stuartl at longlandclan.yi.org
> wrote:

> 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
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140305/4e608bff/attachment.html>

More information about the cryptography mailing list