[curves] Certifying EdDSA public keys

[Simon Josefsson]

Hi.

I'm working on an PKIX draft for EdDSA and one aspect may warrant some
broader discussion, and maybe this is the right forum for it.

The document [1] specify how to encode EdDSA public keys into certs and
how to prepare a signature using those keys.  EdDSA public keys have a
parameter indicating the parameter set, e.g., Ed25519.  The signature is
the raw ENC(R)|ENC'(S) output

I have so far only specified Ed25519 without any pre-hashing.  This has
the IUF API & smartcard legacy issue that appears problematic to some
people.  I believe that for this to go forward easier, the draft could
specify a public-key parameter value corresponding to SHA-512-Ed25519 as
well.

The problem with this is that a certified SHA-512-Ed25519 public key
would not directly be usable for (Pure) Ed25519 signatures.  Recall the
following warning from [2]:

   Any protocol allowing multiple signature schemes needs to
   authenticate the choice of signature scheme, so that signatures under
   one scheme cannot be confused with signatures under another.  For
   example, if a public key A were allowed to be used with both
   PureEdDSA and H'-EdDSA then an attacker could forge a signature of M
   under H'-EdDSA by obtaining a signature of H'(M) under PureEdDSA.
   There are many other “cross-protocol” attacks in the literature; it
   is an error to simply certify a public key A without also certifying
   the signature scheme to be used for A.

Thus, applications that does not have a problem using PureEdDSA could
not take advantage of a certified SHA-512-Ed25519 public-key, as things
currently are written.  They would have to get a certified Ed25519
public-key instead.  Servers could have both keys available, and give
the right one to a client.  But having many keys around is problematic
for many protocols and implementations, as it is adds complexity in
selecting the right one (think downgrade attacks).

I've been thinking about how to work around this.  The objective would
be to have one EdDSA public-key, possibly with some parameter set
associated with it, and for that key to be usable with different
pre-hash algorithms without compromising security.

One way to achieve this would to modify the certified public-key to
include a set of permitted pre-hash algorithms instead of just one.
What I currently have is:

   K = "Ed25519" || Raw-EdDSA-KEY

or

   K = "SHA-512-Ed25519" || Raw-EdDSA-KEY

The "Ed25519" and "SHA-512-Ed25519" values would be replaced by OIDs or
an ENUMERATED members, the details does not matter.

But instead you could have a public-key that would look like:

   K = ["Ed25519", "SHA-512-Ed25519"] || Raw-EdDSA-KEY

That K would be signed by the private key holder and the key and
signature would be put into a certificate.

That is not enough, you can easily see that the signer could be tricked
into signing a hash with Ed25519 which could be cut'n'pasted into a
valid signature with SHA-512-Ed25519.

However if we modify the signing operation to authenticate PH as part of
the signed message, would things be better?  That is:

  S = PH | EdDSA(PH | M)

where PH is "Ed25519" or "SHA-512-Ed25519" for example.

Verifying S will check that PH is in the certified set for the public
key, and that the signature for PH|M holds.

This looks a lot like hash firewalling but I believe the purpose and
properties are different.  I'm not trying to protect against a weak
algorithm -- if one of the PH parameters above would be insecure (e.g.,
if SHA-512 collisions can be found easily), that key has to be revoked.

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.

Thoughts?  Does this work?

Opinions on whether this complexity worth it?

Thanks,
/Simon

[1] https://tools.ietf.org/html/draft-josefsson-pkix-eddsa-02
[2] http://ed25519.cr.yp.to/eddsa-20150704.pdf
-------------- 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/20150922/696d7d49/attachment.sig>