[curves] Certifying EdDSA public keys

[Trevor Perrin]

On Tue, Sep 22, 2015 at 5:19 AM, Simon Josefsson <simon at josefsson.org> wrote:
>
> What I'm trying to achieve is having one public key usable for a set of
> algorithms and defer the decision on which algorithm to use until the
> signature is created.


Hi Simon,

Let me rephrase to make sure I understand:

You're considering EdDSA deterministic Schnorr signatures [1].  The
traditional "PureEdDSA", which Ed25519 is an instance of, hashes its
input message twice.  For long messages that you only want to hash
once you could make the input to the signature scheme a "prehash" of
the message you want to sign ("HashEdDSA").

You're wondering whether HashEdDSA and PureEdDSA signatures could be
produced from the same key without enabling a "cross-protocol" attack,
where a message signed with HashEdDSA is presented as PureEdDSA, or
vice versa.

You point out the input could be prefixed with a tag, so the signature
is calculated on (tag || prehash) or (tag || full_message).

Seems OK except it isn't compatible with existing PureEdDSA signatures
(like Ed25519).

An idea to preserve backwards compatibility, dunno if it's good:
PureEdDSA calculates the Schnorr challenge as Hash(R,A,M) where R is
an encoded point.  Suppose HashEdDSA is defined to calculate
Hash(Z,R,A,M) where Z is an invalid curve point.

PureEdDSA would never calculate an R that equals Z.  If you choose the
Hash carefully to avoid length-extension issues, maybe you could
convince yourself that Schnorr challenges for PureEdDSA and HashEdDSA
are outputs from "domain-separated" random-oracle queries.

I think that might prevent cross-protocol attacks, because the
verifier would be considering unrelated Schnorr challenges for
PureEdDSA and HashEdDSA?

Trevor

[1] http://ed25519.cr.yp.to/eddsa-20150704.pdf