[curves] Certifying EdDSA public keys

[Simon Josefsson]

Trevor Perrin <trevp at trevp.net> writes:

> 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).

Hi Trevor.  Yes, that is an accurate summary.  Thanks for confirming
that my idea seems to work.

Do you think compatibility with pre-PKIX Ed25519 signatures is useful?

I see how compatibility could be useful to cut'n'paste an existing
Ed25519 signature into an PKIX container (e.g., CMS) and have it verify
correctly to someone who could the corresponding Ed25519 public key.

However, it could also be argued that this creates a cross-protocol
attack and is actually harmful.

> 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?

Nice idea!

Trying to simplify; do you really need the invalid curve point tricky?
Wouldn't it be sufficient to modify HashEdDSA to do
Hash("foobar",R,A,M)?  PureEdDSA could not be tricked into computing
that, and HashEdDSA would then work.

/Simon
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 472 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150925/a6a7702b/attachment.sig>