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:
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.
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.
- 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 5-8 mnemonic words (64 - 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 5-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 64 - 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 5 words, even with a strong KDF and salt, but 5 truly random words should be enough for anyone 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 5 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. With 5 random words a 250,000,000 brainflayer botnet generating 100 guesses a second (10X faster than you're currently getting) would take 12 years to crack an unsalted Warpwallet. Salting the Warpwallet would banish cryptographic attacks to the realm of science fiction.
- 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.
- 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
- 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.
- 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.
- 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.
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.
- RyanC You are wrong. The consensus on this from other experts is that you are wrong. Your recommendations will harm users. I've talked to several otherwise smart people who have lost painfully large sums of money to various deterministic wallet tools. Such tools are a trap for people who are smart, but don't quite understand how effective password cracking can be. Many people think they do, but there is a lot of bad advice about passwords and passphrases out there. I personally have used passphrases in the past for things like GPG keys that would have gotten me 0wned if I'd used them even in WarpWallet. I'm done arguing with you, it's clearly not productive. Please talk with some of the Bitcoin developers about this if you still don't believe me. Please also understand how incredibly frustrating it is to have seen firsthand how much damage tools like this can cause their typical users (a paper was published about this), and then have people say "oh, but it's fine if I use it perfectly, so it's okay for everyone". If you want to use it, I can't stop you, but recommending these tools to random newbies is gross negligence. I also want to point out that it's a bit absurd to recommend hardware wallets if you categorically don't trust CSPRNGs. Why are their CSPRNGs trustworthy and others not?
- I'd like to point out you are so fixated on only one branch of the attack tree that you're not seeing how your argument could apply equally well to the other branch that you dismiss as a "tinfoil hat threat" despite massive real-world evidence to the contrary. I could rephrase your comment: "You are wrong. The consensus of endpoint security experts is that you are wrong, and your recommendations to just trust endpoint software is gross negligence that will end up hurting users. If you don't believe me go talk to another expert on endpoint security. Oh but it's fine for me if I setup a perfectly secure endpoint, so it's OK for everybody. Automatic wallet generation on untrusted endpoints are a trap for smart people who don't understand how effective endpoint comprimising techniques are at subverting the integrity of their system in endlessly creative ways". My argument isn't that "my" threat is more important that "your" threat. My argument is that both threats are substantial and that I don't think we should dismiss either of them. If there's a tradeoff to be made where mitigating one risk comes at the expense of mitigating another we need to find the right balance to make a wise choice. Seeing things in black and white, your camp vs my camp, as an argument to be won, that's an all too human but very dangerous an unproductive attitude for a security expert to take.
- Trustworthy is a probability not a binary value. Convenience is also a matter of degree. There's an inescapable trade-off. You can say: As an expert, I recommend you hold up to $100 in your pocket, up to $10000 in a steel vault and the rest in stocks or whatever. You'd be right to criticize my position if I was being simple minded to the point of absurdity. If I somehow miscommunicated that impression, I wouldn't blame you for feeling like there's no point in talking to this idiot.
- For the record, Hardware CSPRNGs are no more trustworthy, if anything I trust them even less because they're such high value targets. That's why I limit their use to relatively small sums. Great for day-to-day use though. Very convenient. But I'm anticipating to wake up one day and learn a whole bunch of wallets got their funds swept and we eventually trace that back to weak/weakened wallet creation. I hope I'll be proven wrong but in the meantime, like you, I'm trying to help users minimize their exposure.
- Before I sign off and stop troubling you with unwanted discussion, I just wanted to express my appreciation for the time you've taken to explain your position, the efforts to protect users and also that you went public with your research and didn't use it to run another botnet. You're a philanthropist. I've been benefiting from your advice and have been spreading it to anyone foolish enough to consider using SHA256 brainwallets. I've even done experiments with leaving various amounts of funds in SHA256 brainwallets just to see what would happen and have seen them grabbed with my own eyes. I never meant to downplay your research or imply that brainwallet stealing botnets don't exist. They obviously do and it's important to take that risk into account. If there's a gap in our understanding I think it's due each of us spending more time researching different classes of threats. I used to work with the military and spent a good chunk of my life researching sophisticated malware. Endpoint security risks looms ever large in my mind. I guess that makes me atypically skeptical of claims of system integrity. I imagine for you the risk of users choosing bad passwords/passphrases, having cracked so many of them seems to deserve more of an emphasis.
- Sorry you feel the discussion was unproductive. If I've rubbed you the wrong way I apologize. FWIW, I found it productive.You've also convinced me that Warpwallet makes it too easy to avoid salting and the default should be changed. I'll try to get a patch through. I'll also be updating my recommendations on the resources I control to stress that the salt is mandatory and that using Warpwallet is unsafe without it.
- We both agree that the threats are real and significant, we just place different weights on them. Before our correspondence it was my understanding that ROI for attacking salted warpwallets was so low that it would make the operation of a botnet most likely unprofitable. I don't think we disagree on that. I think we might disagree on the optimal set of trade-offs to factor into our recommendations to non-experts where protecting against one risk necessarily weakens protection against another. We agree that salts are essential and should be mandatory, key stretching adds security but isn't a silver bullet, humans are bad as sources of entropy, end-point security is really hard, blindly trusting RNGs is unwise, Warpwallet being a PITA to use and a privacy risk to use as your main wallet, and that your research is very important it and you're doing the Bitcoin community a huge service being an advocate against unsafe practices. That's a lot of common ground. Nice chatting with you Ryan (for me anyhow).
- Trust endpoints that can and have been compromised in endlessly creative ways
- Get that endpoint to create a hard to remember seed for your wallet
- Write down the seed on a piece of paper(!), that can be lost, stolen, burned, or water-logged
If worst comes to worse and the government, or criminals or whatever are looking for your coins, they'll ransack your house and bank vaults, find that piece of paper and all of our sophisticated crypto goes up in smoke. I think the future will look back to us and laugh: secrets are meant to be remembered, not written down!
- RyanC People run these botnets already! I gave a talk last summer, one of the bots robbed our bait wallet live on stage! This problem is solved trivially with BIP38 paper wallets. Risk of loss can be mitigated by making multiple copies and storing them in different locations. Requiring adversaries to steal your paper wallet and crack the passphrase is better than publishing what is effectively a hash of your passphrase and hoping for the best.
Liraz (talk) 00:01, 25 January 2017 (UTC) Clarified what I meant regarding botnets above. Regarding BIP38, like all automatic wallet generation procedures, the security of a BIP38 wallet depends on the security of the endpoint generating it, which is not a trivial problem for users to solve. We integrate a BIP38 paper wallet generation tool into BitKey. It's very useful, but I tell people if they don't trust us, our build process and/or their ability to independently verify the integrity of the software, they might want to use something else instead they don't have to trust. Trust-minimized solutions are better than solutions that require trust. I think that was the one of the key innovations Bitcoin/blockchain introduced: http://nakamotoinstitute.org/trusted-third-parties/