Closed
Bug 1125025
(CVE-2015-2730)
Opened 10 years ago
Closed 10 years ago
ECC correctness issues
Categories
(NSS :: Libraries, defect, P2)
NSS
Libraries
Tracking
(firefox37 wontfix, firefox38 wontfix, firefox38.0.5 wontfix, firefox39 fixed, firefox40 fixed, firefox41 fixed, firefox-esr3139+ fixed, firefox-esr3839+ fixed, b2g-v2.0 fixed, b2g-v2.0M fixed, b2g-v2.1 fixed, b2g-v2.1S fixed, b2g-v2.2 fixed, b2g-master fixed)
RESOLVED
FIXED
3.19.1
Tracking | Status | |
---|---|---|
firefox37 | --- | wontfix |
firefox38 | --- | wontfix |
firefox38.0.5 | --- | wontfix |
firefox39 | --- | fixed |
firefox40 | --- | fixed |
firefox41 | --- | fixed |
firefox-esr31 | 39+ | fixed |
firefox-esr38 | 39+ | fixed |
b2g-v2.0 | --- | fixed |
b2g-v2.0M | --- | fixed |
b2g-v2.1 | --- | fixed |
b2g-v2.1S | --- | fixed |
b2g-v2.2 | --- | fixed |
b2g-master | --- | fixed |
People
(Reporter: watsonbladd, Assigned: wtc)
References
Details
(Keywords: sec-moderate, Whiteboard: [adv-main39+][adv-esr31.8+][adv-esr38.1+])
Attachments
(3 files, 2 obsolete files)
1.76 KB,
patch
|
rrelyea
:
review+
watsonbladd
:
feedback+
|
Details | Diff | Splinter Review |
1.79 KB,
patch
|
rrelyea
:
review+
rrelyea
:
superreview+
dveditz
:
sec-approval+
wtc
:
checked-in+
|
Details | Diff | Splinter Review |
1.37 KB,
patch
|
rrelyea
:
review+
wtc
:
checked-in+
|
Details | Diff | Splinter Review |
User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/40.0.2214.91 Safari/537.36
Steps to reproduce:
Examined source code
Actual results:
Incorrect double scalar multiplication algorithm
Expected results:
Implementation should have been correct and efficient. Implementation of ECC multiplication for ECDSA signature validation doesn't handle exceptional cases correctly: an attacker may be able to exploit this to forge signatures.
In detail, the formulas appearing in ecp_jac.c do not handle the case when the addition produces infinity or adds a point to itself. An attacker can use this to generate specially-crafted signatures that cause the validation algorithm to compute the incorrect point. It isn't clear if this can be used to forge signatures. ECDSA verification must use formulas that handle all possible cases, unlike single-point exponentiation where detailed analysis can remove this issue.
Reporter | ||
Comment 1•10 years ago
|
||
Having analyzed ECDSA signatures some more, I believe this doesn't lead to a viable forgery attack. There are other schemes where it does: I don't know if NSS implements any of them or not.
Comment 2•10 years ago
|
||
Adding some NSS folks to comment on this and ask questions.
Updated•10 years ago
|
Flags: needinfo?(rrelyea)
Updated•10 years ago
|
Flags: needinfo?(rlb)
Comment 3•10 years ago
|
||
Brian, we're trying to assess this bug's severity, but no one has weighed in for a few months. Do you have an opinion here?
Flags: needinfo?(brian)
Comment 4•10 years ago
|
||
(In reply to Matt Wobensmith from comment #3)
> Brian, we're trying to assess this bug's severity, but no one has weighed in
> for a few months. Do you have an opinion here?
Maybe try asking Martin.
Flags: needinfo?(brian) → needinfo?(martin.thomson)
Comment 5•10 years ago
|
||
I think we really want Bob. I'll try to remember to ping him on tomorrow's NSS call
Comment 6•10 years ago
|
||
Discussed on the NSS call. If we have a fix, Wan-Teh might be able to review it; otherwise, we will let Bob get around to looking at this in the usual fashion.
Flags: needinfo?(martin.thomson)
Assignee | ||
Comment 7•10 years ago
|
||
Watson:
Thank you for the bug report. I inspected the relevant code
in ecp_jac.c that you pointed out. I compared the code with
the point doubling and point addition algorithms on pp. 88-89
and in Algorithms 3.21 and 3.22 (pp. 91-92) in the "Guide to
Elliptic Curve Cryptography" book by Hankerson, Menezes, and
Vanstone. I agree that the ec_GFp_pt_dbl_jac and
ec_GFp_pt_add_jac_aff functions are not checking the
preconditions.
This patch contains the pseudo code of my proposed fix.
Waston, Bob, please review. Thanks.
Attachment #8596298 -
Flags: review?(rrelyea)
Attachment #8596298 -
Flags: feedback?(watsonbladd)
Reporter | ||
Comment 8•10 years ago
|
||
The pseudo code correctly implements the test for all exceptional cases, as listed in Handbook of Elliptic and Hyperelliptic Curve Cryptography.
Assignee | ||
Comment 9•10 years ago
|
||
Watson: thank you for the review! I just realized that I wrote
the fix for ec_GFp_pt_add_jac_aff can be simplified if we know
ec_GFp_pt_dbl_jac will check for P == -P. Please review this
new patch.
I also wanted to note that I considered the possibility that
the callers of these functions were checking the preconditions
before calling the functions. I inspected a few callers and
didn't see any such checks. So I think these two functions
need to perform the checks for preconditions.
Attachment #8596298 -
Attachment is obsolete: true
Attachment #8596298 -
Flags: review?(rrelyea)
Attachment #8596298 -
Flags: feedback?(watsonbladd)
Attachment #8596694 -
Flags: review?(rrelyea)
Attachment #8596694 -
Flags: feedback?(watsonbladd)
Comment 10•10 years ago
|
||
Comment on attachment 8596694 [details] [diff] [review]
Pseudo code of proposed patch, v2
Review of attachment 8596694 [details] [diff] [review]:
-----------------------------------------------------------------
Summary..
I believe the psuedo code is correct, but may be more or less efficient depending on how common P = -Q and P = -P cases are in these cases.
I believe the current code has a bug, but only in the case where P = Q in the point addition case.
::: lib/freebl/ecl/ecp_jac.c
@@ +155,5 @@
> + /* P == -Q */
> + return point-at-infinity;
> + }
> + }
> +#endif
So I know the current code is fine for a point at infinity. I think the error is in P == Q.
If P == -Q then C == 0 and rz = pz *C which equals 0, makeing R the point at infinity (in Jacobian space the point at infinity is any point of the form (x,y,0)).
For P == Q, it looks like we erroneously create a point at inifinity (in fact we return the point (0, 0, 0). So the minimum corret code is:
if ((C == 0) && (D == 0)) {
return point-double(qx,qy,1); /* or point-double (rx,ry,rz);*/
}
The given pseudo_code may be more efficient, however, since we skip a lot of math in the P == -Q case (depending on how common P == -Q is).
@@ +228,5 @@
> + if (py == 0) {
> + /* P == -P */
> + return point-at-infinity;
> + }
> +#endif
This test isn't necessary for correctness. If py == 0, then rz = 2 * py *pz == 0.
If it's common, then the pseudo_code saves lots of math, but it's not necessary.
Attachment #8596694 -
Flags: review?(rrelyea) → review+
Assignee | ||
Comment 11•10 years ago
|
||
Assignee | ||
Comment 12•10 years ago
|
||
Comment on attachment 8600194 [details] [diff] [review]
Proposed patch
Review of attachment 8600194 [details] [diff] [review]:
-----------------------------------------------------------------
Bob: please review.
I am not sure how common these corner cases are. I would perform the checks as specified if they are not expensive, because it would be easier to verify the correctness of the code. However, if the checks are expensive, I can replace the unnecessary checks with comments. Thanks.
::: lib/freebl/ecl/ecp_jac.c
@@ +219,5 @@
> MP_CHECKOK(mp_init(&M));
> MP_CHECKOK(mp_init(&S));
>
> + /* P == inf or P == -P */
> + if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES || mp_cmp_z(py) == 0) {
Bob: the "Guide to Elliptic Curve Cryptography" book's Algorithm 3.21 doesn't check for P == -P here. I thought that was an error, but perhaps that was an intentional optimization because the rest of the code will return the point at infinity? If you are sure about that, I can remove this check and just add a comment.
Attachment #8600194 -
Flags: review?(rrelyea)
Assignee | ||
Updated•10 years ago
|
Assignee: nobody → wtc
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Priority: -- → P2
Target Milestone: --- → 3.19.1
Assignee | ||
Comment 13•10 years ago
|
||
The ec_GFp_pt_add_jm_aff function is only used inside this file.
Attachment #8600198 -
Flags: review?(rrelyea)
Reporter | ||
Updated•10 years ago
|
Attachment #8596694 -
Flags: feedback?(watsonbladd) → feedback+
Comment 14•10 years ago
|
||
Comment on attachment 8600194 [details] [diff] [review]
Proposed patch
Review of attachment 8600194 [details] [diff] [review]:
-----------------------------------------------------------------
::: lib/freebl/ecl/ecp_jac.c
@@ +219,5 @@
> MP_CHECKOK(mp_init(&M));
> MP_CHECKOK(mp_init(&S));
>
> + /* P == inf or P == -P */
> + if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES || mp_cmp_z(py) == 0) {
Yes, I'm sure the code is correct without the test. It's relatively simple to show:
If py == 0 then:
rz is set to py+py = 0 at line 243 (of the original) if pz = 1;
rz is set to (py+py)*pz = 0 at lines 246,247 (of the original) if pz != 0;
As long as we don't divide, the rest of the cases calculations are not relevant.
Note that the is inf test is also not necessary here because pz is zero, then rz becomes zero (line 247). Certainly the is inf case and the rz = 1 case is prevelant enough to require special checks, so I think the cost of the check is not that much and the savings when it hits is obviously pretty good.
I don't think it's an error in the book, it's just missing a potential optimization.
Attachment #8600194 -
Flags: superreview+
Attachment #8600194 -
Flags: review?(rrelyea)
Attachment #8600194 -
Flags: review+
Comment 15•10 years ago
|
||
Comment on attachment 8600198 [details] [diff] [review]
Mark ec_GFp_pt_add_jm_aff as static
Review of attachment 8600198 [details] [diff] [review]:
-----------------------------------------------------------------
most of these functions should probably be static. Even the globally accessible functions are accessed through a function pointer table.
Attachment #8600198 -
Flags: review?(rrelyea) → review+
Comment 16•10 years ago
|
||
BTW, I should point out that m_cmp_z() is relatively quick:
int mp_cmp_z(const mp_int *a)
{
if(SIGN(a) == NEG)
return MP_LT;
else if(USED(a) == 1 && DIGIT(a, 0) == 0)
return MP_EQ;
else
return MP_GT;
}
It's at least as quick as mp_cmp_d used to see if pz == 1.
Flags: needinfo?(rrelyea)
Assignee | ||
Comment 17•10 years ago
|
||
Bob: thanks a lot for reviewing the two patches carefully. I found
another function in ecp_jm.c that can be marked static.
Attachment #8600198 -
Attachment is obsolete: true
Attachment #8600442 -
Flags: review?(rrelyea)
Updated•10 years ago
|
Attachment #8600442 -
Flags: review?(rrelyea) → review+
Assignee | ||
Comment 18•10 years ago
|
||
Comment on attachment 8600194 [details] [diff] [review]
Proposed patch
[Security approval request comment]
How easily could an exploit be constructed based on the patch?
It doesn't seem easy to construct an exploit based on the patch.
The current code only has a bug in ec_GFp_pt_add_jac_aff when the
two points P and Q that we're adding are equal. Although the
current code doesn't check the other two corner cases, it will
still produce the correct results.
Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?
No.
Which older supported branches are affected by this flaw?
All older supported branches are affected by this flaw.
Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?
This file has not changed much, so the patch should apply
cleanly to all older supported branches.
How likely is this patch to cause regressions; how much testing does it need?
This patch is unlikely to cause regressions because it corrects
a numerical calculation error in a corner case. The NSS test
suite and visiting Facebook and Google over HTTPS should be
enough.
Attachment #8600194 -
Flags: sec-approval?
Comment 19•10 years ago
|
||
Comment on attachment 8600194 [details] [diff] [review]
Proposed patch
sec-approval = dveditz
Attachment #8600194 -
Flags: sec-approval? → sec-approval+
Updated•10 years ago
|
status-firefox37:
--- → wontfix
status-firefox38:
--- → affected
status-firefox38.0.5:
--- → affected
status-firefox39:
--- → affected
status-firefox40:
--- → affected
status-firefox-esr31:
--- → affected
Keywords: sec-moderate
Assignee | ||
Comment 20•10 years ago
|
||
Comment on attachment 8600194 [details] [diff] [review]
Proposed patch
Patch checked in: https://hg.mozilla.org/projects/nss/rev/2c05e861ce07
Attachment #8600194 -
Flags: checked-in+
Assignee | ||
Comment 21•10 years ago
|
||
Comment on attachment 8600442 [details] [diff] [review]
Mark ec_GFp_pt_dbl_jm and ec_GFp_pt_add_jm_aff as static
Patch checked in: https://hg.mozilla.org/projects/nss/rev/fc6870938172
Attachment #8600442 -
Flags: checked-in+
Assignee | ||
Comment 22•10 years ago
|
||
Marked the bug fixed. Watson, thank you very much for reporting
the bug and reviewing my fix.
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Comment 23•10 years ago
|
||
This missed Firefox 38, didn't it? We have final builds and if NSS needs to be updated for this fix, it would seem to be too late.
Updated•10 years ago
|
Blocks: 1166031
status-b2g-v2.0:
--- → affected
status-b2g-v2.0M:
--- → affected
status-b2g-v2.1:
--- → affected
status-b2g-v2.1S:
--- → affected
status-b2g-v2.2:
--- → affected
status-b2g-master:
--- → affected
status-firefox41:
--- → affected
status-firefox-esr38:
--- → affected
Updated•10 years ago
|
Flags: needinfo?(rlb)
Updated•10 years ago
|
tracking-firefox-esr31:
--- → ?
tracking-firefox-esr38:
--- → ?
Updated•10 years ago
|
Whiteboard: [adv-main39+][adv-esr31.8+][adv-esr38.1+]
Updated•10 years ago
|
Alias: CVE-2015-2730
Summary: ECC correctness issues → ECC correctness issues
Updated•10 years ago
|
Group: core-security
You need to log in
before you can comment on or make changes to this bug.
Description
•