User talk:Ryanc

Suspicious minds

Could you please explain what you found suspicious about my Brainwallet edits?

Same Ryan Castelluci from DEFCON talk?

First, if you're the same Ryan from the DEFCON talk on Brainwallets, thanks for publishing your research and increasing awareness of the issues. Your talk was one of the inspirations for adding Warpwallet to BitKey.

However if you're the same Ryan that leaves me confused, because you recommended Warpwallet yourself in your talk, and you should know the Warpwallet challenge for an unsalted 8 character password lasted for 2.5 years before it expired.

Do you disagree that using Warpwallet with a strong passphrase (e.g., eight diceware words) and an e-mail salt would provide very good security, unlike bitaddress-style brainwallets of old?

The problem with trusting RNGs to generate your wallet keys are very real:

http://www.zdnet.com/google-confirms-bitcoin-theft-vulnerability-in-android-7000019431/

Reply

Yes, that is me. In my talk, my comment about WarpWallet was intended to mean "if you still want to do something like this, at least use warpwallet instead". I regret that it was not phrased more clearly. WarpWallet is merely a bad idea (without a seed, it's about 60,000 times more work to crack on CPU) rather than a catastrophically foolish one.

Even if WarpWallet with eight diceware words is secure, I don't think that should be recommended because I believe people will not follow passphrase creation advice.

I am aware of the challenge wallet the WarpWallet creators made. A large botnet (several million nodes) could crack it in a few months (assume 10 guesses per second per node).

Tools that provide a random seed and do not allow free text entry are fine because it would take a lot of effort to use insecurely. WarpWallet is easy to use insecurely, electrum, armory, and bip39 are hard to use insecurely.

As far as bad RNGs go... I think people are safer trusting the RNG of reputable bitcoin wallets than trying to provide their own entropy. If a widespread vulnerability in those wallets is found, it would pose an existential threat to bitcoin.

Warpwallet security analysis

Hi Ryan. Thanks for replying.

What I like about Warpwallet's use of KDFs + salt is that it has the potential to raise the cost of attack beyond the point where it is worth's an attacker's trouble to attempt. You don't spend $100M cracking a $1M safe.

Whether or not that is true depends on the validity of the underlying assumptions and a bit of basic math. You're the brainwallet cracking expert so I'm very much interested in your viewpoint on this.

FWIW, as far as I can tell you made a huge mistake in your estimation of how much more difficult it is to calculate a warpwallet than a SHA256 brainwallet. You're calculation is off by 6 orders of magnitude. Warpwallet uses 524,288 iterations of scrypt + 131,072 iterations of PBKDF2. That is not 60,000 more expensive than calculating a SHA256 hashed brainwallet. It's closer to 100 billion times more expensive.

A few questions:

1) You estimated that a large botnet could crack the unsalted 8-character Warpwallet challenge within several months. What if the challenge was salted with an unknown email? Would it still be feasible in your opinion for a salted Warpwallet 8-character challenge to be cracked?

2) How much faster in your experience is a low-level (e.g., C) implementation of Warpwallet than the in-browser version? On an 3.2 GHz Core i5 the JS WarpWallet implementation takes about 20 seconds to generate a key from a passphrase. A C implementation would have to be 8X faster and run on all 4 cores to get to 10/reqs a second. Does that about match up with your real-world testing?

3) Are there any mistakes in maxtaco's cost cracking calculator: http://maxtaco.github.io/bitcoin/2014/01/16/how-jason-bourne-stores-his-bitcoin/

The calculator estimates that cracking the unsalted random 8-character Warpwallet challenge would cost $1.2M.

Here's my analysis, please correct me where you think I've got it wrong.

Assuming Max's calculation is about right, if the challenge narrowed down the salts to 2 possible e-mails then cracking cost would be $2.4M. If it provided a list of 100 e-mails then the cost would be $120M.

What that seems to imply is that even with the largest botnets and advances in future hardware a truly global search is impossible and even narrowing that down to large number of target e-mails would be unprofitable for attackers. If this is true a warpwallet cracking botnet is unlikely to be worth anyone's trouble to run in the first place.

And that's for a passphrase with just 47 bits of entropy.

If a user generated the recommended 8 words with diceware that's about 100 bits of entropy, raising the cost of attack to a million trillion trillion USD for an unsalted warpwallet, well well above what any wallet is worth under the most optimistic usage scenario.

You pointed out that users make mistakes, and we know humans are notoriously poor sources of entropy. All true, but that kind of security in depth seems to provide quite a bit of room for error. Users are not just bad at choosing passphrases, they're bad at understanding security in general. If you're not a security expert you're likely to do a poor job keeping your wallet keys secret in the face of determined attackers, regardless of how they were originally generated. In that case, a Warpwallet is not going to be the weakest link. If you know enough to create a strong passphrase, a Warpwallet is not going to be the weakest link.

Either way, a Warpwallet doesn't seem like that bad an idea. Does it really deserve to be guilty by association with naive Brainwallet implementations?

Especially when the alternative is to just trust a blackbox process to generate keys for you. I agree that a global RNG failure would be devastating to Bitcoin and cryptography in general. But a local failure like the ones that have already happened would just result in your coins getting stolen.

Why should we place any more faith in the ability of a non expert to verify the integrity of the software they are using than in their ability to generate a secure passphrase?

Generating a secure passphrase with a verifiably secure source of entropy is actually vastly more simple than trying to rule out all the places a backdoor in the automatic seed generation process could be hiding. And so is explaining how to generate a secure passphrase vs how to verify that you're using a faithful wallet.

This touches the heart of the issue because the Bitcoin wiki is an educational resource for non-experts. If we overestimate the risks of a Warpwallet while underestimating the risks of unfaithful software we may end up giving users bad advice and increase the probability they will lose coins.

Another reply

The 10 keys per second is on a four core i7 that's about five years old, and is a real world number.

The 60,000 times more expensive figure isn't a mistake. The same system that can do 10 warpwallet keys per second can do about 600k traditional brainwallet keys per second. The reason for this is that it's not just sha256 vs scrypt+pbkdf2 - the public key generation step must be taken into account and it is much, much slower than sha256. My code is available - https://rya.nc/brainflayer - run your own benchmarks if you find mine questionable.

As far as the rest of your hypothetical math goes... that's assuming "perfect use". It falls apart once the tool gets into the hands of actual users.

Most actual people don't know how to create a secure passphrase. Even if you tell them to use diceware, many of them will do something "clever" and still fail.

There are great tools that are secure under "typical use" with mnemonics that can easily be memorized with a little work. Compared with that, why would you ever recommend the thing that has much weaker security when common usage mistakes are made?

The only other real argument you've got here is about RNGs. Most popular wallets are now using deterministic nonces which dramatically reduce that problem. The key generation remains a risk (though a very tiny one). There is a simple solution to that. Write a tool that generates a BIP39 mnemonic (perhaps also allow electrum compatible output?) by combining CSPRNG output with a hash of the results of 50 die rolls. You get a securely generated seed that is possible to memorize so long as at least on of the entropy sources is good. If you'd like to write such a tool, I'd be happy to audit the code.

• Liraz (talk) 04:06, 24 January 2017 (UTC) Why not just generate the BIP39 mnemonic directly from the 50 die rolls? Why use the CSPRNG at all? As soon as you mix in the CSPRNG the output of the program is no longer deterministic making it harder to verify that it is operating faithfully. If 50 die rolls provide sufficient entropy, let's just use that.

• RyanC Because the dice might be biased, so it's hard to be sure how many is enough, and some foolish person will make up their own die rolls because rolling a die 50 times is too hard. If you display the process output of the die rolls along with the CSPRNG output (generated before the die rolls to shut down any tinfoil hattery about the CSPRNG being malicious adaptively) and xor the two together to output the keys, behavior can be validated.

• Liraz (talk) 17:20, 24 January 2017 (UTC)

1. I really like your idea, though I would implement it differently because I'm not much good at doing XOR in my head, and the more friction something involves the less likely I am to do it. I do agree that creating a user-verifiable key generation tool could blend the best of both manual and automatic entropy. That could be a good default and a real improvement to existing key generation techniques. I'm thinking there's a good way to implement that which would feature the best of what I like about Warpwallets and HD wallets. There would be two steps. First, we would have an entropy collection step that we can reproduce and verify in a deterministic way. For example our tool generates 4-8 mnemonic words (52 - 104 bits) from the CSPRNG and then prompts the user for N additional bits of entropy, using a tool like zxcvbn to measure the entropy. We don't need to XOR, we can just append the manually entropy to the computer entropy. From that we generate a new mnemonic 4-8 word code. The output is deterministic so we could have another mode that allows us to repeat and verify the result, for the "tinfoil" crowd. If it's malware at least it's deterministic malware. Different implementations in different languages running on different platforms could be compared for bonus tinfoil-hat points. Now that we have 52 - 104 bits of entropy, we can use the warpwallet algorithm WITH a mandatory salt to generate the final 12 word BIP39 key. I'd get more tinfoil points for suggesting we force users to seed the wallet with more than 4 words, even with a strong KDF and salt, but 4 truly random words should actually be enough for someone who isn't holding huge sums in their wallet, and we should balance the risk of theft from monster botnets with the much more banal and routine risk of misplacing/exposing your paper wallet and/or forgetting a long mnemonic. If a to-be-stretched-and-salted seed is just 4 words, users are much more likely to store it successfully in their heads, ALA XKCD. For more high risk wallets, 6-8 seed words would be more appropriate, so that could be a choice.
2. The above scheme wouldn't be idiot proof (I believe that's an impossible goal), but it would be more idiot proof than either letting a potentially unfaithful wallet/RNG generate keys for you or trusting the user to do enough die rolls. I also think that user stupidity is something we could a lot to mitigate with a good UX embedding educational elements and an interface that doesn't encourage the user to cheat themselves.
3. If someone is rolling dice instead of letting the computer generate the seed for them, they're probably already quite a bit more informed regarding the risks
4. Biased dice provide less entropy, but they still provide some. The higher the bias, the less entropy we're getting out of each dice roll, the higher the likelyhood someone is going to notice the bias so there's a natural balance there that would mitigate the most aggressive abuses.
5. Even without mixing in computer generated entropy, we can compensate for loaded dice by adding more dice rolls, stretching the entropy with an even stronger KDF (e.g., using a native implementation of scrypt running for longer), mixing-in an e-mail salt and/or distributing instructions for testing the fairness of dice so at least some experts will detect and warn the community regarding exploitable shenanigans. The result will still be deterministic so you could run the technique using multiple implementations, on multiple platforms, and if you get the same result you're probably safe, even without doing the math by by hand.
6. I don't think it's fair to call the concern from sophisticated malware tinfoil asshattery. I agree that excessive security concerns are a net-loss, not a net-gain, especially if they just encourage users to subvert the security. But worrying about the wrong things while ignoring real risks is another way you get less security. End-point security is the bane of security and the Achilles heal of encryption schemes. Security is only as strong as it's weakest link and the crypto is usually not the weakest link. Schneier gave the analogy of an armored truck transporting valuables between two park benches. Case in point, Snowden leaks didn't reveal the NSA was using QC or alien crypto-analysis to break civilian crypto schemes. It revealed TAO compromising end-point security by hook and crook. People were distracting themselves looking under the crypto streetlamp - discussing the relative merits of a 1024 PGP key vs a 2048 PGP key. If you suspect someone might be spending hundreds of millions to break your security you should probably shore up your defenses where they are weakest and implement extreme SecOps, not refine your crypto schemes on relatively poorly secured endpoints.

Brainflayer on CPUs not an upper bound on SHA256 brainwallet cracking efficiency

I'm impressed (and somewhat surprised) that Brainflayer can do 10 warpwallet guesses/sec. That's at least an order of magnitude faster than the JS implementation. I would have guessed that the performance gap between code running on V8 and a compiled library would be smaller.

• RyanC WarpWallet uses an asynchronous scrypt implementation. Every time the progress bar updates is several milliseconds where computations were not being done.

Hard to argue with actual Brainflayer benchmarks, but I think Colin Percival had a point that a realistic estimate of how much scrypt was more expensive to crack would be to assume advanced cracking attempts would involve highly customized hardware.

If you reimplemented Brainflayer to take advantage highly customized hardware you could probably crank up the number of SHA256 brainwallet passphrase guesses much faster you could crank up warpwallets passphrase attempts, including the public key generation step. I admit this is just a hunch, the difficulty of scaling up public key generation on custom hardware is not something I'm familiar with. I'm just assuming that this step wasn't designed to be difficult to accelerate in hardware, unlike scrypt.

• RyanC The hardware cost estimates in the scrypt paper aren't terribly relevant. Nobody's going to build ASICs to crack brainwallets or warpwallets - the hardware costs are too high and the payoff too uncertain. I have yet to see even a GPU implementation of elliptic curve public key generation (no, that is not what oclvanitygen does), let alone an FPGA one. What has been implemented on GPU is elliptic curve point addition, but that's only about one order of magnitude more efficient than on CPU from the benchmarks I've done.

What about salting?

You haven't responded to your thoughts on salting at all. Without salting I would agree that Warpwallet is just a slower to compute improvement of the bitaddress style brainwallet. With salting, it's something qualitatively different. The Warpwallet challenge used an unsalted passphrase to make a point, but criticizing the weakened version is attacking a straw man.

To illustrate, a 25M Brainflayer botnet cracking Warpwallets at 10 guesses/sec could search through 52 bits of unsalted entropy in a year. Now spread that power over 1000 target e-mails (e.g., suspected warpwallet holders) and searching the space takes 1000 years.

If the Warpwallet 8-alphanumeric challenge was on an unknown salt, Brainflayer would never find it. If the challenge included a list of 1000 e-mails, it would take about 9 years to crack. To search 10,000 suspect e-mails: 90 years.

The economics of attacking salted/unsalted warpwallets are vastly different, and that's an important part of what Warpwallet brings to the table, but you're not addressing that.

• RyanC WarpWallet allows an empty salt, and that is the default. Get them to accept a patch that makes it abundantly clear how bad it is not to use a salt, and then we can talk about the security it adds. Attacking a thing that I have seen people do is not a strawman. We should make better tools that make insecure usage difficult.

Liraz (talk) 17:30, 24 January 2017 (UTC) FWIW, I agree that WarpWallet should make the salting mandatory, or at least the default. I'll look into patching that myself and trying to get them to accept that.

RyanC

Even aside from the entropy issue, WarpWallet isn't a good tool. It generates uncompressed addresses and keys which are more expensive to use. It has no built-in scheme for multiple addresses. Partially spending a WarpWallet requires tedious manual transaction work of the sort that people can and do screw up.

• Liraz (talk) 17:34, 24 January 2017 (UTC) For sure, it isn't a good tool to use for your main wallet. That was not my recommendation. Neither is a paper wallet. For my main day-to-day wallet I use (and recommend) a hardware wallet. Partially spending Warpwallet isn't as convenient or efficient, but it's not that much different in that respect from other cold storage transactions. In practice, it takes a few seconds of additional work relative to a standard cold storage transaction. I've documented that workflow on bitkey.io if you're interested. My point is that even in it's current form it's a useful way to place funds in cold storage. The concept of a Brainwallet is actually a pretty good one in my opinion. Encouraging people to backup their wallets in paper (which most wallets do) opens a whole other can of worms. I find it hard to believe we would be doing that if we had a decent easy to remember alternative that wasn't pitifully insecure.