ECC constant time scalar multiplication support

[bbbrumley]

First step in overhauling the EC module. Follow ups:

1. Port as much as we can from OpenSSL evptest.c for more thorough regression testing
2. Strip out binary curve support, deprecating ec2_*.c
3. Implement dedicated ec_GFp_simple_mul_double_nonct, deprecating ec_mult.c
4. Bug attack defenses
5. Updated exception-free projective ECC formulae
6. Switch ECDSA to standards-compliant deterministic ECDSA RFC6979
7. Deprecate ecdsatest.c with evptests.txt KATs
8. Deprecate ecdhtest.c with evptests.txt KATs
9. Add API for blinded inversions modulo the group order; make ECDSA use it
10. Remove ECDSA nonce padding
11. Add X25519 support, following my team's libsuola model
12. Add Ed25519 support similarly

So it's a long road, but this is a start :)

[botovq]

Thanks a lot for the diff. Apologies for letting you wait for so long. I'm trying to push this forward and will hopefully be able to merge this soon into the main OpenBSD tree.

[bbbrumley]

Great that it might get merged!

This PR fixed one defect. Do you want me to add the commit here?

[botovq]

On Mon, Jul 09, 2018 at 11:04:26PM -0700, Billy Brumley wrote:

Great that it might get merged!

This PR fixed one defect. Do you want me to add the commit here?

Thanks, that won't be necessary, I was painless to merge these changes into my tree.

[botovq]

On Mon, Jul 09, 2018 at 11:04:26PM -0700, Billy Brumley wrote:

Great that it might get merged!

I merged a slightly tweaked version (mostly whitespace) to the OpenBSD base tree.

Thanks again!

[botovq]

On Mon, Jul 09, 2018 at 11:04:26PM -0700, Billy Brumley wrote:

Great that it might get merged!

Unfortunately, we had to back it out again as it broke ssh and other things on sparc64.

Jonathan Gray's commit message contains some more details on what broke:

back out ecc constant time changes

after the constant time commits various regress tests started failing
on sparc64 ssh t9, libcrypto ec ecdh ecdsa and trying to ssh out
resulted in 'invalid elliptic curve value'

ok tb@

https://marc.info/?l=openbsd-cvs&m=153163313931413&w=2

[bbbrumley]

Hmm. So sounds like it's sparc64 specific, and not ssh specific? If the build regression tests are failing there ...

[botovq]

On Sat, Jul 14, 2018 at 11:39:51PM -0700, Billy Brumley wrote:

Hmm. So sounds like it's sparc64 specific, and not ssh specific? If the build regression tests are failing there ...

Yes, definitely. The patch works fine on the architectures I tested it on (amd64 and macppc) including ssh and the libcrypto regression tests.

Below is the log that jsg@ sent.

From the error in the ecdh test:

Testing key generation with NIST Prime-Curve P-192464273321432:error:10FFF042:elliptic curve routines:CRYPTO_internal:called a function you should not call:/usr/src/lib/libcrypto/ec/ec_lib.c:1067: *** Error 1 in target 'run-regress-ecdhtest', line 32 of

it looks as if the changes to EC_POINT_mul() are partly responsible.

----- Forwarded message from Jonathan Gray -----

Date: Sun, 15 Jul 2018 13:44:44 +1000 From: Jonathan Gray Subject: ssh fails with 'invalid elliptic curve value' on sparc64

Did a build on sparc64 and now I can't seem to ssh to anything.

ssh_dispatch_run_fatal: Connection to 199.185.137.3 port 22: invalid elliptic curve value

ssh_dispatch_run_fatal: Connection to 192.168.1.43 port 22: invalid elliptic curve value

otis$ pwd /usr/src/regress/usr.bin/ssh otis$ make t9 ssh-keygen -q -t ecdsa -N '' -f t9.out sshkey_generate failed *** Error 255 in /usr/src/regress/usr.bin/ssh (Makefile:162 't9.out')

infinity tests ... ok

testing internal curves: ......... EC_GROUP_check() failed with curve secp224r1 . EC_GROUP_check() failed with curve secp384r1

EC_GROUP_check() failed with curve secp521r1

EC_GROUP_check() failed with curve prime192v1

EC_GROUP_check() failed with curve prime192v2

EC_GROUP_check() failed with curve prime192v3 ... EC_GROUP_check() failed with curve prime256v1 ............................................ EC_GROUP_check() failed with curve wap-wsg-idm-ecid-wtls12 ......................... failed

/usr/src/regress/lib/libcrypto/ec/ectest.c:1225: ABORT *** Error 1 in target 'run-regress-ectest', line 32 of

===> ecdh cc -O2 -pipe -DLIBRESSL_INTERNAL -Werror -Wall -Wpointer-arith -Wuninitialized -Wstrict-prototypes -Wmissing-prototypes -Wunused -Wsign-compare -Wshadow -Wdeclaration-after-statement -MD -MP -c /usr/src/regress/lib/libcrypto/ecdh/ecdhtest.c cc -o ecdhtest ecdhtest.o -lcrypto ./ecdhtest Testing key generation with NIST Prime-Curve P-192464273321432:error:10FFF042:elliptic curve routines:CRYPTO_internal:called a function you should not call:/usr/src/lib/libcrypto/ec/ec_lib.c:1067: *** Error 1 in target 'run-regress-ecdhtest', line 32 of

===> ecdsa cc -O2 -pipe -DLIBRESSL_INTERNAL -Werror -Wall -Wpointer-arith -Wuninitialized -Wstrict-prototypes -Wmissing-prototypes -Wunused -Wsign-compare -Wshadow -Wdeclaration-after-statement -MD -MP -c /usr/src/regress/lib/libcrypto/ecdsa/ecdsatest.c cc -o ecdsatest ecdsatest.o -lcrypto ./ecdsatest

testing ECDSA_sign() and ECDSA_verify() with some internal curves: secp160k1: ........ ok secp160r1: ........ ok secp160r2: ........ ok secp192k1: ........ ok secp224k1: ........ ok secp224r1: failed

ECDSA test failed 253289768216:error:10FFF042:elliptic curve routines:CRYPTO_internal:called a function you should not call:/usr/src/lib/libcrypto/ec/ec_lib.c:1067: *** Error 1 in target 'run-regress-ecdsatest', line 32 of

otis$ ssh -vv largo OpenSSH_7.8, LibreSSL 2.8.0 debug1: Reading configuration data /etc/ssh/ssh_config debug2: resolving "largo" port 22 debug2: ssh_connect_direct: needpriv 0 debug1: Connecting to largo [192.168.1.43] port 22. debug1: Connection established. debug1: identity file /usr/users/jsg/.ssh/id_rsa type -1 debug1: identity file /usr/users/jsg/.ssh/id_rsa-cert type -1 debug1: identity file /usr/users/jsg/.ssh/id_dsa type -1 debug1: identity file /usr/users/jsg/.ssh/id_dsa-cert type -1 debug1: identity file /usr/users/jsg/.ssh/id_ecdsa type -1 debug1: identity file /usr/users/jsg/.ssh/id_ecdsa-cert type -1 debug1: identity file /usr/users/jsg/.ssh/id_ed25519 type -1 debug1: identity file /usr/users/jsg/.ssh/id_ed25519-cert type -1 debug1: identity file /usr/users/jsg/.ssh/id_xmss type -1 debug1: identity file /usr/users/jsg/.ssh/id_xmss-cert type -1 debug1: Local version string SSH-2.0-OpenSSH_7.8 debug1: Remote protocol version 2.0, remote software version OpenSSH_7.7 debug1: match: OpenSSH_7.7 pat OpenSSH_7.0,OpenSSH_7.1,OpenSSH_7.2,OpenSSH_7.3,OpenSSH_7.4,OpenSSH_7.5,OpenSSH_7.6,OpenSSH_7.7 compat 0x04000002 debug2: fd 3 setting O_NONBLOCK debug1: Authenticating to largo:22 as 'jsg' debug1: /usr/users/jsg/.ssh/known_hosts:5: parse error in hostkeys file debug1: SSH2_MSG_KEXINIT sent debug1: SSH2_MSG_KEXINIT received debug2: local client KEXINIT proposal debug2: KEX algorithms: curve25519-sha256,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha256,diffie-hellman-group14-sha1,ext-info-c debug2: host key algorithms: ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ssh-ed25519-cert-v01@openssh.com,rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.com,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa debug2: ciphers ctos: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com debug2: ciphers stoc: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com debug2: MACs ctos: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1 debug2: MACs stoc: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1 debug2: compression ctos: none,zlib@openssh.com,zlib debug2: compression stoc: none,zlib@openssh.com,zlib debug2: languages ctos: debug2: languages stoc: debug2: first_kex_follows 0 debug2: reserved 0 debug2: peer server KEXINIT proposal debug2: KEX algorithms: curve25519-sha256,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group14-sha256,diffie-hellman-group14-sha1 debug2: host key algorithms: ssh-rsa,rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256,ssh-ed25519 debug2: ciphers ctos: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com debug2: ciphers stoc: chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com debug2: MACs ctos: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1 debug2: MACs stoc: umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-sha1 debug2: compression ctos: none,zlib@openssh.com debug2: compression stoc: none,zlib@openssh.com debug2: languages ctos: debug2: languages stoc: debug2: first_kex_follows 0 debug2: reserved 0 debug1: kex: algorithm: curve25519-sha256 debug1: kex: host key algorithm: ecdsa-sha2-nistp256 debug1: kex: server->client cipher: chacha20-poly1305@openssh.com MAC: compression: none debug1: kex: client->server cipher: chacha20-poly1305@openssh.com MAC: compression: none debug1: expecting SSH2_MSG_KEX_ECDH_REPLY ssh_dispatch_run_fatal: Connection to 192.168.1.43 port 22: invalid elliptic curve value

----- End forwarded message -----

[bbbrumley]

    if (group->meth->mul_generator_ct == NULL ||
        group->meth->mul_single_ct == NULL ||
        group->meth->mul_double_nonct == NULL) {
        ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
        return 0;
    }

Should be an easy fix? One of the EC_METHOD isn't declaring the pointers.

[bbbrumley]

Tagging @romen -- looks like he tracked it down.

[romen]

Here I am after running some proper testing!

I believe the problem on sparc64 was that ASM is not enabled (or at least OPENSSL_BN_ASM_MONT doesn't get defined): in such case the default EC_METHOD for prime curves (determined here) is EC_GFp_nist_method (defined in ec/ec_nist.c).

Unfortunately this file slipped through the previous patch, so it was using the new default EC_POINT_mul path even if the EC_METHOD struct does not set specific .mul_{generator,single,double}_ct pointers, thus raising ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); at the beginning of EC_POINT_mul.

I don't have access to a sparc64 machine to do regression tests on that platform, but the following patch at least fixes the described problem for the X86-64 build with ./configure --disable-asm / cmake -DENABLE_ASM=OFF.

diff --git a/src/lib/libcrypto/ec/ecp_nist.c b/src/lib/libcrypto/ec/ecp_nist.c
index 24cba64d2..17ed90c6b 100644
--- a/src/lib/libcrypto/ec/ecp_nist.c
+++ b/src/lib/libcrypto/ec/ecp_nist.c
@@ -103,6 +103,9 @@ EC_GFp_nist_method(void)
        .point_cmp = ec_GFp_simple_cmp,
        .make_affine = ec_GFp_simple_make_affine,
        .points_make_affine = ec_GFp_simple_points_make_affine,
+       .mul_generator_ct = ec_GFp_simple_mul_generator_ct,
+       .mul_single_ct = ec_GFp_simple_mul_single_ct,
+       .mul_double_nonct = ec_GFp_simple_mul_double_nonct,
        .field_mul = ec_GFp_nist_field_mul,
        .field_sqr = ec_GFp_nist_field_sqr
    };

@botovq I also noticed that something else was going on in the full error log you forwarded above:

===> ecdsa cc -O2 -pipe -DLIBRESSL_INTERNAL -Werror -Wall -Wpointer-arith -Wuninitialized -Wstrict-prototypes -Wmissing-prototypes -Wunused -Wsign-compare -Wshadow -Wdeclaration-after-statement -MD -MP -c /usr/src/regress/lib/libcrypto/ecdsa/ecdsatest.c cc -o ecdsatest ecdsatest.o -lcrypto ./ecdsatest

testing ECDSA_sign() and ECDSA_verify() with some internal curves: secp160k1: ........ ok secp160r1: ........ ok secp160r2: ........ ok secp192k1: ........ ok secp224k1: ........ ok secp224r1: failed

ECDSA test failed 253289768216:error:10FFF042:elliptic curve routines:CRYPTO_internal:called a function you should not > call:/usr/src/lib/libcrypto/ec/ec_lib.c:1067: *** Error 1 in target 'run-regress-ecdsatest', line 32 of

Before that output the ectest cleary shows failures on all prime curves (as I would expect) but ECDSA seems to surprisingly fail only on secp224r1.

[romen]

On further inspection, I now see that the ecdsa tests passing were all about prime curves over fields defined by non-NIST primes for which EC_GROUP_new_curve_GFp sets the method to EC_GFp_mont_method !

So I'd say that what at first seemed odd actually further confirms that the reported issue was indeed caused by ecp_nist.c and should be fixed by the above patch!

[botovq]

@romen: Thanks for tracking this down so quickly. I was a bit worried by what appeared to be entirely separate issues. Your explanation sounds to be correct.

I've sent the revised diff out for testing on tech@: https://marc.info/?l=openbsd-tech&m=153167917007750&w=2 and will re-commit once we got some positive feedback.

[botovq]

Recommitted to the OpenBSD tree after positive test on sparc64 (thanks @romen)