1352039 - (CVE-2017-7781) Issue with elliptic curve addition in mixed Jacobian-affine coordinates

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Antonio Sanso]

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)

Comment 1

[Tim Taubert [:ttaubert] (inactive)]

Franziskus, can you take a look?

Comment 2

[Antonio Sanso]

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

Comment 3

[Franziskus Kiefer [:franziskus]]

Yeah, this is an issue. But unfortunately not the only one.

Comment 4

[Antonio Sanso]

Thanks @fkiefer. I think I have noticed some other weird stuff too. Should I report or you are already on it ?

Comment 5

[Franziskus Kiefer [:franziskus]]

Please report everything that you found so I can make sure that we fix everything.

Comment 6

[Antonio Sanso]

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

Comment 7

[Antonio Sanso]

@fkiefer should I take this like: "no worries this is low severity" :) ?

Comment 8

[Franziskus Kiefer [:franziskus]]

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.

Comment 9

[Antonio Sanso]

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!!

Comment 10

[Antonio Sanso]

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

Comment 11

[Antonio Sanso]

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

Comment 12

[Franziskus Kiefer [:franziskus]]

Attachment: jc-aff-mult.patch

This adds a test case and fixes the issue.
Review is happening at [1].

[1] https://nss-review.dev.mozaws.net/D333

Comment 13

[Antonio Sanso]

Thanks Franziskus, LGTM!

Comment 14

[Tim Taubert [:ttaubert] (inactive)]

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.

Comment 15

[Franziskus Kiefer [:franziskus]]

https://hg.mozilla.org/projects/nss/rev/6d1f5f958100a5d33ce1e63887c668d84814e0dd

Comment 16

[Ryan VanderMeulen [:RyanVM]]

Per IRC discussion with Tim, this can ride with NSS 3.31 and Fx55.

Comment 17

[Antonio Sanso]

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

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

LGTM