July 25th 2015
This is a guest post from a security researcher who took a close look at the way that MultiBit receives payment through the BRIT system. As part of our responsible disclosure procedure here are the details of the attack and what has been done to mitigate it.
As an ordinary user of MultiBit HD this does not affect the security of your bitcoins. That said, it is always best to run on the latest version of MultiBit HD so you should upgrade to version 0.1.2 or higher. We announce all our releases on Twitter and our RSS/Atom feed (see below) as a backup to our auto-upgrade system.
If you are a developer with an interest in cryptography we would urge you to read the entirety of the article since it illustrates why AES wrapped in HTTPS does not offer sufficient security against certain attacks.
A vulnerability was identified and fixed in MultiBit HD 0.1.2 that allowed an attacker to insert unspendable Bitcoin addresses into the list MultiBit uses to send fees to the developers. (CVE-2015-6964)
Recently I took a close look at BRIT, the protocol MultiBit uses to send lists of fee addresses from the developers to the wallet users. Each transaction a MultiBit user makes earns the developers a small fee that is periodically sent to one of the Bitcoin addresses received via BRIT, or to a hard coded address if no BRIT addresses are available. I noticed in the documentation that the fee addresses sent to the user from the server are strongly encrypted, but the messages had no built in authentication mechanism. Specifically in step 7 they make the claim that encryption
"...also validates the Matcher is actually the BRIT Matcher and has not been man-in-the-middled."
While it is true that the BRIT Matcher (server) is the only entity that could decrypt the request to get the AES key to use for the exchange, without a message authentication code (MAC) the client has no way to know for sure if whatever response it receives was what the server actually sent. The client could receive random garbage and it has no way of telling the difference between a response from a server with severe memory issues or just random garbage. More subtle, however, is that the client has no way of telling a valid response with some non-malicious corruption from a valid response with malicious corruption. This is bad.
BRIT uses strong encryption to protect the address exchange. Specifically, they use AES-256 (Advanced Encryption Standard) in CBC (cipher block chaining) mode to encrypt the actual address list. CBC mode has the property that changing the ciphertext of block
i causes predictable changes in the plaintext of block
i+1 at the cost of scrambling the plaintext for block
i. Any bits flipped in block
i will cause the same bits to flip in the plaintext for block
i+1. This is called a bit flipping attack and it is especially powerful when the message has a predictable format.
In the case of BRIT the address list changes every day, but the list is static for all users who request it on the same day. Thus if Eve requests it at 00:01 she will get the same list as Bob who requests it at 23:00.
Generally this set of conditions is not good:
It puts a man-in-the-middle (MITM) attacker, Eve, in a pretty powerful position. Specifically, Eve is able to change up to half of the message arbitrarily without needing to break any encryption and the client will accept it as valid.
Let's say Eve doesn't like MultiBit and wants to deny it funding. Let's also say that she can:
Eve is now in a position to cut off nearly all of the fees MultiBit gets if she exploits this vulnerability carefully.
While Bitcoin addresses may look random, they have some strong error detection built in. Specifically, the last 4 bytes of the address are the first 4 bytes of the double SHA-256 of the rest of the address. This means randomly changing any part of an address is very unlikely to still make a valid Bitcoin address. MultiBit does this error checking when importing addresses from BRIT so Eve has to do a little work to get a malicious address inserted into MultiBit's fee address list. Luckily for Eve the list is static for every single user so any change that still gives her a valid address will work for every user for the entire day.
In this context a malicious address is one that the MultiBit developers do not have control over and can not spend any funds sent to it. Additionally it is very, very unlikely that anyone has a corresponding private key for the address so the coins sent to it are effectively burned.
To generate a malicious address:
The above has a complexity of 232 with the actual work being the double SHA-256 calculations. I re-purposed some of the MultiBit and Bitcoinj code to generate these malicious addresses and I was able to get ~0.8M cracks/s on my i7-4790K and found an address about every 90 minutes. It's important to note that the work to validate the addresses is the same as the proof of work to mine a block, so benchmarks from Bitcoin mining with CPUs and GPUs can be used to get an idea of how much faster finding addresses can be done with a better tool or different hardware. This list shows a similar i7 achieving 66.6Mhash/s with a dedicated Bitcoin mining tool, so this attack can be sped up considerably. GPUs (and possibly ASICs) could also be used to further accelerate the attack.
My demonstration exploit script generates these addresses at roughly 10 minute intervals at a cost of about 0.20 USD per address on an Amazon EC2 C4 instance.
Consider an address from the Bitcoin wiki:
16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM we can generate some examples of malicious addresses:
If the original address was one of the fee addresses sent via BRIT, Eve would be able to use any of the above malicious addresses to replace it and keep fees from going back to MultiBit's developers.
If Eve wanted to steal fees for herself she would need to generate an ECDSA keypair that has a partial RIPEMD-160 collision with a genuine address and a valid SHA-256 checksum. Assuming Eve gets an optimal address/block match up and a simplified mapping of the base 58 string to binary to make the math easier (it's not actually 1:1) this task has a complexity of
>=2(25-14)*8 = 288 so stealing fees for herself is unlikely even if Eve is backed by a nation state.
To stop this attack BRIT was updated in version 2 and MultiBit version 0.1.2 to include a keyed MAC so that clients can detect when something was changed in transit. Specifically HMAC-SHA-256 is used to ensure message integrity. If an invalid HMAC is detected MultiBit treats it as if it cannot contact the BRIT server and falls back to hardcoded fee addresses.
It is important to remember that even though something was encrypted with a secret key, that alone is not enough to prove a message's validity. It is essential to include authentication in addition to encryption. In the case of BRIT the lack of a MAC was enough to permit an attacker to cut off a major source of funding for the project. Don't let this happen to you.
Here are some related articles: