Bug 1160139 (CVE-2016-1936)

Small subgroup attack

RESOLVED FIXED in Firefox 44

Status

NSS
Libraries
RESOLVED FIXED
2 years ago
a year ago

People

(Reporter: Antonio Sanso, Assigned: rbarnes)

Tracking

({sec-low})

3.21
sec-low

Firefox Tracking Flags

(firefox42 wontfix, firefox43 wontfix, firefox44 fixed, firefox45 fixed, firefox-esr31 wontfix, firefox-esr38 wontfix, b2g-v2.0 wontfix, b2g-v2.0M wontfix, b2g-v2.1 wontfix, b2g-v2.1S wontfix, b2g-v2.2 affected, b2g-v2.2r affected, b2g-master affected)

Details

(Whiteboard: [adv-main44+])

Attachments

(1 attachment, 2 obsolete attachments)

(Reporter)

Description

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

Steps to reproduce:

When using TLS_DHE_RSA_WITH_AES_128_CBC_SHA Chrome doesn't accept degenerate public key of value 0,1 and -1 since this key lead to pms that is {0,1, -1}.
This (the -1 case) is probably a consequence of CVE-2014-1491 (raised as part of the Triple Handshake Attack [0]).

I would refer to the classic  Diffie Hellman nomenclature

* p as the prime number 
* g the generator with order p-1 = q
* y public key
* x private key

Observation #1

If (p-1)/4  = 0 (mod p) then if I choose my private key x = (p-1)/4 then my public key
y = g^x will generates a prime-order subgroup of size 4.

This means that Chrome will agree on a pms = 1 one time out of 4. 
See below for the details...

[0] https://www.secure-resumption.com/



Actual results:

Tested with Chrome Version 42.0.2311.135 (64-bit)  
I set up a server with

p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084241
g = 3
q =1

and TLS_DHE_RSA_WITH_AES_128_CBC_SHA as cipher.

During the negotiation with Chrome I always choose 

x= (p-1)/4 = 3351951982485649274893506249551461531869841455148098344430890360930441007518386744200468574541725856922507964546621512713438470702986642486608412251521060

and pass 

y = 11130333445084706427994000041243435077443611277989851635896953056790400956946719341695219235480436483595595868058263313228038179294276393680262837344694991

Chrome will happily "agree" on those 4 pms

* 1
* 2277474484857890671580024956962411050035754542602541741826608386931363073126827635106655062686466944094435990128222737625715703517670176266170811661389250

* 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084240

* 11130333445084706427994000041243435077443611277989851635896953056790400956946719341695219235480436483595595868058263313228038179294276393680262837344694991

Of course the "worse" one is 1 and happens to be 1 time out of 4.

If it help a can post several paper and attack link based on "Small subgroup attack".

Just for the record even the easier suggestion given in [1] aka 

"Make sure that g^x,g^y and g^xy do not equal to 1"

 is not followed and this happens with very high probability (25%)
[1]
http://crypto.cs.mcgill.ca/~stiglic/Papers/dhfull.pdf


Expected results:

Tested with

- Chrome
- Firefox 
- Opera

For Safari (not using NSS) the situation is much worse but well known... http://www.openwall.com/lists/oss-security/2014/03/04/8
Flags: needinfo?(rlb)
verifying that a share does not have a small subgroup is hard.  That is why we have https://tools.ietf.org/html/draft-ietf-tls-negotiated-ff-dhe-08.

I believe that the best answer here is to either disable DHE or to implement the ff-dhe draft and require its use.  That does have the same net effect, which is errors on 5% of handshakes, which I don't think we can tolerate.

I thought that we had checks on g^x and g^y being 1.  I'm less sure about g^xy though.

In the end, a choice to use a bad group is one made by the server.  While we might want to avoid this, we can't check everything at the client right now.  There are plenty of bad groups to choose from.
(Reporter)

Comment 2

2 years ago
hi Martin , I do agree with you on all the accounts.
Based on my experience with testing this g^xy is not tested and can end up having pms =1.

Said that it should not be too complicated to check at least that g^xy must differ from 1.

Indeed even section 5.1 (https://tools.ietf.org/html/draft-ietf-tls-negotiated-ff-dhe-08#section-5.1) says 

Peers MUST validate each other's public key Y (dh_Ys offered by the
   server or dh_Yc offered by the client) by ensuring that 1 < Y < p-1.
   This simple check ensures that the remote peer is properly behaved
   and isn't forcing the local system into a small subgroup.

Comment 3

2 years ago
Note: in this comment, x and y are the secret keys of the two
participants in a Diffie-Hellman key agreement.

g^xy can also be equal to 1 for good keys with an extremely small
probability. I'm not sure what a TLS client should do if g^xy is
equal to 1.  Should it abort the handshake, or should it generate
a new y and calculate g^xy again?
Wan-Teh is right here, but g^xy = 1 is of low enough probability that I think we should consider it a potential failure.  The odds are astronomically low if the peers are well-behaved, but it could indicate a small subgroup attack with a much higher probability.  Failing a connection on that basis is probably the safest option.
Status: UNCONFIRMED → NEW
Ever confirmed: true
(Assignee)

Comment 5

2 years ago
I would expand the earlier proposals, and suggest that we should return an error if g^x, g^y, or g^xy is 1 or -1.  That's an easy check to do (at least in principle), and it's also something we could apply to ECDH.

The next question is where to implement the check.  My initial inclination is to just add it to [EC]DH_Derive, so that it applies in all cases.  (And perhaps also in DH_NewKey, just in case.)  Any objections to that path?

It is tempting to take this as the straw that broke the back of DHE.  Do we have any compat numbers?
Flags: needinfo?(rlb)
(Assignee)

Comment 6

2 years ago
Created attachment 8609783 [details] [diff] [review]
bug-1160139.0.patch

It turns out that DH already checks its public input for 1, -1 and 0, and ECDH already checks its output for the point at infinity (~= 1).  

https://dxr.mozilla.org/mozilla-central/source/security/nss/lib/freebl/dh.c#241
https://dxr.mozilla.org/mozilla-central/source/security/nss/lib/freebl/ec.c#567

This patch adds the corresponding checks on the result of the DH computation (g^xy) and the ECDH input public value.

(The ECDH check, of course, is a pure optimization, since the output check would catch this case.  But it does save us the effort of doing the point multiplication in this case.)
Attachment #8609783 - Flags: review?(wtc)
(Assignee)

Updated

2 years ago
Keywords: sec-moderate

Comment 7

2 years ago
Comment on attachment 8609783 [details] [diff] [review]
bug-1160139.0.patch

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

r=wtc. Please make the changes I suggested and upload a new patch.
Thanks.

::: lib/freebl/dh.c
@@ +253,5 @@
>          goto cleanup;
>      }
> +
> +    /*
> +     * We check to make sure that ZZ is not equal to 0, 1 or -1 mod p.  This

If ZZ is 0, then Yb is 0. But we already reject Yb == 0
above, so ZZ cannot be 0.

@@ +256,5 @@
> +    /*
> +     * We check to make sure that ZZ is not equal to 0, 1 or -1 mod p.  This
> +     * helps guard against small subgroup attacks, since an attacker using a
> +     * subgroup of size N will produce this outcome with probability 1/N.
> +     * When the protocol is executed correctly, the probability of this result

Nit: should we say "When the prime p is chosen correctly" instead of
"When the protocol is executed correctly"?

@@ +259,5 @@
> +     * subgroup of size N will produce this outcome with probability 1/N.
> +     * When the protocol is executed correctly, the probability of this result
> +     * will be very small (1/p).
> +     *
> +     * We return MP_BADARG because this probably the result of a bad public

Nit: add "is" before or after "probably"?

@@ +263,5 @@
> +     * We return MP_BADARG because this probably the result of a bad public
> +     * value having been provided.
> +     */
> +    if (mp_cmp_d(&ZZ, 1) <= 0 ||
> +        mp_cmp(&ZZ, &psub1) >=0) {

Nit: add a space before '0'.

Nit: we can test mp_cmp(&ZZ, &psub1) == 0 here because ZZ has been
reduced modulo p.

::: lib/freebl/ec.c
@@ +547,5 @@
> +     * We fail if the public value is the point at infinity, since
> +     * this produces predictable results.
> +     */
> +    if (ec_point_at_infinity(publicValue)) {
> +	PORT_SetError(SEC_ERROR_INVALID_ARGS);

Nit: seems better to set the error code SEC_ERROR_BAD_KEY instead.
Attachment #8609783 - Flags: review?(wtc) → review+

Comment 8

2 years ago
(In reply to Richard Barnes [:rbarnes] from comment #6)
> Created attachment 8609783 [details] [diff] [review]
> bug-1160139.0.patch
> 
[...]
> This patch adds the corresponding checks on the result of the DH computation
> (g^xy) and the ECDH input public value.
>
> (The ECDH check, of course, is a pure optimization, since the output check
> would catch this case.  But it does save us the effort of doing the point
> multiplication in this case.)

It doesn't seem necessary to optimize this case.

Also, it seems that the DH output check should allow us to remove the
DH input check for 1 and -1, right?
(Assignee)

Updated

2 years ago
Assignee: nobody → rlb
(Assignee)

Comment 9

2 years ago
Created attachment 8612395 [details] [diff] [review]
bug-1160139.1.patch r=wtc

(In reply to Wan-Teh Chang from comment #7)
> Comment on attachment 8609783 [details] [diff] [review]
> bug-1160139.0.patch
> 
> Review of attachment 8609783 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: lib/freebl/dh.c
> @@ +253,5 @@
> >          goto cleanup;
> >      }
> > +
> > +    /*
> > +     * We check to make sure that ZZ is not equal to 0, 1 or -1 mod p.  This
> 
> If ZZ is 0, then Yb is 0. But we already reject Yb == 0
> above, so ZZ cannot be 0.

I am leaving the check in, because the checks are cheap, and having both protects against either being accidentally removed.  But I added a note to the comment that they are redundant.


> @@ +263,5 @@
> > +     * We return MP_BADARG because this probably the result of a bad public
> > +     * value having been provided.
> > +     */
> > +    if (mp_cmp_d(&ZZ, 1) <= 0 ||
> > +        mp_cmp(&ZZ, &psub1) >=0) {
> 
> Nit: we can test mp_cmp(&ZZ, &psub1) == 0 here because ZZ has been
> reduced modulo p.

As above, leaving this as-is to be more conservative.


(In reply to Wan-Teh Chang from comment #8)
> (In reply to Richard Barnes [:rbarnes] from comment #6)
> > Created attachment 8609783 [details] [diff] [review]
> > bug-1160139.0.patch
> > 
> [...]
> > This patch adds the corresponding checks on the result of the DH computation
> > (g^xy) and the ECDH input public value.
> >
> > (The ECDH check, of course, is a pure optimization, since the output check
> > would catch this case.  But it does save us the effort of doing the point
> > multiplication in this case.)
> 
> It doesn't seem necessary to optimize this case.
> 
> Also, it seems that the DH output check should allow us to remove the
> DH input check for 1 and -1, right?

In principle, you're correct.  I am still inclined to leave all the checks in, though.  They're cheap.
Attachment #8609783 - Attachment is obsolete: true
Attachment #8612395 - Flags: review+
(Assignee)

Comment 10

2 years ago
n-i to :mt to get it in his queue to check in
Status: NEW → ASSIGNED
Flags: needinfo?(martin.thomson)

Comment 11

2 years ago
Comment on attachment 8612395 [details] [diff] [review]
bug-1160139.1.patch r=wtc

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

::: lib/freebl/dh.c
@@ +266,5 @@
> +     * We return MP_BADARG because this is probably the result of a bad
> +     * public value or a bad prime having been provided.
> +     */
> +    if (mp_cmp_d(&ZZ, 1) <= 0 ||
> +        mp_cmp(&ZZ, &psub1) >= 0) {

Getting the details correct in this kind of code demonstrates
the author understood every line of the code and eliminates any
suspicion that the author may have merely copied the following
code from above:

    if (mp_cmp_d(&Yb, 1) <= 0 ||
        mp_cmp(&Yb, &psub1) >= 0) {
        err = MP_BADARG;
        goto cleanup;
    }

So I think it is important to make the conditional
expressions exact. I wasn't worried about the cost
of the conditional tests.
I'm going to wait until you two sort this one out before landing anything.
Flags: needinfo?(martin.thomson)
(Reporter)

Comment 13

2 years ago
so I guess this did not land yet :)

Updated

2 years ago
Target Milestone: --- → 3.20

Comment 14

2 years ago
possibly related: bug 380351
(Assignee)

Comment 15

2 years ago
Created attachment 8634933 [details] [diff] [review]
bug-1160139.2.patch r=wtc

Making the last check precise, to address the outstanding comment from wtc.
Attachment #8634933 - Flags: review+
(Assignee)

Updated

2 years ago
Attachment #8612395 - Attachment is obsolete: true
(Assignee)

Updated

2 years ago
Keywords: checkin-needed

Comment 16

2 years ago
https://hg.mozilla.org/projects/nss/rev/a3a37589ba7d
Status: ASSIGNED → RESOLVED
Last Resolved: 2 years ago
Keywords: checkin-needed
Resolution: --- → FIXED
status-b2g-v2.1S: --- → affected
status-b2g-v2.2: --- → affected
status-b2g-v2.2r: --- → affected
status-b2g-master: --- → affected
status-firefox40: --- → wontfix
status-firefox41: --- → affected
status-firefox42: --- → affected
status-firefox-esr31: --- → wontfix
status-firefox-esr38: --- → affected

Comment 18

2 years ago
Asking because Ryan set "affected" flags:

Is Mozilla interested to have this fix backported to current/supported Firefox branches?

Currently, the fix has been applied to NSS 3.20 development only, which will most likely take another couple of weeks until it gets released.

If there's a desire to backport, we'd have to create a 3.19.2.x release (because we just devoted 3.19.3 for a CA update on mozilla 42 branch).
Flags: needinfo?(rlb)
I can't answer for Richard, but I don't see any reason why we would need this urgently.  I'd rather just take 3.20a or 3.21 as it comes out.  That has fixes for more serious issues in it.
Yeah, I just set the flags for tracking purposes. Can't see anybody getting horribly bent out of shape over a sec-moderate, though. Maybe Al or Dan feel differently, though.
We don't normally backport sec-moderates without a specific need.
Looks like comment 21 is enough.  Clearly n-i on Richard.
Flags: needinfo?(rlb)

Updated

2 years ago
Target Milestone: 3.20 → 3.21
status-b2g-v2.0: --- → wontfix
status-b2g-v2.0M: --- → wontfix
status-b2g-v2.1: --- → wontfix
status-firefox43: --- → affected

Updated

2 years ago
Group: core-security → core-security-release
status-b2g-v2.1S: affected → wontfix
status-firefox41: affected → wontfix
status-firefox-esr38: affected → wontfix
(Reporter)

Comment 23

2 years ago
given the fact nss 3.21 has been released is there any chance this issue can be set to public now ?
(Reporter)

Comment 24

2 years ago
should i take like a no :) ?
Flags: needinfo?(dveditz)
Group: core-security-release
status-firefox40: wontfix → ---
status-firefox41: wontfix → ---
status-firefox42: affected → wontfix
status-firefox44: --- → fixed
status-firefox45: --- → fixed
Flags: needinfo?(dveditz)
status-firefox43: affected → wontfix
Whiteboard: [adv-main44+]
Alias: CVE-2016-1936
"sec-moderate" overstates the harm here, and calling it "fixed" is somewhat misleading. We've added a reasonable sanity check in case the server is merely badly configured, but if the server is an actual attacker this won't help.

https://code.google.com/p/chromium/issues/detail?id=482950#c20
Keywords: sec-moderate → sec-low
You need to log in before you can comment on or make changes to this bug.