Wikipedia suggests that modern versions of Windows do indeed have something similar to /dev/random. I'm reasonably convinced that the seed for the algorithm is sufficiently random to be secure from an attack that exploits this lack of randomness (and, since the algorithms used in bitcoin are also used in a lot of financial software for banks, &c, it we would have bigger problems on our hands than the loss of a few bitcoins if a vulnerability were found).
That said, anyone know how large of a random number is used to start the key pair generation process? I assume that it is very large, but I wonder just how large it is. I know from experience that a modern computer can count from 0 to 2^32 in a matter of seconds without any trouble (this neglects the time taken to compute the key pairs). If the final product is to be secure to 2^160 combinations, is the initial seed at least that large? (i.e. 160 bits, not 2^160 bits... that's more memory than is on the planet... it's close to being more than could conceivably be stored on the planet, given that 2^160 is about 1% of the number of atoms on Earth, by rough, rough estimate: http://education.jlab.org/qa/mathatom_05.html).
Topic: Security Algorithm for Private Keys (Read 1128 times)
I believe linux clients typically use /dev/random, which gathers entropy from user input over time (mouse movements, key presses). /dev/random is generally considered to be safe for cryptographic purposes. There might be some issue if people use /dev/urandom (random stops you if you haven't generated enough entropy, urandom does not) on a commonly distributed live CD. In that case, people might be using similar sets of data for their seed. It would take someone who is very experienced and has a lot of time on his hands to find just the right vulnerability.
I'm not sure about Windows clients, though. I hope they've got something similar.
I'm not sure about Windows clients, though. I hope they've got something similar.
Earlier, in this thread: https://bitcointalksearch.org/topic/m.1003815, I was looking into just how difficult it would be to attempt to recover lost coins, or, equivalently, to steal unspent coins, by breaking the security function used to generate private keys. (If you want the summary, it would be many millions of dollars more expensive and take thousands of times longer to have a millionth the chance of making a millionth the payout as compared with playing the lottery... hardly good odds).
Now, while I have a cursory understanding of how the elliptic curve hashing function works (not even sure if that's the right term to use here...) and it goes something like this: Some RNG provides a seed to an algorithm that produces a public and private key. The public key is widely distributed and is easily obtainable. The private key, on the other hand, is kept secret and is what is stored in the wallet.dat file. Without getting too much more technical, the private key allows a user to demonstrate ownership of coins and to spend them, and if someone were to guess/generate someone's private key, they could steal those coins.
In the previously mentioned thread, it was shown that just randomly guessing private keys is woefully slow in an attempt to steal/recover coins. You would literally be waiting for the sun to burn out. However, I'm now curious what seed value goes into the asymmetric key generation algorithm, and how that seed is generated. As many people who read up on computer technology are aware, a true random number generator is basically impossible to create, short of implementing it in hardware. I know that some RNGs use a very precise version of the system time as a seed, but that would reduce the problem of brute forcing the key pair from ~2^160 combinations that was quoted for RIPEMD-160 to around 2^46, given a time span of a day and a resolution of 1 nanosecond. While this alone is plenty of entropy to guarantee that two addresses generated for different people will be almost certainly different, it is hardly enough entropy to fend off a brute-force attack that uses this knowledge. Does anyone know what additional entropy is added to the RNG used to create bitcoin private keys?
I'll repeat an earlier disclaimer:
I'm not interested in attempting to steal coins, but I think that by exploring avenues that I would attempt to go down if I were trying to steal coins it is possible to show how unreasonable such an attack would be. I fully hope and expect to find that it is incredibly difficult (to the point of waiting for the sun to burn out) to fake the output of a RNG and generate a pre-existing public/private key pair.
Thoughts?
Now, while I have a cursory understanding of how the elliptic curve hashing function works (not even sure if that's the right term to use here...) and it goes something like this: Some RNG provides a seed to an algorithm that produces a public and private key. The public key is widely distributed and is easily obtainable. The private key, on the other hand, is kept secret and is what is stored in the wallet.dat file. Without getting too much more technical, the private key allows a user to demonstrate ownership of coins and to spend them, and if someone were to guess/generate someone's private key, they could steal those coins.
In the previously mentioned thread, it was shown that just randomly guessing private keys is woefully slow in an attempt to steal/recover coins. You would literally be waiting for the sun to burn out. However, I'm now curious what seed value goes into the asymmetric key generation algorithm, and how that seed is generated. As many people who read up on computer technology are aware, a true random number generator is basically impossible to create, short of implementing it in hardware. I know that some RNGs use a very precise version of the system time as a seed, but that would reduce the problem of brute forcing the key pair from ~2^160 combinations that was quoted for RIPEMD-160 to around 2^46, given a time span of a day and a resolution of 1 nanosecond. While this alone is plenty of entropy to guarantee that two addresses generated for different people will be almost certainly different, it is hardly enough entropy to fend off a brute-force attack that uses this knowledge. Does anyone know what additional entropy is added to the RNG used to create bitcoin private keys?
I'll repeat an earlier disclaimer:
Quote
I don't want to spread FUD--I feel like the average wallet is safe, and countermeasures against this type of attack should be straightforward: since it cannot steal an entire wallet, just the coins from a single transaction (assuming those coins have not been spent again, and even assuming that such an attack is possible), keeping coins as the result of a large number of small transactions instead of bundled as a single transaction would greatly increase the cost and decrease the attractiveness of such an attempt. I'm just curious about what makes bitcoin safe (and on if it is economically viable to attempt to "mine" lost coins that seem abandoned).
I'm not interested in attempting to steal coins, but I think that by exploring avenues that I would attempt to go down if I were trying to steal coins it is possible to show how unreasonable such an attack would be. I fully hope and expect to find that it is incredibly difficult (to the point of waiting for the sun to burn out) to fake the output of a RNG and generate a pre-existing public/private key pair.
Thoughts?
Jump to: