942585 - Review elliptic curves and implement new ones

Status: RESOLVED INVALID

(NSS :: Libraries, defect)

Description

[Florian Bender]

As a fallout of the NSA affair, there is rumor (and some preliminary evidence) that the NSA / NIST recommends elliptic curves that only provide weak security. As a result, some people are recommending against all forms of ECC, though this may leave many people with only weak algorithms to chose from to encrypt their traffic. 

Because we don't know if and what ECs use parameters that make them deliberately weak, and how much of an (cryptographic) impact this results in, I kindly ask you to review the ECs used in NSS (for TLS et al.), and consider implementing curves that are recommended by other parties than the NSA or NIST, and possibly prioritize them (at least in non-FIPS-mode).

E.g., the secp{256,384,521}r1 curves are under suspicion, while Curve25519 is being considered for at least one product (see https://twitter.com/akureiwolf/status/400408161758113792). 

This is a precautionary measure to gain flexibility, and possibly divert attacks on TLS, now and in the future.

(Please move bug if this is the wrong category. This bug is a result of http://www.reddit.com/r/privacy/comments/1q9p2l/nsasafer_choices_for_firefox/ et al.)

Comment 1

[Florian Bender]

(Adding some bugs that are similar though not directly connected to the NSA affair.)

Comment 2

[mail]

As a quick fix I suggest moving to the secp256k1 Koblitz-curve. That's the one Bitcoin uses [1].
Ultimately I would love to see FF move to Curve25519 and the likes [2][5].

Silent Circle are at the moment working on a secp384r1 replacement / a non-NIST cipher suite [3].

Some Quotes:

> I no longer trust the [NIST Elliptic Curves] constants. I believe
> the NSA has manipulated them through their relationships with
> industry.
--Bruce Schneier[4]

> The possibility of attackers manipulating standard curve choices was
> raised in the late 1990s, when NSA volunteered to "contribute"
> elliptic curves to the committee producing ANSI X9.62. NSA did in
> fact end up producing various elliptic curves later standardized by
> ANSI X9.62, SEC 2, and NIST FIPS 186-2; these curves were
> subsequently deployed in many applications.
> 
> In response to NSA's contributions, ANSI X9.62 developed "a method
> for selecting an elliptic curve verifiably at random", and a
> procedure to "verify that a given elliptic curve was indeed generated
> at random"; it even claims that this procedure "serves as proof
> (under the assumption that SHA-1 cannot be inverted) that the
> parameters were indeed generated at random". However, this procedure
> does not verify randomness; it verifies only that the curve
> coefficients were produced as SHA-1 output. The claimed "proof" is
> nonexistent. The ANSI X9.62 curve-generation method is not trivially
> manipulatable but it is manipulatable.
> 
> IEEE P1363 copied the same curve-generation method and stated that it
> allows "others to verify that the curve was indeed chosen
> pseudo-randomly". However, "pseudo-random" is not the same as
> "random", and does nothing to stop a malicious curve generator from
> searching through many choices of seeds. NIST correctly characterized
> the verification procedure for these curves as merely checking "that
> the coefficient b was obtained from s via the cryptographic hash
> function SHA-1".
>
> SEC 2 version 1.0 copied the curves that NSA had produced for NIST,
> and copied the incorrect ANSI X9.62 claim that the curves were
> "chosen verifiably at random". SEC 2 further claimed that the curves
> were chosen "by repeatedly selecting a random seed and counting the
> number of points on the corresponding curve until appropriate
> parameters were found". This claim might be correct but is certainly
> not verifiable." 
--Daniel J. Bernstein[6]

Sources:
[1] http://bitcoinmagazine.com/7781/satoshis-genius-unexpected-ways-in-which-bitcoin-dodged-some-cryptographic-bullet/
[2] http://safecurves.cr.yp.to/
[3] http://silentcircle.wordpress.com/2013/09/30/nncs/
[4] https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929
[5] http://eprint.iacr.org/2013/647.pdf
[6] http://safecurves.cr.yp.to/rigid.html

Additional Sources:
http://it.slashdot.org/story/13/09/11/1224252/are-the-nist-standard-elliptic-curves-back-doored
http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf

Comment 3

[mail]

secp256k1 is already implemented in NSS, that's why I would suggest it as a quick fix. The fix should be as simple as changing some #defines in the source code.

It is IMPORTANT to note, that secp256k1, too, is flawed, though it does not suffer from the unexplained seed problem.
Ultimately some of the Safe Curves from [http://safecurves.cr.yp.to/] should be used. This would require openssl and co. to add new safe curves, too. Also TLS 1.2 allows for only a few named curves: [https://tools.ietf.org/html/rfc4492#section-5.1.1], but there's always the "arbitrary_explicit" option to support any curve.

Comment 4

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

Please move the discussion of what curves to support in NSS and/or Firefox back to the dev-tech-crypto mailing list. When we have some conclusions, we can file more specific bugs the implement the agreed-upon changes.

Information about subscribing to and accessing dev-tech-crypto can be found here:
https://lists.mozilla.org/listinfo/dev-tech-crypto

Comment 5

[mail]

Attachment: nss_secp256k1_only.patch

For the people finding this entry via search engine in the future: This is a patch that forces Firefox to only use secp256k1.