Bitcoin Forum
December 07, 2016, 08:33:51 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Security Algorithm for Private Keys  (Read 906 times)
Koooooj
Member
**
Offline Offline

Activity: 75



View Profile
July 13, 2012, 09:29:26 PM
 #1

Earlier, in this thread: https://bitcointalk.org/index.php?topic=91058.msg1003815#msg1003815, 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:
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?
1481099631
Hero Member
*
Offline Offline

Posts: 1481099631

View Profile Personal Message (Offline)

Ignore
1481099631
Reply with quote  #2

1481099631
Report to moderator
1481099631
Hero Member
*
Offline Offline

Posts: 1481099631

View Profile Personal Message (Offline)

Ignore
1481099631
Reply with quote  #2

1481099631
Report to moderator
1481099631
Hero Member
*
Offline Offline

Posts: 1481099631

View Profile Personal Message (Offline)

Ignore
1481099631
Reply with quote  #2

1481099631
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481099631
Hero Member
*
Offline Offline

Posts: 1481099631

View Profile Personal Message (Offline)

Ignore
1481099631
Reply with quote  #2

1481099631
Report to moderator
1481099631
Hero Member
*
Offline Offline

Posts: 1481099631

View Profile Personal Message (Offline)

Ignore
1481099631
Reply with quote  #2

1481099631
Report to moderator
1481099631
Hero Member
*
Offline Offline

Posts: 1481099631

View Profile Personal Message (Offline)

Ignore
1481099631
Reply with quote  #2

1481099631
Report to moderator
austonst
Member
**
Offline Offline

Activity: 77



View Profile
July 13, 2012, 09:38:11 PM
 #2

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.

Koooooj
Member
**
Offline Offline

Activity: 75



View Profile
July 14, 2012, 05:16:29 AM
 #3

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).
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!