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

[Jeff Burdges]

Appears ECDSA does not use the private key material in exactly quite the
same way as ECDH, so this gets tricky. 


Alice can derive another private key from her private key, but she then
faces a conundrum : If she gives Bob both the derivation scalar and a
signature, then she has provided Bob with a non-deniable signature.


Does Bob need both for authentication?  Not necessarily.  Bob could
authenticate Alice with a cut-n-choose protocol.

Alice generates scalars x_1,...,x_n.  Alice sends Bob x_i A for i in
[1,n].  Bob send Alice a random subset J of [1,n] of size n/2.  Alice
sends Bob x_i for i not in J, proving that all but one signing key were
derived from her signing key.  Alice also sends Bob the Signature(x_j A,
m) for j in J where m denotes whatever message needs singing.  

Bob can now prove that he interacted with Alice, but that's probably
valueless.  As |J|=n/2, an adversary must guess correctly from amongst
$n \choose n/2$ possible J sets.  This is exponential because
$\sum_{k=0}^m {m \choose k} = 2^m$ and $\sum_{k=0}^m {m \choose k}^2 =
{2 m \choose m}$.  Interesting, but quite a taxing protocol.


Can we make this more efficient by allowing Bob control over scalars?
Is there a hashing trick that saves Alice and/or Bob from doing all
those scalar multiplications?  I'd dubious.  We must prevent Bob from
knowing the derivation of any signing scalars x_j for j in J, but Bob
must learn the derivation to skip scalar multiplications, right?  At
best, there might be a Merkle DAG construction in which Bob can be sure
many scalars are related, but not the ones he actually gets signatures
from, maybe pushing us to doubly exponential.  


We should ask ourselves : What is more dangerous wildcard attacks or
non-deniable signatures?

- Signatures are ex-post-facto attacks.  Very bad!  Yet, the application
itself can protect by simply not saving them.  I.e. an adversary must
target you in advance by altering your software.

- Wildcard attacks inherently require that you were targeted in advance.
Yes, impersonation sounds quite bad, but not if you're only consuming
server resources. 


What's the real lesson here?  Axolotl is largely the reason TripleDH
gained prominence.  Axolotl is vulnerable to this wildcard attack only
on first-use, but afterwards an adversary must compromise the ratchet
state.  There is no reason to worry about wildcard attacks if you never
restart a ratchet while allowing a peer to keep its identity.  Radical
forward-secrecy saves the day! 

I suppose radical forward-secrecy cannot work for web apps, or
user-server connections in a peer-to-peer network.  It's fine for
user-user or server-server connections though.  And user-server
connections need real anonymity anyways, making any authentication
problematic.

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