Bug 1352039 (CVE-2017-7781)

Issue with elliptic curve addition in mixed Jacobian-affine coordinates

RESOLVED FIXED in Firefox 55

Status

defect
RESOLVED FIXED
2 years ago
a year ago

People

(Reporter: antonio.sanso, Assigned: franziskus)

Tracking

({sec-moderate})

trunk
3.31
Bug Flags:
sec-bounty +
qe-verify -

Firefox Tracking Flags

(firefox-esr45 wontfix, firefox-esr52 wontfix, firefox53 wontfix, firefox54 wontfix, firefox55 fixed)

Details

(Whiteboard: [adv-main55+][post-critsmash-triage])

Attachments

(1 attachment)

(Reporter)

Description

2 years ago
User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:52.0) Gecko/20100101 Firefox/52.0
Build ID: 20170316213829

Steps to reproduce:

The implemented elliptic curve point  addition  algorithm that uses mixed Jacobian-affine coordinates is currently incorrect. It may yield a result POINT_AT_INFINITY when it should not.

You can find the implementation in 

https://hg.mozilla.org/projects/nss/file/215207b4864c/lib/freebl/ecl/ecp_jm.c

ec_GFp_pt_add_jm_aff(const mp_int *px, const mp_int *py, const mp_int *pz,
                     const mp_int *paz4, const mp_int *qx,
                     const mp_int *qy, mp_int *rx, mp_int *ry, mp_int *rz,
                     mp_int *raz4, mp_int scratch[], const ECGroup *group)





Actual results:

The ec_GFp_pt_add_jm_aff implements the algorithm found in "Software Implementation of the NIST Elliptic Curves Over Prime Fields" (http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=7F30DF02245F1428D542471889BEEAAB?doi=10.1.1.144.5095&rep=rep1&type=pdf) page 12 algorithm 3.

It does implement the algorithm verbatim as in the paper . 
The problem is that in the formula reported in the paper  is actually incomplete. Indeed it can happen that

C = X2 Z1^2  -  A is equal to zero .

This will eventually yield  a result POINT_AT_INFINITY (since C is everywhere in the formulas) when it should not.


Expected results:

You can find the correct algorithm in https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates (Point Addition (12M + 4S)).

There this case is taken in consideration

...
if (U1 == U2)
  if (S1 != S2)
    return POINT_AT_INFINITY
  else 
    return POINT_DOUBLE(X1, Y1, Z1)


and the outcome would be POINT_DOUBLE(X1, Y1, Z1)
Flags: needinfo?(ttaubert)
Franziskus, can you take a look?
Flags: needinfo?(ttaubert) → needinfo?(franziskuskiefer)
(Reporter)

Comment 2

2 years ago
hi there, just to let you know that Oracle confirmed the issue.
I do not know if you are aware of it but basically Java native code for Elliptic Curve is an exact copy of this code base....
Yeah, this is an issue. But unfortunately not the only one.
Assignee: nobody → franziskuskiefer
Status: UNCONFIRMED → NEW
Ever confirmed: true
(Reporter)

Comment 4

2 years ago
Thanks @fkiefer. I think I have noticed some other weird stuff too. Should I report or you are already on it ?
Please report everything that you found so I can make sure that we fix everything.
Flags: needinfo?(antonio.sanso)
(Reporter)

Comment 6

2 years ago
@fkiefer ok I will go throughout some of the weirdness I noted and see if they are really a bug...

question: how critical do you rate this issue ? The reason I ask is that (I do not know if you are aware) Java shares this very own code base. I reported this to Oracle and they also are going to fix. I wonder if we need some coordination for disclosure....
Flags: needinfo?(antonio.sanso)
(Reporter)

Comment 7

2 years ago
@fkiefer should I take this like: "no worries this is low severity" :) ?
This is probably sec-moderate (pretty hard to trigger and exploit). We should fix it anyway. But I don't know when I'll get to it.
(Reporter)

Comment 9

2 years ago
Thanks a lot Franziskus,
for the record here is a way to trigger it in Java 1.7 or early version of java 1.8 (without point validation fix):

https://gist.github.com/asanso/58fd0c8cc6c54c757192cb6da5294f58

As said for some reason Java has the same code base!!
(Reporter)

Comment 10

2 years ago
@Franziskus, just wanted to let you know we are writing a research paper that will include this vulnerability (the paper is not about it but will include this).

My intention is not to disclose this before is fixed but we'd better coordinate on some kind of deadline...
Flags: sec-bounty?
(Reporter)

Comment 11

2 years ago
just wanted to share with you a POC that works with valid curve (P521 in this case).

This works as well with last patched java 1.8 and probably also last patched NSS

https://gist.github.com/asanso/6d33e91a9f85f3d4dba4ec519eece6e9
This adds a test case and fixes the issue.
Review is happening at [1].

[1] https://nss-review.dev.mozaws.net/D333
Flags: needinfo?(franziskuskiefer)
Attachment #8872563 - Flags: feedback?(antonio.sanso)
(Reporter)

Comment 13

2 years ago
Thanks Franziskus, LGTM!
Status: NEW → ASSIGNED
Keywords: sec-moderate
FTR, Franziskus talked to Antonio who confirmed sec-moderate. A MITM would be able to interfere with a connection so that the attacked party computes the wrong shared secret, however they can't determine the secret itself and thus not hijack the session.
https://hg.mozilla.org/projects/nss/rev/6d1f5f958100a5d33ce1e63887c668d84814e0dd
Status: ASSIGNED → RESOLVED
Last Resolved: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → 3.31
Per IRC discussion with Tim, this can ride with NSS 3.31 and Fx55.
Group: crypto-core-security → core-security-release
Flags: sec-bounty? → sec-bounty+
(Reporter)

Comment 17

2 years ago
Comment on attachment 8872563 [details] [diff] [review]
jc-aff-mult.patch

Review of attachment 8872563 [details] [diff] [review]:
-----------------------------------------------------------------

LGTM
(Reporter)

Updated

2 years ago
Attachment #8872563 - Flags: feedback?(antonio.sanso) → feedback-
Whiteboard: [adv-main55+]
Alias: CVE-2017-7781
Flags: qe-verify-
Whiteboard: [adv-main55+] → [adv-main55+][post-critsmash-triage]
Group: core-security-release
You need to log in before you can comment on or make changes to this bug.