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.