1160139 - (CVE-2016-1936) Small subgroup attack

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Antonio Sanso]

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

Comment 1

[Martin Thomson [:mt:]]

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.

Comment 2

[Antonio Sanso]

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

[Wan-Teh Chang]

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?

Comment 4

[Martin Thomson [:mt:]]

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.

Comment 5

[Richard Barnes [:rbarnes]]

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?

Comment 6

[Richard Barnes [:rbarnes]]

Attachment: 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.)

Comment 7

[Wan-Teh Chang]

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.

Comment 8

[Wan-Teh Chang]

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

Comment 9

[Richard Barnes [:rbarnes]]

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

Comment 10

[Richard Barnes [:rbarnes]]

n-i to :mt to get it in his queue to check in

Comment 11

[Wan-Teh Chang]

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.

Comment 12

[Martin Thomson [:mt:]]

I'm going to wait until you two sort this one out before landing anything.

Comment 13

[Antonio Sanso]

so I guess this did not land yet :)

Comment 14

[Kai Engert [:KaiE:]]

possibly related: bug 380351

Comment 15

[Richard Barnes [:rbarnes]]

Attachment: bug-1160139.2.patch r=wtc

Making the last check precise, to address the outstanding comment from wtc.

Comment 16

[Kai Engert [:KaiE:]]

https://hg.mozilla.org/projects/nss/rev/a3a37589ba7d

Comment 18

[Kai Engert [:KaiE:]]

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

Comment 19

[Martin Thomson [:mt:]]

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.

Comment 20

[Ryan VanderMeulen [:RyanVM]]

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.

Comment 21

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

We don't normally backport sec-moderates without a specific need.

Comment 22

[Martin Thomson [:mt:]]

Looks like comment 21 is enough.  Clearly n-i on Richard.

Comment 23

[Antonio Sanso]

given the fact nss 3.21 has been released is there any chance this issue can be set to public now ?

Comment 24

[Antonio Sanso]

should i take like a no :) ?

Comment 25

[Daniel Veditz [:dveditz]]

"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