Hal Finney: secp256k1
2011 Jan 9
See all posts
Hal Finney: secp256k1 @ Satoshi Nakamoto
- Author
-
Hal Finney, Mike Hearn
- Email
-
satoshinakamotonetwork@proton.me
- Site
-
https://satoshinakamoto.network
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.
Reply of Mike
Hearn, January 09, 2011, 01:04:21 PM
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.
Reply of
Gavin Andresen, January 09, 2011, 05:44:15 PM
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....
Reply of Mike
Hearn, January 09, 2011, 08:46:12 PM
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.
Reply of Mike
Hearn, January 10, 2011, 10:35:03 AM
I believe the key factor in the choice of curve, size and indeed ECC
itself was the size of the block chain - which is ultimately based on a
set of educated guesses. The key.h file has a list of signature sizes at
the top along with a comment that the script system can encode
signatures of up to 75 bytes with a single size opcode. It's hard to
know if that's the reason or not but it seems likely.
Becoming fully generic would mean encoding curve parameters into ...
where? Addresses? Scripts and thus the block chain? All of those would
make transactions much much larger and reduce the scalability of the
network as a result. We know Satoshi cares a lot about block chain size,
this is why we cannot embed messages into transactions.
/mike
Reply of Mike
Hearn, January 11, 2011, 10:31:40 PM
I discussed this with Satoshi. There is no particular reason why
secp256k1 is used. It just happened to be around at the time.
However it sounds like there's no real consensus that the k1 curve is
really a terrible thing and indeed it may even be helpful in future as
ECDSA verification is the primary CPU bottleneck for running a network
node. So if Koblitz curves do indeed perform better we might end up
grateful for that in future ...
Hal Finney: secp256k1
2011 Jan 9 See all postsHal Finney, Mike Hearn
satoshinakamotonetwork@proton.me
https://satoshinakamoto.network
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.
Reply of Mike Hearn, January 09, 2011, 01:04:21 PM
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.
Reply of Gavin Andresen, January 09, 2011, 05:44:15 PM
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....
Reply of Mike Hearn, January 09, 2011, 08:46:12 PM
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.
Reply of Mike Hearn, January 10, 2011, 10:35:03 AM
I believe the key factor in the choice of curve, size and indeed ECC itself was the size of the block chain - which is ultimately based on a set of educated guesses. The key.h file has a list of signature sizes at the top along with a comment that the script system can encode signatures of up to 75 bytes with a single size opcode. It's hard to know if that's the reason or not but it seems likely.
Becoming fully generic would mean encoding curve parameters into ... where? Addresses? Scripts and thus the block chain? All of those would make transactions much much larger and reduce the scalability of the network as a result. We know Satoshi cares a lot about block chain size, this is why we cannot embed messages into transactions.
/mike
Reply of Mike Hearn, January 11, 2011, 10:31:40 PM
I discussed this with Satoshi. There is no particular reason why secp256k1 is used. It just happened to be around at the time.
However it sounds like there's no real consensus that the k1 curve is really a terrible thing and indeed it may even be helpful in future as ECDSA verification is the primary CPU bottleneck for running a network node. So if Koblitz curves do indeed perform better we might end up grateful for that in future ...