Topic: secp256k1 - page 2. (Read 29324 times)

I'm not aware of any academic cryptography papers that refer to any curves over prime fields as Koblitz curves. The standards bodies publications do not count as academic papers and I believe that their inclusion of "k" in the name is idiosyncratic.
Indeed the standard states "Here ..[the term "Koblitz"] is generalized to refer also to curves over F_p which possess an efficiently computable endomorphism. [Allong the lines of the paper of Gallant, Lambert and Vanstone "Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms"]
This scheme tends to be referred to in the literature as the "GLV method"

When selecting appropriate cryptography you can vary the "size" parameter which has an obvious effect on security. You can also vary the "peculiarity" paramter which can substantially increase the speed at the cost of a small reduction in the effective "size". Before worrying whether the special nature of the secp256k1 curve loses a few bits of security relative to a random curve we need to examine what reasoning informed the selection of a 256bit curve. Possibly a 224 bit or 192 bit curve would have been perfectly satisfactory. That being the case, the theoretical loss of security due to the special nature of the secp256k1 curve is inconsequential while the speed increase is still useful.

I forsee a general trend towards the use of more specialized curves over the vanilla random elliptic curves as the performance gains are substantial. This is comparable to the shift away from vanilla RSA towards the more specialized ECC in return for shorter keys, that happened about ten years ago.

I see little justification for retiring secp256k1 without a complete redesign of Bitcoin to address existing deficiencies in scalability and implementation security. Future schemes, however, should avoid hard-coding any particular implementation of the essential cryptographic primitives.


ByteCoin

Satoshi does communicate both over email and this forum. I've had several good conversations with him about aspects of the BitCoin system.

Changing curves would mean a new address version (easy), a new OP_CHECKSIG equivalent for the new curve and a network upgrade to understand both of these. Anything else I forgot?

/mike

OMG. Would anyone mail Satoshi to inform him of the existence of this forum?

Sorry for being bitter, but this is becoming frustrating.

It's still worth considering a move away from secp256k1 as changes like this are much easier to make in the projects early days than later, and to be convincing the cryptography behind BitCoin must be unquestionable. If one day BitCoin has hundreds of thousands of users we don't want people using this as a club to beat us over the head with.

That said Gavin is totally right that compared to other security problems BitCoin has (malware, DoS) this one sounds kind of trivial.

How about suggesting a rollout schedule to Satoshi and seeing what he thinks? Implementation wise it'd not be a huge burden, I think.

BTW Chris, you can use Bouncy Castle on Android, you just have to use the lightweight API and rename it to not have the same package names. A good IDE can do this automatically.

Finding an implementation in Java that would not conflict with the BC version on Android was a bit hard, but I found flexiprovider[1] which has a decent implementation in Java, no idea if they use some of the speedup tricks. But for mobile devices being able to verify transactions involving my own address is a must have, and then using a simpler/faster algorithm would make sense :-)

[1] http://flexiprovider.de/

I agree with mh-- if there are real compatibility issues or weaknesses, then those would be a good reason to switch curves.

If there aren't, sep256k1 seems plenty good enough for the forseeable future.  I think most programmers (myself included) have a tendency to worry about small-probability "what if" problems that we know how to solve, when we'd be better off thinking about high-probability problems that we don't want to think about because we don't already know how to solve them.

Like multifactor wallet authentication so trojans don't steal users' wallets....

Have you mailed Satoshi to ask him? I would be interested in why this was chosen too. Unfortunately I didn't really get solid answers last time I asked Satoshi to explain the choice of a few implementation details (eg why 21M coins, answer "educated guess") but maybe you'd have better luck.

BitCoin addresses already have version codes in them, so it wouldn't technically be too hard to switch curves for newly created keys - just a matter of waiting long enough for people to upgrade their clients. I don't think it's likely support for old addresses would ever be removed, being able to do a full block chain verification is likely to be a feature desired by any non-thin client implementor.

That said, there should be a strong rationale. Lack of support doesn't seem to be a good enough reason. I have a Java implementation based on Bouncy Castle working fine with this curve, and helmut in IRC mentioned he had it working in Python too. Worst case you have to specify the parameters to the library yourself, but this isn't hard.

The possibility of an attack on Koblitz curves is a stronger reason, even if it's only a perceived risk rather than a credible one. Support could be phased in slowly over time, for instance, clients could be programmed to start creating secp256r1 keys by default a year after their introduction as measured in block time. This would reduce the disruption significantly.

Bitcoin uses elliptic curve cryptography for its keys and signatures, but the specific curve used is pretty unusual. It is called secp256k1, from a standard called SEC2, published by a group called SECG, http://www.secg.org/index.php?action=secg,docs_secg.

Taking the name secp256k1 apart, sec comes from the standard, p means that the curve coordinates are a prime field, 256 means the prime is 256 bits long, k means it is a variant on a so-called Koblitz curve, and 1 means it is the first (and only) curve of that type in the standard. This is all fine and common, except for the Koblitz part. Koblitz curves are a special kind of elliptic curves that have some internal structure that can be used to speed up calculations. Standards bodies have tended to shy away from Koblitz curves out of fear that this internal structure could someday be exploited to yield a new attack. Indeed certain Koblitz curves, but not secp256k1, lose a couple dozen bits of security to a known attack.

Most standards use what are called random curves when they are using prime fields. SEC2 also includes random curves, and the very next one after secp256k1 is called secp256r1. This curve, secp256r1, is widely standardized and used, including by the U.S. government, which calls it P-256.

I don't know the rationale behind using secp256k1. It has the potential for speed - I've seen estimates from 33% to 50% speedup - but the techniques are quite esoteric as it is not a conventional Koblitz curve, and I doubt that the OpenSSL implementation exploits this. I'm not losing much sleep over the theoretical possibility of an attack on secp256k1, but it is likely to be less widely implemented. I looked at BouncyCastle, a widely used Java crypto library, and they had commented out the code for secp256k1. Whereas secp256r1 (P-256) might well be a default curve for the native crypto keys in future OS's.

It wouldn't be a change to make lightly, but we might want to consider changing to this more widely used standard curve. We'd have to mark the new keys to distinguish them, and be prepared to handle both kinds of signatures.

One question is whether we would ever reach a point where clients could eliminate support for the old curve? Maybe just miners could retain support, and the fact that a transaction got into a block with some confirmations would be good enough evidence that it was valid.