1125025 - (CVE-2015-2730) ECC correctness issues

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[watsonbladd]

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.

Comment 1

[watsonbladd]

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

[Al Billings [:abillings - ex-MoCo]]

Adding some NSS folks to comment on this and ask questions.

Comment 3

[Matt Wobensmith [:mwobensmith][:matt:]]

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?

Comment 4

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

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

Comment 5

[Eric Rescorla (:ekr)]

I think we really want Bob. I'll try to remember to ping him on tomorrow's NSS call

Comment 6

[Martin Thomson [:mt:]]

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.

Comment 7

[Wan-Teh Chang]

Attachment: Pseudo code of proposed patch

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.

Comment 8

[watsonbladd]

The pseudo code correctly implements the test for all exceptional cases, as listed in Handbook of Elliptic and Hyperelliptic Curve Cryptography.

Comment 9

[Wan-Teh Chang]

Attachment: Pseudo code of proposed patch, v2

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.

Comment 10

[Robert Relyea]

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.

Comment 11

[Wan-Teh Chang]

Attachment: Proposed patch

Comment 12

[Wan-Teh Chang]

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.

Comment 13

[Wan-Teh Chang]

Attachment: Mark ec_GFp_pt_add_jm_aff as static

The ec_GFp_pt_add_jm_aff function is only used inside this file.

Comment 14

[Robert Relyea]

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.

Comment 15

[Robert Relyea]

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.

Comment 16

[Robert Relyea]

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.

Comment 17

[Wan-Teh Chang]

Attachment: Mark ec_GFp_pt_dbl_jm and ec_GFp_pt_add_jm_aff as static

Bob: thanks a lot for reviewing the two patches carefully. I found
another function in ecp_jm.c that can be marked static.

Comment 18

[Wan-Teh Chang]

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.

Comment 19

[Daniel Veditz [:dveditz]]

Comment on attachment 8600194 [details] [diff] [review]
Proposed patch

sec-approval = dveditz

Comment 20

[Wan-Teh Chang]

Comment on attachment 8600194 [details] [diff] [review]
Proposed patch

Patch checked in: https://hg.mozilla.org/projects/nss/rev/2c05e861ce07

Comment 21

[Wan-Teh Chang]

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

Comment 22

[Wan-Teh Chang]

Marked the bug fixed. Watson, thank you very much for reporting
the bug and reviewing my fix.

Comment 23

[Al Billings [:abillings - ex-MoCo]]

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.