CVE-2018-5407 fix: ECC ladder by bbbrumley · Pull Request #7593 · openssl/openssl

bbbrumley · 2018-11-08T12:20:10Z

This is a backport of #6009 #6535 #6648 to 1.0.2. In the context of CVE-2018-5407, this changes the code path for generic curves over prime fields from wNAF to ladder scalar multiplication.

Read the technical details.

bbbrumley · 2018-11-08T12:20:43Z

Tagging @romen for review

bbbrumley · 2018-11-08T12:23:39Z

+    t = ((a->flags ^ b->flags) & BN_FLG_CONSTTIME) & condition;
+    a->flags ^= t;
+    b->flags ^= t;
+


@mattcaswell I don't know what this new flag BN_FLG_FIXED_TOP is. Should we be swapping it here, too?

BN_FLG_FIXED_TOP indicates that we haven't called bn_correct_top() on the data, so the d array may be padded with additional 0 values (i.e. top could be greater than the minimal value that it could be). So I think we should be swapping it. Does that suggest we need to make an equivalent change in master/1.1.1?

Does that suggest we need to make an equivalent change in master/1.1.1?

I reckon so. Seems like it came from 327b2c0 -- @dot-asm any comment?

Yes, it's the right thing to do. Just in case for reference, BN_FLG_FIXED_TOP is a very special debugging flag and is customarily zero. So that production builds won't be affected. It's not suggestion to not resolve this, only explanation to how it can go unnoticed.

Thanks @dot-asm ! I'll open a PR for master.

While we are at it, and while you'll be at it, I'd like to suggest to a) reformat commentary prior BN_consttime_swap to fit 80 chars; b) omit switch at the end and replace it with straight loop. Rationale for b) is that compilers are in better position to decide how to handle loops, nor are straight loops hopeless on contemporary processors. I mean straight loop in machine code is not unlikely to perform better than the current loop-switch combo.

While we are at it, and while you'll be at it, I'd like to suggest

#7599 is ready, but I'll follow up on another PR on master with your suggested changes after the merge.

The larger issue is the BN_consttime_swap API is not right. It should have a return value, and return errors instead of asserts.

bbbrumley · 2018-11-08T16:30:02Z

FWIW I checked the code paths in ecdsatest and ecdhtest with gdb. They are indeed hitting the ec_mul_consttime early exit when they should, and falling through when they shouldn't (ECDSA verify).

paulidale · 2018-11-08T21:39:12Z

We should wait for @romen to review too.

romen

Code looks good to me, and I double checked again in gdb that ec_mul_consttime gets called when it's expected and skipped on the verify codepath.

There is the issue of performance loss, that in 1.1.1 was addressed later on by adding scaffolding for specialized implementations of the ladder step: the issue backporting that to 1.0.2 is that it requires altering some of the structs to add new function pointers in the method structures.
Given that the structures in 1.0.2 are not opaque, we might want to think twice about altering those structures to avoid obscure compatibility issues.

Anyway, I believe the scope of this PR should be limited to the security fix backport, and performance should be addressed by a different "feature" PR.
I will delay merge until tomorrow afternoon (let's say 14:00 UTC) to allow other reviewers to dissent on this and comment on the performance issue. (ping @mattcaswell and @paulidale )

romen · 2018-11-10T13:23:23Z

+ */
+static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
+                            const BIGNUM *scalar, const EC_POINT *point,
+                            BN_CTX *ctx)


As a sidenote, in 1.1.1 we also renamed ec_mul_consttime to a more fitting ec_scalar_mul_ladder (during #6690): I believe that, to be consistent with the current status of 1.1.0-stable, it's a good thing to keep ec_mul_consttime for now and replace it when backporting the "ladder scaffold" for specialized implementations.

This way, after merging this PR as it is now:

1.0.2 & 1.1.0: ec_mul_consttime -- only generic ladder (based on raw EC_POINT_dbl+EC_POINT_add);

1.1.1 & master: ec_scalar_mul_ladder -- generic ladder + optional specialized implementations

@mattcaswell do you agree?

Yes - fine by me.

romen · 2018-11-10T13:30:57Z

More about performance

After this PR gets merged, at some point in the future (right now I don't have enough time available), I plan to open a separate PR to backport the following:

EC2m LD ladder #6690 (probably only the scaffolding, not the Lopez-Dahab implementation for binary curves)
EC GFp ladder #6772 + Replace GFp ladder implementation with ladd-2002-it-4 from EFD #7000 (specialized ladder implementation for prime curves, the additional tests are unfortunately hard to backport)

About binary curves, we might want to discuss if we really want to additionally backport #6070 (to unify the scalar multiplication path for prime and binary curves) and then the Lopez-Dahab specialized implementation from #6690.
I, for one, am not sure it's worth to do it, as the worse testing coverage of 1.0.2 carries an heightened risk of unnoticed bugs and compatibility issues with user code.

Until we backport the performance improvements we can expect performance degradation similar to what was reported for 1.1.1 during the beta development cycle (e.g., #6512).

Conclusion

I will hold the merge for one more day to let @paulidale and @mattcaswell comment on this and on the ec_mul_consttime() naming proposal.

romen · 2018-11-10T13:35:09Z

Note to self: verify what is the status about backport to 1.0.2 of #6116 for future work.

Also, if @mattcaswell and @paulidale agree that the current status of this PR is ok and matches its "bug fix" scope, after merging I plan to open a separate issue to track my progress in backporting the above-mentioned PRs and discuss the further backports plan.

paulidale · 2018-11-11T21:47:56Z

Sounds good to me.

mattcaswell · 2018-11-12T11:05:15Z

Fine by me. I'm less clear about backporting the performance changes. Can you quantify for me the scale of the performance loss - I don't remember?

romen · 2018-11-12T14:16:42Z

@mattcaswell , probably we should discuss if we want to backport the performance improvements in a separate issue, but anyway, as a single data point, examining NIST P-384 ECDH using openssl speed: around 37% loss.

From your comment I would assume you agree on merging this and then figuring out separately if we want to backport the performance improvements, but anyway, I will wait for explicit reapproval from you before merging this.

Detailed output

With current OpenSSL_1_0_2-stable (at 59b9c67):

OpenSSL_1_0_2-stable > OPENSSL_CONF=apps/openssl.cnf util/opensslwrap.sh speed ecdhp384
Doing 384 bit  ecdh's for 10s: 7466 384-bit ECDH ops in 9.98s
OpenSSL 1.0.2q-dev  xx XXX xxxx
built on: reproducible build, date unspecified
options:bn(64,64) md2(int) rc4(16x,int) des(idx,cisc,16,int) aes(partial) idea(int) blowfish(idx)
compiler: gcc -I. -I.. -I../include  -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -Wa,--noexecstack -DBN_DEBUG -DREF_CHECK -DCONF_DEBUG -DCRYPTO_MDEBUG -m64 -DL_ENDIAN -g -Wall -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DRC4_ASM -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM -DECP_NISTZ256_ASM -pedantic -DPEDANTIC -Wno-long-long -Wsign-compare -Wmissing-prototypes -Wshadow -Wformat -Wundef -Werror -DCRYPTO_MDEBUG_ALL -DCRYPTO_MDEBUG_ABORT -DOPENSSL_NO_DEPRECATED                                 
                              op      op/s
 384 bit ecdh (nistp384)   0.0013s    748.1

Rebasing #7593 on current OpenSSL_1_0_2-stable:

pr-7593 > OPENSSL_CONF=apps/openssl.cnf util/opensslwrap.sh speed ecdhp384
Doing 384 bit  ecdh's for 10s: 4707 384-bit ECDH ops in 9.98s
OpenSSL 1.0.2q-dev  xx XXX xxxx
built on: reproducible build, date unspecified
options:bn(64,64) md2(int) rc4(16x,int) des(idx,cisc,16,int) aes(partial) idea(int) blowfish(idx)
compiler: gcc -I. -I.. -I../include  -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -Wa,--noexecstack -DBN_DEBUG -DREF_CHECK -DCONF_DEBUG -DCRYPTO_MDEBUG -m64 -DL_ENDIAN -g -Wall -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DRC4_ASM -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM -DECP_NISTZ256_ASM -pedantic -DPEDANTIC -Wno-long-long -Wsign-compare -Wmissing-prototypes -Wshadow -Wformat -Wundef -Werror -DCRYPTO_MDEBUG_ALL -DCRYPTO_MDEBUG_ABORT -DOPENSSL_NO_DEPRECATED                                 
                              op      op/s
 384 bit ecdh (nistp384)   0.0021s    471.6

mattcaswell

Reconfirm

mattcaswell · 2018-11-12T14:19:40Z

Once this is merged I'll send out a security advisory for it

Reviewed-by: Matt Caswell <matt@openssl.org> Reviewed-by: Paul Dale <paul.dale@oracle.com> Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com> (Merged from #7593)

romen · 2018-11-12T14:32:43Z

Merged as b18162a .

Thank you all!

Low severity timing vulnerability in ECC calculations impacting ECDSA and ECDH. Publicly disclosed but unreleased, pending OpenSSL 1.0.1q Ref: https://www.openssl.org/news/secadv/20181112.txt Ref: openssl/openssl#7593 Upstream: openssl/openssl@b18162a7c Original commit message: CVE-2018-5407 fix: ECC ladder Reviewed-by: Matt Caswell <matt@openssl.org> Reviewed-by: Paul Dale <paul.dale@oracle.com> Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com> (Merged from openssl/openssl#7593)

Reviewed-by: Matt Caswell <matt@openssl.org> Reviewed-by: Paul Dale <paul.dale@oracle.com> Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com> (Merged from openssl/openssl#7593) Gbp-Pq: Name CVE-2018-5407+2018-0735.patch

CVE-2018-5407 fix: ECC ladder

93acd59

bbbrumley commented Nov 8, 2018

View reviewed changes

fixup! CVE-2018-5407 fix: ECC ladder

d2e6b3e

mattcaswell requested changes Nov 8, 2018

View reviewed changes

Comment thread crypto/bn/bn_lib.c Outdated

fixup! CVE-2018-5407 fix: ECC ladder

b7c1b9e

mattcaswell approved these changes Nov 8, 2018

View reviewed changes

mattcaswell added the approval: review pending This pull request needs review by a committer label Nov 8, 2018

paulidale approved these changes Nov 8, 2018

View reviewed changes

paulidale added approval: done This pull request has the required number of approvals and removed approval: review pending This pull request needs review by a committer labels Nov 8, 2018

bbbrumley mentioned this pull request Nov 9, 2018

[crypto/bn] swap BN_FLG_FIXED_TOP too #7599

Closed

romen self-assigned this Nov 10, 2018

romen approved these changes Nov 10, 2018

View reviewed changes

romen added the branch: 1.0.2 Applies to OpenSSL_1_0_2-stable branch (EOL) label Nov 10, 2018

romen reviewed Nov 10, 2018

View reviewed changes

mattcaswell approved these changes Nov 12, 2018

View reviewed changes

levitte pushed a commit that referenced this pull request Nov 12, 2018

CVE-2018-5407 fix: ECC ladder

b18162a

Reviewed-by: Matt Caswell <matt@openssl.org> Reviewed-by: Paul Dale <paul.dale@oracle.com> Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com> (Merged from #7593)

romen closed this Nov 12, 2018

romen mentioned this pull request Nov 12, 2018

Performance degradation after #7593 #7622

Closed

l2dy mentioned this pull request Nov 13, 2018

openssl: CVE-2018-5407 AOSC-Dev/aosc-os-abbs#1444

Closed

7 tasks

vang1ong7ang mentioned this pull request Jan 9, 2020

Enhance security (2.x) neo-project/neo#1385

Closed

Uh oh!

Conversation

bbbrumley commented Nov 8, 2018

Uh oh!

bbbrumley commented Nov 8, 2018

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!

dot-asm Nov 8, 2018 • 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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

bbbrumley commented Nov 8, 2018

Uh oh!

paulidale commented Nov 8, 2018

Uh oh!

romen left a comment

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!

romen commented Nov 10, 2018

More about performance

Conclusion

Uh oh!

romen commented Nov 10, 2018

Uh oh!

paulidale commented Nov 11, 2018

Uh oh!

mattcaswell commented Nov 12, 2018

Uh oh!

romen commented Nov 12, 2018

Detailed output

Uh oh!

mattcaswell left a comment

Choose a reason for hiding this comment

Uh oh!

mattcaswell commented Nov 12, 2018

Uh oh!

romen commented Nov 12, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

dot-asm Nov 8, 2018 •

edited

Loading