Although it is very nice that people are working on creating secure and anonymous messaging systems, I am afraid that BitMessage is weak to a variety of attacks. I fear that the people working on it do not have sufficient expertise, in the fields of security and anonymity, to design and implement a proper cryptographic communications system + anonymity network. After reading the two design .pdf documents, I have identified a variety of weaknesses and overall poor design choices in the BitMessage protocol. General Design Inefficiencies BitMessage uses the most inefficient sort of PIR
First of all it should be clarified that BitMessage is what is referred to as an everybody gets everything private information retrieval system (aka: everybody gets everything PIR, https://en.wikipedia.org/wiki/Private_information_retrieval
). For message retrieval, everybody gets everything PIR is information theoretically proven as anonymous to the set size of users (of course other parts of the system can destroy this guarantee, but the actual PIR technique itself is proven as anonymous). Everybody gets everything PIR is the only PIR technique that guarantees anonymity to the set size in all cases (ie: even if all servers are malicious). However, everybody gets everything PIR is very resource intensive and it is the least sophisticated sort of PIR in existence. There are distributed k-out-of-l PIR algorithms that allow for t-private security, meaning that when messages are retrieved from k servers, out of a set size of l total servers, anonymity is guaranteed if no more than t of the k servers are malicious and colluding. There are k-out-of-l (l-1)-private PIR schemes that require orders of magnitude less bandwidth than everybody gets everything. Additionally, these algorithms require constant amounts of bandwidth to retrieve a message regardless of the total number of messages, everybody gets everything PIR increases bandwidth requirements in parallel with the total number of messages. BitMessage is insanely and needlessly processor intensive
In addition to everybody getting everything, everybody tries to decrypt everything. This is very processor intensive, and it has already led to a deanonymizing timing attack (which was incorrectly 'fixed' by sleeping, an approach that is widely recognized as incorrect and insecure).
A better solution is to use a signaling system. I will share with you the signaling system I came up with, if you decide to use it please give me credit since it is being incorporated in a system I am advising on as well:
I don't want to give away too much simply because I am working on a competing system, but I will share this. Have the users pairwise exchange random string pairs (this can be accomplished with the initial long term ECDH key exchange + iterative hashing of the derived shared secret). Alice gives Bob the following strings, both of them keep a record of this string pair :The addressing system is needlessly complex and could lead to attacks, and certainly leads to overloading the network
6d7ebc44c5bc26207e62f4f628f912e1a0f41ed11764891aa7dd99eab83228e7 , 19732980d68fbd00358a0a4d98246c960400b87e4fa2a2e155db98be2b42ed6c
The first message Alice sends to Bob is tagged with the hash of the concatenation of the two strings:
The newly derived string replaces the second string Alice gave to Bob, and the next message Alice sends Bob is tagged with the hash of the concatenation of the string pairs again:
etc. Now Bob can keep a record of the strings that could indicate a message from each of his contacts, and he only needs to try to decrypt the messages if they are detected as having been encrypted to him. Bob should use a constant time membership evaluating algorithm to protect from timing attacks. Attackers can see the strings messages are tagged with, but they cannot gain any information from them without knowing the original strings derived from the pairwise ECDH key exchange between Alice and Bob. Now Bob is not exhausting his CPU trying to decrypt hundreds of thousands of messages, and the time it takes to check if a message is for Bob or not is made constant time in a proper way (ie: not timer based / sleeping).
I am not going to go into any more detail than this (trust me there is a lot more detail than this) but that is a basic signaling system that is certainly better than 'everybody tries to decrypt everything'. 'everybody gets everything and everybody tries to decrypt everything' is a recipe for failing to scale, and it is entirely not required.
Currently BitMessage does an out of band transfer of address, which is the encoded hashes of the ECC public key(s?), instead of doing out of band transfer of the encoded ECC public keys themselves. The addresses are used to query the network for the public keys. Requesting public keys in this way is probably an attack vector, if an attacker can tell who requested the public key then they can obviously link the communicating parties together. Since there needs to be an out of band information exchange in order to get the hash of the public key, why not just use an out of band exchange of the public key and have the address of the party BE their public key instead of the hash of it? That makes a hell of a lot more sense, and base58 (wtf) encoded SHA512 hashes of ECDH public keys are going to be of comparable size to encoded ECDH public keys themselves. Attacks
I will be using traditional anonymity parlance in describing these attacks. For example, an external attacker listens to links between nodes, an internal attacker owns a node on the network. A passive attacker monitors data but does not modify anything about it, an active attacker modifies data / interacts with the network. A local attacker watches a node or link directly neighboring to their position (ie: an internal attacker local to the client is one of the clients peers), a global passive external attacker watches all links on the network but doesn't modify any of the data sent over them, etc. Lack of link level encryption leads to total anonymity compromise in the face of a local external attacker
The BitMessage papers specify message encryption but they make no mention of link level encryption. I can not find any sources that indicate BitMessage uses link level encryption, although I admittedly have not analyzed the source code or even used the system. Lack of link level encryption deals a fatal anonymity blow to BitMessage, allowing a local external attacker (ie: the clients ISP) to completely deanonymize the client.
In the case of internal local attackers, this attack does not work:
for example, assume Node 1 is the attacker and Alice sends an acknowledgement through it:
Alice -> Node 1 -> Node 2
Node 1 cannot tell that the acknowledgement originated at Alice, just as Node 2 cannot tell if the acknowledgement originated at Node 1.
However, from an external perspective:
Alice -> Alice's ISP -> Node 1 ISP -> Node 1 -> Node 1 ISP -> Node2 ISP -> Node2 -> Node 2 ISP
Alice's ISP can see all data coming to and going from Alice. Imagine that Alice sends a broadcast. The BitMessage protocol calls for broadcasts to be tagged with the hash of the senders BitMessage address. Since Alice's ISP does not see an incoming broadcast identical to the outgoing broadcast, it can determine that the Broadcast originated at Alice. Additionally, since the broadcast has a unique identifier linking it to Alice's BitMessage address, the ISP is capable of determining Alice's BitMessage address (or at the very least the hash of it, which can be compared against known addresses), thus deanonymizing her.
Let's say that Alice sends a GetPubKey request for the public key of Bob. Since the ISP does not see Alice getting a GetPubKey request, but does see her sending one out, it can determine that Alice is attempting to communicate with Bob.
I cannot really make heads or tails of the msg format, since it seems to make no sense to me (why do you send an encrypted version of the ECDH key? Are you using ephemeral ECDH keys or are you using long term ECDH keys like they are ephemeral keys?), but it is possible that msgs can hurt the users anonymity due to lack of link level encryption as well. Certainly if Alice sends a message to an internal attacker who is also local external to Alice, the attacker can deanonymize Alice.
The attacker can determine Alice's BitMessage address if she gets a getpubkey request and responds to it, because the attacker will see her sending her public key but not being sent the public key to forward on. Even with link level encryption and layer encrypting outgoing messages with the acknowledgement system, a local external attacker can link Alice to her BitMessage address with a spam + packet counting attack
Imagine an external attacker local to Alice who is also forcing the unknown owner of Alice's BitMessage address to send a lot of acknowledgement messages. This attacker can deanonymize Alice even if she relays her acknowledgement messages through third party nodes.
First the attacker observes Alice's in:out traffic ratio over a period of some days to establish an average. then they send her 100 messages and wait for acknowledgements. Next they compare her in:out ratio average over the observation period to her in:out average over the period when they received acknowledgements from her.
Alice's ISP can determine how many bytes she gets from the BitMessage network. It can also determine how many bytes she sends to the BitMessage network. When Alice gets a message of 50 KB that has 49KB of acknowledgement data in it, she will have 50 KB in and 99KB out (50KB out to rebroadcast the original message, 49KB out for the separate acknowledge message). If the attacker sends Alice 100 such messages, this will cause her to take in 5,000 KB and send out 9,900 KB, a ratio difference that the attacker will be able to detect if they are local external. The nodes Alice routes these messages to will be getting 9,900 KB in from Alice and sending 9,900 KB out.
And of course Alice cannot stop routing a message sent to her after she gets it. Otherwise, the attacker will notice that Alice got a message of 12 KB in and never sent any messages of 12KB out. Then the attacker could use one of their internal nodes to find the 12KB message (assuming link encryption is used, otherwise they can do it from their local external positioning) and determine that it was for Alice.Even with link level encryption, an external attacker local to Alice can determine the messages sent by Alice if the attacker also has an internal positioning
If Alice's attacker owns an internal node on the network and is also local external to Alice, they can determine the size of the messages originating at Alice by contrasting bytes in and out like before (100 KB in and 150 KB out means Alice sent out a 50 KB message). Now when a message of that specific size passes through one of the attackers internal nodes, they can determine that this is the message Alice sent by size correlation. Now they can get Alice's address from the broadcast message + they already know her IP address from their local external positioning.A simple passive internal intersection attack
Let's say there is an attacker A and the network consists of 8 nodes, A[1..3], B, C, D, E, F.
Bob sends A a message that takes the following route:
B -> C -> D -> A -> F -> A -> E -> A
Now the attacker can conclude that Bob might be nodes B, C or D, but he is not nodes F or E. After enough messages sent, the attacker can narrow in on which node Bob is. This is a type of long term intersection attack. The more nodes that the attacker controls, the quicker this attack will identify Bob. forced segmentation via sybil attack can severely degrade anonymity
If all nodes receive all messages, it is natural to be concerned about the system’s scalability. To address
this, we propose that after the number of messages being sent through the Bitmessage network reaches a
certain threshold, nodes begin to self‐segregate into large clusters or streams. Users would start out using
only stream 1. The stream number is encoded into each address. Streams are arranged in a hierarchy.
This reduces the anonymity set size of the system to the userbase of an individual cluster. Essentially it breaks apart one giant everybody gets everything PIR network into a bunch of little everybody gets everything PIR networks. It also opens up room for a Sybil attack, an attacker could flood clusters with malicious nodes that fake network activity in the hopes of drowning out the number of legitimate users per cluster. They can filter off their own traffic and that could severely degrade the anonymity provided to the legitimate clients. Definitely see a lot of room for anonymity attack vectors based on segmentation of the network.Possible intersection attack leading to linkability if you are not re-encrypting messages with new initialization vectors after failure to acknowledge
If the receiver of a message is not
online to receive it during the two‐day window, the sender will notice that he never received an
acknowledgement and will resend the message after waiting an exponentially increasing amount of time.
If the attacker enumerates all of the nodes in a channel, they can observe when these nodes are connected to the BitMessage network. Imagine that Alice sends Bob a message, but Bob is not online for two days. Now Alice resends the message. If the message Alice resends is identical to the original message, the attacker can conclude that the message is going to a client that has not been online in the two day period from when the message was originally sent. If Alice doesn't resend the message again after 4 days, the attacker determines that Bob is one of the nodes that wasn't online in the original two day time frame, and also one of the nodes who was online in the 4 days after that. This attack can be protected from by using a new initialization vector prior to resending the message, although it is possible that message bytesize could also give it away. I cannot tell if messages have anything on them that ties them to the sender, but broadcasts apparently do. A quick and effective active internal intersection attack for deanonymizing Bob
Add a few nodes to the cluster and peer up with many nodes. Send the target address a message with ackdata. Wait to see the ackdata published anywhere, to know the target got the message. Quickly send getdata messages to all peers requesting the ackdata msg. Create two lists, one containing all peers that have the ackdata msg and one containing all peers that do not. The peers that do not have the ackdata msg can be eliminated as suspects. Rinse and repeat until there is only one suspect. Only sending getdata messages to the suspect nodes to speed things up.
The same can be done in reverse. Every time you get a message from the target, quickly send getdata messages to all nodes. Make your two lists again, and wait to get enough messages to identify the target.
If nodes never include messages sent from them in their inventories the attack can be inversed, looking for the node that doesn't have the message listed.
This intersection attack probably identify the IP address of a sender or receiver pretty quickly, and it only actually requires having a single node so long as it is peered with the entire cluster. Since clusters are inherently destined to be relatively small due to scalability issues, it should never be hard to peer with enough nodes to carry this attack out, especially if you have a few nodes on the network.
The reason I think this is the best attack is because it can be carried out by a very weak attacker, internal with a single node.
It looks like Bitmessage waits 0-10 seconds per peer to send a newly inserted message to every node on a clients peer list. It uses 32 threads for outgoing messages, I assume it replaces them as it goes. So assuming there are 1,000 nodes on the network and they all peer with each other, and assuming it takes only 1 second to send the message to each peer, that means it will take 31.25 seconds for the client to send its message to all peers. If Alice is in the set of 32 nodes the inserting client originally sends the message to, and she quickly queries all her peers to see if they have the message, (let's say she has a modified client that uses 1,000 threads, and it takes her 1 second to query nodes to see if they have the message), Alice will have a suspect list of 64 nodes that could have sent the message.
In the case of acks Alice doesn't even need to wait to see it published actually, she can constantly query all of her peers for it with its inventory vector (which she knows as she makes the ack data in the first place and the inventory vector is just a hash of it). This will probably be even more effective actually, as as soon as a node gets a message it has the ack for it and will respond to a getdata query for the ack I assume.Another passive internal intersection attack (should be effective even if acknowledgements are sent through middle nodes)
After enumerating all of the nodes by aggressively peering and having a few nodes yourself, send someone a message with an ack and wait and see how long it takes for them to acknowledge. If they almost immediately acknowledge, either themselves or through a middle node, then you can assume that they are one of the nodes on the network (default behavior is to publish acknowledgements shortly after getting them). If they don't acknowledge for half an hour or so, you can assume they are not any of the nodes on the network currently. Now keep track of nodes on the network by continuing to aggressively peer, and see the nodes that are on the network when you get the acknowledgement. The person you sent the message to is likely one of the people who recently joined the network, either that or the person who acknowledged is a middle node for the person who you sent the message. Do this again when the potential middle nodes are offline, if the recipient acknowledges before the middle nodes come online you can write off the offline potential middle nodes as being your contact. Over enough node churn and acknowledgements you can narrow in on your contacts IP address.