Pondering a Highly Secure Deterministic Brainwallet

[bloss]

I have been thinking long and hard about how I would like to structure my cold storage solution.  It involves a deterministic brainwallet approach.  I’m quite confident that it is extremely secure, and I would like to check my thinking with this community.  I am still quite new to this space, and I am not a programmer, so I don’t understand the deep technical workings of the open source code of brainwallets and encrypted keys.

I have read just about everything I can find about brainwallets, and have seen all of the very vocal advice to not use them.  That is all predicated on the assumption that our passphrases are not sufficiently random.  However, I have formulated my own MindHash approach that can repeatedly generate a large set of passhphrases that each well exceed 160 bits of entropy.  I’ll just have to say “trust me that I can do this” – and I am interested in your feedback about the security of the rest of my deterministic brainwallet design.

First some notation to make the rest of the description more clear:

PP1: a high-entropy passphrase to be used as the initial brainwallet seed
PP2: a different high-entropy passphrase to be used to encrypt all subsequent private keys

PK1: the first private key
PKn: the nth private key

ePK1: the first encrypted private key
ePKn: the nth encrypted private key

I use bitaddress.org to create the brainwallet private keys (PKn)
I use bit2factor.org to create encrypted private keys (ePKn) from the private keys (PKn).  (bit2factor.org uses BIP38 to encrypt private keys, and it works with blockchain.info for importing back for access to the money.)
(Of course, these are run while disconnected from the internet.)

So, here is the process to deterministically create n encrypted private keys and associated public addresses:

Use PP1 as initial passphrase to create the brainwallet PK1
Use PP2 as passphrase to encrypt PK1 to create ePK1
Use ePK1 as passphrase to create the brainwallet PK2
Use PP2 as passphrase to encrypt PK2 to create ePK2
Use ePK2 as passphrase to create the brainwallet PK3
Use PP2 as passphrase to encrypt PK3 to create ePK3
.
.
.
Use ePK(n-1) as passphrase to create the brainwallet PKn
Use PP2 as passphrase to encrypt PKn to create ePKn

Then, to put money into these addresses, I send small amounts of coin to addresses from the bottom up.  In other words, I send money to public address n first, then (n-1), then (n-2), and upwards.  But I would not put any money in the first few addresses (1, 2, 3, etc) just to be extra paranoid.

To use money, I would withdraw from the bottom up, so that the imported private keys can be discarded without jeopardizing the security of other addresses.

Benefits as I see them:
1) The actual final wallets are built with highly random private keys from prior steps in the deterministic approach, and a brute force attack would require solving two high-entropy passphrases.
2) I can very openly record the seed that my MindHash approach needs to generate the two high-entropy passphrases.  I can write the seed down, keep it on my computer and cloud storage, and in a safe deposit box.
3) With BIP38, even if one of my private keys was discovered, it is still strongly encrypted.

As a small test, I put a few BTC in one of my generated ePK1 addresses quite a while ago, and they are still safely there untouched.

At some point, I will have to find some secure and trusted DeadManDrop solution to document my scheme and mindhash approach for my family.  Any suggestions on that would be appreciated.

In the meantime, I look forward to your thoughts and feedback.  I am also specifically interested if the Key Derivation Functions of brainwallets in bitaddress.org and of BIP38 in bit2factor.org from a technical limitation standpoint as it pertains to my scheme above.

EDIT: a couple of minor typos corrected

[kjj]

First, there is absolutely no chance in hell that you remember a passphrase with 160 bits of entropy.

Second, why aren't you just using the published HD wallet spec, using your seed?

[bloss]

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

[bloss]

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.

[wumpus]

The HD wallet spec is available here:

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

[deeplink]

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.

[BadBitcoin (James Sutton)]

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.

[bloss]

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

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.

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.

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.

[gglon]

But my approach is designed to help me generate the high entropy passphrase reliably without having to memorize things.

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. 

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

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).

[bloss]

That is not possible. You have to remember something.

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

So to sum up we get ~55 bits of entropy of brain wallet if the attacker know sth about you.

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.)

[gglon]

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.

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

 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.

(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.

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.

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).

[bloss]

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.

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.

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).

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.

[plaprade]

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.

[bloss]

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?

[kjj]

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.

[dserrano5]

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.

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

[davout]

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.

[bloss]

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

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.

[kjj]

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

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.

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

[DannyHamilton]

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

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.