Safe ECC curves

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Safe ECC curves

Kurt Roeckx
Hi,

I recently ran into this:
http://safecurves.cr.yp.to/

It seems that openssl doesn't support any of the curves that are
listed there as safe.

At least the curve 25519 is popular and has a draft for using it
in TLS.  Would it be possible to add at least support for that
curve?


Kurt

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Daniel Kahn Gillmor
On 01/01/2014 03:45 PM, Kurt Roeckx wrote:

> Hi,
>
> I recently ran into this:
> http://safecurves.cr.yp.to/
>
> It seems that openssl doesn't support any of the curves that are
> listed there as safe.
>
> At least the curve 25519 is popular and has a draft for using it
> in TLS.  Would it be possible to add at least support for that
> curve?
I think you're referring to Simon Josefsson's draft:

  https://tools.ietf.org/html/draft-josefsson-tls-curve25519-01

IIRC, the discussion about that draft over on [hidden email] got a bit
bogged down in the details of how to represent the points for this curve
and other similar curves (e.g. curve3617):

See, for example:

 https://www.ietf.org/mail-archive/web/tls/current/msg10284.html

If we could hash out those details (maybe restarting that conversation
over on [hidden email] with a concrete proposal), i'd agree that
implementing these curves for OpenSSL (at least for ECDHE, if not for
PKIX) would be a Good Thing.

Perhaps a patchset that implements it in one specific way, along with an
update to josefsson's draft clarifying the approach would be the most
useful next step, just so people have something concrete to consider.

Regards,

        --dkg


signature.asc (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Dr. Stephen Henson
On Wed, Jan 01, 2014, Daniel Kahn Gillmor wrote:

> On 01/01/2014 03:45 PM, Kurt Roeckx wrote:
> > Hi,
> >
> > I recently ran into this:
> > http://safecurves.cr.yp.to/
> >
> > It seems that openssl doesn't support any of the curves that are
> > listed there as safe.
> >
> > At least the curve 25519 is popular and has a draft for using it
> > in TLS.  Would it be possible to add at least support for that
> > curve?
>
> I think you're referring to Simon Josefsson's draft:
>
>   https://tools.ietf.org/html/draft-josefsson-tls-curve25519-01
>
> IIRC, the discussion about that draft over on [hidden email] got a bit
> bogged down in the details of how to represent the points for this curve
> and other similar curves (e.g. curve3617):
>

Yes that's a problem.

Adding support for some curves just needs addition of the appropriate curve
parameters, OIDs and in the case of TLS the Named Curve values.

Unfortunately for others (curve 25519 is of this type I believe) the handling
of the curve needs to be treated as a special case. We'd need a way of
representing public keys in SubjectPublicKeyInfo (this the point
representation discussion), private keys in PKCS#8 format and ideally
optimised curve arithemetic to protect it from attack.

Steve.
--
Dr Stephen N. Henson. OpenSSL project core developer.
Commercial tech support now available see: http://www.openssl.org
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Kyle Hamilton

Curve25519 public keys are 32-byte strings of digits.  Private keys are 32-byte strings of digits. The agreement algorithm doesn't use the Y coordinate at all.

djb has a fixed-clock-cycle algorithm he wrote in GNU assembly for Athlon. I am unhappy with his insistence that nobody should try to implement it for other platforms, as though Athlon is the only platform anyone would ever need. I agree that a platform-independent optimized arithmetic would be a good thing.

I would also like to see (since I know nothing about x86, x86_64, or Athlon assembly language) its translation to a 64-bit ABI.  But that's out of scope for this list.

At this point, tls@ has been so thoroughly compromised by BULLRUN and well-meaning rank amateurs that no actual work can be forwarded without a preexisting implementation. Many of the issues cited with the curve25519 tls draft were spurious and irrelevant to its application and adoption; however, I have neither the knowledge to implement it myself or the funds to hire anyone to implement it. I'd throw what pittance I can at a Kickstarter for it, though.

(To be clear: you need to know what digest you're feeding the 256 bits of curve25519 output through, and that might cause a curve25519-sha256, curve25519-sha384, etc ECDHE selection. It's also useful to note that the public key calculation is the output of the same curve25519 function with the specific public key parameter '9', and the function in djb's implementation is fast enough to generate on an Athlon a public key from a pseudorandom private key on connect().)

-Kyle H

On Jan 1, 2014 1:18 PM, "Dr. Stephen Henson" <[hidden email]> wrote:
On Wed, Jan 01, 2014, Daniel Kahn Gillmor wrote:

> On 01/01/2014 03:45 PM, Kurt Roeckx wrote:
> > Hi,
> >
> > I recently ran into this:
> > http://safecurves.cr.yp.to/
> >
> > It seems that openssl doesn't support any of the curves that are
> > listed there as safe.
> >
> > At least the curve 25519 is popular and has a draft for using it
> > in TLS.  Would it be possible to add at least support for that
> > curve?
>
> I think you're referring to Simon Josefsson's draft:
>
>   https://tools.ietf.org/html/draft-josefsson-tls-curve25519-01
>
> IIRC, the discussion about that draft over on [hidden email] got a bit
> bogged down in the details of how to represent the points for this curve
> and other similar curves (e.g. curve3617):
>

Yes that's a problem.

Adding support for some curves just needs addition of the appropriate curve
parameters, OIDs and in the case of TLS the Named Curve values.

Unfortunately for others (curve 25519 is of this type I believe) the handling
of the curve needs to be treated as a special case. We'd need a way of
representing public keys in SubjectPublicKeyInfo (this the point
representation discussion), private keys in PKCS#8 format and ideally
optimised curve arithemetic to protect it from attack.

Steve.
--
Dr Stephen N. Henson. OpenSSL project core developer.
Commercial tech support now available see: http://www.openssl.org
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Dr. Stephen Henson
On Wed, Jan 01, 2014, Kyle Hamilton wrote:

> Curve25519 public keys are 32-byte strings of digits.  Private keys are
> 32-byte strings of digits. The agreement algorithm doesn't use the Y
> coordinate at all.
>

By itself that isn't enough. We need a way to encode those digits in a PKCS#8
sttucture and a SubjectPublicKeyInfo structure. If Curve25519 was treated in a
way similar to existing curves you'd just need another standardised namedCurve
OID (as was the case with brainPool). Then the existing routines would handle
encode and decode just fine.

Curve25519 differs from other ECC curves in a number of ways, not least of
which is that the y component is not used. That probably makes it incompatible
with RFC5480 unless you kludge it to include y anyway.

So Curve25519 needs a standard OID and some notes on the format to use for
ASN.1. Does such a thing exist?

Steve.
--
Dr Stephen N. Henson. OpenSSL project core developer.
Commercial tech support now available see: http://www.openssl.org
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

RE: Safe ECC curves

Salz, Rich
> So Curve25519 needs a standard OID and some notes on the format to use for ASN.1. Does such a thing exist?

I don't think so.  Perhaps the TLS list is the place to discuss this?  Should we (I?) start a thread there on a proposal to fit Curve25519 into common TLS usage?

Strawman proposal:
        The keys are OCTET STRING (or does BIGNUM fit better with existing code?)
        Y is fixed at zero
        An OID is assigned from the IETF arc

Anything else missing?

I can ask djb but I bet he *really* doesn't care. :)

        /r$

--  
Principal Security Engineer
Akamai Technology
Cambridge, MA

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Dr. Stephen Henson
On Thu, Jan 02, 2014, Salz, Rich wrote:

> > So Curve25519 needs a standard OID and some notes on the format to use for ASN.1. Does such a thing exist?
>
> I don't think so.  Perhaps the TLS list is the place to discuss this?  Should we (I?) start a thread there on a proposal to fit Curve25519 into common TLS usage?
>
> Strawman proposal:
> The keys are OCTET STRING (or does BIGNUM fit better with existing code?)
> Y is fixed at zero
> An OID is assigned from the IETF arc
>
> Anything else missing?
>

Well ideally it needs to be as close as possible to RFC5280 which is a PKIX
document and the group has now closed... great timing. But that ends up with
point compression rearing its ugly head.

It's not much use though if it takes a glacial time scale to get an OID
assigned (or preferably several OIDs AFAICS).

> I can ask djb but I bet he *really* doesn't care. :)
>

Well if he doesn't that's fine. I'd otherwise feel a bit guilty ats
"appropriating" his curve with an OID.

Steve.
--
Dr Stephen N. Henson. OpenSSL project core developer.
Commercial tech support now available see: http://www.openssl.org
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Daniel Kahn Gillmor
In reply to this post by Salz, Rich
On 01/02/2014 08:50 AM, Salz, Rich wrote:
> [Dr. Stephen Henson wrote:]
>> So Curve25519 needs a standard OID and some notes on the format to use for ASN.1. Does such a thing exist?
>
> I don't think so.

yes, i mentioned it up-thread:

 https://tools.ietf.org/html/draft-josefsson-tls-curve25519-01

this isn't formalized yet, and it raised discussion that wasn't yet
resolved, but it's the document to work from, i think.

>  Perhaps the TLS list is the place to discuss this?  Should we (I?) start a thread there on a proposal to fit Curve25519 into common TLS usage?
>
> Strawman proposal:
> The keys are OCTET STRING (or does BIGNUM fit better with existing code?)
> Y is fixed at zero
> An OID is assigned from the IETF arc
>
> Anything else missing?

I think we want to clarify the distinction between ECDHE (key exchange)
and ECDSA (PKIX).  it sounds like Curve25519 is only going to be useful
for ECDHE, and if we want to provide a parallel to ECDSA, we would need
to move to EdDSA, which involves even more specification work.

I would be happy to avoid the PKIX stuff for now and just get the thing
standardized for ECDHE.

> I can ask djb but I bet he *really* doesn't care. :)

I don't think we need to involve djb in this directly.  if he was
interested in the standardization process, he could easily get involved
in it.  He's shown pretty clearly that he doesn't bother with that kind
of stuff historically :/

        --dkg


signature.asc (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Manuel Pégourié-Gonnard
In reply to this post by Kyle Hamilton
On 02/01/2014 01:44, Kyle Hamilton wrote:

> djb has a fixed-clock-cycle algorithm he wrote in GNU assembly for Athlon.
> I am unhappy with his insistence that nobody should try to implement it for
> other platforms, as though Athlon is the only platform anyone would ever
> need. I agree that a platform-independent optimized arithmetic would be a
> good thing.
>
> I would also like to see (since I know nothing about x86, x86_64, or Athlon
> assembly language) its translation to a 64-bit ABI.  But that's out of
> scope for this list.
>
You might want to look here: https://code.google.com/p/curve25519-donna/

There is also a fully portable C implementation in NaCl (directory
crypto_scalarmult/curve25519/ref): http://nacl.cr.yp.to/

Manuel.
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Dr. Stephen Henson
In reply to this post by Daniel Kahn Gillmor
On Thu, Jan 02, 2014, Daniel Kahn Gillmor wrote:

> On 01/02/2014 08:50 AM, Salz, Rich wrote:
> > [Dr. Stephen Henson wrote:]
> >> So Curve25519 needs a standard OID and some notes on the format to use for ASN.1. Does such a thing exist?
> >
> > I don't think so.
>
> yes, i mentioned it up-thread:
>
>  https://tools.ietf.org/html/draft-josefsson-tls-curve25519-01
>
> this isn't formalized yet, and it raised discussion that wasn't yet
> resolved, but it's the document to work from, i think.
>

That's just TLS. To add more complete support to OpenSSL including storing
private keys in PEM files and public keys in case we ever use it in ECDH
certificates it needs an OID and some details on how the keys are encoded.

Steve.
--
Dr Stephen N. Henson. OpenSSL project core developer.
Commercial tech support now available see: http://www.openssl.org
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Daniel Kahn Gillmor
On 01/02/2014 12:35 PM, Dr. Stephen Henson wrote:
> That's just TLS. To add more complete support to OpenSSL including storing
> private keys in PEM files and public keys in case we ever use it in ECDH
> certificates it needs an OID and some details on how the keys are encoded.

But ECDHE doesn't need any of these trappings, as nice as they would be
to have.  The curves are known; implementations of them are known;
secret keys can be held in memory in any standard way, and public keys
can be transmitted on the wire for the key exchange as simply as
possible, without specifying PKCS encodings or SPKI or whatever.

Getting Curve25519 (and Curve3617?) functional for ECDHE would be a
demonstrably good thing on its own, and it would be a shame for that
functionality to wait until people could finally agree on how to use
PKCS encodings and EdDSA for X.509 certificates.

        --dkg


signature.asc (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Kurt Roeckx
On Thu, Jan 02, 2014 at 12:59:39PM -0500, Daniel Kahn Gillmor wrote:

> On 01/02/2014 12:35 PM, Dr. Stephen Henson wrote:
> > That's just TLS. To add more complete support to OpenSSL including storing
> > private keys in PEM files and public keys in case we ever use it in ECDH
> > certificates it needs an OID and some details on how the keys are encoded.
>
> But ECDHE doesn't need any of these trappings, as nice as they would be
> to have.  The curves are known; implementations of them are known;
> secret keys can be held in memory in any standard way, and public keys
> can be transmitted on the wire for the key exchange as simply as
> possible, without specifying PKCS encodings or SPKI or whatever.
>
> Getting Curve25519 (and Curve3617?) functional for ECDHE would be a
> demonstrably good thing on its own, and it would be a shame for that
> functionality to wait until people could finally agree on how to use
> PKCS encodings and EdDSA for X.509 certificates.

I also think that ECDHE really is currently the priority, to have
an alternative to the NIST P curves at least some people think are
backdoored by the NSA and as result want to avoid.

Most people seem want to do PFS now, but some want ECDHE for speed
and the other DHE to avoid the NIST P curves.  I think having
something like Curve25519 could make both sides agree on using
ECDHE.


Kurt

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Safe ECC curves

Kyle Hamilton
In reply to this post by Dr. Stephen Henson

1.3.6.1.4.1.22232.15.0: Curve25519  (That's out of my arc)

X coordinate is an OCTET STRING.
Y coordinate is a 0-byte OCTET STRING (since it's not defined as optional in ASN.1, it must be present -- but how can you compress what doesn't exist?)

When does the Point Compression patent expire, anyway?

-Kyle H

On Jan 2, 2014 6:28 AM, "Dr. Stephen Henson" <[hidden email]> wrote:
On Thu, Jan 02, 2014, Salz, Rich wrote:

> > So Curve25519 needs a standard OID and some notes on the format to use for ASN.1. Does such a thing exist?
>
> I don't think so.  Perhaps the TLS list is the place to discuss this?  Should we (I?) start a thread there on a proposal to fit Curve25519 into common TLS usage?
>
> Strawman proposal:
>       The keys are OCTET STRING (or does BIGNUM fit better with existing code?)
>       Y is fixed at zero
>       An OID is assigned from the IETF arc
>
> Anything else missing?
>

Well ideally it needs to be as close as possible to RFC5280 which is a PKIX
document and the group has now closed... great timing. But that ends up with
point compression rearing its ugly head.

It's not much use though if it takes a glacial time scale to get an OID
assigned (or preferably several OIDs AFAICS).

> I can ask djb but I bet he *really* doesn't care. :)
>

Well if he doesn't that's fine. I'd otherwise feel a bit guilty ats
"appropriating" his curve with an OID.

Steve.
--
Dr Stephen N. Henson. OpenSSL project core developer.
Commercial tech support now available see: http://www.openssl.org
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

RE: Safe ECC curves

Salz, Rich

Ø  1.3.6.1.4.1.22232.15.0: Curve25519  (That's out of my arc)

I’ve been in touch with Dan, who sent me to Werner Koch, who said that GPG is using

  { "Curve25519", "1.3.6.1.4.1.3029.1.5.1" }, -- Peter Gutmann's arc

 

So we should use that

 

I’m gonna post an I-D today or tomorrow, and ask the TLS-WG to pick it up.  If not, then it can go as an individual submission because there are no protocol changes.

 

                /r$

 

-- 

Principal Security Engineer

Akamai Technology

Cambridge, MA