ArsenShnurkov
Legendary
Offline
Activity: 1386
Merit: 1000


March 23, 2011, 04:26:36 PM 

The task which is performed during block signing is very special. Why not try to deep into the signing process in order to reduce number of required attempts? May be to prepare some precomputed tables or so. Can you point to topics about this?







Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.




dbitcoin


March 23, 2011, 04:53:46 PM 

The task which is performed during block signing is very special. Why not try to deep into the signing process in order to reduce number of required attempts? May be to prepare some precomputed tables or so. Can you point to topics about this?
http://en.wikipedia.org/wiki/SHA2




rasputin
Newbie
Offline
Activity: 15
Merit: 0


March 23, 2011, 04:53:58 PM 

The task which is performed during block signing is very special. Why not try to deep into the signing process in order to reduce number of required attempts? May be to prepare some precomputed tables or so. Can you point to topics about this? http://en.wikipedia.org/wiki/Cryptographic_hash_function




ArsenShnurkov
Legendary
Offline
Activity: 1386
Merit: 1000


March 23, 2011, 05:11:36 PM 

that article describes all possible use cases, but we have a special one.




dbitcoin


March 23, 2011, 05:32:03 PM 

that article describes all possible use cases, but we have a special one. Where? SHA256(SHA256(x)) All miners just brutforce one hash for current block.




theboos
Member
Offline
Activity: 87
Merit: 10


March 23, 2011, 05:32:31 PM 

Hashes are by design irreversible. In practice, they are simply very hard to reverse. The only effective way to "crack" a hash is to try trillions of hashes per second (the entire bitcoin network currently tests fewer than 600 billion hashes per second), and it would still take you on average longer than the age of the universe to find a key with a hash that matches. Bitcoin uses an "easier" hash to increase the rate of Bitcoin creation. This has been described elsewhere better, but my understanding is that blocks are created when:
hash(hash(hash(data that changes relatively infrequently) + nonce)) < some number inversely proportional to difficulty
If you were to construct a number line and place the values of hashes of random keys on it, you would find that the hashes are approximately uniformly distributed across the line. Difficulty represents the "smallness" of a range at the beginning of the line that hashes must fall into to be validated.
As for precomputed tables, even discounting the variability of the Merkle root, it would take far more time to precompute a hash table for the SHA hash than to generate thousands of bitcoins through legitimate mining. Precomputing a hash table doesn't save you any time in the long run, rather it allows you to invest (a tremendous amount of) time now so you can spend far less time on each block. You might as well generate blocks legitimately now while the difficulty is low.




dacoinminster
Legendary
Offline
Activity: 1218
Merit: 1002
Rational Exuberance


March 23, 2011, 07:01:11 PM 

I personally wonder about the difficulty of discovering someone's private key in their wallet.dat by brute force attack. I think this would require 2^{256} hashes to guarantee finding the private key with an average crack time of 2^{255} hashes. Can anybody familiar with cryptography answer that question and/or elaborate?
If that is true, and we assume that in 2011 a very wealthy attacker can bring 1 THash/second to bear on the problem, and the attacker works constantly on the problem starting now, purchasing new hardware which keeps up with Moore's law over the following years (processing power doubling every two years), his descendants will steal your private key and all your descendants bitcoins somewhere around 2390 (unless they get unbelievably lucky before then). A hundred years later in 2490, anyone with the equivalent of a PC will be able to crack a wallet.dat private key in about a second. Can anyone check my math on that?
If that is true, then bitcoins won't ever truly be "lost" because in a few hundred years, they will turn up again when in becomes feasible to crack a wallet.dat private key. Hopefully whoever manages to dig up those lost coins will be able to exchange them into whatever the equivalent form of bitcoins is at that time (with much stronger cryptography).




FatherMcGruder


March 23, 2011, 07:51:28 PM 

I personally wonder about the difficulty of discovering someone's private key in their wallet.dat by brute force attack. I think this would require 2^{256} hashes to guarantee finding the private key with an average crack time of 2^{255} hashes. Can anybody familiar with cryptography answer that question and/or elaborate?
If that is true, and we assume that in 2011 a very wealthy attacker can bring 1 THash/second to bear on the problem, and the attacker works constantly on the problem starting now, purchasing new hardware which keeps up with Moore's law over the following years (processing power doubling every two years), his descendants will steal your private key and all your descendants bitcoins somewhere around 2390 (unless they get unbelievably lucky before then). A hundred years later in 2490, anyone with the equivalent of a PC will be able to crack a wallet.dat private key in about a second. Can anyone check my math on that?
If that is true, then bitcoins won't ever truly be "lost" because in a few hundred years, they will turn up again when in becomes feasible to crack a wallet.dat private key. Hopefully whoever manages to dig up those lost coins will be able to exchange them into whatever the equivalent form of bitcoins is at that time (with much stronger cryptography).
Wouldn't Moore's Law, if it still holds by then, make the Bitcoin network that much more computationally powerful and increase the difficulty accordingly?

Use my Trade Hill referral code: THR11519 Check out bitcoinity.org and Ripple. Shameless display of my bitcoin address: 1Hio4bqPUZnhr2SWi4WgsnVU1ph3EkusvH



xenon481


March 23, 2011, 07:56:42 PM 

Wouldn't Moore's Law, if it still holds by then, make the Bitcoin network that much more computationally powerful and increase the difficulty accordingly?
But there isn't a changing difficulty for finding the private key as there is only ever 1 answer.

Tips Appreciated: 171TQ2wJg7bxj2q68VNibU75YZB22b7ZDr



FatherMcGruder


March 24, 2011, 01:14:07 PM 

But there isn't a changing difficulty for finding the private key as there is only ever 1 answer.
I see. To defend against this attack, people could just regularly transfer their savings between different wallets. If the target private key doesn't stand a good chance of containing enough bitcoins, the attack is kind of pointless, no?

Use my Trade Hill referral code: THR11519 Check out bitcoinity.org and Ripple. Shameless display of my bitcoin address: 1Hio4bqPUZnhr2SWi4WgsnVU1ph3EkusvH



barbarousrelic


March 24, 2011, 01:46:51 PM 

The encryption of one's private keys is entirely different from the hashing algorithm used in generating blocks.
SHA256 hashing, ECDSA encryption.

Do not waste your time debating whether Bitcoin can work. It does work.
"Early adopters will profit" is not a sufficient condition to classify something as a pyramid or Ponzi scheme. If it was, Apple and Microsoft stock are Ponzi schemes.
There is no such thing as "market manipulation." There is only buying and selling.



gohan
Jr. Member
Offline
Activity: 52
Merit: 0


March 24, 2011, 02:03:02 PM 

I personally wonder about the difficulty of discovering someone's private key in their wallet.dat by brute force attack. I think this would require 2^{256} hashes to guarantee finding the private key with an average crack time of 2^{255} hashes.
I might have gotten you wrong but aren't we talking about asymmetric encryption? So for Bitcoin's 160bit ECDSA addresses, you would need 2 ^{80} (~ 1.2 septillion, i.e. 25 digits) generations. Far easier than cracking symmetric encryption, you don't have to wait for the next century to reclaim lost coins.




ArtForz


March 24, 2011, 02:24:57 PM 

it's ECDSA using secp256k1 curve, so 2^{128} not 2^{80}.

bitcoin: 1Fb77Xq5ePFER8GtKRn2KDbDTVpJKfKmpz i0coin: jNdvyvd6v6gV3kVJLD7HsB5ZwHyHwAkfdw



Jim Hyslop
Member
Offline
Activity: 98
Merit: 10


March 31, 2011, 03:13:26 AM 

I personally wonder about the difficulty of discovering someone's private key in their wallet.dat by brute force attack. I think this would require 2^{256} hashes to guarantee finding the private key with an average crack time of 2^{255} hashes. Can anybody familiar with cryptography answer that question and/or elaborate?
If you're trying to break the private key, forget the hashes. A Bitcoin address is a hash of the public key, which you already know, so there's no point in trying to break that hash. I'm sure there's plenty of literature on the web about how long it would take to find a private key by brute force.

Like my answer? Did I help? Tips gratefully accepted here: 1H6wM8Xj8GNrhqWBrnDugd8Vf3nAfZgMnq



