Bitmessage v1.0: completely broken crypto

EDIT: This posts covered Bitmessage protocol v1.0 before it switched to OpenSSL ECC because of these problems.

When I heard about Bitmessage (http://bitmessage.org) I was pleased to find a new privacy/security preserving project being born.

But after I looked at the source code and grasped the crypto protocol (which is not described in the white paper), I got disappointed.

It seems that was not the intend of the developers to create a snake-oil cryptography product, since the application is open-source, nevertheless it implements the crypto so badly that the protocol would need a complete redesign to be of real use.

One thing I noticed is that clients sends acknowledge messages when they are able to decrypt a message. I realized that this could probably be used as a side channel to recover the user’s private key.
The protocol does not use Authenticated encryption (http://en.wikipedia.org/wiki/Authenticated_encryption) or MACs to verify messages before decrypting public key encrypted messages. Also the same RSA keys are used both for signing and for encryption/decryption. Bad idea, and can lead to an attack.

Then I noticed that decrypt_bigfile(), which is used to decrypt broadcast messages, does not use hybrid encryption (it uses plain RSA!) and has no method for chaining.
Each message is broken into blocks, and each block is independently encrypted using RSA. That means that an attacker can reorder blocks within a message and still create a valid message. Also the attacker can construct a new message by mixing blocks from other captured messages.¬† Since the first block of each message contains the headers, it’s possible to take the first block of an existing message and append blocks of some other messages, creating completely valid new ones. The PoW does not help stopping an attacker from building long messages, since the hash target is little affected by additional blocks (since a contant payloadLengthExtraBytes is added to make short messages more difficult)

At this time I had all the tools to implement a Bleichenbacher attack.

Then I forced decrypt_bigfile() to implements a perfect Bleichenbacher oracle:

1. We take the first block of a 2-block message and re-use it.

2. We modify the second block according to Bleichenbacher attack

3. We add many copies of the second block (the original one) afterwards, e.g. 50 blocks.

If the PKCS#1 1.5 padding of the second block is incorrect, then the function decrypt_bigfile() will fail fast. If the padding is correct then the remaining blocks will be checked and that will take additional measurable time.

If the PKCS padding of the second block is correct, the destination node Bitmessage application will send an ack. If it’s not, then the destination node will keep silent.

The attack was not tested in practice, and since the code that sends the ack back is horribly to read, I’m not planning to implement an exploit. It may be the case that it’s not possible to successfully implement it.

But anyway, it’s enough for my to consider Bitmessage completely flawed by design.

EDIT: Atheros user of Bitcointalk.org pointed out that the signature verification right after the message decryption would deter such attack. That’s correct. Still the attack can be executed using the timing attack. It’s easy to detect if 100 RSA blocks are being decrypted or just only two from a connected peer. Right after the Bleichenbacher message the attacker sends another message, such as “ping”, that must be acknowledged with mesage “pong”. If it takes one second to process, then 100 blocks have been decrypted. If it takes 100 msec, then only two blocks have been decrypted. I’m sure there are still other ways to detect the correct/incorrect PKCS padding and carry the attack.

Advertisements
  1. #1 by nertu on February 17, 2013 - 8:11 pm

    can you release an updated review of the latest version of bitmessage?

    • #2 by SDLerner on February 18, 2013 - 5:20 pm

      Seems fair, I will do it shortly.

  2. #3 by onetruecathal Garvey on February 19, 2013 - 3:52 pm

    I would also love to see an update on the security from your perspective (as, I suspect, would the dev!), as it’s been changed AFAIK to ECC and seems to implement timing-attack mitigation using random sleeps and delays before acking (slowly getting to grips with the source).

    Bitmessage as a concept is critical: encrypted P2P email without bloat. I’d really love to see security experts helping to make this one work and stay on-track where others left security by the wayside and bloated themselves instead with eyecandy.

    Of course, it might all be moot if someone checks the “streams” system the dev opted for instead of a DHT and finds it lacking. It seems.. interesting, at least.

  3. #4 by Hans Rippel on March 9, 2013 - 9:34 pm

    have the cryptographic issues been resolved in the new version?
    http://www.reddit.com/r/Bitcoin/comments/19z4ka/setting_up_and_using_bitmessage_an_encrypted/

    • #5 by SDLerner on April 5, 2013 - 4:51 pm

      I did a preliminary audit of the protocol version 2 (the design, not the source code), and it seems to be ok.

      • #6 by Hans Rippel on April 5, 2013 - 5:05 pm

        thanks for the update … keep us posted if and when you get a chance to audit the source code as well.

  4. #7 by zne2 on April 4, 2013 - 10:04 pm

    I agree with #3… The basic concept of Bitmessage is a brilliant extrapolation from Bitcoin. There are plenty of human rights groups around the world that could explain the need for a decentralized / distributed messaging system which cannot easily be shut down by a fascist government. While it serves a useful purpose to expose any flaws in the cryptography, why stop there? I think this project deserves more publicity and support, not just criticism.

  5. #8 by zne1 on April 4, 2013 - 10:07 pm

    I agree with #3… The basic concept of Bitmessage is a brilliant extrapolation from Bitcoin. There are plenty of human rights groups around the world that could explain the need for a decentralized / distributed messaging system which cannot easily be shut down by a fascist government. While it serves a useful purpose to expose any flaws in the cryptography, why stop there? I think this project deserves more publicity and support, not just criticism.

    • #9 by SDLerner on April 5, 2013 - 4:46 pm

      You’re right. In fact, I helped the developers with the design of the protocol version 2 and I did a preliminary audit of the protocol. The fact that I haven’t post about it yet is because I have almost no time. My apologize.

      • #10 by Dirk Theisen on December 22, 2013 - 12:27 am

        Please post about it, once you find time! There is public interest!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: