[curves] Certifying EdDSA public keys

[Trevor Perrin]

On Fri, Sep 25, 2015 at 1:25 AM, Simon Josefsson <simon at josefsson.org> wrote:
> Trevor Perrin <trevp at trevp.net> writes:
>>
>> 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.

I think it would be bad to introduce a signature scheme the same as
Ed25519 except where the input is (tag || full_message) instead of
full_message.

First, it multiplies schemes: now there's two algorithms that do the
same thing but are incompatible.  Worse, there's no guarantee that the
same private key could safely be used for both new and old signatures.
Even if the protocol-designer ensures the full_message inputs are
domain-separated for different uses, the prepending of the tag might
undermine this and create a cross-protocol attack.

If a new scheme is substantially different (like Ed25519 with a
pre-hash), then compatibility is no longer a concern.  But the
possibility of confusing new and old signatures produced by the same
private key should still be avoided, IMO.

Some would argue the same key should never be used for different
algorithms, so making this safe is unimportant.

That's a complicated topic, but my two cents:  Avoiding key reuse is
correct for symmetric algorithms, where it's easy to derive different
symmetric keys from a master key, and where algorithms have unrelated
hardness assumptions.

For typical closely-related public-key schemes, things are different:
You can't easily derive independent private keys from a single one, so
there's value in having a single key pair that can be used for
multiple purposes.

Also, with closely-related algorithms that have the same hardness
assumption, careful analysis can show when they can be safely used
together.


>> 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.
[...]
>
> 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)?

Maybe, but the analysis seems harder.  The "Schnorr challenge" for
such a HashEdDSA signature would equal the challenge for some
PureEdDSA signature where:
 - PureEdDSA_R = "foobar" || HashEdDSA_R[0:26]
 - PureEdDSA_A = HashEdDSA_R[26:32] || HashEdDSA_A[0:26]
 - PureEdDSA_M = HashEdDSA_A[26:32] || HashEdDSA_M

Suppose you had proofs of security for PureEdDSA and HashEdDSA
individually in the Random Oracle Model, based on reductions that use
a signature adversary to break discrete logs (e.g. Pointcheval-Stern).

It's easier to combine them if hash function queries for PureEdDSA and
HashEdDSA are "domain-separated" - you just route the hash function
queries to the appropriate reduction, which provides the "random
oracle".

But if the queries start with "foobar" and are 102 bytes they could
apply to either HashEdDSA or PureEdDSA, so the reductions have to
share random oracle answers.  Maybe a proof like Pointcheval-Stern
still works, but it seems easier to domain-separate things and not
have to think about that.


Trevor