Researchers Find A Crack That Drains Supposedly Secure Bitcoin Wallets
Source: Glenn Fleishman
Glenn Fleishman 02.12.16 11:00 AM
It's always a pain to memorize a password. This is why we so often choose weak ones. A technique used for protecting bitcoin wallets (called a "brain wallet") seemed to offer a workaround. You use a strong form of cryptography to convert a password that you only keep in your mind—thus reducing vulnerability to malware and other attacks—into something that resists brute force. Brain wallets could thus be stored in the clear (effectively unencrypted) in the bitcoin blockchain, making them always available to an owner without weaknesses that would expose their value to others.
Think again, brainiac! A group of researchers looked into many current brain-wallet implementations and found nothing but moths. Many brain wallets have been pilfered of their value, some within minutes of being added to the blockchain, due to a poor choice of the passwords used to seed more complicated ones.
The blockchain is a public record of all bitcoin transactions, and sites and systems increasingly use transactions to include other information. The blockchain can't be tampered with after about an hour or so following a transaction being baked in, which makes it a perfect permanent repository. It's also widely replicated around the globe.
Bad Passwords Are Bad Passwords
The trouble arises from the same issue as with most successful brute-force methods of cracking passwords: You have to choose a strong starting point, no matter how complex that initial password winds up becoming.
Many of the tools used to create brain wallets use a simple process—taking a sequence of text a user enters and running it through a one-way cryptographic hashing algorithm (SHA-256), which produces a 256-bit number that can't be reverse engineered to find the original. This hash is used in a few successive operations to transform into the private-public key pair used for bitcoin addresses and to sign transactions. This kind of hashing is very computationally cheap: Anyone, anywhere can take the same bit of text and hash it quickly and test it against the publicly stored password in the blockchain.
The upshot? Use a simple password, which many people have done, and it's easily cracked despite the appearance of complexity.
"Castellucci and his co-authors checked a trillion passwords for $55.86 and recovered 18,000 wallets."
Ryan Castellucci of White Ops presented some of his research into this area last August, and is the common link between two new multi-author papers—one out this week and the other available and being presented in two weeks—that dive even deeper into the problems with brain-wallet protection and the techniques which bad guys have used to empty such wallets. Also last August, he released Brainflayer, a tool for automatically testing passwords against brain-wallet encryption keys.
The new paper on cracking shows a significant increase in efficiency in testing brain-wallet keys—by a factor of 2.5 since last August—and said it's possible to test about 17.9 billion passwords for $1 by using Amazon Web Services' Elastic Computing (EC2) on-demand server offering. He and his co-authors checked a trillion passwords for $55.86 and recovered 18,000 brain wallets. Clever wallet owners had used phrases like "say hello to my little friend" and "dudewheresmycar."
Castellucci told me via email that the problem isn't the notion of brain wallets, but that many implementations of the password converters or sites that handle them fail to use cryptographic subtleties now widely employed to protect passwords elsewhere.
First, they typically don't use a salt, which is a separate piece of data that is combined with the starting password. Salts used at websites to encrypt passwords are often recovered if a password database gets hacked, but they break one shortcut used by crackers: The crackers can't compute a password once and match it against all identical occurrences (all uses of "123456", for instance). Rather, they have to compute passwords combined with the salt.
Castellucci suggests an easily remembered piece of data, like someone's birthdate or email address, would work as a salt because it would be unlikely to be associated in any fashion with the brain wallet. He says that Keybase's WarpWallet tool allows the use of a salt when creating a brain wallet, and he'd prefer if it were more discouraging about skipping that step. However, he says users should use random generators to create strong passwords "for high-security applications where offline cracking is a concern."
In addition, most of these conversions rely on a couple of steps to compute SHA256 hashes, which take vanishingly little effort. There are stronger encryption algorithms that impose a "difficulty" requirement, which might reduce the number of calculations by several orders of magnitude without making it more of a pain for the person created the password. The password owner might have to wait one-tenth or half-a-second for their phrase to be converted to unlock a brain wallet, but that would also reduce the ability to launch a trillion attacks for under sixty bucks to potentially just thousands or hundreds of thousands.
A salt and a difficult encryption algorithm together dramatically reduce the risk of cracking. LastPass suffered a data breach in 2015 that was embarrassing, but serious consequences were almost entirely averted due to using this design.
Drained In Minutes
The other paper addresses multiple questions, including how many brain wallets exist in the bitcoin blockchain, and how many of those have been hijacked and emptied. That paper, "The Bitcoin Brain Drain," will be presented at Financial Cryptography 2016 in two weeks.
Castellucci and several colleagues found just 884 wallets in use by anyone other than researchers between September 2011 and August 2015 that had received in total 1,806 Bitcoin (about $100,000). The total wallet count strikes them as surprisingly low. However, they weren't the first to find them. They note, "We find that all but 21 wallets were drained, usually within 24 hours but often within minutes." They also identified common parties who drained multiple accounts, indicating the techniques described are in general use.
The method they used to find bitwallets involved using Castellucci's Brainflayer to generate 300 billion passwords from a variety of word lists and sources, as well as using brute-force generated methods for short passwords. Thus, they didn't start with a list of brain wallets and try to crack them; rather, they identified brain wallets by the password being cracked.
The authors conclude that brain wallet use must be rare, but they can't state it definitively. Castellucci says that he has identified additional brain wallets through owners contacting him (they'd forgotten parts of their passphrases), through public reports of thefts by owners or brags by bitcoin burglars, and some he believes created by researchers in bulk that they weren't able to crack completely.
These brain-wallet encryption flaws stem from wishful thinking that confuses a complicated result with a complicated input. Just like zombies, passwords need brains.
| }
|