Bitcoin brainwallet implementation in Rust

[programmer-frank]

I've implemented the algorithm for brainwallets from https://www.bitaddress.org in Rust as a command line program, for learning how it works and to get more practice with Rust:

https://github.com/FrankBuss/brainwallet

I guess it could be simplified with the bitcoin crate, but I wanted to use just the basic algorithms which are common to many blockchains, like SECP256K1 and SHA256, to see how the Bitcoin addresses and keys are generated.

Should be easy to extend it to other blockchains, or could be used as a starting point for your own blockchain (which I plan to do someday).

[pooya87]

It goes without saying that brainwallets, specially those that perform a single SHA256 hash on a user given password, are not safe at all. Collection of 18.509 found and used Brainwallets.

I don't know how Rust works but if it "throws exceptions" you should get in the habit of handling them without letting your program crash. For example the following line may throw an exception if seed_bytes value is not in range defined by secp256k1 curve. Even though this particular case is very unlikely but it is a good habit to have "error handling" in your code.

Code:

let secret_key = SecretKey::parse(&seed_bytes).unwrap();

[programmer-frank]

You are right, I should probably print a nice error message in case of this error. But it wouldn't crash, at least not in the way C++ crashes with segfaults or undefined behavior. unwrap creates a controlled panic, and unrolls the stack, same like an exception, and then prints the panic on the console (with call stack in debug mode, and if you set an environment variable for it).

Do you have a test case which creates this error? The BitAddress website uses the same function, but looks like it doesn't handle such errors either.

[pooya87]

Do you have a test case which creates this error?

No because as I said this is highly unlikely. You are basically looking for an input (seed variable) that could produce a SHA256 hash that is between N and 2²⁵⁶ and that range is very small in comparison to 1 to N range. We don't know any message that produces such a hash.

What you could do for this test is to split the "create_key_pair" method into two parts, one computes the hash and the other creates the key pair. Now you can feed any hash result you want to the second method like 2²⁵⁶ and see how it fails.

[programmer-frank]

I fixed it 
https://github.com/FrankBuss/brainwallet/blob/325baaa769902ce19b52891db38f8c4736356f43/src/main.rs#L23-L38

[larry_vw_1955]

It goes without saying that brainwallets, specially those that perform a single SHA256 hash on a user given password, are not safe at all. Collection of 18.509 found and used Brainwallets.

Well I don't know if I could agree with that.It all depends on the passphrase. If the passhprase has enough entropy then it is just as secure as a bitcoin address you would generate by throwing dice.

 But just for the sake of argument, to your way of thinking, how many hashes would make it become "safe"?

[pooya87]

Well I don't know if I could agree with that.It all depends on the passphrase. If the passhprase has enough entropy then it is just as secure as a bitcoin address you would generate by throwing dice.

Only a 128 bit entropy entered into a cryptography function can provide the same security as a randomly generated private key. Human beings are terrible at memorizing things in general and they are even worse when the length of what they have to memorize is too long.
In other words the whole idea for a brainwallet is moot if you are using such a big entropy.

But just for the sake of argument, to your way of thinking, how many hashes would make it become "safe"?

There is no easy answer to this. But for your information we are currently computing 165 exa double_SHA256 hashes in bitcoin mining. That is:

Code:

165,000,000,000,000,000,000

[larry_vw_1955]

But just for the sake of argument, to your way of thinking, how many hashes would make it become "safe"?

It's a bit different, but check https://keybase.io/warp.

yeah  warpwallet is a pretty serious attempt to make a real strong brainwallet. uses 2^18 iterations. takes a ton of time on my little computer.

as for the OP's implementation as he mentioned he just uses a single sha256 of the passphrase. unless someone has a seriously hard to guess password you can't really expect it to not be hacked. i guess you could always salt the passphrase with your email address manually so they would have to "target you individually" then if they didn't know you yourself were using a brainwallet well, they wouldn't be able to do anything!

There is no easy answer to this. But for your information we are currently computing 165 exa double_SHA256 hashes in bitcoin mining. That is:

Code:

165,000,000,000,000,000,000

Assuming that is per second that's still a piss in the ocean. So I dont think brainwallets are under any serious threat.

[moderator's note: consecutive posts merged]

[pooya87]

Assuming that is per second that's still a piss in the ocean.

In what world 165 quintillion hashes per second is considered "piss in the ocean"?

So I dont think brainwallets are under any serious threat.

Tell that to the million+ dollar worth of bitcoin that was stolen in total from brainwallets.

[programmer-frank]

In what world 165 quintillion hashes per second is considered "piss in the ocean"?

Well, it is only 0.00000000000000000000000000000000000000000000000000000014% of all possible SHA26 hashes (assuming a bijective mapping, so probably a bit higher, if there are collisions).

[pooya87]

Well, it is only 0.00000000000000000000000000000000000000000000000000000014% of all possible SHA26 hashes (assuming a bijective mapping, so probably a bit higher, if there are collisions).

True, but in the context of a brainwallet we aren't talking about a 256-bit entropy. We are talking about user provided passwords and in this context even a big 8 character passphrase consisting of random alphanumerical characters (eg. _Cf}u$b0) needs computing 6 quadrillion hashes (0.006 quintillion) in total, the "165 quintillion hashes per second" rate is huge.

[larry_vw_1955]

Well, it is only 0.00000000000000000000000000000000000000000000000000000014% of all possible SHA26 hashes (assuming a bijective mapping, so probably a bit higher, if there are collisions).

True, but in the context of a brainwallet we aren't talking about a 256-bit entropy. We are talking about user provided passwords and in this context even a big 8 character passphrase consisting of random alphanumerical characters (eg. _Cf}u$b0) needs computing 6 quadrillion hashes (0.006 quintillion) in total, the "165 quintillion hashes per second" rate is huge.

I do see what you're saying and it caused me to reconsider exactly what is a brainwallet. At first I didn't think it would be something someone has to "remember". But you are taking that to be a requirement.

What if I or someone else came up with some super-secretive procedure for taking a phrase and turned it into a 256-bit private key. Since the method is not published and only exists in their head, although they would have certainly tested it on a computer at some point, as long as they remember the procedure and the passphrase, I don't see how someone woudl be able to crack that. And the phrases could be very simple and yet since no one has the secret method, they don't even know where to start even if they know the phrase itself. yes the sample space has lower entropy but the problem is that you can't just check all 8 character passphrases because you don't even know the algorithm for converting them into a private key.

[pooya87]

What if I or someone else came up with some super-secretive procedure for taking a phrase and turned it into a 256-bit private key.

All I can say to that is people who are not a cryptography expert should never try to invent their own cryptography algorithms. Not to mention that you still can't solve the other more important issue with brainwallets which is the issue with forgetting things over the long term.

[PrimeNumber7]

Well, it is only 0.00000000000000000000000000000000000000000000000000000014% of all possible SHA26 hashes (assuming a bijective mapping, so probably a bit higher, if there are collisions).

True, but in the context of a brainwallet we aren't talking about a 256-bit entropy. We are talking about user provided passwords and in this context even a big 8 character passphrase consisting of random alphanumerical characters (eg. _Cf}u$b0) needs computing 6 quadrillion hashes (0.006 quintillion) in total, the "165 quintillion hashes per second" rate is huge.

I do see what you're saying and it caused me to reconsider exactly what is a brainwallet. At first I didn't think it would be something someone has to "remember". But you are taking that to be a requirement.

What if I or someone else came up with some super-secretive procedure for taking a phrase and turned it into a 256-bit private key. Since the method is not published and only exists in their head, although they would have certainly tested it on a computer at some point, as long as they remember the procedure and the passphrase, I don't see how someone woudl be able to crack that. And the phrases could be very simple and yet since no one has the secret method, they don't even know where to start even if they know the phrase itself. yes the sample space has lower entropy but the problem is that you can't just check all 8 character passphrases because you don't even know the algorithm for converting them into a private key.

So maybe a particular method of generating a private key has 30 (for example) bits of entropy, but the fact that an adversary does not know the first step in creating the private key, it would appear the private key actually has 120 bits of entropy.

For example, someone might call numpy.random.choice([0, 1], size=90), but only after calling numpy.random.seed(420), and prior to doing something that creates 30 bits of actual entropy. The private key would probably remain "private" for a long time, but once an adversary figures out the procedure, any private key created via the above procedure would be quickly learned by adversaries.

Maybe no one thinks to try the above procedure for a long time, but one day, someone learns that the above person has a lot of coin, their favorite number is 420, and they like to generate their private keys via non-standard methods. This might lead someone to try to generate private keys via psudo-random methods in various ways using '420' as the seed up to a certain level of entropy that can be easily cracked.

[larry_vw_1955]

All I can say to that is people who are not a cryptography expert should never try to invent their own cryptography algorithms. Not to mention that you still can't solve the other more important issue with brainwallets which is the issue with forgetting things over the long term.

Well I'm not sure what qualifies someone as a "cryptography expert" but I think we all use things that may have flaws. For example, BIP-32. Could 2 different starting seeds have some overlap in derived keys? If so, is that something the designer felt an acceptable occurrence? Or did they even think about that issue at all?

But you're right that the limitation of brainwallets is the human memory, but even so...

Maybe no one thinks to try the above procedure for a long time, but one day, someone learns that the above person has a lot of coin, their favorite number is 420, and they like to generate their private keys via non-standard methods. This might lead someone to try to generate private keys via psudo-random methods in various ways using '420' as the seed up to a certain level of entropy that can be easily cracked.

What I'm thinking is if I designed some super secret but easy for me to remember branwallet algorithm, it wouldn't even help you to know my starting brainwallet passphrase simply because the main source of entropy is the algorithm itself. And you could spend an eternity going through those before you hit on the correct one.

some people might argue that it's impossible to degisn such an algorithm thats easy to remember. for me, it's the opposite way. i could remember an algorithm but i would have more trouble memorizing a 30 character phrase that had 120 bits of entropy. because a human doesn't have the capability to truly generate such a thing i dont think. unless they roll dice but then that would make it impossible to memorize...

It's more likely they'll lose access to their coin because they forget small detail of the parameter/protocol specification or bug within implementation. They also need to keep the implementation software since it's unlikely they'll rewrite it when they use different device, which open new vulnerability.

Maybe but trying to memorize a 30 character phrase may not be easy either. for me, algorithms are easier to remember than long strings.

[programmer-frank]

Maybe no one thinks to try the above procedure for a long time, but one day, someone learns that the above person has a lot of coin, their favorite number is 420, and they like to generate their private keys via non-standard methods. This might lead someone to try to generate private keys via psudo-random methods in various ways using '420' as the seed up to a certain level of entropy that can be easily cracked.

Right, and in cryptography, it is always assumed that the algorithm is known. For example some malware could find the source code, if it is not developed on an offline computer with no storage, which is not how software these days is developed.

But the standard SH256 brainwallets are very safe, if the password is safe. And I don't see a problem with forgetting it. Just write it down on paper and deposit it at a safe place. There are many ways to disguise it as well, like use the first sentence in a diary. If it is personal and not found somewhere else, it would be very safe. Like "This is the diary of the very knowledgeable programmer Frank, born on x, in the city y.". No way this could be discovered with a brute-force program. It would be much more safe than a random 30 character password.

[BlackHatCoiner]

But the standard SH256 brainwallets are very safe, if the password is safe.

But, the problem is that you can't know how safe it is and most of the times, it isn't same like a seed phrase. When you pick a password, your money are vulnerable to the entropy that you, as a human, think it's unpredictable enough.

So why not just let your computer pick a random number, instead of you, which is a proven fact you can't, represented in twelve words? I mean, you can't really find much passwords which are both so strong and short as a twelve-words phrase.

[PrimeNumber7]

Maybe no one thinks to try the above procedure for a long time, but one day, someone learns that the above person has a lot of coin, their favorite number is 420, and they like to generate their private keys via non-standard methods. This might lead someone to try to generate private keys via psudo-random methods in various ways using '420' as the seed up to a certain level of entropy that can be easily cracked.

What I'm thinking is if I designed some super secret but easy for me to remember branwallet algorithm, it wouldn't even help you to know my starting brainwallet passphrase simply because the main source of entropy is the algorithm itself. And you could spend an eternity going through those before you hit on the correct one.

some people might argue that it's impossible to degisn such an algorithm thats easy to remember. for me, it's the opposite way. i could remember an algorithm but i would have more trouble memorizing a 30 character phrase that had 120 bits of entropy. because a human doesn't have the capability to truly generate such a thing i dont think. unless they roll dice but then that would make it impossible to memorize...

In my example, most of the entropy is from the pseudo-randomness, and very little from the "brain wallet" portion of generating the key.

Does calling a pseudo-random function while using a particular seed really create 90 bits of entropy? It does create a set of numbers that would take 2^90 guesses in order to be guaranteed to guess that particular set of numbers. If you know that the random function of numpy is being used, the amount of entropy is reduced to ~8.75 bits.

The problem with "inventing" an algorithm with the purpose of generating a private key is that it is difficult to measure how much entropy (security) your private key really has. If you can think of an algorithm, there is no reason why someone else couldn't think of a similar algorithm.

Although my recommendation is to create a seed that has 256 bits of entropy, if you insist on creating a brain wallet with low amounts of entropy, I would suggest using an algorithm that is computationally inefficient. If it is difficult to calculate the private key from the 'brain wallet' phrase, then each bit of entropy is "worth" more. Obviously, this assumes that new technology will not be invented that can go from 'brain wallet' phrase to private key more efficiently in the future.

But the standard SH256 brainwallets are very safe, if the password is safe. And I don't see a problem with forgetting it. Just write it down on paper and deposit it at a safe place. There are many ways to disguise it as well, like use the first sentence in a diary. If it is personal and not found somewhere else, it would be very safe. Like "This is the diary of the very knowledgeable programmer Frank, born on x, in the city y.". No way this could be discovered with a brute-force program. It would be much more safe than a random 30 character password.

My understanding is that most scripts/programs that try to find/steal brain wallets are not doing what most would describe as "brute forcing". I believe they will look at literature to find phrases, and use those phrases against bitcoin addresses that are known to have ever received any transactions. They likely also append things such as birthdays, popular vacation locations, and various punctuation to these phrases. This is somewhat similar to trying 'password1' when someone's known password is 'password!'

There are around 171k words in the English dictionary, and randomly using 7 words as a brain wallet would generate about 121 bits of entropy. The risk of using your method is that if anyone has ever said the phrase you use in a book, movie or TV show, (or something similar), or has ever appeared in a news article, blog post or forum post, there is a high probability that someone will try your phrase against bitcoin addresses that have ever received coin. If your brain wallet is not generated randomly, it will not have anywhere near the amount of entropy you think it has.

[larry_vw_1955]

Right, and in cryptography, it is always assumed that the algorithm is known. For example some malware could find the source code, if it is not developed on an offline computer with no storage, which is not how software these days is developed.

Not always. Not with my brainwallet idea. The algorithm needs to be something I keep in my head only. And that's easily doable.

But the standard SH256 brainwallets are very safe, if the password is safe. And I don't see a problem with forgetting it. Just write it down on paper and deposit it at a safe place. There are many ways to disguise it as well, like use the first sentence in a diary. If it is personal and not found somewhere else, it would be very safe. Like "This is the diary of the very knowledgeable programmer Frank, born on x, in the city y.". No way this could be discovered with a brute-force program. It would be much more safe than a random 30 character password.

maybe it's just me but i wouldn't feel secure using a setup like that. people know how to go about hacking it. it's trully just a matter of time before they get around to trying that particular phrase you mentioned. and then your mone is gone by bye. as well to be anal, brainwallets should only be stored in the brain not on any paper anywhere. bank employees have keys to deposit boxes robbers dont need them.

[pooya87]

Well I'm not sure what qualifies someone as a "cryptography expert" but I think we all use things that may have flaws. For example, BIP-32. Could 2 different starting seeds have some overlap in derived keys? If so, is that something the designer felt an acceptable occurrence? Or did they even think about that issue at all?

That's not a flaw. Such a collision in cryptography exists in all algorithms and it is only considered a flaw if one could spend reasonable amount of computing power and find such collision in reasonable time. Otherwise when it would take something like millions of years we consider it safe.