[curves] Ed25519 signatures from Curve25519 keys

[Trevor Perrin]

On Wed, Jun 18, 2014 at 5:47 AM, David Leon Gil <coruus at gmail.com> wrote:
> Just a quick question: Not reusing keys requires no security proofs at all.
> Is there really a benefit that justifies key reuse?

Some systems have entities that create signatures as well as do
decryption / key agreement.  For example:
 - A user sign outbound messages, and decrypt inbound ones.
 - A server that does DH key agreement might publish signed statements
about how it should be contacted (key rollover, alternate URLs, policy
like strict-transport-security, etc.)
 - A user that does end-to-end DH key agreement with other users might
publish signed statements to inform correspondents of (presence, key
rollover, contact info, etc.)

Of course, you can do this with separate signing and DH keys:

 * Pretend they're a single "double key", e.g. issue a certificate to
the "double key", create a fingerprint for it, and bind the double-key
into any use of either key (include the DH public-key into
to-be-hashed data when signing, and vice versa for DH).

 * Use the signing key as a "master key" to sign the DH "subkey" (e.g. PGP).

But these are awkward and less efficient: less-compatible with
existing formats and protocols, more data to store and transmit, and
(with signatures) more computation.  It's simpler to give each entity
a single key.

Also, systems evolve.  A party who only needed to authenticate
yesterday might need to sign tomorrow.  Reusing keys and formats is
more attractive than retrofitting "double-key" or "master/subkey"
notions, and distributing new keys.


> I, personally, am rather uncomfortable with Gap-DH. Especially when CDH is
> what you're giving up.

This isn't giving up CDH for Gap-DH.  The DH protocols I'm talking
about already have Gap-DH / ROM security proofs.  I'm just copying the
argument from [1] that such proofs continue to hold if the DH-protocol
attacker is given a Schnorr signing oracle for the private key,
provided care is taken with hashing.

Gap-DH is used for security models where an attacker can choose a
public key (g^a), get the target to perform a DH using the target
private key (b), and then somehow steal the resulting hashed session
key H(g^ab).  By hashing guesses for g^ab, the attacker gains a sort
of DDH oracle, i.e. he can guess X and check whether CDH(g^a, g^b) =
X.

This seems like a minor and unavoidable characteristic of DH protocols
that reuse static keys in an ephemeral-static pattern, when analyzed
in an aggressive security model.  Does it bother other people?


> (And as a note to folks who may not be aware, I believe that Adam Langley
> has implemented  this:
> https://github.com/agl/ed25519/tree/master/extra25519)

That does Ed25519 -> Curve25519 conversion of public and private keys.
I believe it's used in Pond, where the client uses the same key for an
end-to-end DH key agreement, and signatures.

I'm arguing for storing pubkeys in Curve25519 format, and decoding to
Ed25519 when needed.  As Robert Ransom and others have argued, using a
pubkey format compatible with Montgomery ladder makes DH faster, and
can be almost the same speed for signature verification.

(Though Curve -> Ed privkey conversion is complicated by the lack of
pubkey sign bit, and by existing Ed25519 implementations deriving the
private scalar from a master key).


Trevor

[1] http://eprint.iacr.org/2011/615