Bitcoin Entropy Questions?

[RealBitcoin]

So it's concluded by the opinion of experts:

Unspent bitcoin address -> private key =160 bit entropy +  other resource intensive operations

Spent bitcoin address (revealed pubkey)  -> private key = 128 bit entropy (naked)

Parsing through all private keys to find yours-> 256 bit entropy - **[86 bit/1000 years] = 170 bit entropy+ hashing/calculating address + other resource intensive operations @ 1000 years

** 2^86 = 4.7 * 10^25 which is a bit larger than the total bitcoin hashing power over 1000 years realistically, because the bitcoin network is the biggest supercomputer currently


CONCLUSION:

Minimum bitcoin security = 128 bit entropy, minimum security for your bitcoins!

Maximum bitcoin security = 160 bit entropy + other resource intensive operations ,only if the address doesnt have outwards transaction!


If these numbers aren't correct, please signal!

[DannyHamilton]

A private key is 256 bits.
A public key is a 256 bit X-value and a 256 bit Y-value, but the Y-value can be calculated from the X-value.
A bitcoin address is 160 bits.

[RealBitcoin]

A public key is a 256 bit X-value and a 256 bit Y-value, but the Y-value can be calculated from the X-value.
A bitcoin address is 160 bits.

I keep hearing that  an unspent address has more security. So if the pubkey adds 256bit, and a bitcoin address is by default 160 bit, then an unspent bitcoin address is 416 bit?


Why do people say that a private key has only 128 bit because  ECDSA provides only 128, see the quotes below

I get it... However, bitcoin already has key stretching. 

Bitcoin the protocol does not use key stretching.

Bitcoin-core "the client" uses key stretching to harden to the WALLET DECRYPTION PASSPHRASE against brute force attack.  Nothing more.   Electrum doesn't copy that code from bitcoin-core wallet so it isn't key stretching "again".

edit: actually i dont think it would increase the entropy, just add more stretching, since the seed has less entropy than a 160 bit "normal" priv key

Private keys only have 128 bit key strength.  Not 160 bit and not 256 bit.

256 bit ECDSA keys have 128 bits of key strength.  It requires 2^128 operations to brute force the privKey from the PubKey.  This assumes the PubKey is known.  If it isn't the an attacker would need to attempt a hash collision against the PubKeyHash, looking for any privKey which produces the same PubKeyHash.  That would require on average 2^160 operations.  Yes the PubKeyHash is oversized.  Bitcoin would have similar security (when PubKey is known) is the PubKeyHash was only 128 bits (i.e. RIPEMD-128 or XOR the left and right 128 bit sequence of SHA-256).

As for key stretching reducing entropy is depends on how it is implemented.  I haven't looked at Electrum source code but PBKDF2 was created to remove the entropy loss associated with PBKDF1.

There is a cap to the maximum security possible on secp256k1 at n/2 of key size.

256 bit keys therefore only provide 128 bits of security.

Anything more than 128 bit for bitcoin is just "feel good" territory.

It's kinda hard to tell who is right and wrong, so please enlighten me

[shorena]

A public key is a 256 bit X-value and a 256 bit Y-value, but the Y-value can be calculated from the X-value.
A bitcoin address is 160 bits.

I keep hearing that  an unspent address has more security. So if the pubkey adds 256bit, and a bitcoin address is by default 160 bit, then an unspent bitcoin address is 416 bit?

No.

Why do people say that a private key has only 128 bit because  ECDSA provides only 128, see the quotes below

I get it... However, bitcoin already has key stretching.  

Bitcoin the protocol does not use key stretching.

Bitcoin-core "the client" uses key stretching to harden to the WALLET DECRYPTION PASSPHRASE against brute force attack.  Nothing more.   Electrum doesn't copy that code from bitcoin-core wallet so it isn't key stretching "again".

edit: actually i dont think it would increase the entropy, just add more stretching, since the seed has less entropy than a 160 bit "normal" priv key

Private keys only have 128 bit key strength.  Not 160 bit and not 256 bit.

256 bit ECDSA keys have 128 bits of key strength.  It requires 2^128 operations to brute force the privKey from the PubKey.  This assumes the PubKey is known.  If it isn't the an attacker would need to attempt a hash collision against the PubKeyHash, looking for any privKey which produces the same PubKeyHash.  That would require on average 2^160 operations.  Yes the PubKeyHash is oversized.  Bitcoin would have similar security (when PubKey is known) is the PubKeyHash was only 128 bits (i.e. RIPEMD-128 or XOR the left and right 128 bit sequence of SHA-256).

As for key stretching reducing entropy is depends on how it is implemented.  I haven't looked at Electrum source code but PBKDF2 was created to remove the entropy loss associated with PBKDF1.

It's kinda hard to tell who is right and wrong, so please enlighten me

There are different kinds of bits. One kind is the number of 1's and 0's. As Dany said a ECDSA private key as used in bitcoin has 256 different of these.

Another kind is a measurement for the amount of information a message contains (this message may or may not be encoded in bits). This measurement is called entropy and is given in bits as well.

There is also the kind of bits used by DeathAndTaxes which is a comparisson between algorithms. What it means is that ECDSA is as strong as a 128bit symmetric encryption scheme. Another common example is RSA, where a 1024 bit key is as strong as ~70 bits. This number can decrease over time as better ways are found to calculate the private key from the public key.

[RealBitcoin]

There are different kinds of bits. One kind is the number of 1's and 0's. As Dany said a ECDSA private key as used in bitcoin has 256 different of these.

Another kind is a measurement for the amount of information a message contains (this message may or may not be encoded in bits). This measurement is called entropy and is given in bits as well.

There is also the kind of bits used by DeathAndTaxes which is a comparisson between algorithms. What it means is that ECDSA is as strong as a 128bit symmetric encryption scheme. Another common example is RSA, where a 1024 bit key is as strong as ~70 bits. This number can decrease over time as better ways are found to calculate the private key from the public key.

Yes but I was asking for the entropy NOT the keysize, hence the title of the thread:

I`m a bit confused about the maximum entropy that bitcoin provides.

Alright so private key = 128 bit entropy, finally that is settled

No.

Ok so then how much entropy security does a spent vs unspent address provide?

[shorena]

There are different kinds of bits. One kind is the number of 1's and 0's. As Dany said a ECDSA private key as used in bitcoin has 256 different of these.

Another kind is a measurement for the amount of information a message contains (this message may or may not be encoded in bits). This measurement is called entropy and is given in bits as well.

There is also the kind of bits used by DeathAndTaxes which is a comparisson between algorithms. What it means is that ECDSA is as strong as a 128bit symmetric encryption scheme. Another common example is RSA, where a 1024 bit key is as strong as ~70 bits. This number can decrease over time as better ways are found to calculate the private key from the public key.

Yes but I was asking for the entropy, hence the title of the thread:

I`m a bit confused about the maximum entropy that bitcoin provides.

Alright so private key = 128 bit entropy, finally that is settled

No.

Ok so then how much entropy security does a spent vs unspent address provide?

I think you are looking for security not entropy. Anyway Ill put the names aside and try to answer your question. Im pretty sure Danny will correct me when I make a mistake. The question the way I understand it is, how easy is it for someone to steal your coins if you re use addresses.

Scenario #1: You have spend coins received on the address in the past and thus the public key is stored in the blockchain. In this case the attacker would need 2¹²⁸ elemantary operations to find the correct private key. Aka a security level of 128 bit. This ignores randomness and chance, e.g. the birthday paradox.

Scenario #2: You have never spend coins received on the address, ever. You also have not otherwise published your private key (e.g. due to a payment to pubkey instead of to an address). In this case the attacker has to break the RIPEMD160 hash in order to get to the SHA256 of the public key. Since there are no known attacks to improve from simple brute force its security is 160 bit. Once RIPEMD160 is done, an attacker would need to break SHA256 (256 bit security, unless used with reduced number of rounds) in order to get to the public key and from there try to find the private key. This however makes no sense as its way faster to just try private keys until you found one that results in the same address. As there are only 2¹⁶⁰ different (version 1) addresses due to the 160 bits of RIPEMD160 there are 2⁹⁶ different private keys for each address. As such you have a total security level of 160 bits.

[RealBitcoin]

I think you are looking for security not entropy.

The two is the same, because i was not asking for keysizes which can be arbitrary if the underlying function only provides so much.

For example creating a 4096 bit private key is useless (and probably invalid) if the ECDSA gives only 128 bit. So therefore the entropy is what matters not the keysize.

Scenario #1: You have spend coins received on the address in the past and thus the public key is stored in the blockchain. In this case the attacker would need 2¹²⁸ elemantary operations to find the correct private key. Aka a security level of 128 bit. This ignores randomness and chance, e.g. the birthday paradox.

Scenario #2: You have never spend coins received on the address, ever. You also have not otherwise published your private key (e.g. due to a payment to pubkey instead of to an address). In this case the attacker has to break the RIPEMD160 hash in order to get to the SHA256 of the public key. Since there are no known attacks to improve from simple brute force its security is 160 bit. Once RIPEMD160 is done, an attacker would need to break SHA256 (256 bit security, unless used with reduced number of rounds) in order to get to the public key and from there try to find the private key. This however makes no sense as its way faster to just try private keys until you found one that results in the same address. As there are only 2¹⁶⁰ different (version 1) addresses due to the 160 bits of RIPEMD160 there are 2⁹⁶ different private keys for each address. As such you have a total security level of 160 bits.

Yes I've heard this variant before. We need some more expert's confirmations on this.

Also are you sure the operations are elementary, there is a lot of hashing going on, It looks like this, and there are many operations going on, not just elementary, so I think there is more security here:

[shorena]

I think you are looking for security not entropy.

The two is the same, because i was not asking for keysizes which can be arbitrary if the underlying function only provides so much.

The values might be the same, but they are not the same thing.

For example creating a 4096 bit private key is useless (and probably invalid) if the ECDSA gives only 128 bit. So therefore the entropy is what matters not the keysize.

Well you cant use a 4096 bit private key with ECDSA as used by bitcoin and 4096 bit RSA keys are not useless even though they only provide a security level of 128 bit[1].

Scenario #1: You have spend coins received on the address in the past and thus the public key is stored in the blockchain. In this case the attacker would need 2¹²⁸ elemantary operations to find the correct private key. Aka a security level of 128 bit. This ignores randomness and chance, e.g. the birthday paradox.

Scenario #2: You have never spend coins received on the address, ever. You also have not otherwise published your private key (e.g. due to a payment to pubkey instead of to an address). In this case the attacker has to break the RIPEMD160 hash in order to get to the SHA256 of the public key. Since there are no known attacks to improve from simple brute force its security is 160 bit. Once RIPEMD160 is done, an attacker would need to break SHA256 (256 bit security, unless used with reduced number of rounds) in order to get to the public key and from there try to find the private key. This however makes no sense as its way faster to just try private keys until you found one that results in the same address. As there are only 2¹⁶⁰ different (version 1) addresses due to the 160 bits of RIPEMD160 there are 2⁹⁶ different private keys for each address. As such you have a total security level of 160 bits.

Yes I've heard this variant before. We need some more expert's confirmations on this.

Also are you sure the operations are elementary, there is a lot of hashing going on, It looks like this, and there are many operations going on, not just elementary, so I think there is more security here:

-pic here-

True calculating a bitcoin address from a private key is not an elemantary operation. It would make an attack even slower for an unused address. I dont think it matters much though. 2¹⁶⁰ or 2¹²⁸ are both very large search spaces.

[1] might not be the exact correct value, cant find a table atm.

[RealBitcoin]

Well you cant use a 4096 bit private key with ECDSA as used by bitcoin and 4096 bit RSA keys are not useless even though they only provide a security level of 128 bit[1].

Yes, I was referring in the contect of ECDSA not other algos.

True calculating a bitcoin address from a private key is not an elemantary operation. It would make an attack even slower for an unused address. I dont think it matters much though. 2¹⁶⁰ or 2¹²⁸ are both very large search spaces.

[1] might not be the exact correct value, cant find a table atm.

Yes so an unspent address is 160 bit + work of doing the other operations.

However a spent address has only ECDSA separating your money from the thief, and it's very scary. So I think public keys should be treated confidential as well as private keys, in the sense that newbies should not reveal them to strangers.

[DannyHamilton]

Shorena is giving answers at least as good as I could.  There's nothing I can offer beyond what he's already said.  GMaxwell or Death&Taxes might be able to give better details or correct any errors.

I think a big part of the problem here is that words are being used without a clear understanding of what those words mean.

In the original post, you talk about three different examples "for brute forcing".

If you are talking about brute forcing (trying every possible input value until you find the output value you are looking for, then key size (or rather total possible values) is what you are talking about.

If you are talking about weaknesses in the algorithms, and techniques that take advantage of those weaknesses, then you're more interested in level of security.

Entropy is typically a measure of randomness.  (You'll notice that D&T doesn't say "bits of entropy", he says "bits of key STRENGTH")

[DannyHamilton]

However a spent address has only ECDSA separating your money from the thief, and it's very scary.

Yes, a spent address has only ECDSA separating your money from the thief, but no, it really isn't scary.

So I think public keys should be treated confidential as well as private keys, in the sense that newbies should not reveal them to strangers.

That is only possible if you NEVER re-use an address.  You should generate a new address EVERY TIME that you receive bitcoins.

Otherwise, the public key is right there in the blockchain for the whole world to see as soon as you spend an output that was received at the address.

[RealBitcoin]

Shorena is giving answers at least as good as I could.  There's nothing I can offer beyond what he's already said.  GMaxwell or Death&Taxes might be able to give better details or correct any errors.

I think a big part of the problem here is that words are being used without a clear understanding of what those words mean.

Yes it would be very nice if more people would confirm our thoughts.

In the original post, you talk about three different examples "for brute forcing".

If you are talking about brute forcing (trying every possible input value until you find the output value you are looking for, then key size (or rather total possible values) is what you are talking about.

If you are talking about weaknesses in the algorithms, and techniques that take advantage of those weaknesses, then you're more interested in level of security.

Entropy is typically a measure of randomness.  (You'll notice that D&T doesn't say "bits of entropy", he says "bits of key STRENGTH")

Yes I need to reformulate it, i dont just care about brute force, but also other types of weaknesses, which might be present, but as a benchmark we only look at brute force.

Of cours if half of the cipher rounds can be broken then the security immediately halvens.

BUT just for simplicity we look at brute force vulnerability.

I mislooked D&T's post, thanks for corecting me.

That is only possible if you NEVER re-use an address.  You should generate a new address EVERY TIME that you receive bitcoins.

Otherwise, the public key is right there in the blockchain for the whole world to see as soon as you spend an output that was received at the address.

Yes I know, probably need to include this advice in my guide too.

[RealBitcoin]

What if the attacker tries to guess all private keys?

For example run through all private keys, which would mean 128 bit security, but he has to compute the address for every key to see if there is a balance.

So he has to compute the address, check the balance, keep and parse a blockchain or some API to get the balance.


For example I saw a paper a while ago that had a very efficient theory how to go through all private keys, by saving all used addresses in a memory streamable text file. And then only compare those addresses that have bigger balance on them.

It would still mean a lot of memory operations, many read/write to disk, it would be extremely impossible + the 128 bits.

And probably after they tried a very small amount of combinations, most of the funds were already moved, it would be impossible to cycle through.

In my opinion guessing the private key is the hardest of them all, because it involves the most work.


That being said I think an spent address is the most vulnerable.

Because the other 2 approaches have all some sort of key stretching or extra work added to it. But a spent address only has 128 bit ECDSA wall between you and the thief.

So yea its very important if people reuse addresses!

[cr1776]

What if the attacker tries to guess all private keys?
...

They would run out of time and energy in the universe first. 

(*At least with our understanding of physics today.)

[RealBitcoin]

What if the attacker tries to guess all private keys?
...

They would run out of time and energy in the universe first. 

(*At least with our understanding of physics today.)

Yes but it would take considerably less to get to your address.

So i meant it in the context that they go from 1st to the last, and in there somewhere they might hit an address that is used by someone.

Still very very hard.

[etparle]

What if the attacker tries to guess all private keys?
...

They would run out of time and energy in the universe first. 

(*At least with our understanding of physics today.)

How is this affected by quantum computing? Say for example Quantum computers were fully developed and as accessible as home PCs?

[DannyHamilton]

What if the attacker tries to guess all private keys?

Then they will waste a LOT of time, a lot of money, and will accomplish nothing.  They'd make MUCH more money MUCH faster by using all that money and computing power to just mine bitcoins.

For example run through all private keys, which would mean 128 bit security

You really need to decide which one you are trying to discuss.  If you are going to "run through all private keys", then I'm pretty sure you're going to need to try 2^256 possibilities.  If you are going to use one of the fastest known algorithms that allow one to solve the ECDLP, then you'll have only "128 bit security".

In my opinion guessing the private key is the hardest of them all, because it involves the most work.

Finding a private key is the ONLY method.  If you don't have the private key, then you don't have the information that you'll need in order to spend the bitcoins.

That being said I think an spent address is the most vulnerable.

Because the other 2 approaches have all some sort of key stretching or extra work added to it. But a spent address only has 128 bit ECDSA wall between you and the thief.

While your security is *slightly* less when the public key is available, 128 bit security is still a huge amount of security.  The risk isn't that someone will be able to use the algorithms that reduce the security to 128 bit, the risk is that perhaps in the future someone finds a new algorithm that reduces the security far lower than 128 bit.

So yea its very important if people reuse addresses!

"very important" is a huge exaggeration.

128 bit security is still very secure and more than enough for current technology.

Yes but it would take considerably less to get to your address.

So i meant it in the context that they go from 1st to the last, and in there somewhere they might hit an address that is used by someone.

Still very very hard.

Assuming that you properly generated a random private key, it would take longer than the earth has existed so far.  So when you say "very hard", what you really mean is "impossible".

The earth is approximately 4.5 X 10⁹ years old.

If you could calculate and check the values of the public keys for 1.5 X 10¹⁵ addresses per second, you would only be able to check 4.7 X 10²² addresses per year.  That means in the 4.5 X 10⁹ years that the earth has existed you could check 2.13 X 10³² addresses.  That's less than 2¹⁰⁸ addresses in the entire history of the existence of the earth as a solid body.  That's nowhere near your 2¹²⁸, or your 2¹⁶⁰, or your 2²⁵⁶, and it certainly isn't within someone's lifetime.

Now, if you used that same computing power to mine bitcoins instead, you would most likely be able to mine 656250 BTC per year for the next 4 years, and another 328125 BTC per year for the 4 years after that.

Why would you spend all that effort for a few billion years attempting to find a single private key that might only have 0.00000001 BTC in it, when instead you could spend 8 years mining and get 3937500.00000000 BTC.

[RealBitcoin]

Assuming that you properly generated a random private key, it would take longer than the earth has existed so far.  So when you say "very hard", what you really mean is "impossible".

The earth is approximately 4.5 X 10⁹ years old.

If you could calculate and check the values of the public keys for 1.5 X 10¹⁵ addresses per second, you would only be able to check 4.7 X 10²² addresses per year.  That means in the 4.5 X 10⁹ years that the earth has existed you could check 2.13 X 10³² addresses.  That's less than 2¹⁰⁸ addresses in the entire history of the existence of the earth as a solid body.  That's nowhere near your 2¹²⁸, or your 2¹⁶⁰, or your 2²⁵⁶, and it certainly isn't within someone's lifetime.

Now, if you used that same computing power to mine bitcoins instead, you would most likely be able to mine 656250 BTC per year for the next 4 years, and another 328125 BTC per year for the 4 years after that.

Why would you spend all that effort for a few billion years attempting to find a single private key that might only have 0.00000001 BTC in it, when instead you could spend 8 years mining and get 3937500.00000000 BTC.

Indeed, and you can probably not calculate 1.5 X 10¹⁵ / second.

Not even with the best supercomputer, I mean you have to stream all the balances in memory,  do many disk read/write operations to delete the already calculated ones to free up memory.

We are talking enourmous resources around here.

[DannyHamilton]

Indeed, and you can probably not calculate 1.5 X 10¹⁵ / second.

I chose that number specifically because that's a bit more than the number of double SHA256 hash calculations the entire world combined does while mining bitcoin right now.  Therefore, if you could do the same number of private key to public key calculations as the entire world does block hashes, you could either use that computing power to mine all the blocks, or to try to find an address with some bitcoins in it.

We are talking enourmous resources around here.

Yes, and even with those enormous resources, it would still take longer than the entire existence of the earth so far.  Clearly, you'd get a lot richer a lot faster if you just mine all the bitcoin blocks.

[RealBitcoin]

Indeed, and you can probably not calculate 1.5 X 10¹⁵ / second.

I chose that number specifically because that's a bit more than the number of double SHA256 hash calculations the entire world combined does while mining bitcoin right now.  Therefore, if you could do the same number of private key to public key calculations as the entire world does block hashes, you could either use that computing power to mine all the blocks, or to try to find an address with some bitcoins in it.

We are talking enourmous resources around here.

Yes, and even with those enormous resources, it would still take longer than the entire existence of the earth so far.  Clearly, you'd get a lot richer a lot faster if you just mine all the bitcoin blocks.

Yes I have updated the OP, with the information gathered in this thread.

Your 4.7 * 10 ^22, is 4.7 * 10 ^ 25 over 1000 years, which is  ~ 86 bit decay in 1000 years (given if the network wont grow, but even then its questionable).

So over the course of a human lifetime, guessing his private key is very unfeasable.

Therefore we know the minimum security is 128 bit, as lowest denominator, and maximum is 160 bit from unspent address.


If I put incorrect info in the OP, anyone please correct me, thanks!