Closed Bug 1352039 (CVE-2017-7781) Opened 3 years ago Closed 3 years ago
Issue with elliptic curve addition in mixed Jacobian-affine coordinates
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)
Franziskus, can you take a look?
Flags: needinfo?(ttaubert) → needinfo?(franziskuskiefer)
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
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.
@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....
@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.
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!!
@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...
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 .  https://nss-review.dev.mozaws.net/D333
Attachment #8872563 - Flags: feedback?(antonio.sanso)
Thanks Franziskus, LGTM!
Status: NEW → ASSIGNED
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.
Status: ASSIGNED → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → 3.31
Per IRC discussion with Tim, this can ride with NSS 3.31 and Fx55.
Comment on attachment 8872563 [details] [diff] [review] jc-aff-mult.patch Review of attachment 8872563 [details] [diff] [review]: ----------------------------------------------------------------- LGTM
Attachment #8872563 - Flags: feedback?(antonio.sanso) → feedback-
Whiteboard: [adv-main55+] → [adv-main55+][post-critsmash-triage]
You need to log in before you can comment on or make changes to this bug.