Subject: [Curdle] EdDSA and CAs redux

From: Jim Schaad <[email-masked]>
Date: Mon, 5 Sep 2016 12:24:31 -0700

I am going to try and summarize what I see as the main issued raised so far.

*  Should we be defining OIDs for an algorithm which has a SHOULD NOT in the
text?  The CFRG document on EdDSA says that we SHOULD NOT use the pre-hash
versions of the algorithm.  

Text from EdDSA document in section 10.5:
The Ed25519ph and Ed448ph variants are prehashed.  ... These variants SHOULD
NOT be used.

Should we instead ask that this be removed from the text of EdDSA if we are
going to assign the OIDs and recommend use.

*  Should we be defining algorithms that we immediately turn around and say
are not to be used by a set of protocols?  There has been some pushback on
the idea of saying that we are defining the pre-hash versions of the EdDSA
algorithms and then promptly saying that they are not to be used for CAs.  

*  There are size problems with pure mode EdDSA that have been brought up.
This may be a problem for other things, but the big issue is that of CRLs.
Since there are two passes over the content being signed, it cannot be
streamed pass the hash function and then the result of that signed.  This is
a known problem with some HSMs today where they want to keep all of the
content in memory and therefore have messages length restrictions (per
Erwan).  

There are also issues with saying that two modes should be allowed with a
single key and if that should be allowed.  The extremely strong
recommendation from CFRG is that the same key set should not be used for
both pure and pre-hash modes even after the changes so that the known attack
has been removed.

How do we make the statement for dealing with CRLs if we need to address
this issue?  Does this mean we need to allow pre-hash mode for Certificates
and OCSP responses or does it mean that we need to recommend that a CA have
a second key set for signing CRLs.  It may be that the usage of OCSP can be
used to finesse this problem, if the cases where HSMs are going to be used
are almost always targeted at OCSP rather than CRLs.  There have been
conflicting views about this on the list.

* What happens with PKCS#11 - we still need to get somebody who uses this to
have some type of opinion or we need to get some contacts with the OASIS
group.  Looking at the membership list there appear to be 3 people from EMC
and one from Google so that might be people we can get someone to contact
for us (Kathleen and David?).

I have thought of two different ways that this can be addressed, but my
understanding may be weak as I don't use or implement PKCS#11:

- New mechanisms can be defined that deal with these new algorithms.  This
is a bigger issue for ECDH than for EdDSA as it makes a degree of sense to
do this for the new signature structure and less sense to re-defined all of
the ECDH mechanisms that already exist.

- Define some new mechanism information flags such as
CKF_EC_BINARYPARAMETERS which would modify or signal the use of how the
public key parameters are defined/used.  This would mean either than
CKA_EC_POINT would either not exist and CKA_EC_BINARY_POINT would be used or
that CKA_EC_POINT would have a different value rather than the DER-encoding
of an ANS1 X9.62 Parameters value.  Similar changes would be made for
parameters, private key

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 6 Sep 2016 09:06:28 +0300

> The Ed25519ph and Ed448ph variants are prehashed.  ... These variants SHOULD

Maybe this is a good bit of my biases showing. But I think Ed25519ph is
trouble.
 
> content in memory and therefore have messages length restrictions (per

And modifications that would enable streaming without breaking
verification are dangerous... Especially with high-value keys like
that (get it wrong and the keys walk).

> both pure and pre-hash modes even after the changes so that the known attack

If you are talking about the document, that text got softened down a
lot during the latest round of changes (since there are no longer any
trivial breaks with non-neglebiliable probabilities).

> conflicting views about this on the list.

I would rather not have to deal with Ed25519ph for anything "important",
that is certs and OCSP. CRLs are in my view secondary.

> of an ANS1 X9.62 Parameters value.  Similar changes would be made for

The abstract way I would implement X* stuff (sorry, don't know PKCS#11,
so the terminology will be wrong):

- generate: () -> privkey_handle:handle
- pubkey: privkey_handle:handle -> point:octets
- agree: privkey_handle:handle, peerpub:octets -> result:octets

And similarly for Ed*

- generate: () -> privkey_handle:handle
- pubkey: privkey_handle:handle -> pubkey:octets
- sign: privkey_handle:handle, message:octets -> signature:octets

... I have recently worked on a TLS library, and the internal interfaces
look like that (except that agree on X* is one-use).

(I hope I don't see stuff like this for Ed*-nonph:

- init_sign: privkey_handle:handle -> sig_ctx:handle
- update_sign: sig_ctx:handle, message:octets -> ()
- finish_sign: sig_ctx:handle -> signature:octets  [USE ONCE]

... All implemented in O(1) memory, as this type of thing can only be
done in dangerous ways).

-Ilari

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 06 Sep 2016 09:39:28 +0200

On Mon, 2016-09-05 at 12:24 -0700, Jim Schaad wrote:
> Should we instead ask that this be removed from the text of EdDSA if
> we are going to assign the OIDs and recommend use.

Yes please. There is no point for a document describing a new algorithm
to describe variants which are marked as "SHOULD NOT" use.

> content in memory and therefore have messages length restrictions
> (per Erwan).  

That just means that some other signing algorithm will be used for
large data. I think that's acceptable. I only see confusion from using
a SHOULD NOT use algorithm for certain cases, while the main algorithm
for others. I cannot even think how this can be presented or explained
to end-users to use correctly.

regards,
Nikos

---

From: Russ Housley <[email-masked]>
Date: Wed, 7 Sep 2016 00:32:31 -0400

Jim:

Here is my view on the issues that you summarized.

> going to assign the OIDs and recommend use.

I think that assigning an OID will enable other to use it.  Let’s not do that.

> algorithms and then promptly saying that they are not to be used for CAs.  

I’d rather focus on signature algorithm that can be used in all of our protocols.

> conflicting views about this on the list.

This is not a new issue.  RSA, RSA-PSS, DSA, and ECDSA all compute a hash value, and then sign it.  I do not think we need to do anything different here.

> of an ANS1 X9.62 Parameters value.  Similar changes would be made for

Someone with more PKCS#11 experience than me should tackle this one.

Russ

---

From: Jim Schaad <[email-masked]>
Date: Tue, 6 Sep 2016 21:38:12 -0700

> -----Original Message-----
> From: Russ Housley [mailto:[email-masked]]
> Sent: Tuesday, September 06, 2016 9:33 PM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [Curdle] EdDSA and CAs redux
> 
> Jim:
> 
> > *  Should we be defining OIDs for an algorithm which has a SHOULD NOT
> > in the text?  The CFRG document on EdDSA says that we SHOULD NOT use
> > the pre-hash versions of the algorithm.
> >
> > The Ed25519ph and Ed448ph variants are prehashed.  ... These variants
> > SHOULD NOT be used.
> >
> I think that assigning an OID will enable other to use it.  Let's not do
that.
> 
> > *  Should we be defining algorithms that we immediately turn around
> > and say are not to be used by a set of protocols?  There has been some
> > pushback on the idea of saying that we are defining the pre-hash
> > versions of the EdDSA algorithms and then promptly saying that they are
not
> to be used for CAs.
> 
> I'd rather focus on signature algorithm that can be used in all of our
protocols.
> > streamed pass the hash function and then the result of that signed.
> > This is a known problem with some HSMs today where they want to keep
> > all of the content in memory and therefore have messages length
> > restrictions (per Erwan).
> >
> > There are also issues with saying that two modes should be allowed
> > with a single key and if that should be allowed.  The extremely strong
> > recommendation from CFRG is that the same key set should not be used
> > for both pure and pre-hash modes even after the changes so that the
> > known attack has been removed.
> >
> > How do we make the statement for dealing with CRLs if we need to
> > address this issue?  Does this mean we need to allow pre-hash mode for
> > Certificates and OCSP responses or does it mean that we need to
> > recommend that a CA have a second key set for signing CRLs.  It may be
> > that the usage of OCSP can be used to finesse this problem, if the
> > cases where HSMs are going to be used are almost always targeted at
> > OCSP rather than CRLs.  There have been conflicting views about this on
the
> list.
> 
> This is not a new issue.  RSA, RSA-PSS, DSA, and ECDSA all compute a hash
value,
> and then sign it.  I do not think we need to do anything different here.

This appears to be an opposite opinion of the first bullet item. 

The first one says - don't assign an OID for pre-hash mode because CFRG says
SHOULD NOT.
This one says - use pre-hash mode because we should be doing the compute a
hash value and then signing it.

Jim

> 
> > * What happens with PKCS#11 - we still need to get somebody who uses
> > this to have some type of opinion or we need to get some contacts with
> > the OASIS group.  Looking at the membership list there appear to be 3
> > people from EMC and one from Google so that might be people we can get
> > someone to contact for us (Kathleen and David?).
> >
> > I have thought of two different ways that this can be addressed, but
> > my understanding may be weak as I don't use or implement PKCS#11:
> >
> > - New mechanisms can be defined that deal with these new algorithms.
> > This is a bigger issue for ECDH than for EdDSA as it makes a degree of
> > sense to do this for the new signature structure and less sense to
> > re-defined all of the ECDH mechanisms that already exist.
> >
> > CKF_EC_BINARYPARAMETERS which would modify or signal the use of how
> > the public key parameters are defined/used.  This would mean either
> > than CKA_EC_POINT would either not exist and CKA_EC_BINARY_POINT would
> > be used or that CKA_EC_POINT would have a different value rather than
> > the DER-encoding of an ANS1 X9.62 Parameters value.  Similar changes
> > would be made for parameters, private key
>

---

From: Brian Smith <[email-masked]>
Date: Tue, 6 Sep 2016 18:58:32 -1000

> of an ANS1 X9.62 Parameters value.  Similar changes would be made for

AFAICT, it is definitely possible to do something like this in PKCS#11 for
EdDSA to avoid the issues of HSMs that have limited memory. The PKCS#11
standards group would need to define new mechanisms for the new algorithms
anyway. A mechanism can be defined that outputs the hash of the entire
input that is used input to the EdDSA operation. Then, another mechanism
can be used that takes the result of the first operation as a parameter.
Signing large objects that don't fit in the token's memory would be a
two-pass process, which would be reasonable for CRLs.

Cheers,
Brian

---

From: Russ Housley <[email-masked]>
Date: Wed, 7 Sep 2016 01:35:57 -0400

Jim Schaad <[email-masked]> wrote:

>>> OCSP rather than CRLs.  There have been conflicting views about this on the list.
>> 
>> This is not a new issue.  RSA, RSA-PSS, DSA, and ECDSA all compute a hash value,

Sorry, I was not clear.  Our protocols do not impose an API on these primitives.  The API could do the two steps in one call, or there could be many calls.  I do not think we need to do the API work here.

Russ

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 7 Sep 2016 10:47:02 +0300

> two-pass process, which would be reasonable for CRLs.

Well, one just needs to include hash of the input in returned state
and to make that state unmalleable, so one can't do crap like:

1) Request first part for M1
2) Request second part for M1
3) Request first part for M1
4) Request second part for M2 (M2!=M1)

Which would cause the private key to walk...

-Ilari