How to Create a Truly Randomized Private Key that Could Never be Figured Out?

[Robvcompton]

I'm having a problem understanding how to create secure and randomized private keys for paper wallets. Let me explain what I understand so far and then you can let me know if I'm misunderstanding something...
 
When your private key has been imported into the client and it becomes a digital wallet, you can choose to encrypt it by choosing a pass phrase. This pass phrase protects your digital wallet in case it's ever stolen from your computer by a person or malware/viruses, etc...
 
You can turn this same digital wallet into a paper wallet by dumping the private key. You then write down your address and key and hide it somewhere safe. Rather than reusing the same private key though, the best way to do this would be to create a new paper wallet off-line, preferably on a boot CD of Ubuntu and then transfer your coins to the new address.
 
If this is all correct so far, let me explain my problem in more detail. What I need to do right now is create a bunch of brand new private keys and addresses so I can make paper wallets out of them. I encountered 3 problems though, which I detail below.

1. It's been said not to trust random private key generators because they're not random enough and can be figured out by hackers, putting your newly created keys at risk. After hearing about this, I went searching for another way to create secure private keys. I then found out about http://brainwallet.org/. Using that website, rather than using the random key generator, I can enter in my own pass phrase, which will convert what I wrote into a new private key that I could then use. User input makes the resulting private key more unique than anything the random key generator algorithm could come up with by itself.

2. This is where I ran into the second problem. It seems that when people make brain wallets, they use easy to figure out pass phrases. They use lines from books or movies, or anything simple. Hackers then try out different pass phrases until they find one that leads to a private key that has money in it, which they then steal.
 
3. So I don't want to use a random key generator and I don't want to use a simple pass phrase on brainwallet.org to create my own unique key. This gave me the idea of entering in a bunch of gibberish as the pass phrase, for example: fgjDLKJH*gu48;p(guiMmp;r,/;)$%I^)WP$^?)_-[.-HKED)HPvre,/ptrkp Using brainwallet.org, all that gibberish would then be converted into a unique private key which I could then use. It would be much harder for hackers to figure out that pass phrase than something like "The dog jumped over the moon". But then I found out that even typing a bunch of keys is not TRULY random, since there can be some minor repetition. It might take hackers longer to figure out, but it's possible they could.
 
So my problem is, how do I create a TRULY randomized pass phrase to be used on brainwallet.org, so that it will create a TRULY randomized private key that nobody can ever figure out? I've heard about something called Diceware, but I haven't looked into it yet. Is that an acceptable method or is there something better out there I can use?

Thanks for any help!

[dwdoc]

Your long gibberish entry into the brain wallet will never be cracked and is the safest way to go (assuming you generate it off line with ubuntu as you describe).
This assumes no one else has access to the private keys on your paper wallets. If you want to add an extra layer of security (in case someone finds your paper wallets) you can add an additional memorable pass phrase to further encrypt your private key using BIP38 encryption.

[Robvcompton]

Thanks! Just out of curiosity, would you also recommend Diceware for creating strong enough random pass phrases? I'm just wondering if it's also a good method to use.

[deepceleron]

It's best to use a wallet address that you can never figure out, except by storing the raw secret in your wallet or offline. This precludes the use of human-comprehensible phrases, or by typing in data that you think looks random enough.

Bitcoin wallet software takes care of the randomness for users. If you need a strongly-generated address that doesn't use unobservable methods, I made a paper wallet address creator here:

https://bitcointalk.org/index.php?topic=361092

You can memorize a wallet private key that has been securely generated. I call this a rain-wallet (as in Rainman).

[dwdoc]

Diceware is only useful if you are trying to memorize your private key which is not necessary if you are using a paper wallet and theoretically less secure than a gibberish password.

[RoxxR]

I like the "nobrainr" script very much.
(Google it). It is inspired by diceware and i believe it satisfies your requirements by generating addresses that you can use as a brainwallet!

All you will need is an offline computer and 1 to 5 dice!

[dwdoc]

I have a somewhat related video showing how to create a paper wallet using a windows PC and a single CD. No usb drive necessary:

http://youtu.be/azZYO4FuBCs

[chandrew]

Here is a website with all bitcoin private keys: http://directory.io/

we will find your private key!

[dwdoc]

Here is a website with all bitcoin private keys: http://directory.io/

we will find your private key!

Seeing that it would take more computer power than the total energy in the solar system to brute force crack a single private key, I think we're safe.

[taipo]

There are three issues at play here. Firstly is how secure is the application you use, the second is the password hashing method the application is using, thirdly is creating a password that is difficult through to almost impossible to crack.

Diceware is a method that if used correctly can decrease the chances of a state sized adversary discovering your password quite significantly, while still making the password at least memorisable.

It takes the guesswork out of password hardness. For example if the wordlist has 128k words, then a 5 word password randomly generated from that list will give you about 2^84 bits of entropy. A strong password begins at about 2^80.

Password hashes can be made exponentially more difficult to crack if the application designers correctly implement BCRYPT or SCRYPT.

It would take 100 x 10 TH/s password crackers about 563 years to exhaust the keyspace of a 5 word diceware password where the word base is 128k words ( 128,000^5 keyspace ). 72.5 million years to break a 6 word password ( 128,000^6 ) and so on.

However a good application should use lots of random entropy when generating public / private keys that takes cracking them beyond the scope of possibility.

Seeing that it would take more computer power than the total energy in the solar system to brute force crack a single private key, I think we're safe.

The bitcoin address itself is derived from Base58_Encode( Version.( RIPEMD-160( SHA-256( public_key ) ) ).Checksum ), so if you know someones bitcoin address, with enough processing power...lets say, all the processing power in the world today, you could eventually find the public key by breaking SHA-256, but you would have to break ECDSA in order to find the private key that way. If you can break SHA-256 AND ECDSA, then much of the net is broken by that too and not just bitcoin.

If a wallet however is giving up the private keys to attackers ( the most likely culprit ) then the problem lays with the on and offline application designers allowing either rogue malware or 3rd party addon derived malware to steal the private keys, or just straight leaking them somehow via a crafted request to cryptocoin wallets.