Bug 1125025 (CVE-2015-2730)

ECC correctness issues

RESOLVED FIXED in Firefox 39

Status

defect
P2
normal
RESOLVED FIXED
5 years ago
4 years ago

People

(Reporter: watsonbladd, Assigned: wtc)

Tracking

({sec-moderate})

Dependency tree / graph

Firefox Tracking Flags

(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)

Details

(Whiteboard: [adv-main39+][adv-esr31.8+][adv-esr38.1+])

Attachments

(3 attachments, 2 obsolete attachments)

Reporter

Description

5 years ago
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

5 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.
Adding some NSS folks to comment on this and ask questions.
Flags: needinfo?(rrelyea)
Flags: needinfo?(rlb)
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)
(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)
I think we really want Bob. I'll try to remember to ping him on tomorrow's NSS call
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

4 years ago
Posted patch Pseudo code of proposed patch (obsolete) — Splinter Review
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

4 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

4 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

4 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

4 years ago
Assignee

Comment 12

4 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

4 years ago
Assignee: nobody → wtc
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Priority: -- → P2
Target Milestone: --- → 3.19.1
Assignee

Comment 13

4 years ago
The ec_GFp_pt_add_jm_aff function is only used inside this file.
Attachment #8600198 - Flags: review?(rrelyea)
Reporter

Updated

4 years ago
Attachment #8596694 - Flags: feedback?(watsonbladd) → feedback+

Comment 14

4 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

4 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

4 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

4 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

4 years ago
Attachment #8600442 - Flags: review?(rrelyea) → review+
Assignee

Comment 18

4 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 on attachment 8600194 [details] [diff] [review]
Proposed patch

sec-approval = dveditz
Attachment #8600194 - Flags: sec-approval? → sec-approval+
Assignee

Comment 20

4 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

4 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

4 years ago
Marked the bug fixed. Watson, thank you very much for reporting
the bug and reviewing my fix.
Status: ASSIGNED → RESOLVED
Closed: 4 years ago
Resolution: --- → FIXED
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.
Flags: needinfo?(rlb)
Whiteboard: [adv-main39+][adv-esr31.8+][adv-esr38.1+]
Alias: CVE-2015-2730
Summary: ECC correctness issues → ECC correctness issues
Group: core-security
You need to log in before you can comment on or make changes to this bug.