957105 - (curve25519) Add support for curve25519 key exchange

Status: RESOLVED FIXED

(NSS :: Libraries, enhancement)

Description

[spam]

Since the NSA scandal, it should be wise to prove Elliptic Curves, specifically curve25519, not engineered (with the help) by NSA. One implementation is [e-mail] for Key Exchange.

More information at http://git.libssh.org/projects/libssh.git/tree/doc/[e-mail]  and author of the curve: http://cr.yp.to/ecdh.html


UMAC is much faster than HMAC for message authentication in TLS. see RFC http://www.ietf.org/rfc/rfc4418.txt or http://fastcrypto.org/umac/

Some benchmarks of UMAC in gnutls/nettle: 
http://nmav.gnutls.org/2013/05/salsa20-and-umac-in-tls.html


I'd also like to see TLS1.2 enabled by default, as Chrome and Opera has on both Android and PC...

Comment 1

[sjw]

See 861266 for TLS1.2 support.

Comment 2

[cod3 ang3l]

Attachment: curve25519.patch

I try to help you add Curve25519.

From http://safecurves.cr.yp.to/base.html
order is
7237005577332262213973186563042994240857116359379907606001950938285454250989
= 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed
= 2^252 + 27742317777372353535851937790883648493 

From http://safecurves.cr.yp.to/field.html
prime is
57896044618658097711785492504343953926634992332820282019728792003956564819949
= 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
= 2^255 - 19

Size is 255 yes?

From http://safecurves.cr.yp.to/equation.html
formula is y^2 = x^3+486662x^2+x

Curve parameter a is 486662 is 0x76d06. Parameter b is 1. Yes?

From http://safecurves.cr.yp.to/base.html
base point is
(9,
14781619447589544791020593568409986887264606134616475288964881837755586237401)
= (0x9,
0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9)

Comment 3

[Rob Stradling]

See here for links to some relevant IETF drafts:
http://www.ietf.org/mail-archive/web/tls/current/msg11161.html

Comment 4

[Dave Huseby [:huseby]]

this patch needs to be fixed before rebasing.  the ecdecode.c file has been moved to lib/freebl.

Comment 5

[Johannes Pfrang [:johnp]]

There is now a first draft published for EdDSA and Ed25519 in TLS.
Development can be followed in this git repo and on the TLS WG mailing list:
https://gitlab.com/jas/ietf-tls-eddsa

Comment 6

[Eric Rescorla (:ekr)]

- The TLS WG is likely to take a Curve25519 key exchange draft.
- The CFRG hasn't converged on new curves for signatures, so an Ed25519 patch is premature.
- I don't see a lot of enthusiasm in TLS for UMAC as an HMAC replacement. Rather the trend is to go to AEAD constructions.

Comment 7

[Kosuke Kaizuka]

There is an IETF draft for Curve25519 in TLS.
https://tools.ietf.org/html/draft-ietf-tls-curve25519-00

Comment 8

[Kosuke Kaizuka]

IETF draft has been updated.
https://tools.ietf.org/html/draft-ietf-tls-curve25519-01

Curve448 is added as well as Curve25519.

Comment 9

[Danny Moules]

Last update was that the proposed patch needs fixing. Any idea if these changes have been made and, if not, what needs to be resolved, so this can be moved forward?

Comment 10

[Eric Rescorla (:ekr)]

Watson, can you take a look at this patch and provide feedback on whether this is the right direction?

Comment 11

[Watson Ladd]

It's not. Our ECC code assumes that all curves are presented in short Weierstrass form, and doesn't support x coordinate only support. The work that is required involves adding an implementation of Curve255519, and then plumbing to expose it at the softtoken layer, instead of putting in Curve25519 in Weierstrass form.

Comment 12

[Eric Rescorla (:ekr)]

Bob, thoughts?

Comment 13

[Paul Wouters]

It is also proposed for IKE:

https://tools.ietf.org/html/draft-nir-ipsecme-curve25519-01

Comment 14

[Robert Relyea]

Comment on attachment 8376422 [details] [diff] [review]
curve25519.patch

Review of attachment 8376422 [details] [diff] [review]:
-----------------------------------------------------------------

r- there are 3 issues with this patch:

1) The curve parameters have not been transformed.
2) When we use this curve we also need to transform the curve points in and out (the way to tranform one curve to another is to do a transform on the points.
3) The points for the curve25519 are specified in reverse order bit order from the rest of the curves (and without a point format byte). We'll have to take that into account as well.

I'll include the math for the transform in the body of the bug.

::: lib/freebl/ecl/ecl-curve.h
@@ +51,5 @@
> +	"1",
> +	"9",
> +	"20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9",
> +	"1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed",
> +	8

So these curve parameters are incorrect. the published values for the Curve25519 are based on the elliptic curve form

y^2 = x^3 + a*x^2 + x

Our elliptic curve engine is based on the curve form:

y^2 = x^3 + a*x + b

The 25519 form can be converted into the standard curve form (giving up the bernstein accellerations), but these curve values have not been converted. 0x76d06 is the decimal 486662 (the raw a in bernstein's equation).

What needs to change in this structure is curvea, curveb, genx and geny (cofactor, order, and iir should be the same between the two curve forms).

Comment 15

[Robert Relyea]

"Guide to Elliptic Curve Cryptography" by Hankerson, Menezes and Vanstone  page 78 give the general equation of an elliptic curve and the transforms to simplify them. The general equation is:

y^2 + a1*x*6 + a3*y = x^3 + a2*x^2 + a4*x + a6

The transform to the our standard y^2 = x^3 + a*x + b is:

(x,y) -> ( (1/36)*(x' - 3*a1^2 - 12*a2), (1/216)*(y' - 3*a1*x') - (1/24)*(a1^3 + 4*a1*a2 - 12*a3) )

In bernstein's equation:

a1=0 a2=a a3=0 a4=1 a6=0, so

(x,y) -> ( (1/36)*(x' - 12*a2), (1/216)*(y') )

Substituting all these into bernstein's equation yields:

(y'/216)^2 = (1/36)^3*(x' - 12*a)^3 + a*(1/36)^2*(x' - 12*a)^2 + (1/36)*(x' - 12*a)

Note: 216^2 = 36^3, so

y' = (x' - 12*a)^3 + 36*a*(x' - 12*a)^2 + 36^2*(x' - 12*a)
y' = x'^3 + 12*36(a^2-a/2)x' - (12)^3*(a^3-3*a+9*a)

so a'= 12*36*(a^2-a/2)
   b' = -(12^3)*(a^3-3*a^2+9*a)

In the next post I'll reduce those to real values.

Comment 16

[Robert Relyea]

So:

y' = (x' - 12*a)^3 + 36*a*(x' - 12*a)^2 + 36^2*(x' - 12*a)
y' = x'^3 + 12*36(a^2-a/2)x' - (12)^3*(a^3-3*a+9*a)

Should be:

y'^2 = (x' - 12*a)^3 + 36*a*(x' - 12*a)^2 + 36^2*(x' - 12*a)
y'^2 =  x'^3 + 12*36(a^2-a/2)x' - (12)^3*(a^3-3*a+9*a)

Comment 17

[Robert Relyea]

OK the reduced equation had some algebra errors in it. Here is the final reduced equation:

y'^2 = x'^3 + 36*(36-12*a^2)*x' + 12^3*(2*a^3-9*a)

yielding:
a' = 36*(36-12*a^2)
b' = 12^3*(2*a^3-9*a)

On input we need to convert the given points to our internal curve by:
x' = 36*x + 12*a = 36*x + 12*486662
y' = 216*y

On output we need to convert out internal curve to the output curve by:
x = inv36 * (x' - 12*486662)
y = inv216*y'

I've written a program go calculate genx, geny, a', b', inv36 and inv216. I'll attach the program and the results.

bob

Comment 18

[Robert Relyea]

Attachment: curve25519.c - calculate the a,b parameters for curve25519.

Comment 19

[Robert Relyea]

./curve25519 
x   = +0000000000000009
y   = +20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9
p   = +7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED
a   = +0000000000076D06
>>             y^2 = +00000000025981C8
>> x^3 + a*x^2 + x = +00000000025981C8
Orig Confirm
=============================================================
1/36 mod p   = +51C71C71C71C71C71C71C71C71C71C71C71C71C71C71C71C71C71C71C71C71BB
1/216 mod p = +22F684BDA12F684BDA12F684BDA12F684BDA12F684BDA12F684BDA12F684BD9C
a' = +7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA2F1F870883D
b' = +0000000000000015981AE3C3B2B63780
x' = +0000000000591D8C
y' = +12E5A073C771A89D1A0A9D84A570989B63B962AC60F26E535D3EC11AFE82C32D
>>            y'^2 = +000001AC38A4A200
>> x'^3 + a*x' + b = +000001AC38A4A200
Confirm

a' is curvea
b' is curveb
x' is genx
y' is geny
1/36 mod p is inv36 from comment 17
1/216 mod p is inv216 from comment 17

bob

Comment 20

[Dave Huseby [:huseby]]

So those are the correct values for our code?  Who is going to update the patch?

Comment 21

[Robert Relyea]

If someone else updates the patch I'll be able to review it. Be sure to update add the transform in and out of the curve new curve.

Comment 22

[Robert Relyea]

As a hint to how to do the conversion, There's a function in the ECC methods call field_enc and field_dec. Look at ecp_mont.c for how it's used.

Comment 23

[Dave Huseby [:huseby]]

If we landed this curve in NSS, would we be able to expose this in webcrypto?  I'm certain there interest in trying to implement the TextSecure protocol--which uses curve25519--in JS for both FxOS and for web-based messaging apps in desktop.

Comment 24

[Richard Barnes [:rbarnes]]

If we get this plumbed through to the PKCS#11 interface, we would probably be able to expose it in WebCrypto.

Comment 25

[rugk]

Curve25519 and Curve448 are now standardized by the IETF in RFC7748: https://www.rfc-editor.org/rfc/rfc7748.txt
It's also going to be implemented in Chrome (https://groups.google.com/a/chromium.org/forum/#!topic/security-dev/A9RTBPzwe8w ) in Chrome 50 (https://www.chromestatus.com/feature/5682529109540864 ).

Comment 26

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519.patch

basic curve25519 freebl support

Comment 27

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519-test.patch

adhoc curve25519 test

Comment 28

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519.patch

Hi Bob,
could you give feedback on this patch? It is an implementation of curve25519 from rfc 7748. We decided not to take the generic approach. Because of that there are many places where I have to check for this curve (we only supported uncompressed points so far and here we use only the X coordinate without any encoding). That's a bit ugly, but I wouldn't know a better way without changing more of the API, which I don't want to do before cleaning up the rest of the ec code. There are still some todos in there but I'd like to get some first feedback.

Comment 29

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519-test.patch

additional freebl tests and basic pk11 tests.

Comment 30

[Robert Relyea]

Comment on attachment 8738961 [details] [diff] [review]
curve25519.patch

Review of attachment 8738961 [details] [diff] [review]:
-----------------------------------------------------------------

I'm OK with implementing raw  y2 = x3 + bx2 + x, curve support directly, but we should implement it as a generic curve type and it should be named appropriately. There are a lot of if "curve25519" in this patch should should be handled either as an if montladder curve (or whatever is the appropriate generic name), or in the specific montladder implementations.

Most of what you have is on the right track. Just be sure to separate curve25519 specific stuff (which in the ecl directory should be pretty much only in ecl-curve.h), and the base curve implementation that curve25519 (which is more akin to the differences between F2m and FGp curves (even if it's a prime curve, it's a different class). I've pointed out some of the places where this occurs.

bob

(I'm not sure whether the appropriate thing to do is feedback- or feedback+. Really your on the right track, but there are some things that need to be tweaked).

::: lib/freebl/ecl/ecl-curve.h
@@ +57,5 @@
> +};
> +
> +/* Original */
> +static const ECCurveParams ecCurve25519 = {
> +	"Curve25519", ECField_GFp, 255,

ECField_GFp should be ECField_MontLadder

::: lib/freebl/ecl/ecl_mult.c
@@ +24,5 @@
>  
> +	/* want scalar to be less than or equal to group order
> +	 * NOT necessarily when we have curve 25519 */
> +	if (mp_cmp(k, &group->order) > 0 &&
> +		strncmp(group->text, "Curve25519", 10) != 0) {

1) why don't we still want the scalor to be less then equal to the group order. It's still a group and k > group order should always be reduceable to k_prime = k mod group_order and get the same results.

2) if we do need to skip this test, we should skip it for the whole class, not just curve 25519.

@@ +44,5 @@
>  								 group));
>  		}
>  	} else {
> +		if (group->meth->field_enc &&
> +			strncmp(group->text, "Curve25519", 10) != 0) {

If we don't need to do a field_enc for this curve, we simple set the field_enc for the class to zero.

::: lib/freebl/ecl/ecp.h
@@ +31,5 @@
>  /* Validates a point on a GFp curve. */
>  mp_err ec_GFp_validate_point(const mp_int *px, const mp_int *py, const ECGroup *group);
>  
> +mp_err
> +ec_Curve25519_pt_validate(const mp_int *px, const mp_int *py, const ECGroup *group);

Don't call this curve25519, we need to give it a generic name. It's really a category of curves of which curve25519 is just one (like GFp and GF2m). Maybe MontLadder or something like that.

@@ +111,5 @@
> + * NOTE: py and ry are not used!
> + */
> +mp_err
> +ec_Curve25519_pt_mul(const mp_int *n, const mp_int *px, const mp_int *py,
> +					 mp_int *rx, mp_int *ry, const ECGroup *group);

Same as above.

Comment 31

[Eric Rescorla (:ekr)]

Watson PTAL

Comment 32

[Watson Ladd]

The current code is unfortunately dependent on wordsize being 64 bits. There are a number of places where this assumption is made, for instance in allocating the size of temporaries as a fixed number of words, and in iterating over limbs when decoding as little endian.

I feel reasonably strongly that the endianness issue should be dealt with in freebl/ec.c and not in the scalar multiplication algorithm. Furthermore, we already have a with cofactor flag in freebl/ec.c which removes the need to clear the low bits (as it will multiply the key by eight), and we can start the Montgomery ladder differently to avoid setting the top bit, so we might not need to deal with the key modifications in the ecl directory code.

However, the ECC code in the ssl/ directory doesn't call the PKCS ECDH cofactor derive method, but the ECDH derive method. Given that we might want to cheat and set the cofactor flag in freebl/ec.c if we are using a Montgomery curve, to have the same effect as the current code.

Comment 33

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519.patch

This is a minimally intrusive patch for Curve25519 that uses separate multiplication routines.
The actual curve implementations are public domain code from nacl (https://nacl.cr.yp.to/) with some minor fixes. The _64 version is used on all Intel platforms (with a custom uint128 on windows and 32 bit systems). The _32 bit version is used on all other platforms.
Notable changes to existing code:
* SECKEY_SetCurveName in keyhi.h sets the name field in SECKEYECPublicKeyStr.
* ECCurveParamsStr in ecl-exp.h is extended by security, pointSize, and usage that define bit security, size of an encoded point, and functions the curve can be used for respectively.

Comment 34

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519-tls.patch

This patch enables curve25519 ecdh in TLS.

Comment 35

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519-tls.patch

Comment 36

[Watson Ladd]

Ref10 can work on all 32 bit platforms by faking a 32x32->64 bit multiply, with very similar conditions on compiler support to our 64x64->128 bit multiply. I would not be surprised if mobile platforms had issues with the performance of the 32 bit code here. Do we have measurements?

What happens on 32 bit Windows builds? My guess is a failure, as there is no uint64_t which the uint128 fake type depends on, but I haven't run on windows to verify.

We should check appropriate key usage in ECDSA signing, and in ECDH derivation. I couldn't find the spots where the checks happen, leading me to suspect they should be added.

A few places I spotted us cheating with magic enum values. Symbolic constants are probably better.

Otherwise I didn't see much. The ref code is pretty obviously right.

Comment 37

[Martin Thomson [:mt:]]

Back as far as MSVC 2010 the __int64 type exists, so we could use that.  And according to stackoverflow, stdint.h also exists in later versions of MSVC2010.  I don't see it being used in prtypes.h, so we might need specific defines for it.

Comment 38

[Martin Thomson [:mt:]]

Franziskus, would you mind putting these up on rietveld?

Comment 39

[Franziskus Kiefer [:franziskus]]

(In reply to Watson Ladd from comment #36)
> Ref10 can work on all 32 bit platforms by faking a 32x32->64 bit multiply,
> with very similar conditions on compiler support to our 64x64->128 bit
> multiply. I would not be surprised if mobile platforms had issues with the
> performance of the 32 bit code here. Do we have measurements?

Performance of the 32 bit implementation on ARM isn't great, but the same goes for all our curves :( I'm looking into the general problem.

> We should check appropriate key usage in ECDSA signing, and in ECDH
> derivation. I couldn't find the spots where the checks happen, leading me to
> suspect they should be added.

Yeah, I introduced this mainly for testing. Using a curve25519 key for ecdsa will currently crash. I should probably add a check and return an error in this case.

(In reply to Martin Thomson [:mt:] from comment #37)
> Back as far as MSVC 2010 the __int64 type exists, so we could use that.  And
> according to stackoverflow, stdint.h also exists in later versions of
> MSVC2010.  I don't see it being used in prtypes.h, so we might need specific
> defines for it.

Yeah, uint64 is no problem on Windows with MSVC2015. I didn't test another one. I'm not sure what currently the minimum version is we support (since 2015 is the version we require for Firefox and have on TC that might be the one we want).

patches at rietveld (not sure why I can't upload from the office):
https://codereview.appspot.com/302400043
https://codereview.appspot.com/304400043

Comment 40

[Watson Ladd]

The TLS patch looks dirty to me. See for instance https://codereview.appspot.com/304400043/diff/1/lib/ssl/tls13con.c Maybe it isn't, but I don't get why that change is in it.

The ARM perf issue for all our curves is no mystery: On an A-7 a multiply and accumulate instruction 32x32->64 has a 1 cycle issue latency, and a 3 cycle result delay, unless you are issuing a bunch of them with same result. Our built-in assembly routine in mpi_arm.c does a short loop with no unrolling, and doesn't use all the registers it could for latency hiding on loads or unrolling. Counting by hand (which for an in-order core like the A7 is enough) I get 1 word operation per every 10 cycles and 2 load delays. I don't have that much assembly experience/understand how we test our ARM builds to check/fix. It doesn't use NEON, unlike our x86 assembler which uses the SSE2 multipliers. Unrolling would help, very clever rework of the unrolled loop would also help, but I don't have a CPU or cycle accurate simulator to play with to see what is going on/what the capability of the accumulator forwarder is. (Can it forward the high half to the low half is the real test)

I'd have to examine the assembler output to see what is going on with ref, but the inner loop has a complex conditional: in experiments I've done this can lead to much worse code then the basic schoolboy loop. Fully unrolled multiply operations tend to work better, and we have room for Karatsuba, which definitely should bring about a gain. But it's pointless given that ref10 uses a much bigger radix, and we have a formally verified version.

Long story short: use ref10 and the problem is fixed here for curve25519, do some fun assembly coding and we can make inroads on the other ones.

Comment 41

[Martin Thomson [:mt:]]

The tls13con.c change is probably OK, it's just refactoring of the way we import remote key shares.

Comment 42

[Franziskus Kiefer [:franziskus]]

(In reply to Watson Ladd from comment #40)
> The TLS patch looks dirty to me. See for instance
> https://codereview.appspot.com/304400043/diff/1/lib/ssl/tls13con.c Maybe it
> isn't, but I don't get why that change is in it.

Indeed, as Martin said, this is refactoring the name because the function is now used not only by tls 1.3

> Long story short: use ref10 and the problem is fixed here for curve25519, do
> some fun assembly coding and we can make inroads on the other ones.

I'm currently looking into arm performance but would probably prefer landing as is as. Any significant performance improvements here require a significant amount of additional work that would delay landing the entire curve. I filed bug 1293936 for this.

Comment 43

[Wan-Teh Chang]

(In reply to Franziskus Kiefer [:fkiefer or :franziskus] from comment #39)
>
> Yeah, uint64 is no problem on Windows with MSVC2015. I didn't test another
> one. I'm not sure what currently the minimum version is we support (since
> 2015 is the version we require for Firefox and have on TC that might be the
> one we want).

All the compilers we use today support uint64_t, whether they target a 32-bit
or 64-bit CPU. Also, NSPR's PRUint64 typedef is a 64-bit integer type, not
emulated by a struct, under all the compilers we use today.

Comment 44

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519.patch

addressed feedback from mt on rietveld.

Comment 45

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519-tls.patch

Comment 46

[Robert Relyea]

Comment on attachment 8782468 [details] [diff] [review]
curve25519.patch

Review of attachment 8782468 [details] [diff] [review]:
-----------------------------------------------------------------

OK, I have not reviewed the actual curve math yet (curve25519_32.c and curve25519_64.c). But I do have some comments on the rest.

1) there are way to many 'if this is curve25519, do something different' checks. These checks *should* either be relegated to function pointers in the field structure, or at the very least, changed to 'curve category' checks. curve25519 is not the only curve bernstein suggested. His other curves will have the same issue, so we should have a general curve category that curve 25519 falls into.

2) ecl-exp.h has been 'exported' into normal NSS, which is a layering violation. This will cause us issues because we can't reference those headers inside NSS proper. Only util headers can be shared between NSS proper and softoken/freebl. Initially I thought we could move that definition to a util header file (and maybe it makes sense to do so someday), but given the fact we use ECNAME in the current patch exclusively to check if the curve is 25519, then I think instead we should just add a value that gives us curve class rather than curve name. Then all those checks will be fine, and we set the curve class in our new set curve name function. One class is unencoded points and the other is encoded points. That would clean up a ton of those 25519 specific calls in NSS proper.

::: lib/cryptohi/keythi.h
@@ +3,5 @@
>   * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
>  #ifndef _KEYTHI_H_
>  #define _KEYTHI_H_ 1
>  
> +#include "ecl-exp.h"

Ah wait. This is a layer violation ecl-exp.h is part of softoken and not allowed at the NSS layer. We need to move the exported definition to util (where both freebl and NSS can reference it).

It's probably a resonable thing to do. I think we dance around this in SSL, so we should probably bite the bullet.

@@ +126,5 @@
>  struct SECKEYECPublicKeyStr {
>      SECKEYECParams DEREncodedParams;
>      int size;            /* size in bits */
>      SECItem publicValue; /* encoded point */
> +    ECCurveName name;

OK, this is safe, even though SECKEYPublicKey is a public structure (unforunately), and can be built by hand, SECKEYECPublicKeyStr is part
of a union, so as long as we stay under the size of a SECKEYFortezzaPublicKey( 156 bytes on 32 bit platforms, 192 bytes on 64 bit platforms with 32 bit ints, 256 bytes on 64 bit platforms) We should be fine with this change we have the following sizes for SECKEYECPublicKey : (32, 40, 64). If we get close we should add a pointer and store the rest of the data in that pointer, but we have a ways to go before that becomes necessary.

::: lib/cryptohi/seckey.c
@@ +584,5 @@
> +        break;
> +    default:
> +        /* unsupported curve */
> +        return SECFailure;
> +   }

This mapping function could be useful as a generic function in util. I wouldn't hold this patch up for that, though.

@@ +686,2 @@
>                      return pubk;
> +                }

I'm wondering if we need to let applications access the SetCurveName function, or at least a 'fixup' function.

 Not essential for this patch.

::: lib/freebl/Makefile
@@ +515,5 @@
> +        endif
> +        ifeq (,$(filter 0 1 2 3 4,$(word 1,$(GCC_VERSION))))
> +            HAVE_INT128_SUPPORT = 1
> +            DEFINES += -DHAVE_INT128_SUPPORT
> +        endif

This looks like a non-ecc specific fix. I'm fine with it, but I wonder if it should not be hidden in the ECC patch.

::: lib/freebl/blapit.h
@@ +386,5 @@
>      int           cofactor;
>      SECItem       DEREncoding;
>      ECCurveName   name;
>      SECItem       curveOID;
> +    int           pointSize;

OK ECParamsStr is "private", so the pointSize addition is fine.

::: lib/freebl/ec.c
@@ +260,5 @@
> +    /* Curve25519 uses curve specific code for point multiplication */
> +    if (ecParams->name == ECCurve25519) {
> +        rv = ec_Curve25519_pt_mul(&key->publicValue, &key->privateValue, NULL);
> +        goto done;
> +    }

Sigh, We should be using the field type pointers. It's OK for Curve25519 to have a different pt_mul, but the function should be access through an indirect pointer like the rest of the ECC code. Every form of curve has different implementations for the different portions. We don't want a lot of 'If this curve do this and that curve do that' explicit in the code. If we need to override points_mul completely, then we should add a new field poitner for points_mul.

There will be more bernstein curves and we'll want to reuse the 25519 code for them.

@@ +430,5 @@
> +
> +    /* Curve25519 uses curve specific code for point validation */
> +     if (ecParams->name == ECCurve25519) {
> +        return ec_Curve25519_pt_validate(publicValue);
> +     }

Again, this should be field specific.

@@ +539,5 @@
> +        memset(derivedSecret, 0, sizeof(*derivedSecret));
> +        SECITEM_AllocItem(NULL, derivedSecret, 32);
> +        return ec_Curve25519_pt_mul(derivedSecret, privateValue, publicValue);
> +     }
> +

So to test things, this seems fine, but again, we should handle this with field pointers. right now we are skipping ec_point_at_infinity check (which may be in your ec_curve25519_pt_mul() function). Instead we should make sure ec_point_at_inifity() is modified to handle all curves properly.

The only ECCurve25519 specific code should be the encoding below, and that shouldn't trigger on ECCurve25519, but on it's field value (since all berntein curves should have the same encoding).

::: lib/freebl/ecdecode.c
@@ +564,5 @@
>  	break;
>  
> +    case SEC_OID_CURVE25519:
> +       /* Populate params for Curve25519 */
> +       CHECK_SEC_OK( gf_populate_params(ECCurve25519, ec_field_GFp, params) );

ec_field here should be a curve25519 specific field (even if it mostly uses ec_field_GFp).

::: lib/freebl/ecl/curve25519.h
@@ +1,5 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +#include <stdint.h>

This whole header is really good, but not curve25519 specific. Other curves could potentially use these macros for more efficient implementations (like NIST p256 and friends).

::: lib/freebl/ecl/ecl.h
@@ +55,5 @@
>  mp_err ECPoint_validate(const ECGroup *group, const mp_int *px, const 
>  					mp_int *py);
>  
> +SECStatus ec_Curve25519_pt_mul(SECItem *X, SECItem *k, SECItem *P);
> +SECStatus ec_Curve25519_pt_validate(const SECItem *px);

These should be in the Curve25519 field structure.

::: lib/freebl/ecl/ecp_25519.c
@@ +113,5 @@
> +        if (P->len != 32) {
> +            return SECFailure;
> +        }
> +        px = P->data;
> +    }

ok, we aren't checking for point at infinity, so we are vulernerable to MITM attacks on derive (unless we are depending on such a check elsewhere).

::: lib/freebl/ecl/uint128.c
@@ +1,5 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +#include "curve25519.h"

Ah, cureve25519.h should probably be called uin128.h

::: lib/pk11wrap/pk11akey.c
@@ +407,5 @@
> +     * it is sufficient to check keyLen. There is no other curve of this size.
> +     */
> +    if (ecPoint->ulValueLen == (unsigned int)keyLen && keyLen == 32) {
> +        return pk11_Attr2SecItem(arena, ecPoint, publicKeyValue);
> +    }

Hmm, not great, what happens for the next Bernstein curve?

::: lib/pk11wrap/pk11skey.c
@@ +1992,5 @@
> +    SECItem *publicValue = &pubKey->u.ec.publicValue;
> +
> +    if (pubKey->u.ec.name == ECCurve25519) {
> +        return publicValue->len;
> +    }

Sigh, I don't see a way around this for now either.

Comment 47

[Franziskus Kiefer [:franziskus]]

(In reply to Robert Relyea from comment #46)
> Comment on attachment 8782468 [details] [diff] [review]
> curve25519.patch
> 
> Review of attachment 8782468 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> OK, I have not reviewed the actual curve math yet (curve25519_32.c and
> curve25519_64.c). But I do have some comments on the rest.

I think I found a way to address your main comments. See inline below.

> ::: lib/cryptohi/keythi.h
> @@ +3,5 @@
> >   * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> >  #ifndef _KEYTHI_H_
> >  #define _KEYTHI_H_ 1
> >  
> > +#include "ecl-exp.h"
> 
> Ah wait. This is a layer violation ecl-exp.h is part of softoken and not
> allowed at the NSS layer. We need to move the exported definition to util
> (where both freebl and NSS can reference it).

Ah, I expected something like that but wasn't sure... I pulled out the definition. Not sure if there's a naming convention for things in lib/util.

> It's probably a resonable thing to do. I think we dance around this in SSL,
> so we should probably bite the bullet.
> @@ +126,5 @@
> >  struct SECKEYECPublicKeyStr {
> >      SECKEYECParams DEREncodedParams;
> >      int size;            /* size in bits */
> >      SECItem publicValue; /* encoded point */
> > +    ECCurveName name;
> ::: lib/pk11wrap/pk11skey.c
> @@ +1992,5 @@
> > +    SECItem *publicValue = &pubKey->u.ec.publicValue;
> > +
> > +    if (pubKey->u.ec.name == ECCurve25519) {
> > +        return publicValue->len;
> > +    }
> 
> Sigh, I don't see a way around this for now either.

I renamed this encoding and put that in util/freebl.h. That makes pk11_ECPubKeySize also work for other curves that don't use uncompressed points.

> ::: lib/cryptohi/seckey.c
> @@ +584,5 @@
> > +        break;
> > +    default:
> > +        /* unsupported curve */
> > +        return SECFailure;
> > +   }
> 
> This mapping function could be useful as a generic function in util. I
> wouldn't hold this patch up for that, though.
> I'm wondering if we need to let applications access the SetCurveName
> function, or at least a 'fixup' function.

Pulled this out into util. By that it's public.

> ::: lib/freebl/ec.c
> @@ +260,5 @@
> > +    /* Curve25519 uses curve specific code for point multiplication */
> > +    if (ecParams->name == ECCurve25519) {
> > +        rv = ec_Curve25519_pt_mul(&key->publicValue, &key->privateValue, NULL);
> > +        goto done;
> > +    }
> 
> Sigh, We should be using the field type pointers. It's OK for Curve25519 to
> have a different pt_mul, but the function should be access through an
> indirect pointer like the rest of the ECC code. Every form of curve has
> different implementations for the different portions. We don't want a lot of
> 'If this curve do this and that curve do that' explicit in the code. If we
> need to override points_mul completely, then we should add a new field
> poitner for points_mul.

I added a lightweight ECMethod struct to handle different curves when sidestepping ecl.

> There will be more bernstein curves and we'll want to reuse the 25519 code
> for them.

No we won't be reusing code for other curves. The curve arithmetic is specific to 25519. This goes back to my arguments regarding your first point (see e-mail).

> @@ +539,5 @@
> > +        memset(derivedSecret, 0, sizeof(*derivedSecret));
> > +        SECITEM_AllocItem(NULL, derivedSecret, 32);
> > +        return ec_Curve25519_pt_mul(derivedSecret, privateValue, publicValue);
> > +     }
> > +
> 
> So to test things, this seems fine, but again, we should handle this with
> field pointers. right now we are skipping ec_point_at_infinity check (which
> may be in your ec_curve25519_pt_mul() function). Instead we should make sure
> ec_point_at_inifity() is modified to handle all curves properly.

I added a point validation call to the multiplication.

> The only ECCurve25519 specific code should be the encoding below, and that
> shouldn't trigger on ECCurve25519, but on it's field value (since all
> berntein curves should have the same encoding).
> 
> ::: lib/freebl/ecdecode.c
> @@ +564,5 @@
> >  	break;
> >  
> > +    case SEC_OID_CURVE25519:
> > +       /* Populate params for Curve25519 */
> > +       CHECK_SEC_OK( gf_populate_params(ECCurve25519, ec_field_GFp, params) );
> 
> ec_field here should be a curve25519 specific field (even if it mostly uses
> ec_field_GFp).

I added a ec_field_plain for the new way of handling things, i.e. side-stepping the code ec.c and use function pointers for curve specific operations. ec_field_plain is used in two different ways at the moment. 1) plain point encoding, i.e. not uncompressed and 2) side-stepping the ecl implementation.
The second usage allows us to avoid checks for 25519 but this type of curve and should go away with refactoring the ec code, i.e. all curves use ECMethod.

> ::: lib/freebl/ecl/curve25519.h
> @@ +1,5 @@
> > +/* This Source Code Form is subject to the terms of the Mozilla Public
> > + * License, v. 2.0. If a copy of the MPL was not distributed with this
> > + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> > +
> > +#include <stdint.h>
> 
> This whole header is really good, but not curve25519 specific. Other curves
> could potentially use these macros for more efficient implementations (like
> NIST p256 and friends).

Agreed, renamed it to uint128.h

> ::: lib/freebl/ecl/ecp_25519.c
> @@ +113,5 @@
> > +        if (P->len != 32) {
> > +            return SECFailure;
> > +        }
> > +        px = P->data;
> > +    }
> 
> ok, we aren't checking for point at infinity, so we are vulernerable to MITM
> attacks on derive (unless we are depending on such a check elsewhere).

Indeed, I added point validation (which checks for all bad points).

> ::: lib/pk11wrap/pk11akey.c
> @@ +407,5 @@
> > +     * it is sufficient to check keyLen. There is no other curve of this size.
> > +     */
> > +    if (ecPoint->ulValueLen == (unsigned int)keyLen && keyLen == 32) {
> > +        return pk11_Attr2SecItem(arena, ecPoint, publicKeyValue);
> > +    }
> 
> Hmm, not great, what happens for the next Bernstein curve?

Yeah, that's not ideal. The problem is that we don't have a lot of information here. I extended pk11_get_EC_PointLenInBytes to return an additional boolean on whether the code has encoding or not.

> > +        ifeq (,$(filter 0 1 2 3 4,$(word 1,$(GCC_VERSION))))
> > +            HAVE_INT128_SUPPORT = 1
> > +            DEFINES += -DHAVE_INT128_SUPPORT
> > +        endif
> 
> This looks like a non-ecc specific fix. I'm fine with it, but I wonder if it should not be hidden in the ECC patch.

Well, it fixes HAVE_INT128_SUPPORT, i.e. sets it only when USE_64 is set. So it's not completely unrelated. But I'm happy to move it out if you prefer.

Comment 48

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519.patch

Comment 49

[Robert Relyea]

Comment on attachment 8783480 [details] [diff] [review]
curve25519.patch

Review of attachment 8783480 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks for the changes! This is much better. The only issue that prevents an r+ is moving SECKEY_SetCurveName back to NSS (meaning moving the symbol, seckey.c and secky.h). As is NSS won't build in our modular version (Hmm maybe we need a try build test for that).

There are other things we can talk about with the curve code, but nothing that I would hold up getting this in. on.

bob
r+ for everythithing except nssutil.def seckey.c and seckey.h

bob

::: lib/freebl/ec.c
@@ +236,5 @@
>      key->ecParams.fieldID.size = ecParams->fieldID.size;
>      key->ecParams.fieldID.type = ecParams->fieldID.type;
> +    key->ecParams.pointSize = ecParams->pointSize;
> +    if (ecParams->fieldID.type == ec_field_GFp ||
> +        ecParams->fieldID.type == ec_field_plain) {

I like this check better. Thanks!

::: lib/pk11wrap/pk11akey.c
@@ +355,5 @@
>      case SEC_OID_SECG_EC_SECT571R1:
>  	return 145; /*curve len in bytes = 72 bytes */
> +    case SEC_OID_CURVE25519:
> +        *plain = PR_TRUE;
> +	return 32; /* curve len in bytes = 32 bytes (only X) */

This is a good change. Better than peppering CURVE25519 throughout the code.

::: lib/util/freebl.h
@@ +8,5 @@
> +/* point encoding type */
> +typedef enum {
> +    ECPoint_Uncompressed,
> +    ECPoint_XOnly
> +} ECPointEncoding;

It'd name it eccutil.h Otherwise, this is the right place to softoken and nss can share the definition.

::: lib/util/nssutil.def
@@ +291,5 @@
>  ;+       *;
>  ;+};
> +;+NSSUTIL_3.27 {       # NSS Utilities 3.27 release
> +;+    global:
> +SECKEY_SetCurveName;

sigh. I see SECKEY_ in util and I realize somehting is probably wrong. I is indeed. the SECKEY structure is an NSS level structure (softoken has a different structure). Neither structure is accessible to nssutil, which needs to be able to build without any other NSS headers (it's the lowest level).

The fix is easy, just move

::: lib/util/seckey.c
@@ +1,3 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

Looking at thie file, there's no reason it can't be in it's proper spot in NSS. SECKEYPublicKeys are only a that level anyway. You don't include any freebl headers (either in here or in seckey.h).

Also, it's not a good idea to include two files with the same name in the NSS tree (it makes debugging and and file identification an issue.

The contents of these two files are fine.

::: lib/util/seckey.h
@@ +6,5 @@
> +#define _FREEBLI_H_
> +
> +#include "seccomon.h"
> +#include "plarena.h"
> +#include "keythi.h"

Major layer violation... keythi is in NSS proper, and can't. If this moved so nss proper, there shouldn't be an issue. (same with seckey.c)

Comment 50

[Franziskus Kiefer [:franziskus]]

Attachment: curve25519.patch

Comment 51

[Robert Relyea]

Comment on attachment 8787639 [details] [diff] [review]
curve25519.patch

Review of attachment 8787639 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks for addressing my issues. whole hearted r+

::: lib/cryptohi/seckey.c
@@ +1951,5 @@
> + * If the encoding is not set, determining the key size of EC public keys will
> + * fail.
> + */
> +SECStatus
> +seckey_SetPointEncoding(PLArenaPool *arena, SECKEYPublicKey *pubKey)

good.

::: lib/util/eccutil.h
@@ +1,3 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

Thanks!

Comment 52

[Franziskus Kiefer [:franziskus]]

curve25519 implementation landed as https://hg.mozilla.org/projects/nss/rev/047ab976840a

Comment 53

[Johann Oskarsson]

I got this assertion error when I tried to create a key with this curve.  Is that not supposed to work?

  Assertion failure: pubKey->u.ec.ecParams.name != ECCurve25519, at pkcs11.c:1813

when trying this command

  certutil -G -d . -k ec -q curve25519 -f passwd.file

Comment 54

[Martin Thomson [:mt:]]

I tried the same with sect571r1 and some of the non-standard curves that are enabled on Fedora and that didn't work either (though it didn't assert, it just failed with SEC_ERROR_INVALID_KEY).  Maybe this is intentional.  It probably shouldn't crash though.

Comment 55

[Hubert Kario]

(In reply to Johann Oskarsson from comment #53)
> I got this assertion error when I tried to create a key with this curve.  Is
> that not supposed to work?
> 
>   Assertion failure: pubKey->u.ec.ecParams.name != ECCurve25519, at
> pkcs11.c:1813
> 
> when trying this command
> 
>   certutil -G -d . -k ec -q curve25519 -f passwd.file

I'm confused.

It's my understanding Curve25519 is the generic name for the Bernstein curve. But that curve can be transformed for use either in signatures, where is is named Ed25519 and for key agreement (ECDHE), where it is named X25519. The important thing is that Ed25519 is *not* binary compatible with X25519.

As far as I can tell from the title of this bug, it is asking for X25519, in other words https://tools.ietf.org/html/draft-ietf-tls-curve25519-01

It is *not* asking for https://tools.ietf.org/html/draft-irtf-cfrg-eddsa-08 or https://tools.ietf.org/html/draft-ietf-curdle-pkix-01

So, am I missing something, and certutil can be used for manipulation of ECDHE key pairs, or the addition of the curve25519 (especially *as* "curve25519") to certutil is a bit premature?

Note that for supported_groups TLS extension X25519 *is* different from Ed25519.

Comment 56

[Franziskus Kiefer [:franziskus]]

yeah, it shouldn't crash for 25519. For sect571r1 I think this is correct as softoken doesn't support that curve. The error message could me more descriptive though.
Unfortunately pk11 isn't very intelligent, so we'll have to work around it to make this work where it should. I filed bug 1303986 to handle this specific issue.

This bug is implementing x25519 (not sure yet if we're doing ed25519). But this is independent of the bug mentioned in comment 53 that's being resolved in bug 1303986.

Comment 57

[Hubert Kario]

then why addition of curve25519 to certtool?

I also wonder if the naming shouldn't be changed to X25519 to indicate that it's the ECDHE curve, not the signing curve. I don't think we can expect NSS to not implement Ed25519, it will get confusing then...

That being said, I don't see X25519 or X448 being advertised in elliptic_curves extension of client hello when I compiled the rev 4553276f3873. But by quick look at the latest merged patch, that seems expected.

Comment 58

[Franziskus Kiefer [:franziskus]]

> I don't see X25519 or X448 being advertised in elliptic_curves extension of client hello when I compiled the rev 4553276f3873. But by quick look at the latest merged patch, that seems expected.

No it's not. The patch that landed only implements the curve, not the integration into TLS. That's landing later.

Comment 59

[Franziskus Kiefer [:franziskus]]

landed tls integration at https://hg.mozilla.org/projects/nss/rev/18e77125978c
with review at https://nss-dev.phacility.com/D7

Comment 60

[Martin Thomson [:mt:]]

Comment on attachment 8782469 [details] [diff] [review]
curve25519-tls.patch

Other patch landed.

Comment 61

[Hubert Kario]

I'm not able to negotiate X25519 using OpenSSL 1.1.0 as the client.

If the x25519 is the only curve advertised, selfserv chooses cipher with DHE-RSA key exchange.

That is using master branch 12679:0b302b719dff

Comment 62

[Franziskus Kiefer [:franziskus]]

(In reply to Hubert Kario from comment #61)
> I'm not able to negotiate X25519 using OpenSSL 1.1.0 as the client.
> 
> If the x25519 is the only curve advertised, selfserv chooses cipher with
> DHE-RSA key exchange.
> 
> That is using master branch 12679:0b302b719dff

You have explicitly enable at the moment (using SSL_NamedGroupConfig). This shouldn't be necessary with the 3.28 release, but is for now. Firefox nightly happily uses x25519 already for a while now.

Comment 63

[Hubert Kario]

I asked as I didn't see an option in selfserv or tstclnt to enable it.

Making it the default for 3.28 should be sufficient.

Comment 64

[Martin Thomson [:mt:]]

This is a timely reminder that I should probably add flags to those tools, if only to demonstrate how to use the API.

Comment 65

[Marcin Cieślak (:saper)]

Is Ed25519 supported? If not, then https://bugzilla.mozilla.org/show_bug.cgi?id=1644232 is an extension request (and certutil should probably be more conservative about the choices offered)