z

[flatfly]

I wonder how many people fired up vanitygen trying to find the keys for that one large address?  I know it would take millions of years, but you never know, you might get lucky.

I think very few people are trying to do that.

I have to believe that most people involved with bitcoin are neither thieves nor stupid.

Vanitygen doesn't support full addresses anyway.

[1715165266]

1715165266

[1715165266]

1715165266

[payb.tc]

I wonder how many people fired up vanitygen trying to find the keys for that one large address?  I know it would take millions of years, but you never know, you might get lucky.

I think very few people are trying to do that.

I have to believe that most people involved with bitcoin are neither thieves nor stupid.

Vanitygen doesn't support full addresses anyway.

really? what's the longest string you can search for, if not 34?

[dooglus]

The conjectured security level of ECDSA 256 bit keys is
128bit (source: http://www.nsa.gov/business/programs/elliptic_curve.shtml).
It's in fact likely to be closer to 2^256, the size of the space of all possible secp256k1 keys.

That means : breaking an ECDSA 256 bit key would take, using the best known
algorithms today, on the order of 2^128 attempts.

That's 340282366920938463463374607431768211456 attempts.

Don't forget that there are only 2^160 different addresses, due to the hash160 step in making an address from a private key.  You don't need to find the rich account's private key.  Any private key with the same bitcoin address will let you spend its money.

I don't know how you got from 2^256 to 2^128 in your analysis, but can you use the same magic to get from 2^160 to 2^80?

[rjk]

Any private key with the same bitcoin address will let you spend its money.

Is this true though? I thought the public key was present in the blockchain, and having 2 public keys that resolved to the same bitcoin address would probably cause the quintessential swirling vortex of doom, but shouldn't allow the coins to be spent. This assumes that there are 2^256 public keys that go with those 2^256 private keys.

[BoardGameCoin]

Dooglus is saying there's 2^160 public keys for the 2^256 private keys. In other words the mapping is not injective, meaning that more than one private key can map to the same public key.

[rjk]

Dooglus is saying there's 2^160 public keys for the 2^256 private keys. In other words the mapping is not injective, meaning that more than one private key can map to the same public key.

OK I see - I thought the public key was still 256 bit and the public-key-to-bitcoin-address transformation reduced that to 160 bits. However, I looked at how it works again, and the bitcoin address is just the 160 bit public key written in Base58. EDIT: tired, need sleep

BTW, what are the 4 alphanumerics that are left out of a Base58 address, and why were they left out instead of using a standard Base62 alphanemeric  character set? (26 alphas x2 case + 10 numbers)

[DeathAndTaxes]

No you were right the first time.

Bitcoin public keys are 256 bit HOWEVER multiple public keys will map to the same address (which is 160 bit).

address_base = version + RIPEMD-160(SHA-256(256bit ECDSA public key))
checksum = Left4Bytes(SHA-256(SHA-256(address_base))
address = Base58(address_base + checksum)

The end result is the same.  Bitcoin keypairs have 160bits of strength when facing a brute force attack.

On base-58.  The missing values are O0Il  ("upper case oh", "zero", "upper case eye", "lower case ell").
The reason it to make errors in manual copying less likely.

[sadpandatech]

[dooglus]

Any private key with the same bitcoin address will let you spend its money.

Is this true though? I thought the public key was present in the blockchain, and having 2 public keys that resolved to the same bitcoin address would probably cause the quintessential swirling vortex of doom, but shouldn't allow the coins to be spent. This assumes that there are 2^256 public keys that go with those 2^256 private keys.

Yes, it's true.  Look at the scripts on blockexplorer.  They say "to spend this, you must provide a public key with the following 160 bit hash, and a signature made with the corresponding private key".  It doesn't specify which public key must be used.  Any one with the correct 160 bit hash will work.

Here's an example script:

OP_DUP OP_HASH160 5b62be019b9c39991daed3c3d0e2186986476c11 OP_EQUALVERIFY OP_CHECKSIG

[dooglus]

Dooglus is saying there's 2^160 public keys for the 2^256 private keys. In other words the mapping is not injective, meaning that more than one private key can map to the same public key.

No, there are 2^256 public keys but only 2^160 bitcoin addresses.

i.e. there are around 2^96 public/private keypairs for each bitcoin address, and any of those 2^96 can spend the coins at an address.

More than one private key can map to the same *address*.

[rjk]

Yes, it's true.  Look at the scripts on blockexplorer.  They say "to spend this, you must provide a public key with the following 160 bit hash, and a signature made with the corresponding private key".  It doesn't specify which public key must be used.  Any one with the correct 160 bit hash will work.

Here's an example script:

OP_DUP OP_HASH160 5b62be019b9c39991daed3c3d0e2186986476c11 OP_EQUALVERIFY OP_CHECKSIG

Yes that is the part I was misunderstanding, thanks for the explanation.

[dooglus]

Mostly always true, but not 100% always true: not all transactions
work the way you describe.

For example, block reward TX have the full public key specified, not
just the 160 bit hash.

It's 100% true for payments to bitcoin addresses, and 0% true for payments to public keys...

Block rewards are no different than regular payments in this respect - both block rewards and regular payments can be made to bitcoin addresses or public keys.  In practice nobody much sends payments to public keys, whereas it's common for block rewards to go to public keys, but there's no technical reason for that to be the case.

In the thread about quantum computers it was mentioned that the use of 160 bit addresses quite possibly strengthens the network, since the advent of quantum computers would make cracking a 256 bit public key a 2^128 step operation, whereas reversing a 160 bit hash would still be a 2^160 step operation.  i.e. finding the public key from an address would be the hard bit, and finding the private key for the public key would be relatively easy.  That implies that you should only spend from each address once, since in order to spend from an address you have to publicly declare its public key.

[BurtW]

Don't forget that there are only 2^160 different addresses, due to the hash160 step in making an address from a private key.  You don't need to find the rich account's private key.  Any private key with the same bitcoin address will let you spend its money.

dooglus,  Thanks!  I have studied Bitcoin for a long time now and just when I think I totally understand it I learn something new.  What you are saying is of course true and makes perfect sense.  But I just never realized it.  By design the address space was reduced.  I suggest we start a BIP to increase the length of all future Bitcoin address up to their full potential address space in order to increase the security of our precious BTC.  Want to help me co-author it? 

[[Tycho]]

Don't forget that there are only 2^160 different addresses, due to the hash160 step in making an address from a private key.  You don't need to find the rich account's private key.  Any private key with the same bitcoin address will let you spend its money.

dooglus,  Thanks!  I have studied Bitcoin for a long time now and just when I think I totally understand it I learn something new.  What you are saying is of course true and makes perfect sense.  But I just never realized it.  By design the address space was reduced.

Note that this is only true if TX was sent to address, not pubkey.

[BurtW]

Don't forget that there are only 2^160 different addresses, due to the hash160 step in making an address from a private key.  You don't need to find the rich account's private key.  Any private key with the same bitcoin address will let you spend its money.

dooglus,  Thanks!  I have studied Bitcoin for a long time now and just when I think I totally understand it I learn something new.  What you are saying is of course true and makes perfect sense.  But I just never realized it.  By design the address space was reduced.

Note that this is only true if TX was sent to address, not pubkey.

Most are, right?  What % of all transactions are sent to a pubKey?  Would be an interesting statistic.

[[Tycho]]

Most are, right?  What % of all transactions are sent to a pubKey?  Would be an interesting statistic.

Most generation TXes are sent to pubkey.
DeepBit's hot wallet also sends change to pubkey.

[bg002h]

I wonder how many people fired up vanitygen trying to find the keys for that one large address?  I know it would take millions of years, but you never know, you might get lucky.

What you describe is essentially trying to brute force break ECDSA for secp256k1
(the public key crypto mechanism used by bitcoin).

The conjectured security level of ECDSA 256 bit keys is
128bit (source: http://www.nsa.gov/business/programs/elliptic_curve.shtml).
It's in fact likely to be closer to 2^256, the size of the space of all possible secp256k1 keys.

That means : breaking an ECDSA 256 bit key would take, using the best known
algorithms today, on the order of 2^128 attempts.

That's 340282366920938463463374607431768211456 attempts.



Assuming your computer could try a billion per seconds (it can't, according to the vanitygen
post, vanitygen can do ~20 Million attempts per second on a 6990), that'd still take you, oh,
about 10790283070806014188 years.

Even if you managed to somehow harness processing power equivalent to that of the whole
bitcoin hashing network today, you'd still have to wait about 10 '790 '283 '070 years.

That's 10 billions years.

In other words, chances are you'd witness the heat death of the universe before you actually
"get lucky".

So....give it a try?

Sometimes a simple "no, silly" speaks louder than eloquent, precise logic Enjoyed your post!

[dooglus]

dooglus,  Thanks!  I have studied Bitcoin for a long time now and just when I think I totally understand it I learn something new.  What you are saying is of course true and makes perfect sense.  But I just never realized it.  By design the address space was reduced.  I suggest we start a BIP to increase the length of all future Bitcoin address up to their full potential address space in order to increase the security of our precious BTC.  Want to help me co-author it? 

I think 160 bits of security is plenty for now.

And apparently the 160 bits that bitcoin addresses give us is more secure than the 256 bits that private keys give us because the advent of quantum computing apparently would reduce the 256 bit private key security effectively down to 128 bits, whereas the 160 bit security of addresses isn't hurt by quantum computing (so long as you keep your public key private by only spending from each address once!)

[CodesInChaos]

dooglus,  Thanks!  I have studied Bitcoin for a long time now and just when I think I totally understand it I learn something new.  What you are saying is of course true and makes perfect sense.  But I just never realized it.  By design the address space was reduced.  I suggest we start a BIP to increase the length of all future Bitcoin address up to their full potential address space in order to increase the security of our precious BTC.  Want to help me co-author it?  

I think 160 bits of security is plenty for now.

And apparently the 160 bits that bitcoin addresses give us is more secure than the 256 bits that private keys give us because the advent of quantum computing apparently would reduce the 256 bit private key security effectively down to 128 bits, whereas the 160 bit security of addresses isn't hurt by quantum computing (so long as you keep your public key private by only spending from each address once!)

You misunderstood the ECC part. 256 bit ECC has a security level of 128 on classical computers. For bitcoin it's even a bit less, since Koblitz curves are a bit weaker than prime curves. See How strong is the ECDSA algorithm? on crypto.SE
Using a quantum computer the security of ECC is very low. A sufficiently big quantum computer would endanger all addresses with known public key, i.e. those that were already used as input.

A big quantum computer would also affect hash functions and symmetric crypto. But the attack is not nearly as severe, effectively halving their length. i.e. it would reduce a 160 bit hash to an 80 bit security level.

Luckily it's very unlikely that such a big quantum computer will suddenly appear. We probably will have enough time to migrate most coins to new secure addresses if it becomes apparent that such a qc upcoming.

[Savior]

Sun Jul 15 20:36:59 2012 comes up on very many off the top addresses. Added together that's over 868 000 bitcoins .. This most be mtgox?