Subject: [pkix] Edwards/DJB curves - New PKI(X) work?

From: Anders Rundgren <[email-masked]>
Date: Thu, 14 Aug 2014 06:46:23 +0200

Hi Max,

Did you find any new useful PKIX tasks?
Edwards/DJB curves seem to be discussed everywhere so it should be an excellent target!
Microsoft has also released a bunch of new curves.
You will need to correlate with CRFG, WebCrypto, TLS, and JOSE.

Anders

---

From: Stephen Kent <[email-masked]>
Date: Thu, 14 Aug 2014 07:33:06 -0400

Anders,

Discussions of public key algorithms are the province of the CFRG, not PKIX.

Steve

---

From: Anders Rundgren <[email-masked]>
Date: Thu, 14 Aug 2014 13:36:20 +0200

> Discussions of public key algorithms are the province of the CFRG, not PKIX.

Of course.

But the inclusion of new algorithms in X.509 structures sounds
like a PKI(X)-like task.

Anders

>
>
> Steve
>
> _______________________________________________
> pkix mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/pkix
>

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 14 Aug 2014 16:51:16 +0200

> But the inclusion of new algorithms in X.509 structures sounds

Well, "new algorithms" is not exactly the right term for introducing a new curve representation; it's rather a new
semantic of public keys, digital signatures and cryptograms. (There are some people on the CFRG advocating
standardization of simplified ECC-based signature algorithms, like Schnorr signatures, but currently, the discussion
focuses on curves and their representation.) But essentially, you are right: if we want to use new semantics in PKIX,
new specs for X.509 certs / CRLs, for CMS etc. would be needed.

However, it is yet too early for action. It is not yet clear, what exactly CFRG recommends to the tls WG. Even if
Montgomery curves or Edwards curves are chosen, there is still the option of using traditional (Weierstrass)
representation / semantic on-the-wire, as transformation is quite simple. See
https://www.ietf.org/mail-archive/web/cfrg/current/msg04816.html

Johannes

---

From: Anders Rundgren <[email-masked]>
Date: Thu, 14 Aug 2014 18:05:35 +0200

> new specs for X.509 certs / CRLs, for CMS etc. would be needed.

I'm not a cryptographer you know :-)

Anyway, wouldn't you need algorithms also like EdDSA-SHA256 or would ECDSA-SHA256 apply?
Again, pardon a non-cryptographer for asking stupid/strange questions...

Anders

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 15 Aug 2014 09:38:27 +0200

> Again, pardon a non-cryptographer for asking stupid/strange questions...

The usage of ECDSA-SHA256 within PKIX is already fully specified in RFC 5758. The curve (more specifically, the elliptic
curve parameters) are a property of the public key not of the digital signature, DH value or cipher text.
In order to use other curves, you just need to replace the OID for the named curve which is a parameter of the
SubjectPublicKeyInfo according to RFC 5480.

As I said, there are ideas to define new digital signature algorithms, like Schnorr signature or EdDSA. The motivation
for this is both performance and ease of (secure) implementation, but is is perfectly possible to use Montogomery or
Edwards curves with ECDSA in a secure and efficient way. There has been some confusion about this, because Daniel
Bernstein has introduced his Edwards curve Ed25519 together with a new signature algorithm (and also suggested to use
the Montgomery curve Curve25519 for DH only), but this combination of curves and algorithms (and, actually, of a
specific arithmetic as well) is just an optimization, and does not really fit the modular approach of PKIX.

My perception is that CFRG (and tls WG) will take one step after another and will now standardize new curves only. After
that is accomplished, they might consider standardization of new signature algorithms, but this has not been decided yet.

-- 
Johannes

---

From: Anders Rundgren <[email-masked]>
Date: Fri, 15 Aug 2014 10:02:29 +0200

> that is accomplished, they might consider standardization of new signature algorithms, but this has not been decided yet.

Thanx for the update!
It looks very messy to me.

Personally I wonder if CFRG will be able to stop new signature algorithms
since OpenSSH already supports EdDSA:
http://www.gossamer-threads.com/lists/openssh/dev/57162

Anders

Anders

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 15 Aug 2014 07:59:56 -0700

> since OpenSSH already supports EdDSA:

Please do not impute bad intentions on people you do not know. The CFRG is not trying to stop anyone from any curves, even the current ones.

--Paul Hoffman

---

From: Michael StJohns <[email-masked]>
Date: Sat, 16 Aug 2014 23:16:24 -0400

>SubjectPublicKeyInfo according to RFC 5480.

If I had to make a guess as to whether this is correct or not I'd say that it mostly isn't.  Starting with PKIX public key representation, the OID for the AlgorithmIdentifier.algorithm type idEcPublicKey specifies how the public key is formatted; the curve OID (included in the parameters field) merely describes the curve parameters by reference.   (Section 2.2 of RFC5480 - but other places as well).  So you can't really reuse that algorithm type identifier.

Then there's the actual verification process.  The code I use for example looks first at the SignatureAlgorithm field of a certificate.  When it sees "SHA256withECDSA",  it instantiates a Signature object of that specific type *before* grabbing the appropriate public key to initialize the verification operation.   In other words, I'm stuck with  FIPS186-3 compliant signature function trying to parse a DJB curve key.

Basically, while you're correct that the key  curve is going to determine how you verify the signature, I would be surprised if any code checks the key curve first as the current understanding is that ECDSA means SECG1/X9.62/NISP FIPS186-3 (which are basically the same math and representations).  

For PKIX at least for signatures you need:

1) An ASN1 public key representation (and the appropriate OID).  Since there's only one DJB curve(?is that correct or are two needed for signature and ecdh?), you could get away with just a new OID for AlgorithmIdentifier.algorithm.
2) The format of the bitstring that represents a signature 
3) One or more signature algorithms (e.g. SHA256withX, SomeOtherHashWithX, etc) and their OIDs.

I think that any attempt to use the current set of EC code points  for DJB curve data is going to lead to really bad interactions with existing code (included but not limited to PKIX, TLS and IPSEC).  Better to assign new code points where necessary.

Later, Mike

---

From: Anders Rundgren <[email-masked]>
Date: Sun, 17 Aug 2014 15:21:16 +0200

> I think that any attempt to use the current set of EC code points  for DJB curve data is going to lead to really bad interactions with existing code (included but not limited to PKIX, TLS and IPSEC…

GOST apparently required such measures as well:
http://tools.ietf.org/rfc/rfc4491.txt

Anders

---

From: Johannes Merkle <[email-masked]>
Date: Mon, 18 Aug 2014 10:55:32 +0200

> Basically, while you're correct that the key  curve is going to determine how you verify the signature, I would be surprised if any code checks the key curve first as the current understanding is t…

You are right, I was imprecise. As I wrote in my previous message:

  Even if

My statement above (that using a new curve only requires a curve OID) only referred to the case that the representation
of the EC points don't change. In the alternative case, you are right: if we want to use new EC point semantics, new
specs for X.509 certs / CRLs, for CMS etc. would be needed.

> 1) An ASN1 public key representation (and the appropriate OID).  Since there's only one DJB curve(?is that correct or
are two needed for signature and ecdh?), you could get away with just a new OID for AlgorithmIdentifier.algorithm.
> 3) One or more signature algorithms (e.g. SHA256withX, SomeOtherHashWithX, etc) and their OIDs.

I disagree with 2) though: In all Schnorr-like signatures, the signature consists of two integers, not (EC) group
elements. Thus, the EC point semantic has no influence on the signature encoding. It only has impact on the signature
generation and verification algorithms (e.g. defined in ANSI X9.62 and FIPS 186-4), but these are out of the scope of PKIX.

Of course, if new signature algorithms are introduced in PKIX (3), this implies that new semantics of signature values (2).

Johannes

---

From: Anders Rundgren <[email-masked]>
Date: Mon, 18 Aug 2014 13:25:58 +0200

I guess the same issues belong to signature standards like JWS?
https://datatracker.ietf.org/doc/draft-ietf-jose-json-web-signature/

More stuff to consider includes the NUMS (Nothing Up My Sleeve) curves from Microsoft:
http://research.microsoft.com/en-us/projects/nums/

Anders

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 18 Aug 2014 12:37:06 +0100

As a few folks (incl. me:-) said elsewhere...

> http://research.microsoft.com/en-us/projects/nums/

If you're interested in which new curves might make sense to use
in IETF work, please engage on that topic with the CFRG [1] who
are running a process now to tey reach consensus on some curves.

But let's not try do that in parallel here. When CFRG are done
then there will be some bits and pieces of work to be done here
perhaps, but not just yet.

Thanks,
S.

[1] https://irtf.org/cfrg

---

From: Anders Rundgren <[email-masked]>
Date: Mon, 18 Aug 2014 16:23:14 +0200

> are running a process now to tey reach consensus on some curves.

There are two issues here:

1. Creating external representations of Keys, Curves and Algorithms that
    can be reused by various standards in development or in need of a "refresh".
    This is actually a bit urgent since the using systems are designed *now*.

2. Recommending algorithms/curves to use is less critical since the proponents
    (which even includes *countries* like Russia/GOST, China/SM3 and USG/NIST),
    have already made their choices.  Internet-scale TLS server certificates and
    DNSSEC are exceptions that indeed need recommendations.

Anders

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 18 Aug 2014 15:27:22 +0100

>    This is actually a bit urgent since the using systems are designed

I don't agree. Some of the CFRG discussion may touch on that
so getting ahead of them here would be a bad idea. And CFRG
have set themselves a target of getting back to the TLS WG
before November, so I'd recommend a bit of patience for now,
for this part of the puzzle.

S.

---

From: Michael StJohns <[email-masked]>
Date: Mon, 18 Aug 2014 14:02:54 -0400

>generation and verification algorithms (e.g. defined in ANSI X9.62 and FIPS 186-4), but these are out of the scope of PKIX.

Sort of.  The representation for PKIX EC signatures using X9.63/FIPS186-3/SECG1 is 

BIT STRING encapsulating {
    SEQUENCE {
           INTEGER r,
         INTEGER s
     }
}

 - I assume that's what you mean for Schnorr signatures?

In DJB's ED25519, the signature is actually a single integer, and tucked away in his paper is the notation that the representation of that integer is little endian.

So you could use either of 

BIT STRING encapsulatiing {
    INTEGER s
}

or 
BIT STRING encapsulating {
    OCTET STRING SIZE (32) s   ; little endian representation of a 255 bit integer
}

or even

BIT STRING SIZE(255)

or 

BIT STRING

At this point I would assume new key type OID's, *maybe*  new curve OIDs if the curve  isn't implied by the key type, and new signature type OIDs and representations. 

Mike

---

From: Michael StJohns <[email-masked]>
Date: Mon, 18 Aug 2014 14:20:49 -0400

>for this part of the puzzle.

There's at least two different things going on here - the possible selection of new curve/math/etc, and the representational aspects of those choices.  I've been commenting on/arguing about draft-turner-thecurve25519function with the authors and realized during that interaction that our process is really rather poorly set up to deal with these two items appropriately.

For example, the math in draft-turner... has no dependency at all on endianess (pretty much every element of the system is a bignum integer), but there are about 5-8 lines that state an absolute requirement that the representation of those elements when externalized be little endian.  Indeed, there have already been several arguments about representation of Curve25519 elements on the TLS mailing list and elsewhere.    I'm somewhat disturbed that this non-WG, non-IETF, CFRG draft could end up setting (or strait jacketing) representations for all IETF protocols without input from those involved in the protocol formation.

I guess the question comes down to competencies.  I believe the CFRG competent to rule on the security of the math.  I would suggest that it may be outside CFRG's purview to be directing protocol representations.  But the CFRG is not set up to handle the wide participation necessary to discuss representational forms nor would I really want it to be. 

So getting back to your point above - happy to have the CFRG pick the math.  But PKIX/TLS/IPSec et al should get a say in on-the-wire representation.  If we can keep those two separate in the decision process, I expect you'll have less dissent in later stages.

Mike

---

From: Stephen Kent <[email-masked]>
Date: Mon, 18 Aug 2014 14:50:49 -0400

Once we hear from the CFRG, and if there is interest, then a document
could be written, as an individual submission, and sponsored by one
of the Sec ADs.

Steve

> ...

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 18 Aug 2014 20:50:30 +0100

On 18/08/14 19:20, Michael StJohns wrote:
> 
> I guess the question comes down to competencies.  I believe the CFRG
> competent to rule on the security of the math.  I would suggest that
> it may be outside CFRG's purview to be directing protocol
> representations.  But the CFRG is not set up to handle the wide
> participation necessary to discuss representational forms nor would I
> really want it to be.
> 
> So getting back to your point above - happy to have the CFRG pick the
> math.  But PKIX/TLS/IPSec et al should get a say in on-the-wire
> representation.  If we can keep those two separate in the decision
> process, I expect you'll have less dissent in later stages.

Sure. This isn't really that new though - algorithm RFCs tend
to be a little odd anyway in that they're often "imports" from
elsewhere, in this case the elsewhere is a bit closer (and new
curves are not quite the same as new algs). But in any case,
yes, we'll do the right thing.

That could be to separate the math and the on-the-wire stuff.
Or it may make more sense to keep those in one doc. In the
latter case we can make sure there's an IETF LC by simply
making it an IETF doc (as Steve K. mentioned in his mail).
Or it could be done by taking an experimental CFRG RFC and
putting that on the standards track via an IETF LC for that.
I doubt that latter would make sense but just note it to make
it clear we do have all the process tools to do whatever
ends up being needed.

That said, I do hope that we all take proper account of running
code where it exists and get involved in the discussion in the
right places at the right times so that this all doesn't take
twice as long as it needs to. (Sadly we're all quite good at
making that happen;-)

I suspect in practice it'd make most sense to get comments on
endianness etc around the time CFRG are finishing their work.
And then we can figure out process stuff so's it works out.

Cheers,
S.

---

From: Erwann Abalea <[email-masked]>
Date: Tue, 19 Aug 2014 12:46:36 +0200

2014-08-18 20:02 GMT+02:00 Michael StJohns <[email-masked]>:

> >> 1) An ASN1 public key representation (and the appropriate OID).  Since
> there's only one DJB curve(?is that correct or
> >are two needed for signature and ecdh?), you could get away with just a
> new OID for AlgorithmIdentifier.algorithm.
> >elements. Thus, the EC point semantic has no influence on the signature
> encoding. It only has impact on the signature
> >generation and verification algorithms (e.g. defined in ANSI X9.62 and
> FIPS 186-4), but these are out of the scope of PKIX.
>
>
> In DJB's ED25519, the signature is actually a single integer, and tucked
> away in his paper is the notation that the representation of that integer
> is little endian.
>

Even in Ed25519 the signature consists of two 256bits integers. Little/big
endian representation doesn't care here.
R is a compressed version of a point (concatenation of y and lsb of x).
S is the standard S.

-- 
Erwann.

---

From: Michael StJohns <[email-masked]>
Date: Tue, 19 Aug 2014 12:01:30 -0400

Sent from my iPad

> On Aug 19, 2014, at 6:46, Erwann Abalea <[email-masked]> wrote:
> 
> 
> Even in Ed25519 the signature consists of two 256bits integers. Little/big endian representation doesn't care here.

*sigh* you're correct.  I misread a summary of the DJB paper.   Mike