Bitcoin’s Public-Key Security Level

[nullius]

In a number of threads, I have observed confusion over the security level of the of the secp256k1 elliptic curve used by Bitcoin’s public keys.  Following is an image of Table 1 at page 8 of the pertinent standard (PDF).  I have added a red arrow pointing to the line matching what Bitcoin uses.  The two most important columns here are “Strength”, representing the security level of the algorithm, and “Size”, the actual key size in bits.  The strength equivalence to RSA/DSA is a vexed estimate I would prefer to mostly ignore here.

Thus, as you can see, Bitcoin’s public-key crypto uses 256-bit keys but is deemed to have a 128-bit security level.  I will briefly explain what that means.

If an attacker were to use a bruteforce attack, trying keys one by one, that would require on the order of 2²⁵⁶ work.  (I here ignore the restrictions on valid secp256k1 keys, which reduces that to about 2^255.5; the difference would be negligible in practical terms, and it’s anyway not here relevant.)

However, no serious attacker would ever try to bruteforce elliptic-curve crypto.  Rather, it is estimated that breaking Bitcoin’s 256-bit keys with the best known attacks should require around 2¹²⁸ work to solve the ECDLP and thus calculate the private key from the public key.  In practical terms, it is therefore considered to have security equivalent to that of a 128-bit cipher for which the best known attack is bruteforce.

Similar security-level estimates are used for other public-key crypto, such as RSA.  However, RSA security level estimates are so vexed and unreliable that I quite mistrust them.  I remember when 1024-bit RSA was oftentimes claimed to be oh so secure—um, no.  The above table estimates that Bitcoin’s public-key crypto has an equivalent strength to 3072-bit RSA.  I suppose that sounds reasonable—maybe.

For comparison, Ed25519 is also considered to have a 128-bit security level; and Ed448-goldilocks is considered to have a 224-bit security level.  NIST P256 is claimed to have a 128-bit security level, and NIST P521 is claimed to have a 256-bit security level, although nobody sane uses NIST curves anymore.

In layman’s terms, a 128-bit security level is very, very strong.  It is what buzzword-lovers usually refer to as “military-grade security”.  Those who seek better than “military-grade security” (or wish to make fun of that idiotic term) may instead seek “‘Spinal Tap grade’ security”.

How strong is a 128-bit security level?  For reference, at current hashrate, it would take the entire Bitcoin mining network more than one trillion (10¹²) years to perform 2¹²⁸ work—and that’s with SHA-256 ASICs, which can’t be repurposed to do other calculations.  Performing 2¹²⁸ calculations of any kind is what I call “boil the oceans” security:  The energy required would actually do that, and worse.  It is unreasonable to suppose that it could ever be humanly possible to do 2¹²⁸ work.

Thus, Bitcoin’s public-key security is humanly impossible to break now and for the foreseeable future.  It could only be broken in one of two cases:  Either a new mathematical advance drastically reduces the work required for the best known attack, say to 2⁸⁰ or less; or there is constructed that mythical quantum computer which doesn’t exist, and may or may not be possible.  Very smart people have spent many years trying to do each of these tasks.  Research in these fields usually tends to be incremental; so if (if) they ever succeed, we will probably have at least a few years’ warning.

The usual reasons for seeking a 256-bit security level are (0) to provide an extra security margin against unforeseen mathematical breakthroughs, and (1) because for most use cases, the extra cost is relatively small; so why not have the security of something which is twice as impossible to break?  (Well, if you need to store keys in transaction outputs on the Bitcoin blockchain, the size difference would cause higher fees—for one problem, a real and immediate cost to users.)

But setting aside the potential of such unlikely events, the upshot is that Bitcoin’s public keys are plenty strong enough to protect the monetary value equivalent of hundreds of billions of dollars.  Or trillions.  Or all the money on Earth.

I strongly recommend that anybody not deeply involved in developing Bitcoin’s long-term security should absolutely not worry about the strength of Bitcoin’s public-key security.  It’s worse than useless worry:  It is a distraction from real problems.  Worry instead about your computer security, your operational security, and your financial privacy.  (Nobody can target you for theft or coercion if nobody knows you have anything significant to take.)

It is as if many people are keeping their coins in a safe with an unbreakable door (the cryptography—all of it) and walls made of tissue paper (the malware-infested PC, privacy leaks which may allow thieves to identify you and know what money you have, etc., etc.).  Then, they obsessively worry about the security of the door!  Don’t do that.

[Valle]

What do you think of P2WKH (160bit hash of pubkey) vs P2WSH (256bit hash of pubkey) security?

[mvrcrypto]

What do you think of P2WKH (160bit hash of pubkey) vs P2WSH (256bit hash of pubkey) security?

In P2WKH you have to re-built an unknow script, and if you want to unlock a P2WKH Tx, you have to found a sha256 collision with the lock script of this transaction.
To me, it is still very secure unless you break sha256 and then, find a way to create a new valid script corresponding to the precedent hash.

[Anti-Cen]

Well written and i would had thought that brute forcing a 256 bit key would be just as hard for
secp256k1 as RSA so something must be used from failed attempts on RSA that helps the
attacker to zoom in on the key.

Anyone who knows anything about microsoft know they are CIA/NSA/MOSSOD and when you generate keys pairs
you run this code

RSACryptoServiceProvider rsa = new RSACryptoServiceProvider(512);  // Key bits length
rsa.PersistKeyInCsp = false;

By default the keys get saved unless you remember to add the second line of code I am told by just now
on my version or Dot.Net it is defaulted to false so maybe they keep flipping it.

RSA and BigInt's were made for each other so it's easy to write you own encrypt/decrypt functions
but I never trust microsoft and would feel safer if i knew how to generate my own key pair so that
RSACryptoServiceProvider could be placed in the bin

secp256k1 =lots of code
RSA = Blackbox and you don't know whats in the box

[Anti-Cen]

What do you think of P2WKH (160bit hash of pubkey) vs P2WSH (256bit hash of pubkey) security?

In P2WKH you have to re-built an unknow script, and if you want to unlock a P2WKH Tx, you have to found a sha256 collision with the lock script of this transaction.
To me, it is still very secure unless you break sha256 and then, find a way to create a new valid script corresponding to the precedent hash.

in the code I am looking at on windows the wrapper just uses
System.Security.Cryptography.SHA256 and does a double hash and I can see that the public key
gets used to to create a signature along with the double hash so how does this work ?

I just thought the hash was used as a checksum of the signature contents and don't quite understand whats going on in the code below.

Code:

 public BigInteger[] GenerateSignature(BigInteger privateKey, byte[] hash, BigInteger? k)
        {
            for(int i = 0; i < 100; i++)
            {
                if (k == null)
                {
                    byte[] kBytes = new byte[33];
                    rngCsp.GetBytes(kBytes);
                    kBytes[32] = 0;

                    k = new BigInteger(kBytes);
                }
                var z = hash.ToBigIntegerUnsigned(true);
                if (k.Value.IsZero || k >= Secp256k1.N) continue;
                var r = Secp256k1.G.Multiply(k.Value).X % Secp256k1.N;
                if (r.IsZero) continue;
                var ss = (z + r * privateKey);
                var s = (ss * (k.Value.ModInverse(Secp256k1.N))) % Secp256k1.N;
                if (s.IsZero) continue;

                return new BigInteger[] { r, s };
            }

            throw new Exception("Unable to generate signature");
        }

Somehow later the public key must be used to somehow validate the two bigints returned from this funtion

[pebwindkraft]

...
in the code I am looking at on windows the wrapper just uses
System.Security.Cryptography.SHA256 and does a double hash and I can see that the public key
gets used to to create a signature along with the double hash so how does this work ?

In bitcoin all keys are managed by ECDSA logic, and I would hope, that the code to create the signatures (also in the windows systems) use the private key.  
On the tx and the signature: there is a fairly complex process to create the tx (see answer from runeks here: http://bitcoin.stackexchange.com/questions/3374/how-to-redeem-a-basic-tx), and then this tx is hashed (sha256), and this hash is signed.

[Anti-Cen]

In bitcoin all keys are managed by ECDSA logic, and I would hope, that the code to create the signatures (also in the windows systems) use the private key.  

Not quite sure what your laughing at so let the cat out the bag because I like a good joke

RSA does both public and private key encryption but maybe you didn't know about that 

[SHOSHI ISLAM 5]

                               Bitcoin’s Public-Key Security Level
                                :



In P2WKH you have to re-built an unknow script, and if you want to unlock a P2WKH Tx,

you have to found a sha256 collision with the lock script of this transaction.

To me,it is still very secure unless you break sha256 and then,

find a way to create a new valid script corresponding to the precedent hash.//////////

[Anti-Cen]

find a way to create a new valid script corresponding to the precedent hash.//////////

The best i can make out is something like this

string Msg="My transaction Text , input/outputs "
Hash=DoubleHash(Msg);
byte[]SendData=privateKey.Encrypt(Hash + " " + Msg);


On the Bitcoin node they must be using the public key to then decrypt "SendData" but I suspected that the public key
could only be used to encrypt data and it did not work both ways around with Secp256k1 and thought therefore something from the public key
was being send to the nodes that somehow got linked back to the double hash so maybe my test code trying to decrypt using the
public key was wrong.

Someone please tell me that encryption with private key can be decoded with the public key using Secp256k1 will you please

[Anti-Cen]

Bitcoin is using RijndaelManaged AES-Encryption with a 32 byte key so that makes 256 bit encryption
but the key that gets send at the start of the AES packet are PublicKey.point.X + PublicKey.point.Y using 65 bytes
and are based on a 256 bit Secp256k1 key

I can see that the X,Y bytes are based on the private key using Secp256k1.G.Multiply(privateKeyBig)
so what do I need here to get PrivateKey.X and PrivateKey.Y to do private key encryption because I am
sure this must be possible.

Would be nice to also incorporate transactions in at this level by playing with VI

[alexeyneu]

...
Thus, Bitcoin’s public-key security is humanly impossible to break ...

wtf you talkin about. all that power(2,256) turns to just one if you can catch random generator pattern

[hatshepsut93]

...
Thus, Bitcoin’s public-key security is humanly impossible to break ...

wtf you talkin about. all that power(2,256) turns to just one if you can catch random generator pattern

This is not an argument against a crypto system, because any crypto system can theoretically be broken due to human errors and side channel attacks. When cryptographers analyze crypto systems, it is assumed that all random parameters (like keys) are generated with cryptographically secure random number generators and are kept secret, so there's nothing wrong with OP's reasoning.

[alexeyneu]

...
Thus, Bitcoin’s public-key security is humanly impossible to break ...

wtf you talkin about. all that power(2,256) turns to just one if you can catch random generator pattern

This is not an argument against a crypto system, because any crypto system can theoretically be broken due to human errors and side channel attacks. When cryptographers analyze crypto systems, it is assumed that all random parameters (like keys) are generated with cryptographically secure random number generators and are kept secret, so there's nothing wrong with OP's reasoning.

i've read that what is written

rng algo is part of a key if not to assume that you see only one key.

[nullius]

Preface:  I wish to more concisely restate and amplify the greater point of my original post.

People are worrying about the wrong measure of the wrong thing.

I’ve seen endlessly repeated forum discussions of how big 2²⁵⁶ is, in the context of Bitcoin’s 256-bit keys—oft accompanied by estimates of how long it would take to try each potential key in a bruteforce attack.  That’s the wrong measure:  No actual attacker would use a bruteforce attack against ECC.  Against actual attackers, Bitcoin’s public-key crypto has a 128-bit security level.  This means that breaking it would require a humanly impossible amount of computation, approximately 2¹²⁸ work.

And it’s the wrong thing to worry about.  Worry about your computer security, your operational security, your privacy.  Those are all incomparably weaker and more vulnerable than crypto with a 128-bit security level.  Bitcoin’s public key security level is a strength.  Worry about your weaknesses.  Worry about all the many weak links in the chain of your security, not one of the few strong links.

I expect that if people put into their “weak links” even half the energy they expend obsessing over how hard it is to break things which are humanly impossible to break, then many fewer coins would be stolen.

What do you think of P2WKH (160bit hash of pubkey) vs P2WSH (256bit hash of pubkey) security?

Breaking the security of a 160-bit key hash requires a full preimage attack.  Therefore, the security level for this particular component is 160 bits.  That exceeds the 128-bit security level of the public key itself; so, “what I think” is that it’s stronger than strong enough.  So as for P2WPKH.

P2WSH upgraded to a 256-bit hash because multisig transactions are vulnerable to a collision attack by a malicious signer, such as a cheating party in an escrow transaction.  Collision attacks are much easier than preimage attacks, due to the birthday paradox.  In old-style P2SH (with “3” addresses), using a 160-bit hash, multisig has only an 80-bit security level against malicious signers; the hash still has a 160-bit security level against anybody who is not a signer.  Multisig with Segwit P2WSH and its 256-bit hashes has a 128-bit security level against malicious signers, and a 256-bit security level against everybody else.

Exponentials confuse many people.  The difference between 80-bit and 128-bit doesn’t sound like much.  Whereas 2¹²⁸ work is more than 281 trillion times bigger than 2⁸⁰ work.  To do 2⁸⁰ work is feasible today, albeit costly in the extreme.  To do 2⁸⁰ work more than 281 trillion times over is humanly impossible and unthinkable.

N.b. that this pertains primarily to multisig.  I can imagine it might also affect some other uses, but multisig is the major use case which invokes vulnerability to collision attacks.  There are other P2SH uses, which do not include in the script any data from an untrusted party—for example, the backwards-compatibility nesting of P2WPKH in P2SH.  For such use cases, old-style P2SH has a 160-bit security level; and Segwit P2WSH has a 256-bit security level.

There are some interesting references apropos in this Core blog post.  Note that the “comparison” to the Bitcoin mining network is outdated:  Hashrate has much increased; it now takes a bit over a day and a half for Bitcoin miners to collectively do 2⁸⁰ work.

In P2WKH you have to re-built an unknow script, and if you want to unlock a P2WKH Tx, you have to found a sha256 collision with the lock script of this transaction.
To me, it is still very secure unless you break sha256 and then, find a way to create a new valid script corresponding to the precedent hash.

Do you mean P2WSH?  What you said does not make any sense.  s/P2WKH/P2WSH/g.  Next, understand the difference between a collision and a preimage.  A collision means finding two different inputs which have the same hash—any hash.  Whereas in P2WSH (or almost anywhere else in the on-chain use of hashes), the hash is already determined.  To find an input matching a particular hash requires a preimage attack, not a collision attack.  This is a huge difference.  Preimage attacks are much harder.


I am now convinced that Anti-Cen is trolling.

This is a note for people who are not forum regulars, and newbies trying to learn.  Just ignore Anti-Cen.  Apologies for the noise.

On the tx and the signature: there is a fairly complex process to create the tx (see answer from runeks here: https://bitcoin.stackexchange.com/questions/3374/how-to-redeem-a-basic-tx), and then this tx is hashed (sha256), and this hash is signed.

(Link upgraded to https in quote.)  Thanks, pebwindkraft.  Good link, though note that the pertains to old-style P2KH transactions.  Segwit P2WPKH transactions involve a different serialization (not instead of, but in addition to the old serialization for non-witness data), among other differences.  Of course, P2SH and P2WSH are much different.

                              Bitcoin’s Public-Key Security Level
                                :o :o :o :o :o :o :o :o :o :o :o :o :

If that’s intended to suggest that Bitcoin’s security-level is, wow, mind-bogglingly huge, then yes, I would agree with that.

...
Thus, Bitcoin’s public-key security is humanly impossible to break ...

wtf you talkin about. all that power(2,256) turns to just one if you can catch random generator pattern

hatshepsut93 is right.  As I recently expressed elsewhere:  If you do not have a working Cryptographically Secure PRNG, then you have nothing else, either.  Your concern is almost tantamount to saying, well, what if you give the attacker your secret key?  Then, of course all the crypto is “broken”!  Of course!  The security of random number generation is important, because using a bad random generator to make your secret key is nearly like giving your secret key to the attacker.

That says absolutely nothing about the security of Bitcoin’s public-key crypto, which has a 128-bit security level—which is extremely secure.

[DannyHamilton]

- snip -
I am now convinced that Anti-Cen is trolling.

This is a note for people who are not forum regulars, and newbies trying to learn.  Just ignore Anti-Cen.  Apologies for the noise.
- snip -

I've been noticing recently that Anti-Cen's posts are making less and less sense and are sounding more and more paranoid.  He's also become very repetitive, reflexively responding over and over with the same phrases that have already been demonstrated to him to be false. I'm starting to grow concerned for his health and wondering if he perhaps has stopped taking his medication.

[Anti-Cen]

I've been noticing recently that Anti-Cen's posts are making less and less sense and are sounding more and more paranoid.  He's also become very repetitive, reflexively responding over and over with the same phrases that have already been demonstrated to him to be false. I'm starting to grow concerned for his health and wondering if he perhaps has stopped taking his medication.

Your trouble I suspect is more connect to your being a member of this particular faith and seeing it come under attack because you have a
vested interest in trying to preserve faith in the development team or help maintain the value of Bitcoins that your gambling with.

Yeah "demonstrated to him to be false" in your dreams so keep drinking the holy water

[Anti-Cen]

I am now convinced that Anti-Cen is trolling.

Why is that or are you another defender of the faith, vicar sent you in did he to ruff me up.

I make no excuses for calling out the bitcoin development team for the parts they have screwed up and if you must know I
am looking to pinch some of the good stuff without reinventing the wheel and so far I have found Secp256k1 to be quite good
not that I pretend to understand all the maths behind it but two of you have attacked me in this thread and I am not a big fan of brown
nose points myself.

This is a note for people who are not forum regulars, and newbies trying to learn.  Just ignore Anti-Cen.  Apologies for the noise.

Could it be that new visitors to the church are not allowed to think for themselves, could it be the only way to do anything
is as it's written in the Bitcoin bible and my presence makes you nervous because we have come a long way from burning
witches at the stake.