Re: [GNUnet-developers] key exchanges [updated, resend]

[Jeff Burdges]

We'll try this once more.  

Setup :  Bob sends Alice a scalar x or maybe a point X = x Q.  Let a be
Alice's private key.  

Idea 1 :  Bob should effectively run ECDSA_Bob(x A,m) where A = a Q is
Alice's public key, but we're hoping that if Bob does so by running a
slightly different algorithm varECDSA_Bob(x,A,m) then he cannot prove
Alice signed it.  Also, Alice should effectively run ECDSA_Alice(x a,m)
but by running a different algorithm varECDSA_Alice(a,X,m).

Can this work?  Not as stated.  If Alice send Bob the same wire values
as with ECDSA, then Bob possesses a signature by x A.  We prove this
violates deniability : Imagine Bob could choose x and y such that x A =
y Q.  As Bob knows x, Bob can compute x^{-1}, so Bob can compute b =
x^{-1} y with the property that A = b Q, violating assumptions on our
Elliptic curve.

Is there a variation that does not send the same wire values?  Maybe.
We suspect that introducing an additive constant should allow Bob to
fake Alice's signature.  

Check out the description of ECDSA here : 
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Idea 2 :  Bob sends Alice a scalar x.  Alice sends (r',s) over the wire
where s is computed as before, but r' = r + x = x_1 + x mod n  !=  r =
x_1 mod n.  This fails deniability because Bob can compute r = r' - x
mod n to get a valid ECDSA signature.

Idea 3 :  Bob sends Alice a scalar x.  Alice send (r,s) but computes r =
x_1 + x mod n instead of r = x_1 mod n, thereby altering her computation
of s too.  

Does this verify?  Yes.  Bob computes 
 u_1 G + u_2 Q_A 
  = (z s^{-1} + r s^{-1} d_A) G 
  = (z + r d_A) s^{-1} G
  = (z + r d_A) (z + r d_A)^{-1} k G
  = (x_1,y_1)  as desired.
So Bob's verification that r = x_1 + x mod n convinces him that Alice
signed the message.  

Can Bob fake Alice's signature?  Yes.  Bob picks (r,s) at random and
computes (x_1,y_1) as above.   Bob now picks x = r - x_1 mod n. 

It's critical that an adversary cannot observe x traveling over the
wire, so Alice must not accept x until after she and Bob have
established an encrypted connection.  

Idea 4 : Can we do the same with EdDSA?  Not quite so easily

EdDSA computes R as a hash of Alice's private key with the message,
meaning that if Alice's private key is ever compromised then her
signatures become non-deniable.
        See p.6 in http://ed25519.cr.yp.to/ed25519-20110926.pdf
There is probably an approach that works for EdDSA too, like by using
random values when computing R, but this changes the nature of EdDSA
enough that another name might be more appropriate. 

Jeff

p.s.  I've attached a latex version of part of this email that's kinda
beginning to a paper.

wild_vs_deny.pdf
Description: Adobe PDF document

signature.asc
Description: This is a digitally signed message part