[crypto/ec] constant time P-384 EC_METHOD by bbbrumley · Pull Request #12201 · openssl/openssl

bbbrumley · 2020-06-19T07:25:57Z

We've been experimenting with tooling (edit: now public, called ECCKiila with preprint) that generates curve-specific EC_METHODs. The idea is you get a whole stack similar to ecp_nistp224.c ecp_nistp256.c ecp_nistp521.c. Features include

100% computer generated, including the OpenSSL rigging
Most of the GF layer comes from fiat, so you get some formal verification guarantees from there (which is where the guarantees end)
CT scalar multiplication by base point (keygen, sign)
CT scalar multiplication by arbitrary point (derive)
static
variable time scalar multiplication for two points (verify)
Both 64-bit (highly tested) and 32-bit support (not so much)
No alignment assumptions (not explicitly tested)
No endianness assumptions (coded that way, yet untested on BE)

~~So this is just a WiP PR to solicit feedback. Also, merge #12096 then I'll rebase and we should see CI failures ;)~~ out of WiP with e84eaffc4908f6a926ec8fec264fa14ee3bc1ccd

It is really push-button stuff so whatever curve you think is important for the lib, it takes like 2min.

P-384 isn't the best curve to showcase the value of the tool because of size and limited GF optimization options. But nevertheless, maybe it's important for the lib because it's currently a gap in FIPS coverage.

Tagging @mattcaswell @romen

Before

$ apps/openssl speed ecdsap384
Doing 384 bits sign ecdsa's for 10s: 9611 384 bits ECDSA signs in 10.00s 
Doing 384 bits verify ecdsa's for 10s: 11739 384 bits ECDSA verify in 10.00s
version: 3.0.0-alpha4-dev
built on: built on: Fri Jun 19 06:56:42 2020 UTC
options:bn(64,64) rc4(16x,int) des(int) aes(partial) idea(int) blowfish(ptr) 
compiler: ccache clang-10 -fPIC -pthread -m64 -Wa,--noexecstack -Qunused-arguments -Wall -O3 -DOPENSSL_USE_NODELETE -DL_ENDIAN -DOPENSSL_PIC -DOPENSSL_BUILDING_OPENSSL -DNDEBUG
CPUINFO: OPENSSL_ia32cap=0x7ffef3ffffebffff:0x18d39efffb
                              sign    verify    sign/s verify/s
 384 bits ecdsa (nistp384)   0.0010s   0.0009s    961.1   1173.9
$ apps/openssl speed ecdhp384
Doing 384 bits  ecdh's for 10s: 10057 384-bits ECDH ops in 10.00s
version: 3.0.0-alpha4-dev
built on: built on: Fri Jun 19 06:56:42 2020 UTC
options:bn(64,64) rc4(16x,int) des(int) aes(partial) idea(int) blowfish(ptr) 
compiler: ccache clang-10 -fPIC -pthread -m64 -Wa,--noexecstack -Qunused-arguments -Wall -O3 -DOPENSSL_USE_NODELETE -DL_ENDIAN -DOPENSSL_PIC -DOPENSSL_BUILDING_OPENSSL -DNDEBUG
CPUINFO: OPENSSL_ia32cap=0x7ffef3ffffebffff:0x18d39efffb
                              op      op/s
 384 bits ecdh (nistp384)   0.0010s   1005.7

After

$ apps/openssl speed ecdsap384
Doing 384 bits sign ecdsa's for 10s: 41855 384 bits ECDSA signs in 10.00s 
Doing 384 bits verify ecdsa's for 10s: 11740 384 bits ECDSA verify in 10.00s
version: 3.0.0-alpha4-dev
built on: built on: Tue Jun 30 05:10:45 2020 UTC
options:bn(64,64) rc4(16x,int) des(int) aes(partial) idea(int) blowfish(ptr) 
compiler: ccache clang -fPIC -pthread -m64 -Wa,--noexecstack -Qunused-arguments -Wall -O3 -DOPENSSL_USE_NODELETE -DL_ENDIAN -DOPENSSL_PIC -DOPENSSL_BUILDING_OPENSSL -DNDEBUG
CPUINFO: OPENSSL_ia32cap=0x7ffef3ffffebffff:0x18d39efffb
                              sign    verify    sign/s verify/s
 384 bits ecdsa (nistp384)   0.0002s   0.0009s   4185.5   1174.0

$ apps/openssl speed ecdhp384
Doing 384 bits  ecdh's for 10s: 13119 384-bits ECDH ops in 10.00s
version: 3.0.0-alpha4-dev
built on: built on: Tue Jun 30 05:10:45 2020 UTC
options:bn(64,64) rc4(16x,int) des(int) aes(partial) idea(int) blowfish(ptr) 
compiler: ccache clang -fPIC -pthread -m64 -Wa,--noexecstack -Qunused-arguments -Wall -O3 -DOPENSSL_USE_NODELETE -DL_ENDIAN -DOPENSSL_PIC -DOPENSSL_BUILDING_OPENSSL -DNDEBUG
CPUINFO: OPENSSL_ia32cap=0x7ffef3ffffebffff:0x18d39efffb
                              op      op/s
 384 bits ecdh (nistp384)   0.0008s   1311.9

~~The slight regression on ECDSA verify is because we haven't really put any effort there, and also it speaks to the efficiency of the old NAF code in OpenSSL.~~ more performance improvements in 7e10f3b

crypto/ec/build.info

crypto/ec/ecp_secp384r1.c

bbbrumley · 2020-06-30T06:56:34Z

After #12096 goes in, I will have to do silliness like this:

https://github.com/openssl/openssl/blob/master/crypto/ec/ecp_nistp521.c#L1914-L1926

A better approach would be, inside EC_GROUP, consolidating a_is_minus3 and asn1_flag into a general flags field, then reserve a bit for dirty generators.

romen · 2020-06-30T10:18:33Z

After #12096 goes in, I will have to do silliness like this:

https://github.com/openssl/openssl/blob/master/crypto/ec/ecp_nistp521.c#L1914-L1926

A better approach would be, inside EC_GROUP, consolidating a_is_minus3 and asn1_flag into a general flags field, then reserve a bit for dirty generators.

Yeah, actually the asn1_flag field is a bit meh right now in master anyway, as it is used by legacy code but not by providers, and I would say it is not correct to have it inside EC_GROUP as it should be a EVP_PKEY/EC_KEY parameter or a OSSL_SERIALIZER_CTX option to select if a particular key should be encoded with explicit parameters or using the curve OID upon serialization.

This is a discussion that deserves its own issue, but my recommendation if you decide to consolidate the flags is to leave asn1_flag aside as an exception, as it is controversial and will likely slow down the development of unrelated features.

romen · 2020-06-30T10:22:52Z

crypto/ec/ecp_secp384r1.c

@mattcaswell @levitte are there potential licensing issues to address here?

My understanding is that the fiat code is under the MIT license. I think that if we can't get this under the Apache license, we need an OMC exception to allow this.

There's some prior discussion on this at mit-plv/fiat-crypto#678, in particular,

given the two institutions holding copyright on this project, and that any licensing changes at this point would be rather cumbersome and come at a significant cost of dev time better spent on improving the library.

So I think it's unlikely that we'll manage a license change at this point, though if it's important, we can look into it. (If you want me to reopen mit-plv/fiat-crypto#678, leave a comment there with your concerns and I can reopen it.)

My understanding is that the fiat code is under the MIT license. I think that if we can't get this under the Apache license, we need an OMC exception to allow this.

I agree. I think this is likely to be a significant problem. I don't recall any previous occasion where the OMC has granted such an exception. Another issue is that we require all original authors to provide a CLA. Do we actually know who all the original authors of this code are?

I've asked the OMC about this. I'm not feeling very hopeful.

I've gotten confirmation from @zoep that she's fine with us relicensing, so if it'd help you, we can relicense to be dual-licensed, user's choice, MIT or Apache 2.0. However, my current understanding is that MIT doesn't permit us to sign CLA's, so I don't think you'll be able to get CLAs for fiat-crypto. Given this, would you like us to relicense fiat-crypto to allow use under Apache?

Wow! @JasonGross - that's fantastic that you're willing to relicense!! What an amazing offer. However without a solution to the CLA problem we still have an issue. Are you sure about the MIT policy? I notice several mit.edu addresses in our CLA database. Presumably you individually own the copyright on your own submissions (not MIT as an institution), so these CLAs would be individual agreements?

Sorry for the delay in getting back. I'm not sure what's going on in the other cases; in our case, MIT owns the copyright, and this is MIT's policy on code where it owns copyright.

Some people on the Go issue tracker (golang/go#40171 (comment)) suggested:

An alternative solution to our problem of imposing new notice requirements on every Go binary would be if the generator outputs could be licensed under a non-attribution license such as MIT-0 or a source-code-attribution-only license such as BSD-1-Clause.

Would either of these licenses allow integration of the generated code into OpenSSL without us needing to sign CLAs?

Well there are two issues: licence and CLAs. Your offer above to relicence to Apache 2.0 solves the licence issue. The CLA issue is independent of licensing. So, unfortunately, I don't think swapping to a different licence solves it.

bbbrumley · 2020-07-01T09:33:34Z

I don't really understand the latest Travis failure. How can it pass on CONFIG_OPTS="--strict-warnings" but fail on CONFIG_OPTS="--strict-warnings" MAKEVERBOSE="yes" ?

romen · 2020-07-01T09:38:41Z

I don't really understand the latest Travis failure. How can it pass on CONFIG_OPTS="--strict-warnings" but fail on CONFIG_OPTS="--strict-warnings" MAKEVERBOSE="yes" ?

The failure is happening on ARM64, I can't look into details now and I have very limited availability until Sunday.

crypto/ec/ecp_secp384r1.c

bbbrumley · 2020-07-12T08:44:05Z

The failure is happening on ARM64

This is now fixed. char defaults to signed on x86/x64, but ~~signed~~ unsigned on ARM.

bbbrumley · 2020-07-12T08:46:32Z

Rebased in 80dccc62c0fb6da37326f1b35b5fc41ca79a4127 (thanks @beldmit for merging #12096). We can see the test failure now:

    # Subtest: custom_generator_test
    1..82
    # Curve secp112r1
    ok 1 - iteration 1
...
    # Curve secp224r1
    ok 10 - iteration 10
    # Curve secp256k1
    ok 11 - iteration 11
    # Curve secp384r1
    # ERROR: (int) 'CRYPTO_memcmp(b1, b2, bsize) == 0' failed @ test/ectest.c:2405
    # [1] compared to [0]
    not ok 12 - iteration 12

I will start working on the fix, then I think I can take this out of WiP.

kroeckx · 2020-07-12T08:46:46Z

Do you mean unsigned on s390x?

bbbrumley · 2020-07-12T08:51:54Z

Do you mean unsigned on s390x?

I meant unsigned on armv7 and aarch64 :) This code should rarely get compiled in on s390x.

kroeckx · 2020-07-12T08:56:48Z

I forgot that arm was unsigned too. powerpc would be the other that's unsigned.

kroeckx · 2020-07-25T20:00:54Z

It was not clear that you took this out of WIP. Are you waiting for a review now?

I see that NSS has just released a version with P384 and P521 based on this.

bbbrumley · 2020-07-26T05:24:02Z

Are you waiting for a review now?

From my perspective, yea it's ready :)

bbbrumley · 2020-07-26T05:53:07Z

Also the preprint is now live. Table 2 gives some benchmarks.

crypto/ec/ecp_secp384r1.c

kroeckx · 2020-07-26T20:18:48Z

crypto/ec/ecp_secp384r1.c

This line looks too long for our coding style.

I was wrapping before but @romen gave me the clang-format option to preserve this one. Which I think makes sense.

kroeckx · 2020-07-26T20:29:23Z

crypto/ec/ecp_secp384r1.c

This looks a little weird. I wonder why there is an | 0, that doesn't seem to be doing much.

I'm also not sure why all the parentheses are there. Is the order important?

Regarding the | 0, the template definition is much simpler if we include it; see https://github.com/mit-plv/fiat-crypto/blob/37daa2d8bb34e3e0a30c7396952226407e5e19a3/src/Arithmetic/WordByWordMontgomery.v#L122-L123
And we just didn't have a rule for eliminating this previously.
I've added such a rule in mit-plv/fiat-crypto@37daa2d, so if you regenerate the file, it should drop the | 0.

As far as the parentheses, we always emit parentheses around operations because it's simpler that way; if we didn't do this, we'd have to add in (unverified) pretty-printing logic for associativity and levels of operators (and there's not a universal convention across languages, for example, for which of & and | binds more tightly).

crypto/ec/ecp_secp384r1.c

kroeckx · 2020-07-26T20:38:24Z

crypto/ec/ecp_secp384r1.c

I'm not sure if I should look at the coding style, since this is auto generated code. But our coding style would have the { on the next line, and have an empty line before this one.

I don't think we'll be updating fiat-crypto to allow parameterizing over coding styles. And adding an extra line before this one would be annoying, as I'd have to extend the AST with a specific "blank line" constructor, which seems much more work and overhead than it's worth. So if you do want consistent style, even with the generated code, I'd suggest running the generated code through a code reformatter.

@kroeckx

our coding style would have

One of the last ECCKiila passes is clang-format. If there's something particularly egregious you see in the output, I'm happy to add it as an option there if you let me know what the option is -- I'm no clang-format expert. (E.g. @romen suggested the ReflowComments: false option.)

beldmit · 2020-07-28T16:35:31Z

It will be very pity if this great work is not included in the OpenSSL because of the licence clash.

This portable code comes from [ECCKiila](https://gitlab.com/nisec/ecckiila) that uses [Fiat](https://github.com/mit-plv/fiat-crypto) for the underlying field arithmetic. Co-authored-by: Luis Rivera-Zamarripa <[email protected]> Co-authored-by: Jesús-Javier Chi-Domínguez <[email protected]>

mattcaswell · 2020-08-26T16:08:47Z

my current understanding is that MIT doesn't permit us to sign CLA's, so I don't think you'll be able to get CLAs for fiat-crypto

We had an OMC meeting today and discussed this quite a bit. Ultimately the OMC decided that we cannot make an exception to our CLA rules and so, unfortunately, this PR is not going to be acceptable.

This is a great shame as I can see the value that having this code would bring (and I think that sentiment was shared by the rest of the OMC). I'd encourage looking at making this code available via a third party provider.

beldmit · 2020-08-27T07:50:25Z

Is the current code constant-time? If no, rejecting of this PR seems like leaving a vulnerability.

mattcaswell · 2020-08-27T08:45:25Z

Is the current code constant-time? If no, rejecting of this PR seems like leaving a vulnerability.

No, the current code is not constant time. IMO this PR is highly desirable and it was my impression that others in the OMC agree. However we have to balance that against conflicting requirements for CLAs.

bbbrumley · 2020-08-28T07:36:43Z

this PR is not going to be acceptable.

That's unfortunate.

If you change you mind, ECCKiila is there and you can generate whatever stack you want for any curve, not just P-384.

So if there's a next time, you won't need me or my PR ;)

DDvO · 2020-09-29T12:06:55Z

I'm just copying @mattcaswell's most recent reply in the discussion on this PR
from a within a sub-thread shown further up #12201 (comment) down to here
such that the current state of the discussion becomes easier to find/see:

Well there are two issues: licence and CLAs.
Your offer above to relicence to Apache 2.0 solves the licence issue.
The CLA issue is independent of licensing.
So, unfortunately, I don't think swapping to a different licence solves it.

romen self-assigned this Jun 19, 2020

romen added the branch: master Applies to master branch label Jun 19, 2020

romen reviewed Jun 19, 2020

View reviewed changes

crypto/ec/build.info Outdated Show resolved Hide resolved

romen reviewed Jun 19, 2020

View reviewed changes

crypto/ec/ecp_secp384r1.c Show resolved Hide resolved

romen reviewed Jun 19, 2020

View reviewed changes

crypto/ec/ecp_secp384r1.c Outdated Show resolved Hide resolved

romen reviewed Jun 19, 2020

View reviewed changes

crypto/ec/ecp_secp384r1.c Outdated Show resolved Hide resolved

This was referenced Jun 25, 2020

Fatal error: exception Stack overflow mit-plv/fiat-crypto#823

Closed

Mixed declarations and code mit-plv/fiat-crypto#824

Closed

romen reviewed Jun 30, 2020

View reviewed changes

paulidale reviewed Jul 2, 2020

View reviewed changes

crypto/ec/ecp_secp384r1.c Outdated Show resolved Hide resolved

bbbrumley force-pushed the bbb_p384 branch from 5a18d30 to 6c6198c Compare July 10, 2020 11:47

bbbrumley mentioned this pull request Jul 11, 2020

[test] ectest: check custom generators #12096

Closed

bbbrumley force-pushed the bbb_p384 branch from 6c6198c to 80dccc6 Compare July 12, 2020 08:40

bbbrumley changed the title ~~[crypto/ec] WiP: constant time P-384 EC_METHOD~~ [crypto/ec] constant time P-384 EC_METHOD Jul 14, 2020

bbbrumley force-pushed the bbb_p384 branch from a0673a2 to e84eaff Compare July 14, 2020 08:20

kroeckx reviewed Jul 26, 2020

View reviewed changes

crypto/ec/ecp_secp384r1.c Outdated Show resolved Hide resolved

kroeckx reviewed Jul 26, 2020

View reviewed changes

crypto/ec/ecp_secp384r1.c Outdated Show resolved Hide resolved

kroeckx reviewed Jul 26, 2020

View reviewed changes

tjh-omc added the hold: license clash The license of the contributed code is not compatible label Jul 26, 2020

bbbrumley force-pushed the bbb_p384 branch from a1f6cbc to d63e8fe Compare July 29, 2020 16:52

bbbrumley closed this Aug 28, 2020

JasonGross mentioned this pull request Sep 16, 2020

crypto: import fiat-crypto implementations golang/go#40171

Open

arapov mentioned this pull request Jul 25, 2023

EC Kiila P-384, constant time openssl/project#120

Open

bbbrumley mentioned this pull request Oct 2, 2023

RT3667 Faster GLV elliptic curves #776

Closed

slontis mentioned this pull request Dec 17, 2023

Draft a proposal for fetch of EC implementations/curves openssl/project#112

Open

Uh oh!

Conversation

bbbrumley commented Jun 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Before

After

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

bbbrumley commented Jun 30, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

romen commented Jun 30, 2020

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

bbbrumley commented Jul 1, 2020

Uh oh!

romen commented Jul 1, 2020

Uh oh!

Uh oh!

bbbrumley commented Jul 12, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

bbbrumley commented Jul 12, 2020

Uh oh!

kroeckx commented Jul 12, 2020 via email

Uh oh!

bbbrumley commented Jul 12, 2020

Uh oh!

kroeckx commented Jul 12, 2020

Uh oh!

kroeckx commented Jul 25, 2020

Uh oh!

bbbrumley commented Jul 26, 2020

Uh oh!

bbbrumley commented Jul 26, 2020

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

JasonGross Jul 26, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

beldmit commented Jul 28, 2020

Uh oh!

mattcaswell commented Aug 26, 2020

Uh oh!

bbbrumley commented Jun 19, 2020 •

edited

Loading

bbbrumley commented Jun 30, 2020 •

edited

Loading

bbbrumley commented Jul 12, 2020 •

edited

Loading

JasonGross Jul 26, 2020 •

edited

Loading