Use of questionable NIST EC

[taltman]

PassLok uses the NIST 521 curve. All modern crypto apps have standardized on the vetted curve 25519 by cryptographer DJB:

http://cr.yp.to/ecdh.html

It's not clear why PassLok uses this curve, when other crypto platforms have moved away from it. Only DoD and related orgs demand FIPS compliance, and thus NIST curves.

[fruiz500]

Curve 25519 uses keys that are only 255 bits long. Besides code tampering at the source, I believe the weakest point in PassLok is brute-force reversal of public-key generation. Keylength.com shows 256-bit elliptic curve functions to be as "strong" in a broad computational sense, as AES-128, while 512-bit elliptic curves are considered comparable to AES-256. Since PassLok uses AES-256 exclusively, I chose an elliptic curve of comparable strength. The only one supported by SJCL at the moment is the NIST p521 curve.

I've read up on the reasons why people are moving away from NIST-standardized curves and I find them excessively paranoid. The argument is that the initial point and r parameter (I think it's called the "order") for this curve were chosen by a person who was a NSA employee at the time. Since no explanation was given for the choice, there is a suspicion that there may be a secret weakness just waiting to be exploited.

On the other hand, the standard was published in 1999, some time before NSA got seriously into the business of weakening standards (or at least, that's what I see in the EFF timeline of government actions). This standard was defined for their own use, too. It would seem stupid in the extreme to be using parameters that you know are weak, waiting for someone else to discover the weakness. In the intervening years, no such weakness has been reported for the NIST curves, as far as I know.

I've also been looking into some of the curves presented at http://safecurves.cr.yp.to. Curve E-521 uses the same Mersenne prime modulus as the NIST curve, but is of a form that is not currently supported by SJCL. Curve M-511 may be supported with some small changes in the SJCL code and uses keys that are nearly as long, but its modulus does not appear to have the cool property (see the current PassLok technical document at http://passlok.weebly.com/uploads/2/4/1/8/24187628/passlok_technical_document.pdf) that makes taking a square root real easy by the Tonelli-Shanks algorithm, thereby shortening public keys by half.

This is a very interesting discussion. Let's keep it open for a while.

[taltman]

Agreed. I am learning here, too. At the very least I think it is important to put this in a FAQ on the weebly site, along with the corresponding section in the technical documentation. That way, when someone asks, "why not Curve 25519?", instead of them thinking that the selection was naive, they'll see that there's a justification.

[fruiz500]

I've submitted a pull request to have the parameters of the NIST p521 curve merged into the SJCL master, and it has been accepted right away. I'll add a section to the PassLok technical document along the lines of this discussion.

[taltman]

Wow, that's great news!

Yes, I think it would be a good section to include, as interested amateurs like myself might wonder why you're not using Curve25519, like TextSecure. This might be a good discussion to have on ModernCrypto's ECC mailing list.

[fruiz500]

There is a short discussion on this in the next version of the technical document, which I will upload soon. Another reason for not using Curve25519 that I've found out recently is that this curve does not support DSA just yet.

[taltman]

TextSecure gets by without DSA using Curve25519 with a triple-DH exchange:

https://whispersystems.org/blog/simplifying-otr-deniability/

[fruiz500]

I see that TextSecure manages to provide authentication by doing Diffie-Hellman three times. Interesting. Now, TextSecure can afford to exchange several pieces of data back and forth because it is a real-time chat app. PassLok, on the other hand, is conceived as a one-shot deal to supplement conventional email. But in any case, the use of DSA in PassLok is independent of messaging. It's just one more tool in the kit.

[fruiz500]

I have been doing a lot of thinking about this. In essence, the EC discrete logarithm problem can be solved with a computational complexity of 2^(bitsize/2). That is, using the p521 curve the strength is comparable to 160 bits, using curve25519, the strength would be about 127 bits.

Which in any case is a lot bigger than the strength derived from the user-supplied key. In Advanced mode, PassLok displays a value for key entropy, which I believe is quite accurate. Working pretty hard at it, I can barely make a memorable key with more than 80 bits of entropy. So the actual weak point is the user-generated key, even with key stretching, because no key stretching algorithm can compensate for such a large difference: 127 - 80 = 47 bits in the best case, and then 2^47 = 140 trillion. That is, the key derivation function would have to slow down the key generation process by a 140 trillion times in the best case, in order to make it not weaker than the next weaker component, which is the elliptic curve. Nobody is going to wait that long.

Therefore, I'm preparing to move to curve25519 for the next version, since it looks like using p521 is overkill and is not going to add any security in real terms. I just forked the p521 version in order to preserve it, and the next main brach will be based on curve25519 instead. Expect lots of changes.

[fruiz500]

Version 2.2 has just been pushed. It uses Curve25519 rather than the NIST p521 curve. As a result the code is significantly faster. Security is not really reduced because the weak point is the user-memorized Key, which usually has low entropy. In order to improve matters somewhat, a larger number of SCRYPT iterations are used.