Subject: [Cfrg] Elliptic Curves - signature scheme (ends on April 22nd)

From: Alexey Melnikov <[email-masked]>
Date: Wed, 08 Apr 2015 13:38:55 +0100

CFRG chairs are starting discussion of the next topic.

Background:

ECDSA is standardised by NIST and already supported in TLS 
specifications. ECDSA is also becoming more heavily used in TLS (see for 
example http://notary.icsi.berkeley.edu/ which indicates that ECDSA is 
currently used in about 16% of observed TLS sessions and that 1.6% of 
valid certificates are for ECDSA public keys).

Analogues of ECDSA can be written down for the curves which CFRG has
already selected (Curve25519, Goldilocks), and for closely related
versions of those curves (e.g. Edwards-form versions of those curves,
which may offer advantages for implementation security of these ECDSA
analogues).

However whether these ECDSA analogues would be NIST-compliant for
non-Weierstras-form curves is uncertain.

There is also the question of when or whether CAs would start to issue
certificates for public keys for any new signature scheme that we
recommend (whether this be an ECDSA analogue for a new curve type or
otherwise).

ECDSA has some undesirable features, including its dependence on a high
quality source of randomness during signing (and its well-documented
potential for catastrophic failure when that condition is not met).

ECDSA, and other schemes like it, can be de-randomised by generating the
"random" value used during signing in a pseudorandom manner from the
message to be signed. Several methods for doing so are described in RFC
6979 (http://tools.ietf.org/html/rfc6979). However, these methods appear
to be incompatible with the ECDSA standard (see, specifically, Appendix
B.5 of http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf: 
"ECDSA requires the generation of a new random number k for each message 
to be signed. Two methods are provided for the generation of k; one of 
these two methods or another approved method shall be used".)

ECDSA also requires the implementation of modular inversion during 
signing and verification. This can be avoided by modifying the equations 
governing signing and verification, as is done in Schnorr-like schemes. 
A specific example of a scheme of this type is EdDSA (as described in 
http://ed25519.cr.yp.to/ed25519-20110926.pdf).

Chairs are going to ask a sequence of questions to direct discussion and
help us determine which signature scheme to recommend. The first two
questions follow. Later questions will address other relevant topics;
their sequence and wording may depend on the views of the research group
on preceding questions. We are not carrying out a formal poll at this
time, but we may do so if we do not see clear consensus emerging from 
the discussion of two questions listed below:

-------------------------------------------------------------
Q6: Is NIST compliance sufficiently important that we should
recommend ECDSA as is (suitably modified for our new curves or closely
related versions of those curves)? Or do the advantages of the available
alternative signature schemes outweigh the benefits of maintaining NIST
compliance?
-------------------------------------------------------------
Q7: How serious a barrier to adoption of any new signature scheme
that we might recommend is the current lack of support from CAs for the
issuance of certificates on public keys for such schemes?
-------------------------------------------------------------

Please don't discuss any other topic in this thread.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 08 Apr 2015 09:39:49 -0400

On Wed 2015-04-08 08:38:55 -0400, Alexey Melnikov wrote:

> Q6: Is NIST compliance sufficiently important that we should recommend
> ECDSA as is (suitably modified for our new curves or closely related
> versions of those curves)? Or do the advantages of the available
> alternative signature schemes outweigh the benefits of maintaining
> NIST compliance?

I do not believe that NIST compliance is an important factor here.
People who need NIST compliance can continue to use NIST curves with
NIST signature schemes.  NIST may also be open to adopting a new scheme
if they see well-justified support in the new scheme from the community.

We should strongly consider the advantages in implementation security of
alternative signature schemes.

> Q7: How serious a barrier to adoption of any new signature scheme that
> we might recommend is the current lack of support from CAs for the

Reasonable CAs will figure out how to deploy certificates that use a new
scheme that we endorse.  Deployment may take slightly longer by choosing
a new scheme, but this is a worthwhile price to pay if it means avoiding
pitfalls in implementation security for the long term.

            --dkg

---

From: Santosh Chokhani <[email-masked]>
Date: Wed, 8 Apr 2015 13:43:43 +0000

Alexey,

Should Q6 be rephrased in terms of another option under which we gauge the willingness of NIST to revise FIPS 186-4 to accommodate the final recommendations by CFRG.

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Alexey Melnikov
Sent: Wednesday, April 08, 2015 8:39 AM
To: [email-masked]
Subject: [Cfrg] Elliptic Curves - signature scheme (ends on April 22nd)

Background:

ECDSA is standardised by NIST and already supported in TLS specifications. ECDSA is also becoming more heavily used in TLS (see for example http://notary.icsi.berkeley.edu/ which indicates that ECDSA is currently used in about 16% of observed TLS sessions and that 1.6% of valid certificates are for ECDSA public keys).

Analogues of ECDSA can be written down for the curves which CFRG has already selected (Curve25519, Goldilocks), and for closely related versions of those curves (e.g. Edwards-form versions of those curves, which may offer advantages for implementation security of these ECDSA analogues).

However whether these ECDSA analogues would be NIST-compliant for non-Weierstras-form curves is uncertain.

There is also the question of when or whether CAs would start to issue certificates for public keys for any new signature scheme that we recommend (whether this be an ECDSA analogue for a new curve type or otherwise).

ECDSA has some undesirable features, including its dependence on a high quality source of randomness during signing (and its well-documented potential for catastrophic failure when that condition is not met).

ECDSA, and other schemes like it, can be de-randomised by generating the "random" value used during signing in a pseudorandom manner from the message to be signed. Several methods for doing so are described in RFC
6979 (http://tools.ietf.org/html/rfc6979). However, these methods appear to be incompatible with the ECDSA standard (see, specifically, Appendix
B.5 of http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf: 
"ECDSA requires the generation of a new random number k for each message to be signed. Two methods are provided for the generation of k; one of these two methods or another approved method shall be used".)

ECDSA also requires the implementation of modular inversion during signing and verification. This can be avoided by modifying the equations governing signing and verification, as is done in Schnorr-like schemes. 
A specific example of a scheme of this type is EdDSA (as described in http://ed25519.cr.yp.to/ed25519-20110926.pdf).

Chairs are going to ask a sequence of questions to direct discussion and help us determine which signature scheme to recommend. The first two questions follow. Later questions will address other relevant topics; their sequence and wording may depend on the views of the research group on preceding questions. We are not carrying out a formal poll at this time, but we may do so if we do not see clear consensus emerging from the discussion of two questions listed below:

-------------------------------------------------------------
Q6: Is NIST compliance sufficiently important that we should recommend ECDSA as is (suitably modified for our new curves or closely related versions of those curves)? Or do the advantages of the available alternative signature schemes outweigh the benefits of maintaining NIST compliance?
-------------------------------------------------------------
Q7: How serious a barrier to adoption of any new signature scheme that we might recommend is the current lack of support from CAs for the issuance of certificates on public keys for such schemes?
-------------------------------------------------------------

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 08 Apr 2015 14:51:12 +0100

I don't think NIST compliance is an issue for this work.

We're dealing with curves on which NIST has no opinion
so far. When/if NIST consider 25519 and 448, we can talk
to them about this, but in the meantime speculation (as to
what NIST might or might not do/say) would not be useful
I think. And even if we get talking happily to NIST (which
I'd expect is quite likely), they will take too long to
reach a conclusion, as they will need to consult with
their other constituencies.

And in any case, fixing the randomness issues would still
be worthwhile. And that is true even if NIST compliance
for these curves were possible (which is not the case)
and would be lost because of the security fix.

I believe there will also be demand from DNSSEC and W3C,
and possibly openpgp, so X.509 CAs alone are not the only
consumer of this work. In any case, I'm sure the CAs will
catch up if the demand for certified signature keys grows
so I do not think this is a major issue (esp. since RSA
signing keys can still work just fine for esp. TLS in
the meantime).

Cheers,
S.

---

From: Hanno Böck <[email-masked]>
Date: Wed, 8 Apr 2015 15:58:58 +0200

On Wed, 08 Apr 2015 13:38:55 +0100
Alexey Melnikov <[email-masked]> wrote:

> related versions of those curves)? Or do the advantages of the
> available alternative signature schemes outweigh the benefits of
> maintaining NIST compliance?

I think there is an implicit assumption in this question that NIST
compliance is a fixed thing. However as far as I'm aware NIST is
currently itself in the process of reviewing elliptic curve issues and
preparing a workshop on that in June.

If CFRG (and others) come up with a good set of curves and algorithms
for the future with plausible security arguments I find it likely that
NIST will follow.

> that we might recommend is the current lack of support from CAs for
> the issuance of certificates on public keys for such schemes?

I think right now ECDSA deployment in the TLS world is mostly happening
beside RSA, because everyone needs RSA due to backwards compatibility.
This is unlikely to change any time soon, I expect RSA to be the backup
option for quite some time.
Therefore adoption issues may be less severe, because everyone always
has the RSA backup option.

-- 
Hanno Böck
http://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 8 Apr 2015 14:03:12 +0000

Hi Santosh,

On 08/04/2015 14:43, "Santosh Chokhani" <[email-masked]> wrote:

>Alexey,
>
>Should Q6 be rephrased in terms of another option under which we gauge
>the willingness of NIST to revise FIPS 186-4 to accommodate the final
>recommendations by CFRG.

Replying for the chairs:

NIST's process on re-examining curves and algorithms is going to take much
longer than ours (years as opposed to a few more months for us, I hope)
and involve a different and likely wider set of stakeholders.

This means that, while the lines of communication between CFRG/IETF and
NIST are open and information is flowing well, it's unlikely that our
timelines and theirs are sufficiently well-synced that your proposal would
be useful: NIST is simply not in a position to commit to such an
accommodation at this stage.

(If anyone from NIST is reading and wants to contradict this, please go
ahead.)

Regards

Kenny  

>time, but we may do so if we do not see clear consensus emerging from the
>discussion of two questions listed below:
>
>Q7: How serious a barrier to adoption of any new signature scheme that we
>might recommend is the current lack of support from CAs for the issuance
>of certificates on public keys for such schemes?

---

From: Yoav Nir <[email-masked]>
Date: Wed, 8 Apr 2015 17:19:37 +0300

As I said at the meeting, I don’t believe that we can or should consider what NIST may or may not think or the curves and signature scheme that we are going to propose.

Arguably if we recommend a set of new scheme and new curve, this is more likely to appeal to NIST than just a new curve shoe-horned into the old scheme. 

So my opinion is that the answer is that ECDSA compliance is not important.

> issuance of certificates on public keys for such schemes?

Signatures are used in protocols as well as in certificates. As long as the TLS working group removes silly requirements that the signature in the protocol and the signature in the certificate match, as we’re doing in rfc4492bis.

If a signature scheme works well and is widely implemented, the CAs might also use it. If they do, great! If they don’t, this should not be a barrier for adoption by other users.

Yoav

---

From: James Cloos <[email-masked]>
Date: Wed, 08 Apr 2015 10:53:52 -0400

It is unanimous so far, but I agree that:

> Q6

cfrg should not worry about compliance with current nist standards

> Q7

for the CAs, "uild it and they will come".

In other words, security is more important than compatibility with
agencies' and companies' existing products.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 8 Apr 2015 14:56:11 +0000

On 4/8/15, 10:19 , "Yoav Nir" <[email-masked]> wrote:

>As I said at the meeting, I don’t believe that we can or should consider
>what NIST may or may not think or the curves and signature scheme that we
>are going to propose.

Reluctantly agree.

>Arguably if we recommend a set of new scheme and new curve, this is more
>likely to appeal to NIST than just a new curve shoe-horned into the old
>scheme.

This doesn’t make sense to me at all. The wider we diverge from what NIST
has at this point, the likelier it is to appeal to NIST?!

>Signatures are used in protocols as well as in certificates.

Yes. Then the question would be - how useful are signatures that cannot be
employed in/with certificates. Especially when other signatures exist that
can be employed in both protocols and certificates.

>As long as the TLS working group removes silly requirements that the
>signature in the protocol and the signature in the certificate match, as
>we’re doing in rfc4492bis.

100% agree. That requirement just doesn’t make any sense.

>If a signature scheme works well and is widely implemented, the CAs might
>also use it. If they do, great! If they don’t, this should not be a
>barrier for adoption by other users.

There’s no reason for any (cryptographically sound) signature scheme not
to work well. But I for one fail to see how it can be adopted by users if
CAs do not support it. This is not a PGP Web of Trust where you are
reasonably free to choose - your cert either is traceable to a
widely-accepted well-known CA, or it isn’t.

---

From: Dan Brown <[email-masked]>
Date: Wed, 8 Apr 2015 15:01:59 +0000

> From: Alexey Melnikov
> ECDSA is standardised by NIST and already supported in TLS specifications.
> ECDSA is also becoming more heavily used in TLS (see for example
> http://notary.icsi.berkeley.edu/ which indicates that ECDSA is currently
used in
> about 16% of observed TLS sessions and that 1.6% of valid certificates are
for
> ECDSA public keys).

[DB] Yes, but please consider that ECDSA is also standardized/recommended in
ANSI X9F, Suite B, IEEE 1363, SEC1, ISO 14888(?), SEC1, Nessie and Cryptrec.

> already selected (Curve25519, Goldilocks), and for closely related
versions of
> those curves (e.g. Edwards-form versions of those curves, which may offer
> advantages for implementation security of these ECDSA analogues).
> 

[DB] I think that FIPS 140-* CAVP-compliance currently requires one of the
15 NIST curves.  But ECDSA in FIPS 186-3 (and maybe 4, though I haven't
confirmed), is specified via reference to ANSI X9.62.  I've been the
(maintenance) editor of ANSI X9.62 since 2001, even though I tend to think
of ECDSA in a more abstract research perspective.  As I recall, ECDSA is
designed to support _any_ elliptic curve: just convert it to short
Weierstrass form to convert the ephemeral public key R to an integer r.

> certificates for public keys for any new signature scheme that we
recommend
> (whether this be an ECDSA analogue for a new curve type or otherwise).
> 
[DB] Wrongly worded and characterized.  (1) Abstractly, at a high level,
most DL-based signatures, including Schnorr, have this "dependence". (2)
Avoiding the fatal pitfall of repeated keys does not require a "high quality
source of randomness" in the sense of new fresh entropy per each signature
anything like that: consider deterministic signatures or DRBG-based
signatures.  (3) Avoiding biased and correlated keys requires only a decent
form of pseudorandomness, which is rather easily achieved, e.g. DRBG plus a
means to adjust bit strings to unbiased mod n integers.  On the other hand,
it may be quite fair to criticize ECDSA standards for not being clear enough
on these potential pitfalls.  

> 6979 (http://tools.ietf.org/html/rfc6979). However, these methods appear
to
> be incompatible with the ECDSA standard (see, specifically, Appendix
these
> two methods or another approved method shall be used".)
> 
[DB] Hmm, well, where's the incompatibility?  If it said "ECDSA requires the
generation of new random number k for each signature to be generated", that
would be incompatible, but it doesn't say that.  Again, to be fair, maybe
the wording is unclear.  Years ago, I had some interactaions with ECDSA CAVP
tool, and I don't recall anything it that would cause a deterministic
version (e.g. per 6979) of ECDSA to fail. (Does a more recent version
request multiple signatures of a single message?) Perhaps some CMVP labs
would reject a technique like 6979, but I think that would be their mistake.

> ECDSA also requires the implementation of modular inversion during signing
> and verification. This can be avoided by modifying the equations governing
> signing and verification, as is done in Schnorr-like schemes.
[DB] Qu, Johnson and Vanstone have a patent describing a variant of ECDSA,
which, in a nutshell, represents the s value in projective coordinates, i.e.
(r,s) -> (r ,(t:u)), and thereby avoids an inversion, at the cost of
expanded signature size (note: for security, the representation must be
pseudorandomized).  (Unfortunately, I only recent realized this, otherwise I
would have tried to add it as an optional feature to SEC1 years ago;)
Schnorr-like signatures avoid the inversion, but also have a different
theoretical security basis, so avoidance of inversion is not free. 

> Chairs are going to ask a sequence of questions to direct discussion and
help us
> determine which signature scheme to recommend. The first two questions
> follow. Later questions will address other relevant topics; their sequence
and
> wording may depend on the views of the research group on preceding
> questions. We are not carrying out a formal poll at this time, but we may
do so
> if we do not see clear consensus emerging from the discussion of two
> questions listed below:
> 
versions of
> those curves)? Or do the advantages of the available alternative signature
> schemes outweigh the benefits of maintaining NIST compliance?
[DB] I personally don't value NIST compliance too much (because I'm more
interested in the theoretical security issues) but I have many colleagues
who are quite interested in NIST compliance.

of
> certificates on public keys for such schemes?
[DB] As I recall it, traditional PKIX certificates do not specify the
subject's signature algorithm.

[DB] I'm sorry if my comments on the background section violated this
request.  While I'm apologizing, I might as well apologize for any details
I've misremembered, and for any lack of clarity, in this message (or
standards I've failed to clarify).

---

From: Viktor Dukhovni <[email-masked]>
Date: Wed, 8 Apr 2015 15:15:25 +0000

On Wed, Apr 08, 2015 at 02:56:11PM +0000, Blumenthal, Uri - 0553 - MITLL wrote:

> >also use it. If they do, great! If they don't, this should not be a
> There's no reason for any (cryptographically sound) signature scheme not
> widely-accepted well-known CA, or it isn't.

With DANE TLSA there need not be a CA at all, or if there is one,
it need not be well known.  Of course servers need to publish TLSA
RRs that have near universal clients support.  So initially any
certificates that use new curves would need to be deployed along-side
established "interoperable" algorithms:

	_25._tcp.mail.example.com. IN TLSA 3 1 1 <RSA-spki-digest>
	_25._tcp.mail.example.com. IN TLSA 3 1 1 <X25119-spki-digest>

Clients that support X25519 and negotiate a corresponding cipher-suite
can authenticate the server via the second TLSA RR, while clients with
older stacks use RSA and the first TLSA RR.

Even without DANE, TLS is also used in environments where explicit
private trust anchors are employed and the "well known" CAs are
deliberately excluded.  Such deployments can use new algorithms
as soon as they have software that supports them.

-- 
	Viktor.

---

From: Yoav Nir <[email-masked]>
Date: Wed, 8 Apr 2015 18:27:24 +0300

> On Apr 8, 2015, at 5:56 PM, Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:
> 
> 

My (perhaps faulty) reasoning is that if we offer Curve25519 with ECDSA NIST will say that they already have something pretty much exactly the same. Something completely new might be worth the effort.

> widely-accepted well-known CA, or it isn’t.

There is no reason that a certificate signed with an ECDSA (or RSA) key should not contain an end-entity public key that is something else. Something like a Curve25519 key. This will require some work by the CAs - they should be able to verify a CSR with a Curve25519 key, but as long as they can sign with their old key, that should be fine.

Yoav

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 8 Apr 2015 18:32:24 +0300

> CFRG chairs are starting discussion of the next topic.

NIST-compliance with ECDSA is speculation, as many others have said.

Larger proven benefits against smaller speculative benefits[1]. I
prefer defining an alternative scheme.

Should not be a big issue either way (CabForum BRs need changing
to allow the new signatures for "public" CAs either way[3]).

And as others have noted, there is use for TLS outside the "public"
CA system.

Also, X.509 signs the key and algorithm just as an bag of bits,
so the only part that needs changing on CA (or RA) side is CSR
verification.

[1] I actually have implemented both (deterministic) ECDSA and an
EdDSA-variant[2] with the new curves. I find the result for ECDSA
terrifies me:
1) The hash truncation is annoying bitshift (vs modular reduce
   that is needed anyway).
2) Inversions are both slow and magnets for timing attacks (vs
   avoiding inversions entierely)
3) For derandomization, I don't think RFC 6979 is good[4] (vs defined
   stateless derandomization)
4) The mathematics required for verification is either a
   minefield or dark magic (vs a few scalar ops and an Edwards
   doublemul).

[2] The variant actually becomes verification-compatible with
Ed25519 if instantiated with correct curve and hash (signatures
cross-verify).

[3] Those specs actually specify (as of version 1.2.3) that the
_only_ allowed ECC signatures are:
- ECDSA with NIST P-256
- ECDSA with NIST P-384
- ECDSA with NIST P-521

Change to that would be ballot process.

[4] The implementation I did actually reuses the (v)EdDSA
derandomizer for ECDSA (which I actually consider a mistake).

-Ilari

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 8 Apr 2015 09:10:00 -0700

> alternative signature schemes outweigh the benefits of maintaining NIST

I think the CFRG should recommend what it feels is best from a technical
position. Anyone in need of NIST compliance can already use ECDSA in
conjunction with the NIST curves today. I think the reason that people find
the CFRG curves compelling is they are not in a position where they need
NIST compliance and would prefer faster, more secure alternatives.

> issuance of certificates on public keys for such schemes?

I think ECDSA adoption is relatively low as-is, at least for TLS purposes.
Beyond Google and CloudFlare, I don't think ECDSA certificates are widely
used.

Given that, I think now is a great time to introduce a new signature
scheme. We're not yet to the point that I think many people will cry "but
we just switched from RSA to ECDSA", and ECDSA has proven itself to be
quite brittle in practice.

-- 
Tony Arcieri

---

From: Nick Mathewson <[email-masked]>
Date: Wed, 8 Apr 2015 12:14:22 -0400

On Wed, Apr 8, 2015 at 12:10 PM, Tony Arcieri <[email-masked]> wrote:
> Given that, I think now is a great time to introduce a new signature scheme.
> We're not yet to the point that I think many people will cry "but we just
> switched from RSA to ECDSA", and ECDSA has proven itself to be quite brittle
> in practice.

Speaking as an implementor who does some secure stuff in practice: +1
to both of these. If we want NIST signatures, we know where to find
them. If commercial CAs are a requirement, we can work around it.
What's important to us is that we have a signature system that's
robust enough that we don't need to be afraid of it.

(Here at Tor, we are afraid of ECDSA. EdDSA seems like our best
implemented option at the moment.)

-- 
Nick

---

From: "Mehmet Adalier (Antara Teknik)" <[email-masked]>
Date: Wed, 8 Apr 2015 16:47:21 +0000 (UTC)

the challenge with this discussion and the questions 6 & 7 is the perception that 'these alternative signature schemes are advantageous' over ECDSA.
i am not making any value judgement on either ECDSA or 'other' proposed signature algorithms.However, a properly implemented ECDSA P-256 solution is as secure and fast as the proposed ~128 security strength curve.
I agree and support the notion that  "CFRG should recommend what it feels best from a technical position.' This technical position should be backed up by both solid math and repeatable experimental data.
mehmet adalier
      From: Tony Arcieri <[email-masked]>
 To: Alexey Melnikov <[email-masked]> 
Cc: "[email-masked]" <[email-masked]> 
 Sent: Wednesday, April 8, 2015 9:10 AM
 Subject: Re: [Cfrg] Elliptic Curves - signature scheme (ends on April 22nd)
   
On Wed, Apr 8, 2015 at 5:38 AM, Alexey Melnikov <[email-masked]> wrote:

I think the CFRG should recommend what it feels is best from a technical position. Anyone in need of NIST compliance can already use ECDSA in conjunction with the NIST curves today. I think the reason that people find the CFRG curves compelling is they are not in a position where they need NIST compliance and would prefer faster, more secure alternatives.

I think ECDSA adoption is relatively low as-is, at least for TLS purposes. Beyond Google and CloudFlare, I don't think ECDSA certificates are widely used.
Given that, I think now is a great time to introduce a new signature scheme. We're not yet to the point that I think many people will cry "but we just switched from RSA to ECDSA", and ECDSA has proven itself to be quite brittle in practice.
-- 
Tony Arcieri

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Apr 2015 09:59:36 -0700

On Wed, Apr 8, 2015 at 5:38 AM, Alexey Melnikov <[email-masked]>
wrote:
> used in about 16% of observed TLS sessions and that 1.6% of valid
> certificates are for ECDSA public keys).
>

They wouldn't be: looking at FIPS 186-4, I see that they defer to ASNI
X9.26 on how domain parameters are defined. Of course, one could always
work over a Weierstrass model with nonzero cofactor, but then our proposal
has minimal advantages over ECDSA: it will be slightly faster if you
implement using alternative models.

> recommend (whether this be an ECDSA analogue for a new curve type or

Why would this be more of an issue then for ECDSA on a different curve?
What is the problem we're trying to solve?

> B.5 of http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf: "ECDSA
> requires the generation of a new random number k for each message to be
> signed. Two methods are provided for the generation of k; one of these two
> methods or another approved method shall be used".)
>
> signing and verification, as is done in Schnorr-like schemes. A specific
> example of a scheme of this type is EdDSA (as described in

Schemes like EdDSA support batch signature verification. This is very
relevant to the TLS setting, as it can dramatically accelerate verification.

EdDSA is also significantly more performant then ECDSA due to avoiding
inversions. People claiming otherwise are welcome to submit code showing
this.

--
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 8 Apr 2015 17:09:49 +0000

Watson,

On 08/04/2015 17:59, "Watson Ladd" <[email-masked]> wrote:

>>specifications.
>X9.26 on how domain parameters are defined.

I assume you mean X9.62 here? Then FIPS 186-4 does indeed defer to the
afore-mentioned document. But there do not appear to be any free, legal
copies of that standard floating around. Assuming you've paid your $100
for a copy, perhaps you would be so kind as to share with us relevant
parts of the text that would settle this question once and for all?

>Of course, one could always work over a Weierstrass model with nonzero
>cofactor, but then our proposal has minimal advantages over
> ECDSA: it will be slightly faster if you implement using alternative
>models.
>>

It wouldn't. The text you are commenting on doesn't suggest that it would,
does it?

The "problem we're trying to solve" is to understand the barriers to
adoption of any new scheme that we might wish to propose.

>>signing
>>the

Thank you. Should the chairs interpret your answer here as a "no" then?

Thanks

Kenny

---

From: Olafur Gudmundsson <[email-masked]>
Date: Wed, 8 Apr 2015 13:54:41 -0400

> On Apr 8, 2015, at 8:38 AM, Alexey Melnikov <[email-masked]> wrote:
> 

NIST compliance is not an issue. 

I would argue that any new signature schema is fine as long as it can be shown to be
strong and FAST. 

Olafur

---

From: Jon Callas <[email-masked]>
Date: Wed, 8 Apr 2015 10:57:24 -0700

NIST compliance is orthogonal to what we do. NIST is a fine organization with competent and wonderful people in it. Obviously, their opinion counts. However, it's a US government organization, and shouldn't have any more compliance power than any other government organization.

None. There are other uses for signatures than ones that involve CAs.

	Jon

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 8 Apr 2015 11:12:57 -0700

> On Apr 8, 2015, at 5:38 AM, Alexey Melnikov <[email-masked]> wrote:
> related versions of those curves)? 

No.  And as have others have stated, we probably won’t be NIST compliant even with ECDSA; and NIST can add whatever signature scheme we decide on.

> Or do the advantages of the available

Yes, the advantages of not-ECDSA would outweigh the benefits of NIST compliance, even if we could have NIST compliance.  This is especially true because derandomization is not NIST compliant.

> issuance of certificates on public keys for such schemes?

It is an equally serious barrier for any signature scheme.  They will need new software to verify CSRs on the new curve, and using ECDSA won’t make that software simpler.

— Mike

---

From: Paul Lambert <[email-masked]>
Date: Wed, 8 Apr 2015 11:27:25 -0700

>NIST compliance is orthogonal to what we do. NIST is a fine organization
>with competent and wonderful people in it. Obviously, their opinion
>counts. However, it's a US government organization, and shouldn't have
>any more compliance power than any other government organization.
+1

>None. There are other uses for signatures than ones that involve CAs.
+1   Yes, many interesting applications that.

Paul

>
>	Jon
>
>
>
>-----BEGIN PGP SIGNATURE-----
>Version: PGP Universal 3.3.0 (Build 9060)
>Charset: us-ascii
>
>wsBVAwUBVSVsB/D9H+HfsTZWAQgYPQgAi2ULlvlbw9vL6vWco1+7zH+jG6nVjdYu
>S8Sg+dkhnJ3KE3f+OqafpQ4vaPRdXemKKTSLJ5dKGfLGSFDWfhmNQJLyoFsblWU1
>8bO6wUlDrWGslBDfRQc1ENvKubxgRJYyjvHAHLfilDIBSl5/n8Q9baPLo276oYvc
>FmixtammvKDvLbx+pkyFlRb58QWeeXB3Tc9rZzUcDHoFJDwqwy0L76HHemCjxebL
>Udiu8wBecE7JrSrm8bBTQNQwpbSywY6sorGUxZAjSUrPlNLmrQ6KwkWTYtL/bDCB
>Dmn8TlosehuKnP5RgIr+jrM6lZDwiqutJBVhcuK3t3oe4hNX/VX3cQ==
>=pI8M
>-----END PGP SIGNATURE-----
>

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 08 Apr 2015 21:16:36 +0100

On 2015-04-08 13:38, Alexey Melnikov wrote:

> recommend ECDSA as is (suitably modified for our new curves or 
> closely related versions of those curves)?

No, NIST compliance is absolutely insignificant to our work.

The requirements of the few people who need NIST, or NSA Suite B,
compliance are already addressed by their existing recommendations.

We were asked to make new recommendations to working groups, for
international use in public internet protocols.

The practices or decisions of any national standards agency are not
relevant to our task; and we therefore should not be guided by them.

(NIST's re-evaluation of their recommendations might later be guided
by our work, amongst others - but that's up to them.)

> Or do the advantages of the available alternative signature schemes
>  outweigh the benefits of maintaining NIST compliance?

Yes to this part. We can now specify faster, better, less fragile
schemes than ECDSA: we should absolutely take the opportunity to do so.

>  the issuance of certificates on public keys for such schemes?

Insignificant, I think, beyond new curves themselves. (Might CAs;
CAB/F; PKIX; TLS be better forums to ask?)

As others have said, other than Google and CloudFlare, ECDSA usage on
the web is still quite limited. Most people are still stuck with RSA.

As I see it:
• For encryption everywhere, customers want faster/better crypto
• CAs will want to sign faster/better crypto keys for those customers
• Hardware vendors will want to deliver to those customers too
• CAs need CA/B Forum agreement to work with new algorithms & curves
• CA/B Forum demands high-assurance hardware key storage (HSM) support
• Some HSMs are flexible enough to support whatever we recommend
• We only really need support in one _good_ HSM
• Whomever that is will get customers! <grin>
• Conclusion: Demand drives supply. If we build it, they will come!

- -- 
/akr

---

From: Damien Miller <[email-masked]>
Date: Thu, 9 Apr 2015 09:55:37 +1000 (AEST)

> alternative signature schemes outweigh the benefits of maintaining NIST

Weak "no".

> issuance of certificates on public keys for such schemes?

SSH and other protocols have already adopted one of the signature schemes
that will presumably be discussed, so I'll go with "minor barrier".

-d

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Apr 2015 18:06:00 -0700

> parts of the text that would settle this question once and for all?

I did indeed mean X9.62, not 26. I don't have a copy. But I think it's
clear that domain parameters are specified in short Weierstrass form:
enough of it is quoted in FIPS 186-4 and in the accompanying algorithm
guidance from NIST to make clear that Edwards curves cannot be domain
parameters.

> adoption of any new scheme that we might wish to propose.

Ah, I meant that it seems from this email that we're considering two options:
1: Use ECDSA with different parameters
2: Change the scheme.

All the problems listed in this email with ECDSA are solved only by 2.
Changing parameters solves a different problem: the idea that one can
have a backdoor in EC parameters.

> Thank you. Should the chairs interpret your answer here as a "no" then?

Yes, exactly right.

---

From: Erwann Abalea <[email-masked]>
Date: Thu, 09 Apr 2015 11:44:25 +0200

Le 08/04/2015 14:38, Alexey Melnikov a écrit :
> specifications. ECDSA is also becoming more heavily used in TLS (see 
> for example http://notary.icsi.berkeley.edu/ which indicates that 
> ECDSA is currently used in about 16% of observed TLS sessions and that 
> 1.6% of valid certificates are for ECDSA public keys).
> [...]

"Recommend ECDSA as is": no
"Propose ECDSA with those new curves": maybe

If NIST compliance is important, one should stay with NIST compliant curves.

(CA and CA operator hat on)

Current lack of support from CAs isn't a barrier. Yet.

If there's no standardized structure to hold a public key under the new 
curves, they can't be represented in a certificate. We need an OID to 
identify the new curves (it will be placed in 
Certificate.tbsCertificate.subjectPublicKeyInfo.algorithm.parameters), 
and we need a way to properly encode/decode the 
Cert.tbs.sPKI.subjectPublicKey without breaking current ECC 
certificates. And of course, we also need OIDs to identify these new 
signature schemes and appropriate structures to hold the new signatures 
(if there's a change).

If there's no HSM to work with keys under these curves and these 
signature schemes, CAs won't be able to use such keys and schemes to 
sign certificates with.

If there's no user-level hardware token (USB key, smartcard, whatever) 
to work with keys under these curves and these signatures schemes, and a 
hardware token is mandatory, then CAs won't sign certificates with such 
public keys inside.

If whatever the signature is applied to doesn't support the new curves 
or the new signature schemes, there won't be any user to request for 
them. I'm thinking outside of TLS here, because CAs are not limited to 
TLS use. Think about email signature (CMS). Think about document signing 
(PAdES/CAdES -> CMS, XAdES -> xmldsig). Think about timestamping and 
their use (codesigning, document signing)...

If there's local regulation that limits signature schemes or curves, 
again, there won't be any request. ECDSA and NIST curves are acceptable 
pretty anywhere, China and Russia probably recommend or require their 
own schemes and curves. Germany probably pushes for ECGDSA and Brainpool 
curves, France accepts ECDSA and ECKCDSA under NIST and FRP256v1 curves 
to be "RGS compliant".

Someone already mentioned CABForum BR, that's another barrier.

All of this is out of scope of this group. Push for better schemes, the 
market will follow, hopefully.

-- 
Erwann ABALEA

---

From: Tom Ritter <[email-masked]>
Date: Sat, 11 Apr 2015 04:26:36 -0500

I will add to the chorus of

Not very important

Not a barrier.

-tom

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 15 Apr 2015 20:07:09 +0200

> related versions of those curves)?

No.

> outweigh the benefits of maintaining NIST compliance?

Yes.

> issuance of certificates on public keys for such schemes?

No barrier at all.

/Simon

---

From: Nico Williams <[email-masked]>
Date: Thu, 16 Apr 2015 16:42:11 -0500

NIST compliance should not be relevant to CFRG's recommendations.
Ultimately TLS and other WGs should decide what to require or recommend.
CFRG should recommend (to TLS and other WGs) cryptographic primitives
that CFRG believes are solid regardless of NIST compliance or other
bonafides.

The key is that CFRG is an RG, and an independent one at that.  CFRG
would add no value if it merely rubber-stamped others' recommendations.
The WGs will be aware -no doubt- of NIST's and others' recommendations,
and should make requirements and recommendations according to consensus
amongst their participants.

CFRG should note that CA lack of support for new algorithms is a reason
for TLS and other WGs to continue to recommend relying party support for
legacy signature algorithms.  I think that's as much as CFRG must do
here.

CFRG could also explain the signature algorithm agility issues for
protocols like PKIX and TLS, but I think that's something that the WGs
can do on their own.  If CFRG feels generous enough to contribute such
text, great.

I don't think there will be a serious barrier to adoption of new
signature algorithms.  It will take time, of course, and we know
-roughly- the signature algorithm agility issues at play.

Nico
--

---

From: Alexey Melnikov <[email-masked]>
Date: Thu, 30 Apr 2015 18:41:12 +0100

Hi,
My apologies for being late with closing this discussion.

Based on the discussions on the mailing list, chairs are declaring rough 
consensus on:

1) It looks like most people are not keen on ECDSA as specified by NIST, 
people are willing to work on/recommend better alternatives.
2) While there are some challenges in deploying new signature schemes by 
CAs, the problems don't seem to be serious enough for deploying a new 
signature scheme different from ECDSA. Deploying curve 25519 would 
require CAs to update anyway.

If this doesn't agree with your reading of the mailing list, please let 
the chairs know.

Chairs are in the process of discussing the next question(s).

Best Regards,
Alexey