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

[Jeff Burdges]

Appears there is a much easier way to do all this.  

Idea 2 below effectively modifies ECDSA to sign a mathematical
relationship between two numbers, as opposed to signing the number
directly.  It's slightly opaque what that mathematical relationship is,
but one must still take great care that the numbers are random and not
themselves signed.

I now think this care with randomness alone suffices and one does not
need to modify ECDSA at all.

Key exchange algorithm : 

Trip 1.  Alice generates a blinding values x_A,y_A and an ephemeral key
pair (a',A').  Alice connects to Bob and sends (B', hash(x_A) ).

Trip 2.  Bob generates a blinding values x_B,y_B and an ephemeral key
pair (b',B').  Let s_2' = a' B' = b' A' denote the ephemeral DH secret.
Let s_2 = hash(K ++ s_2') where K is a protocol specific value.  Alice
connects to Bob and sends (B', nonce, e) where e = encrypt(s_2,nonce,
m_2) where m_2 = (x_B hash(y_B)).  

Alice and Bob now share the ephemeral DH secret s_2' and s_2.  Alice
therefore extracts x_B = decrypt(s_2, nonce, e).  If decryption fails,
then Alice drops the connection, probably not the right protocol.

Trip 3.  Let (a,A) and (b,B) denote Alice and Bob's longer term key
pairs.  Let s_3' = a' B = b A' be a partially ephemeral DH secret.  Set
s_3 = has(s_3' ++ s_2).  Also let x = x_A xor x_B denote this random
number collaboratively generated by Alice and Bob.  Alice sends (nonce,
encrypt(s_3, nonce, m_3 ) ) where 
        m_3 = (x_A, y_A, A, sign(a, x xor m')) )
        m' = hash(K ++ A ++ B ++ hash(s_2)
Bob decrypts m_3 and verifies hash(x_A) from the first message and
Alice's signature.  If decryption or verification fails, then Bob drops
the connection.

We sent hash(x_A) in the clear, but x_A and x_B traveled over the wire
encrypted, so our adversary cannot know them without breaking one side
of the key exchange.  We claim the following properties : 
- Alice's signature is deniable in that Bob could claim any x_B he likes
to sign any message he likes retrospectively.  
- Alice cannot manipulate x_A to be using a forged signature because she
committed to her choice of x_A in Trip 1.

Trip 4.  Let s_4' = b' A = a B' be a partially ephemeral DH secret.  Set
s_4 = has(s_4' ++ s_3).  Also let y = y_A xor y_B.  Bob sends (nonce,
encrypt(s, nonce, m_4 ) where
        m_4 = (y_B, sign(b, y xor m'), ...)

As y has similar properties to x, we claim analogous properties for
Bob's signature as we did for Alice's signature in Trip 3.  I donno if
we really need a fully separate y value here, but :
- If we omit Bob's signature all together, then Alice is vulnerable to
the wildcard attack if her private key is compromised.  
- If we use x in constructing Bob's signature, then Alice early
commitment might be problematic.  I'll need to think about y further.

I'll write this up in latex once I've figured out the y business and
chatted with Christian further.


On Mon, 2015-08-24 at 17:00 +0200, Jeff Burdges wrote:
> 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. 
> 
> _______________________________________________
> GNUnet-developers mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/gnunet-developers

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