Topic: Pondering a Highly Secure Deterministic Brainwallet (Read 3263 times)

https://gist.github.com/gavinandresen/3840286

I'm struggling searching this.  Any more hint at specifically what I'm looking for?
Thanks.


Very excellent point.  Well said.

As Bitcoin gains in popularity, what is more likely than an intentional cracking is that someone else (of the over 7 billion people on earth) that also happens to be a fan of both the game of chess and Fibonacci accdentally use the same sequence as you.

Humans just aren't very good at being random.  We just aren't wired that way.  We tend to share interests and thought patterns.

Even if the others that like chess and Fibonacci don't choose the exact same sequence as you, one of them very well may mention in a public forum that he has an idea for using chess matches and Fibonacci sequences to create a brainwallet.  At that time, a hacker can create a program to cycle through every published chess game applying Fibonacci sequences to the selection criteria.

As much as we all like to think that we are the only person capable of choosing a particular pattern for selecting information, the fact that a pattern is being used at all is a strong indication that someone else in the world somewhere would come up with the same idea eventually.

Have you read Gavin's stuff on using sentries?  Look it up if you haven't.

I have already put 0.025 BTC in a brainwallet using a variation of my theme a couple of months ago, and it is still safely there.  I'll monitor it for a while.

Diceware is the best way to create high-entropy passphrases, mine is ~128 bits for ten words, remembered it in 10 seconds, a 256 bits entropy passphrase shouldn't be much harder to remember.

Just create a wallet, send 0.001 BTC to it and wait for anyone to crack it .

Yes, probably.  Maybe not very soon.

There aren't that many published games.  There aren't that many sequences of moves in a game.  Your final obfuscation is something that password crackers already check.

I appreciate all the good advice from everyone.  I think I will stay away from this approach, even though I still find it hard to believe that anyone would have ever discovered my brainwallet passphrases.

Since I won't be using this technique, I might as well disclose the actual approach I was going to use.  When it is clear how I was obscuring the passphrase, I'd love to get comments with honest thoughts on whether there was a chance that someone would find the passhphrase.

First, I only planned on using one chess game (yes, I was using the chess structure).  It was a long game, with lots of moves to work with.  It was Nikolic v. Arsovic in 1989 in Belgrade.  Since I was only going to use this one game for all my passphrases, I only needed to remember a 4-digit PIN for the clue to generate my passphrase.  This allowed me to use memorable PINs in my life as the starting point.

For this example, my PIN is 1110, which means that I will start at move #11, and record 10 moves.  For my first obfuscation, I don't record sequential moves, but rather start at move #11, and index the moves by the Fibonacci sequence.  So, the 10 moves that are recorded are: 11, 13, 16, 21, 29, 42, 63, 97, 152, 241.  I first record the moves alternating white, black, etc.  Then I repeat the moves but do the opposite alternating sequence (black, white, etc.).  That results in the intermediate result:

Rb1g5c5Qe8Ne3Rc3Kg3Rh2Rc2Rd8f5b4g4Kh1Re8Be2Rb6Ke2Kd6Bc4

My final obfuscation is to take the intermediate result, and adjust each character at a Finonacci position.  If the character is alphabetic, then I change its case.  If it is numeric, I replace the digit with the symbol on the same key of my keyboard.  (i.e. a "3" becomes a "#").  This final obfuscation becomes the final brainwallet passphrase:

rB!g%c5qe8Ne#Rc3Kg3RH2Rc2Rd8f5b4g$Kh1Re8Be2Rb6Ke2Kd6Bc$

It generated a 55 character passphrase which has an apparent 322 bits of entropy.  I realize that this seems so very complicated, but I assure you that it is firmly implanted in my memory.  And I was going to leave very detailed instructions for my family in a TrueCrypt container that they would have access to.

Do you really think anyone would have ever generated this passphrase with a cracking approach?

I wanted to add the following notes to this discussion if you find them relevant:

• Security through obscurity is bad. Don't do it. You must always assume that an attacker knows your password generation schemes.
• In light of the previous point, the only correct way of generating a brain wallet is to pick character or words with sufficient entropy in a complete random fashion. For example a 12 word diceware (where the random process is the results of throwing dices). An attacker that knows you used diceware to generate your passphrase can not recover any information on it.

If you don't follow these elementary security practices, you will get hacked. Don't play with fire when your money is at stake.

You may be right, but I thought that all combinations of both passphrases would be necessary to break the encrypted private key.  So I would think that the full entropy of both are additive.

In any case, I appreciate all the good input for consideration.  My intuition tells me that if an underlying structure high enough entropy, and some human convoluted obfuscation is applied, the resulting passphrase output will be safe.  But as you point out, the sophistication of the development of cracking techniques will keep getting better.


Very good points here.  However, our whole bitcoin set of processes and methodologies are quite complex and convoluted in themselves.  My biggest fear is irrevocably losing my few BTCs.  I am very intrigued by encrypted private keys and brainwallets -- so this has been an interesting exploration for me.  Besides my small test, I don't know if I will leverage my approach for real.

Of course further obfuscation is possible, making it more difficult to remember.


(If I understand you correctly) If you assume that cx-xxxx gives you 75bit then cy-yyyy doesn't add another 75bits since it is the same strategy and the same championships. So you only get entropy from repeating procedure: 2bits + 5 almost random numbers (14bits) + bip38 (20)  = 36bits.


Nowadays cracking techniques are becoming very sophisticated. Very huge computers are equipped with databases of human generated passwords revealed in many website leaks. As a result it is possible to uncover most popular obfuscation strategies, words, numbers used to generate password. It is very easy to underestimate current, and most importantly future AI capabilities in this area. Using non standard method is just another way to add entropy, and sth to remember. But it is very misleading to assume that computers wont try to break those non standard methods. And it is very easy to overestimate human generated password entropy. 

My point is that while it is possible to create safe brainwallet with human generated obfuscation method, it is very difficult thing to do so. It may be slightly easier to remember, but they require a lot of time to be created. Also, while people can't calculate entropy properly they will never be sure if they created enough of it. Even if you come up with clever and provably safe instructions, most people would just not follow them properly (and the method will no longer be non standard).

Agreed.  I just want the thing to remember to be easy to remember, and also safe to record openly if necessary.

I'm not in agreement with this assessment.  (But you've got me thinking!)

First, a minor part of the disagreement is that if I were to use the chess approach, I would select a much, much more obscure game to use for the passphrase data.  With easily up to a million recorded games, that adds another 20 bits of entropy to my BrainSeed.  And I think there is more obfuscation possible.  But let's say that the BrainSeed has 75 bits of entropy.  In normal BrainWallet cracking efforts, the target is to try derived addresses and check if there is BTC there.  However, here the target is to find a passphrase that has to be used in conjunction with another passphrase.  So really there is another 75 bits of entropy to deal with.  And then the iterative process adds a lot of time delay between each cycle.

Second, my real desire here is to create a Brainwallet passphrase with high enough entropy that the standard cracking efforts won't uncover.  And with BIP38, they would have to crack another high entropy passphrase to get at the encrypted private key.

You've got me thinking hard about how realistic it is to figure out the obscurity of the overall approach.  I guess the real lesson is to make the underlying structure highly obscure.  (I'm quite confident that my own underlying structure is highly obscure.)

That is not possible. You have to remember something. Either these are words, symbols, functions, method of obfuscation - you still need to remember them. As a result you get passphrase with some entropy. But calculating this entropy is not that easy as just calculating length of the passphrase. You need to calculate entropy of obtaining that passphrase. And that entropy may depend on the information the attacker has about his target. 


So let's assume that attacker somehow get the information about you. Now we will estimate the enropy:
topic: chess matches - one of ~32 most likely topics - 5 bits of entropy
some popular game: one of ~128 most notable ones - 7 bits
shortcut of above 2 steps "c1" - one of ~16 most likely - 4 bits
common separator "-" - 2 bits
method of further obfuscation - one of ~64 most likely ones - 6 bits
first digit 0 or 1 - 1bit
three random digits - 10bits
bip38 - i don't know exactly but perhaps ~20 bits

So to sum up we get ~55 bits of entropy of brain wallet if the attacker know sth about you. If not, add ~5 bits and you get brainwallet with ~60bits. While it may be enough today, it is much lower than recommended standard of 128 bits. And I wouldn't recommend to choose anything below 80bits.

While above calculation may seem to overestimate the attacker capabilities, you need to remember that passwords are being broken by highly intelligent AI which is aware of all common human password choosing strategies.

You also have to take into consideration that when humans are told to follow your procedure, they would probably choose sth like: take first 20 words of bible, choose every 2nd, and add some 2 digit nr to get <40bit brainwallet entropy, which is a disaster.

That is way it is recommended just to create 12 random word (128bit) seed. Then you can bip38 it (~20) with 4 random words from seed(~40) and hide it physically (~20) to get total ~80bits (in case you forget the whole 12 initial words).

One of the objectives is to create encrypted private keys with BIP38, so I need to do the intermediate steps of having private keys to encrypt.


My other objective was in being able to have nothing recorded anywhere.  I would create a set of encrypted private keys. Then populate the addresses with BTC.  Then delete all traces of everything (except for the address, which I can keep handy to include in a watch list.)  This is a long term cold storage brainwallet.  The only thing I would record in plain sight is a clue to myself about how to recreate everything.  Using the chess example from ablove, that would be something like: 1) MindHash c1-0308 & c1-0708; 2) Create 50 encrpted PKs.

From my limited understanding, I don't see how this physically does anything.

If your would-be attacker has your wallet, chances are he also has your MindHash program that converts your small string into a huge function.
What's stopping him from just brute forcing your MindHash? I understand that this process would take a very long time but I don't see it taking any longer than a multi word bitcoin wallet password, seems a little convoluted.

Why is it not a good idea to use your BrainSeed to directly create the private keys?

e.g. PK1 = sha256(BrainSeed)
PK2 = sha256(PK1)
PK3 = sha256(PK2)
etc.

The HD wallet spec is available here:

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

So, to finish the thought and close the loop with the first post:

I use the MindHash process to generate two high-entropy passphrases.  I then use the process in the original post to create a series of encrypted private keys.

Since this can all be created from scratch repeatedly, there is really no reason to have to record anything in hidden ways.  And if you have a catastrophic loss of records, it can all be re-created easily.

kjj,

I don't know the HD Wallet spec.  Is it available in a HTML format like bitaddress.org is to generate keys?  And does it allow for encrypted private keys?

Regarding the passphrase with high entropy.  It is possible to memorize things that large; when I was in highschool I could recite 200+ digits of Pi.  But my approach is designed to help me generate the high entropy passphrase reliably without having to memorize things.  I’ve had some folk ask me specifically what I mean by a MindHash.  It is a method of reliably and repeatedly generating the passphrase from a very simple coded seed.  I am not going to share the specific variant that I personally use since that would render my private keys (possibly) discoverable, but I will share with you a completely different example that is in the same general spirit of my process.

It starts with something that you are very familiar with that already has a high level of complexity to build from.  This “something” is the underlying structure that has some high degree of complexity, and it is also something you are aware of and know how to easily access.  You then do some manipulation of the information you have to create the passphrase.  You also encode what you need to know to recreate it.  This final encoded clue is what I call the BrainSeed.  From the simple BrainSeed, you can recreate the complex passphrase.

For this example, the simple BrainSeed that you have to remember is:

c1-0520

That simple BrainSeed reliably generates this passphrase:
Nf3Be2H30-0Be3cxD4a3Nc3NB5Ne5!QxE2Rac1BG5Bxf6NC4!Nxb6!RFd1Qe3!d5!rxd5

It is a 69-character passphrase with an apparent 452 bits of entropy.  
All this from a BrainSeed of c1-0520.

So how does this convoluted MindHash work?  I’ll tell you.  “c1” represents my favorite chess match, which happens to be Game 1 of Deep Blue versus Kasparov in 1996.  “05” means to start at Move 5 of that game, and “20” means to record the next 20 Moves.  I just record the moves in standard chess notation.  This example MindHash also only records the White moves.  And one further convolution is that the “05” also instructs me to change the case of every 5th alphabetic character.  (Every 5th character become upper-case if it is already lower-case, and it becomes lower-case if it is already upper-case.)

So, an another example from the same game, a code of c1-0710 would generate this passphrase:
h30-0Be3cxd4A3Nc3Nb5Ne5!qxe2Rac1

It is a 32-character passphrase with an apparent 209 bits of entropy.

In the example, the only reason for “c1” is in case you may want to generate other passphrases from other favorite chess games, such as c2 or c3, etc.  However, if you only want to use one game and will always remember that your MindHash is always using c1, you can just use a 4-digit PIN to create a repeatable high entropy passphrase. So, “1209” becomes: Nc3Nb5Ne5!Qxe2RaC1Bg5Bxf6Nc4!Nxb6!

There you have it.  Sorry if I have messed up the chess usage for the underlying structure.  However, if you still like the chess staring point, you can convolute the MindHash however you want, as long as you can remember it.

I still am interest in hearing feedback on the overall process of generating encrypted deterministic brainwallets.

Edit: Spelling error