934545 - (CVE-2014-1491) Do not allow p-1 as a public DH value

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Antoine Delignat-Lavaud]

Attachment: Creating two TLS sessions with the same keys on different servers

User Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:25.0) Gecko/20100101 Firefox/25.0 (Beta/Release)
Build ID: 20131025151332

Steps to reproduce:

1. Create a TLS server supporting only the DHE key exchange.
2. During any handshake, send the parameters <p, g, g^q> where p=2q+1 is a prime such that q is also prime and g is not a quadratic residue mod p
3. NSS accepts this value and proceeds with the handshake. The PMS computed by NSS is g^(q*Kc)


Actual results:

NSS accepts to proceed with the exchange. If g is not a quadratic residue mod p, then g^q = p-1 which is not rejected by NSS as it accepts any public value in [2, p-1] (this is allowed by rfc2631). Then, the computed PMS g^(q*Kc) is 1 if Kc is even (because g^(2q)=g^(p-1)=1 [mod p]) and p-1 if Kc is odd (because g^q=p-1 [mod p]). If the server chose a Ks with the same parity, the PMS will be the same on the client and server but the communication is not safe because an attacker can derive it from the parameters sent over the network.


Expected results:

In itself, the impact of accepting <2p+1,g,g^p> is not too high, because these parameters are signed by the server certificate's public key and very few server will chose them.

However, our worry is the ability for a malicious website to send such parameters both to the client and to a victim server acting as man in the middle. This can allow a TLS session to the malicious server to be resumed on the victim server, which breaks Channel Bindings / Channel ID and can be combined with renegotiation in Chromium to break client authentication, among other things. This is discussed in Chrome bugs [305951, 306959, 305220] and is the main reason why this report should stay private for a short while.

Comment 1

[Antoine Delignat-Lavaud]

Attachment: degenerate_dh_openssl1.0.1e.patch

A patch for OpenSSL 1.0.1e to always send degenerate DHE parameters.

Comment 2

[Antoine Delignat-Lavaud]

Technical reference (NIST 800-56A, Section 5.6.2.4):
http://csrc.nist.gov/publications/nistpubs/800-56A/SP800-56A_Revision1_Mar08-2007.pdf

Latest versions of OpenSSL and GnuTLS do not accept p-1, but some previous versions did for both, and about 15% of Alexa top10k webservers will accept p-1 as well.

Comment 3

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

My understanding is that agl is going to fix this, based on email I received from Karthikeyan Bhargavan.

Comment 4

[Adam Langley]

Attachment: patch

This patches freebl to ensure that DH public values are not 0, 1, p-1 nor >= p. This duplicates some checks in ssl3con.c, but I think that's ok.

Comment 5

[Antoine Delignat-Lavaud]

I was going to post that k*p+1 is also accepted (with PMS=1) but you clearly noticed that already.

Comment 6

[Antoine Delignat-Lavaud]

Apparently, there is no primality test on p, thus parameters such as <2p, g, p> are also accepted.

Comment 7

[Adam Langley]

(In reply to Antoine Delignat-Lavaud from comment #6)
> Apparently, there is no primality test on p, thus parameters such as <2p, g,
> p> are also accepted.

Yes, this only protects the server (which chooses p itself), not the client. I believe that protecting the server is sufficient as it prevents an attacker from seeding a session with a chosen master key at both sides.

Primality testing would just be a sanity check in any case. Primality tests are fine for testing a random number but they are not adversarial checks. An attacker could still send a pseudoprime that passes the tests. An adversarial check would involve implementing the AKS test(?) and I suspect that wouldn't be sufficiently performant.

Comment 8

[Daniel Veditz [:dveditz]]

From the description this sounds sec-high for Chrome at least. I assume Firefox works the same way, although I don't know if this needs to be combined with chrome-specific behavior to achieve the worst case.

Comment 9

[Adam Langley]

(In reply to Daniel Veditz [:dveditz] from comment #8)
> From the description this sounds sec-high for Chrome at least.

I might have missed something, but I think the issue with Chromium is that Chromoting uses a channel-binding like system for authentication and we need to bandaid it to prevent these session-fixation attacks. I think it falls somewhere like sec-medium for us.

I'm not sure whether this is an issue for Firefox.

Comment 10

[Antoine Delignat-Lavaud]

On its own, this is not really a security issue, in fact all browsers currently accept at least one kind of degenerate parameters. However, it can become problematic when mixed with TLS level authentication features or other TLS bugs in Chromium. As far as we know there is no direct impact on Firefox.

Comment 7 raises a very good point. It seems that with a probabilistic primality check, a malicious server can send a pseudo-prime and public key such that it passes all checks and results in a degenerate PMS. However, isn't it possible to instead check after receiving <p,g,g^Ks> that g^KcKs is not weak? What matters for an attacker is the PMS that the client stored, and the fact that the KDF in TLS has the bad idea to remove leading zeros from the PMS (which has the effect of making p and g irrelevant to its value).

Yet, a probabilistic check on the public server key is not completely useless, as it is always possible given <p,g,g^Ks> to create a q such that the parameters <q,g,g^Ks> result with high probability in the client storing a PMS of g^Ks (this is useful to a MITM because it can always have a server use this value as a PMS by sending g).

There are various ways to create such a q from legitimate parameters <p,g,K>. An easy one that we implemented and tested is q=K²-1. When Firefox or Chrome receives <K²-1,g,K> there is a high chance that K^Kc=K mod K²-1, and thus a PMS of K is stored. Thus, without a primality test, there is no real reason not to accept K=1 or K=p-1. TLS is also at fault for not including p and g in the PMS computation.

Comment 12

[Karthikeyan Bhargavan]

(In reply to Adam Langley from comment #7)

> Yes, this only protects the server (which chooses p itself), not the client.
> I believe that protecting the server is sufficient as it prevents an
> attacker from seeding a session with a chosen master key at both sides.

Only to an extent. Comment 10 presents the following attack, let me elaborate:

S chooses (p, g, K = g^x) and sends it to A
A forwards (K^2-K, g, K) and sends it to C   [i.e. it changes the p value to K^2-K]
C chooses g^y mod (K^2-K) and sends it to A
A forwards g to S

So, C and A will end up with pms = K^y mod (K^2 - K) = K
And A and S will end up with pms = K^1 = K

So even if the server is completely honest and does all its checks, A can force C to have the same master secret.

This attack works very well on Firefox and Chrome.
For some other clients (e.g. openssl), you have to ensure that the resulting prime is odd, or else the BN library crashes. In that case, A can find a K^z mod p value that is even (easy) and pick the p-value K^2 - 1.
If C picks an even y (50% chance), the attack still works as described above.

In summary, this means that absent full-primality checking at the client (which I understand is expensive),
DHE master secrets are completely at the mercy of the server. A server could advertise perfect forward secrecy
by accepting DHE cipher suites, but in fact force every single client to use the same premaster secret.



> 
> Primality testing would just be a sanity check in any case. Primality tests
> are fine for testing a random number but they are not adversarial checks. An
> attacker could still send a pseudoprime that passes the tests. An
> adversarial check would involve implementing the AKS test(?) and I suspect
> that wouldn't be sufficiently performant.

Comment 13

[Adam Langley]

> that absent full-primality checking at the client (which I understand is expensive)

Sadly, it appears to be not just expensive, but infeasible:

AKS:

"Our implementation was able to determine primality for bitlengths on the order of 64 bits in a few hours"
http://www.uploadtak.com/images/b3357_Salembier_Southering.pdf

There appears to be a deterministic version of Miller-Rabin: http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

However, the complexity of Õ((log n)4) does not sound like it's reasonable for ~2048-bit numbers.

So this line of inquiry appears to be nonsense. Let's fix session resumption to hash in a hash of the original handshake. Do you have a design for that lying around?

Off the top of my head, we can require the client and server to store the handshake hash of the original handshake in the session state. Then mix that into the master_secret calculation with the nonces? Indicate with an extension and refuse to interoperate with servers that don't use the extension when doing something channel bindings like?

Comment 14

[Karthikeyan Bhargavan]

I agree, primality testing is out.

We have two designs we're trying out in openssl, both sound like something you're describing above.

1. An "extended master secret computation" extension, that computes the master secret as:
   ms = prf(pms,"master secret",<hash of handshake log up to ClientCCS>)

2. A "secure resumption indication" extension that kicks in during session resumption only.
   The session state/ticket stores the handshake hashes of the original handshake.
   During resumption, the ClientHello and ServerHello echo the handshake hashes stored for the session.
   
It seems that there is support from the TLS WG and implementors (e.g. openssl) for one or both of these.
And both seem very easy to patch in to openssl, maybe also to NSS?

To fix renego and protocols using channel bindings (e.g. SASL), 2 may suffice.

I personally like 1, because I think it makes all handshakes safer and the crypto agility proofs easier.
(For every ciphersuite/protocol version/DH group/server cert, we are guaranteed a different key, so the possibility of cross protocol attacks and downgrade attacks diminishes.)

Plus, for PEAP and other protocols relying on the master secret being unique, 1 may be the only good option.

Comment 15

[Karthikeyan Bhargavan]

I agree, primality testing is out.

We have two designs we're trying out in openssl, both sound like something you're describing above.

1. An "extended master secret computation" extension, that computes the master secret as:
   ms = prf(pms,"master secret",<hash of handshake log up to ClientCCS>)

2. A "secure resumption indication" extension that kicks in during session resumption only.
   The session state/ticket stores the handshake hashes of the original handshake.
   During resumption, the ClientHello and ServerHello echo the handshake hashes stored for the session.
   
It seems that there is support from the TLS WG and implementors (e.g. openssl) for one or both of these.
And both seem very easy to patch in to openssl, maybe also to NSS?

To fix renego and protocols using channel bindings (e.g. SASL), 2 may suffice.

I personally like 1, because I think it makes all handshakes safer and the crypto agility proofs easier.
(For every ciphersuite/protocol version/DH group/server cert, we are guaranteed a different key, so the possibility of cross protocol attacks and downgrade attacks diminishes.)

Plus, for PEAP and other protocols relying on the master secret being unique, 1 may be the only good option.

Comment 16

[Antoine Delignat-Lavaud]

(In reply to Adam Langley from comment #13)
> So this line of inquiry appears to be nonsense.

Going back to the topic of this bug, we initially thought that with simple parameter validation, DHE could prevent the same PMS being used on different TLS connections.

Our conclusion is now that it is not the case, and in addition, clients are not guaranteed any secrecy of communications with a server that picks a bad DH group, even against a purely passive network attacker (such as the NSA) that doesn't control the server.

This is an interesting finding that should be documented for cases where it may matter, but as far as NSS is concerned, it seems nothing can be done. Thus, this bug can be closed and discussion continue on the relevant Chromium bugs.

Comment 17

[Adam Langley]

(In reply to Karthikeyan Bhargavan from comment #15)
> We have two designs we're trying out in openssl, both sound like something
> you're describing above.

(2) appears to be what I was thinking of, but I like (1) also. Hopefully we can bring ekr and other IETF folks to pick one. Both sound pretty easy to implement in NSS and I can do that if need be.

Comment 18

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Adam, do you think that it isn't worth doing the bounds checking either? It seems strange that we already are checking these edge cases *except* for (p-1). If the bounds checking is worthless then we should at least add a comment about why we avoid doing the bounds checking even though SP800-56A "requires" it.

Comment 19

[Adam Langley]

bsmith: I think the patch is probably independently a good idea. The rejection of zero and one was to address a cross-protocol attack by Nikos Mavrogiannopoulos where a ServerKeyExchange for P384 ECDHE can be used in place of a DH ServerKeyExchange. p-1 wasn't a problem in that case and we didn't have the bigint library to hand. But we might as well land this change where we do.

Comment 20

[Robert Relyea]

> Going back to the topic of this bug, we initially thought that with simple parameter validation,
> DHE could prevent the same PMS being used on different TLS connections.

Right, It's still probably good to check for the degenerate groups, but checking for the small all subgroups is a bit much, so at some point we need to trust the pgy parameters sent by the server. DSA has a solution for this (generators to create pq and g).

The current thought in that world is that probabilistic prime checks are fine, but you need to either do a lot of them, or mix their types up to prevent well chosen psuedo-primes. FIPS -186-4 has recommendations for pqg checks for DSA, though DSA is easier because you are given q (such that p=k*q+1, q is a prime of a minimum size), so its easy to check if g is in the subgroup q.

bob

bob

Comment 21

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

Wan-Teh, can we get a review on the patch for this?

Comment 22

[Wan-Teh Chang]

Comment on attachment 827004 [details] [diff] [review]
patch

I will post a patch with minor improvements.

Comment 23

[Wan-Teh Chang]

Attachment: patch v2, by Adam Langley

Adam: I made the following changes.

1. |pMinus1| was renamed |psub1|, which is used in other freebl code.
2. Added CHECK_MPI_OK around the mp_sub_d call.
3. I merged the four comparisons:

    Yb == 0, Yb == 1, Yb == p-1, Yb >= p

into just two:

    Yb <= 1, Yb >= p-1.

This matches NIST SP 800-56A, Section 5.6.2.4, Step 1:

    1. Verify that 2 <= y <= p-2.

Patch checked in: https://hg.mozilla.org/projects/nss/rev/12c42006aed8

Comment 24

[Wan-Teh Chang]

Comment on attachment 8346903 [details] [diff] [review]
patch v2, by Adam Langley

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

Adam: this link shows my changes to your patch:
https://bugzilla.mozilla.org/attachment.cgi?oldid=827004&action=interdiff&newid=8346903&headers=1

Comment 25

[Paul Theriault [:pauljt] (no longer reading bugmail)]

I don't know if this is possible to backport to b2g18, but would seem to be like a patch we should include if we are making a 1.1.1 release.

Comment 26

[Ryan VanderMeulen [:RyanVM]]

(In reply to Paul Theriault [:pauljt] from comment #25)
> I don't know if this is possible to backport to b2g18, but would seem to be
> like a patch we should include if we are making a 1.1.1 release.

Bug 898431 is requesting to update NSS to version 3.15.4 on all supported branches, which would pickup this fix with it.

Comment 27

[Daniel Veditz [:dveditz]]

Lowering security severity to moderate after discussing w/NSS folks. We will only accept a problematic p=1 parameter from servers who's cert we trust. They can mistakenly end up with a less secure channel than they intended but this isn't something an external party can use to attack Firefox users with (if the server you're talking to is malicious then the security of the TLS channel isn't your main problem).

Comment 28

[Antoine Delignat-Lavaud]

(In reply to Daniel Veditz [:dveditz] from comment #27)
> Lowering security severity to moderate after discussing w/NSS folks. We will
> only accept a problematic p=1 parameter from servers who's cert we trust.
> They can mistakenly end up with a less secure channel than they intended but
> this isn't something an external party can use to attack Firefox users with
> (if the server you're talking to is malicious then the security of the TLS
> channel isn't your main problem).

While I agree this is a sec-moderate problem, I disagree with your assertion that "this isn't something an external party can use to attack Firefox users with". Key exchange messages are in the clear and if an eavesdropper sees a server sending p-1 in its ServerKeyExchange message, the connection can be decrypted.

Comment 29

[u279076]

Matt, is this something that needs to be tested by QA before Firefox 27 is released?

Comment 30

[Matt Wobensmith [:mwobensmith][:matt:]]

Anthony: from what I gather, testing would not be trivial and we don't have much time.

Comment 31

[Matt Wobensmith [:mwobensmith][:matt:]]

Antoine, have you by any chance had the opportunity to review the patch? We'd appreciate your input, if you have any.

Comment 32

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

What is the date when we will no longer need to keep this hidden?

Comment 33

[Antoine Delignat-Lavaud]

I approve this patch, the check it adds definitely needs to be there.

Comment 34

[u279076]

[qa-] as per comment 30.

Comment 35

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

Antoine, should we write an advisory for this since we've fixed this in the next release or keep this hidden until your paper is published? If the latter, when will it be published?

Comment 36

[Daniel Veditz [:dveditz]]

I saw dkeeler landed NSS 3.15.4 on the ESR-24 branch so this should be fixed there.

(In reply to Antoine Delignat-Lavaud from comment #28)
> I disagree with your assertion that "this isn't something an external party can
> use to attack Firefox users with".

This is what I meant by ending up with a less secure channel. If the trusted server is being stupid it could redirect to the non-SSL version of the site and be 100% in the clear. Yes, it affects Firefox users but it's more a bug in the server than an attack on Firefox.

Comment 37

[Antoine Delignat-Lavaud]

(In reply to Al Billings [:abillings] from comment #35)
> Antoine, should we write an advisory for this since we've fixed this in the
> next release or keep this hidden until your paper is published? If the
> latter, when will it be published?

Our concern is not really the publication of our paper in May but the fact that other libraries, such as SChannel (IE) or Secure Transport (Safari) have similar or worse problems with DH parameter validation. That being said, it's actually unlikely that Apple will fix this (we previously reported bigger issues with their TLS implementation that never got addressed) so it would make sense if you decided to patch this for FF27.

Comment 38

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

(In reply to Antoine Delignat-Lavaud from comment #37)
> That being
> said, it's actually unlikely that Apple will fix this (we previously
> reported bigger issues with their TLS implementation that never got
> addressed) so it would make sense if you decided to patch this for FF27.

This is already patched. This is about whether or when we write a public advisory.

Comment 39

[Antoine Delignat-Lavaud]

(In reply to Al Billings [:abillings] from comment #38)
> This is already patched. This is about whether or when we write a public
> advisory.
A patch like this one is as good as any advisory. I don't think it makes much sense to leave it out of the release notes when it's in the source code.

Comment 40

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

Not everything in the source code gets an advisory.

If you don't feel a need to keep it undisclosed while other vendors are vulnerable, we'll have a discussion about what we want to do with an advisory.