Welcome, Guest. Please login or register.

Author Topic: My Security Analysis of Bitmessage  (Read 46901 times)

helpinghand

  • Newbie
  • *
  • Posts: 23
  • Karma: +6/-0
    • View Profile
My Security Analysis of Bitmessage
« on: May 20, 2013, 09:10:34 PM »
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:

Quote
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 :

6d7ebc44c5bc26207e62f4f628f912e1a0f41ed11764891aa7dd99eab83228e7 , 19732980d68fbd00358a0a4d98246c960400b87e4fa2a2e155db98be2b42ed6c

The first message Alice sends to Bob is tagged with the hash of the concatenation of the two strings:

82b77ccc6b3596d6c16fffc35d68611faf28953ae8708ba0aa56ef3ff7df6288

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:

9737f35b450c69e40dca253815b2a593c3fd56eaa30e69878bedab0106423563

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.


The addressing system is needlessly complex and could lead to attacks, and certainly leads to overloading the network

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[1] -> F -> A[2] -> E -> A[3]

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

Quote
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

Quote
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.
« Last Edit: May 20, 2013, 11:09:35 PM by helpinghand »

helpinghand

  • Newbie
  • *
  • Posts: 23
  • Karma: +6/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #1 on: May 20, 2013, 11:50:36 PM »
other notes:

You are using signatures like they are message authentication codes

Quote
Bob decrypts  the  message  then  checks  the  signature  using  the  public  signing  key  included  in  the  message.

This is not really a proper way to go about this. First of all, there is really absolutely no point to include the signature key encrypted in the message. Long term ECC keys are already known by anybody who wants to contact Bob, so what is the point of including them encrypted in the body of the message? It seems redundant, and it sounds like what you really want to use is called a Message Authentication Code aka MAC.


I don't think you actually need two ECC keys

For RSA you definitely should use a different key for signatures and encryption, but if you use ECDH and ECDSA I am pretty sure you can use the same key for each. You should double check with a professional cryptographer though (I know more about traffic analysis than cryptography). Below I will share a paper that gives a proof that using the same private key for ECDSA and ECIES is secure. I cannot find a citation for ECDSA and ECDH, however once a cryptographer did suggest to me that this can be safe if properly implemented.

the paper about using a single private key for ECIES and ECDSA: http://eprint.iacr.org/2011/615.pdf

Quote
In the rest of this section we study the joint security of ECIES and the signature schemes EC-DSA and
EC-Schnorr, that is, the security of these schemes when the same key-pair is used for both signature and
encryption. We show that all known security results carry over to the joint setting. Hence, if EMV Co allow
the use of a single key-pair for their elliptic curve based algorithms (as they currently do for RSA-based
schemes), there are no negative security implications: they would still obtain the strong security guarantees
described above, just as if they had used two distinct key pairs.

Are you using ephemeral ECC keys?

I cannot find any mention of ephemeral versus long term ECC keys in either of the two papers I have read, and it leads me to conclude that you are incorrectly using ECC. Proper use of ECC involves Alice and Bob exchanging long term public keys, these can be used for ECDSA. When Alice wants to send a message to Bob, first she generates an ephemeral ECC keypair, she uses Bob's long term public ECC key with the ephemeral private ECC key to derive a shared secret (with ECDH presumably) , which is then hashed into the session key. Now Alice can delete her ephemeral private key, she attaches the ephemeral public key to the outgoing message to Bob, and symmetrically encrypts the message payload data using the derived session key. Every single outgoing message should have an ephemeral public key attached to it, using long term public ECC keys for secret derivation is really bad practice.

Why are you encrypting the ECDH public key with the message??

It appears from the paper that the encrypted content of the message includes the public ECDH key, but that makes no sense as the public ECDH key must be in plaintext format for Bob to use it to derive the session key used for decrypting the message. I don't see how the protocol you have specified can even possibly work.



« Last Edit: May 21, 2013, 12:02:25 AM by helpinghand »

AyrA

  • BM-Bc7Rspa4zxAPy9PK26vmcyoovftipStp
  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1242
  • Karma: +74/-7
  • bitmessage.ch and timeservice operator
    • View Profile
    • AyrAs Homepage
Re: My Security Analysis of Bitmessage
« Reply #2 on: May 21, 2013, 03:51:58 AM »
I just quickly looked over your security audit and some of the flaws you point out rely on the fact, that the attacker owns nodes "between" two communicating nodes to find out who they are. This does not really works with the current network Design. If your node receives the same Message from 3 connected nodes in a row you cannot just assume that the node who gives you the message first is the closest to the sender. A node with a Broadband connection will relay a message faster than one with Dialup.
There is always some sort of Guessing involved. If you really want to pin down the IP of a Node you ned to occupy all open connections to that node to make sure a message originates from him. If you do not have all connections you can no longer distinguish between relayed and originating messages.
Also the fact, that everyone gets everything is used in Bitcoin as well and works just fine, even with the f**king huge Blockchain. Messages in Bitmessage get deleted after two Days, so it will at some Point no longer grow if a steady user base has been reached.
Bitmessage being CPU intensive can be solved by switching to a Language, that compiles to machine code. Somebody is implementing it in C++ and has a few Seconds on POW. It also might be faster in trying to decode the Messages.
Current CPUs are much faster than the Internet connection required to flood them with work.
My Address: BM-Bc7Rspa4zxAPy9PK26vmcyoovftipStp
Bitmessage Time Service (Subscribe): BM-BcbRqcFFSQUUmXFKsPJgVQPSiFA3Xash
Support the Multipart Message Declaration Draft for Bitmessage: https://bitmessage.org/forum/index.php/topic,1553.0.html
Free Bitmessage to E-Mail Gateway: https://bitmessage.ch

JonathanCoe

  • Full Member
  • ***
  • Posts: 178
  • Karma: +26/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #3 on: May 21, 2013, 06:23:52 AM »
Many thanks for taking the time to write this, it's exactly the sort of scrutiny that Bitmessage needs.
My address: BM-NBdhY8vpWJVL2YocA2Gfjf7eVoZAgbEs

helpinghand

  • Newbie
  • *
  • Posts: 23
  • Karma: +6/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #4 on: May 21, 2013, 06:24:30 AM »
I just quickly looked over your security audit and some of the flaws you point out rely on the fact, that the attacker owns nodes "between" two communicating nodes to find out who they are. This does not really works with the current network Design. If your node receives the same Message from 3 connected nodes in a row you cannot just assume that the node who gives you the message first is the closest to the sender. A node with a Broadband connection will relay a message faster than one with Dialup.

First of all, the papers I have read are not very technically detailed or clear, and it makes it hard to analyze the protocol. It confuses me to hear that you would get the same message from three nodes in a row, because in the paper it makes it seem like you filter for messages that you already have

Quote
getdata is used in response to an inv message to retrieve the content of a specific object after filtering known elements.

granted it also says

Quote
Each client forwards messages to every other client.

But I took that to mean that every client routes messages in a free route overlay. For example, in I2P and Freenet, every client can forward messages to every other client (versus JAP where certain nodes forward messages only to specific other nodes, AKA a cascading network), but they do not forward every single message to every single client. Ambiguity like this makes understanding the protocol difficult. If every client really forwards every message to every other client, this system is not going to scale. If there are 1,000 nodes on the network and I send an 80 KB message, I just cost the network 80 * 1000 * 1000 KB , or 76.29 gigabytes of bandwidth for me to send Bob an 80 KB message, with each individual node spending 78 megabytes of bandwidth . If I send Bob fifty 80 KB messages I just cost the network 3.8 terabytes, and each individual node almost 4 gigabytes. Assuming every one of the 1,000 users sends 80kb of data a day, that costs the network 80 * 1000 * 1000 * 1000 KB , or 74 terabytes of bandwidth per day to send 78 megabytes worth of actual communications data, at a daily bandwidth cost of about 76 gigabytes a day per node . An attacker merely needs to spam the network to grind the entire thing to a halt, and POW is not going to protect from this with that level of amplification. In most of the world residential consumers pay for bandwidth per gigabyte, and that is pretty standard for business users in the USA... Most hosting providers only give you 1TB or less of bandwidth per month, which means about 13 days until the server is out of bandwidth with 1,000 users sending 80kb per day.

If nodes really send all messages they get to all of their peers, without the peers declining to get messages they already have, how do you prevent infinite loops of Bob sends the message to Alice sends the message to Carol sends the message to Bob sends the message to Alice etc? None of this is specified in the papers I read.


That said, assuming I have not misinterpreted the paper and that nodes actually do not receive the same message N times, none of the attacks I mention assume that the node that sends you the message first is closest to the sender. You are probably talking about one of the intersection attacks. Intersection attacks involve taking multiple crowds that you know the target is in, and comparing them with each other, eliminating nodes that are not in all of the crowds.

In the case where the network consists of 8 nodes (A[1-3], B, C, D, E, F) the entire attack would look something like this:

Alice the attacker (A nodes) wants to identify her contact Bob's IP address. She starts with the crowd B, C, D, E , F , which is the entire BitMessage channel that Bob is a part of. She knows that  Bob is either B, C, D, E or F because she is all of the other nodes.

Bob sends Alice a message and it takes this route:

B -> C -> D -> A[1] -> F -> A[2] -> E -> A[3]

Since Alice forwarded the message on to nodes F and E, she can eliminate them from her crowd of suspect nodes.

BCDEF
BCD

Later Bob sends Alice another message and it takes this route:

B -> E -> A[1] -> C -> A[2] -> D -> A[3] -> F

Now since Alice forwarded the message to node C, D and F she can eliminate them as suspects:

BCDEF
BCD
B is the only remaining node and thus must be Bob

This particular attack will not work if nodes continue to accept receiving the same message from all of the clients (however if nodes do continue to receive messages they already have from all clients in the channel, BitMessage is never going to scale to channels of any significant size, and is going to be super weak to DOS attacks. Everybody gets everything PIR already has trouble to scale, everybody gets everything N times seems impossible to scale to any significant crowd size).

Quote
There is always some sort of Guessing involved. If you really want to pin down the IP of a Node you ned to occupy all open connections to that node to make sure a message originates from him. If you do not have all connections you can no longer distinguish between relayed and originating messages.

For an internal attacker who isn't carrying out an intersection attack, you are right, as I mentioned

Quote
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 the perspective of an external attacker, this is not true unless there is link level encryption, which is not specified anywhere in any of the papers I read so I must assume it is not currently part of BitMessage:

Quote
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.

 
Quote
Also the fact, that everyone gets everything is used in Bitcoin as well and works just fine, even with the f**king huge Blockchain. Messages in Bitmessage get deleted after two Days, so it will at some Point no longer grow if a steady user base has been reached.

I don't know how much data every Bitcoin transaction adds to the blockchain, but I assume it is less than the amount of data expected to travel through a popular messaging system. Eventually Bitcoin is going to run into scalability issues itself though, since the blockchain constantly grows. For a system like Bitcoin everybody gets everything is required, for a message retrieval system it is considered the least efficient system (although everybody gets everything N times might hold that crown now).

Quote
Bitmessage being CPU intensive can be solved by switching to a Language, that compiles to machine code. Somebody is implementing it in C++ and has a few Seconds on POW. It also might be faster in trying to decode the Messages.
Current CPUs are much faster than the Internet connection required to flood them with work.

I think a better way of solving it is by not needlessly trying to decrypt everything. Hopefully you at least don't try to decrypt everything every time. Also I wouldn't count on CPU not being a bottleneck, Tor hidden services get DoSed from introduction node CPU bottlenecks before they get DoSed from introduction node bandwidth bottlenecks.
« Last Edit: May 21, 2013, 07:27:42 AM by helpinghand »

helpinghand

  • Newbie
  • *
  • Posts: 23
  • Karma: +6/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #5 on: May 21, 2013, 06:58:57 AM »
Damn it I just typed out a big explanation and lost it all because of getting logged out.

Here I go again :<. Sorry, this time it is not as detailed as the first time.

All of the other intersection attacks I discussed will continue to work even if everybody gets everything from all of the clients. Assume A is always Alice who is trying to identify Bob's (B) IP address. Also the non-intersection attacks will also continue to work.

1. Assume the network consists of nodes A[1-3], B, C, D, E, F

Alice enumerates the channel by aggressively peering. Her starting crowd is B, C, D, E, F because she is all of the other nodes.

Alice notices that node C has disconnected. She sends a message to Bob with ACK data in it. Shortly after doing this, she notices the ACK data is in the network. C was offline during this entire time, so she can eliminate node C as a suspect.

B, C, D, E, F
B, D, E, F

Now Alice notices that node C is back online, but nodes D, E and F are offline. She sends another message with ACK data to Bob, and again notices the ACK data is sent through the network. During the entire time nodes D, E and F were offline.

1. B, C, D, E, F
2. B, D, E, F
3. B


2. Assume the network consists of nodes A[1-3], B, C, D (this attack can actually be thought of as an active version of the passive intersection attack from my previous post, the passive version may actually not work if nodes get the same message multiple times, but the active version will continue to work)

Alice maintains connections to each node on the channel

A[1] <-> B <-> C
A[2] <-> C <-> B
A[3] <-> D <-> A[1]

Bob sends Alice a message. First it goes to node C

B <-> C

then it goes to Alice at A[1]

B <-> A[1]

After receiving the message, Alice quickly queries all nodes for it. Since the message has not yet arrived at D, only nodes B and C have it:

B, C, D
B, C

Bob sends Alice another message. This time it goes to node D first:

B <-> D

then to node A[2]

B <-> A[2]

Once again Alice quickly queries all of the nodes for the message. This time only B and D have it.

1. B, C, D
2. B, C
3. B, D

Node D is eliminated in the second crowd, node C is eliminated in the third crowd, leaving only node B as a member of all crowds. Therefor Bob is node B.

Alternatively, Alice could maintain connections to all nodes and continuously query them for ACK data in a message she sends to Bob.

A[1] <-> B
A[2] <-> C
A[3] <-> D

Since Bob should always be the first person with the ACK data (even if he uses a middle node, depending on how the implementation is done anyway, it isn't really specified in the specification), he will be the first to respond to Alice's GetData query.
« Last Edit: May 21, 2013, 07:13:38 AM by helpinghand »

dokument

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 488
  • Karma: +37/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #6 on: May 21, 2013, 07:48:59 AM »
First of all, the papers I have read are not very technically detailed or clear, and it makes it hard to analyze the protocol.

No, they are not. However, they are presented as a proposal of goals and not specific methods. Reading the github code will lend you much more accurate information about what is actually happening. No this is not ideal but for a <1 year project I think it is okay.

Quote
Each client forwards messages to every other client.

But I took that to mean that every client routes messages
You took it correctly. I believe that Ayra meant that messages are dispersed to every client in the network and not that every client directly connects to every client and sends a copy of every message. Yes, that would be rediculous. Currently clients have about 8-50 connections from which they exchange messages with.

Quote
Bob sends Alice a message and it takes this route:

B -> C -> D -> A[1] -> F -> A[2] -> E -> A[3]

But that would require B, C, D, E, and F to either not be connected to each other, or not be connected via yet another client. There is no way to know what connections they have unless you are monitoring their lines/packets.

Quote
I think a better way of solving it is by not needlessly trying to decrypt everything. Hopefully you at least don't try to decrypt everything every time. Also I wouldn't count on CPU not being a bottleneck, Tor hidden services get DoSed from introduction node CPU bottlenecks before they get DoSed from introduction node bandwidth bottlenecks.

I agree that solving the problem just by doing it faster isn't really a solution. However, it really is not that large of a problem. The pros and cons can be weighed but currently I don't see one being much different than the other.

Quote
BitMessage is insanely and needlessly processor intensive
This would have more impact on a battery powered, or low processing power device but it really is not cpu intensive. Even in an interpreted language like Python. I would be interested to hear your thoughts on the Proof of Work method of preventing flood attacks.

Quote
A better solution is to use a signaling system. I will share with you the signaling system I came up with...

How would this work if I used multiple clients with the same addresses?

How would the signaling system work with broadcast messages?

Quote
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

I agree that it makes more sense to use the public key as the address (or an address that you can derive the public key from). It would remove the need for public key requests.

Currently the receiver has to be online in order for you to send a message. Unless you already have their public key. I would also think that this is an opening to an attack since you could verify that the public key was sent after the person you are physically monitoring returns to the computer. The same is true for Ack messages. They are sent when a message is received. It is easy to tell (if you monitor this) when an address is online and offline. From that you could determine geo-location based on time of day and go from there. Personally, I think that acknowledgements should be request only. Even then, the recipient could deny the request.

Quote
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.

I am not a fan of streams either but I do not know of a better way to handle scalability. The new streams are only used for new addresses when the parent stream is nearing full/full. Since there are default bootstrap servers, it would be difficult to corner the new users. The ability to change these servers is going to be added in an upcoming version so that mitigates the issues with centralized bootstrapping.

Quote
Everybody gets everything PIR is the only PIR technique that guarantees anonymity to the set size in all cases
That sounds like a good thing. No it is not the most efficient way to get a message between two people, if that was the goal then nothing would be encrypted among other things. I believe that the downfalls of this method are acceptable since they allow it to be so anonymous.

Quote
It uses 32 threads for outgoing messages, I assume it replaces them as it goes
As in, establish all new connections after sending connections? No.

Quote
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
Well they don't all peer with each other directly (as you pointed out to Ayra) but they do peer in groups of ~8-50. How did you get 31.25 seconds?

Quote
let's say she has a modified client that uses 1,000 threads
I suppose with a client like that there is nothing to stop her from connecting to every client on the network (potentially), in which she could easily determine the routing of messages (including originator and recipient) unless I am missing something.

Quote
For a system like Bitcoin everything gets everything is required, for a message retrieval system it is considered the least efficient system
What keeps it from being required for a messenger system? You said yourself that it is " the only PIR technique that guarantees anonymity". So why make it something less than what it could be?

I'm not an expert in this field at all so thanks for the input. Much appreciated.

.dok
BM-2cTtoitr47Q7weyKr9pFX363YBRMQfBWzt

AyrA

  • BM-Bc7Rspa4zxAPy9PK26vmcyoovftipStp
  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1242
  • Karma: +74/-7
  • bitmessage.ch and timeservice operator
    • View Profile
    • AyrAs Homepage
Re: My Security Analysis of Bitmessage
« Reply #7 on: May 21, 2013, 07:54:40 AM »
Atheros already stated somewhere, that the ACK Message can be disabled in future Versions. People who really do not want to be tracked then will disable this. Also you stated in another thread that you had issue signing in with tor and open HTTP Proxies.
If you want privacy just buy a proxy or VPN, also you have to expect, that people who do not want to be tracked will use TOR, your system works very quickly with 5 Nodes but with an increasing amount of nodes and an increasing amount of always online nodes the atacks will be difficult to do. There are many Services that are online 24x7 if there are at least two (for example an Echo Server and the Client you want to track) you probably will never nail it down to a single IP. if the user uses a service like bitmessage.ch his client will stay always on and the messages he sends and receives are getting lost between others.

And remember, always [CTRL]+[C] before hitting the Post Button!
My Address: BM-Bc7Rspa4zxAPy9PK26vmcyoovftipStp
Bitmessage Time Service (Subscribe): BM-BcbRqcFFSQUUmXFKsPJgVQPSiFA3Xash
Support the Multipart Message Declaration Draft for Bitmessage: https://bitmessage.org/forum/index.php/topic,1553.0.html
Free Bitmessage to E-Mail Gateway: https://bitmessage.ch

AyrA

  • BM-Bc7Rspa4zxAPy9PK26vmcyoovftipStp
  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1242
  • Karma: +74/-7
  • bitmessage.ch and timeservice operator
    • View Profile
    • AyrAs Homepage
Re: My Security Analysis of Bitmessage
« Reply #8 on: May 21, 2013, 08:03:59 AM »
I suppose with a client like that there is nothing to stop her from connecting to every client on the network (potentially), in which she could easily determine the routing of messages (including originator and recipient) unless I am missing something.
A Node does not send the Message to all connected Nodes at the same time, this is done more or less sequentially, so if A, B and C are connected (C is the bad node) you can get a message originating from A from client B, because of network latency or A getting occupied with another task before sending it to C itself. There is also the possibility, that the Message originated from D, which only had a connection to A and B. There are always clients out there you cannot connect to (yellow Icon). If they do not connect to your Node there is no chance in ever getting their IP.
My Address: BM-Bc7Rspa4zxAPy9PK26vmcyoovftipStp
Bitmessage Time Service (Subscribe): BM-BcbRqcFFSQUUmXFKsPJgVQPSiFA3Xash
Support the Multipart Message Declaration Draft for Bitmessage: https://bitmessage.org/forum/index.php/topic,1553.0.html
Free Bitmessage to E-Mail Gateway: https://bitmessage.ch

dokument

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 488
  • Karma: +37/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #9 on: May 21, 2013, 08:22:19 AM »
Also. Forgive me for my simplicity in presentation but PIR is essentially retrieving everything to hide what it is that you were actually after. As a Bitmessage client, you download everything from your connections and then sift through it yourself. Every application is both a client and a server for the network. I am almost positive that even after a client successfully identifies a messages as theirs, they continue to relay it to others. This makes the reading anonymous. The problem is in sending/writing. So things like sending messages, broadcasts, ackdata, and pubkeys are all susceptible to this insecurity. Sending messages and broadcasts are the main function of bitmessage so those are not changing. Being able to determine the pubkey from an address would remove the need for pubkey requests, and making acknowledgements optional would remove the need for them. The could still be requested but when privacy is concerned but another solution to ensuring message delivery would be needed. Without an acknowledgement, a client has 2-2.5 days to connect or else their messages are deleted. The ~2 day limit is just the current preference. It would be easy to setup a few long-term storage servers that users could connect to for retrieval of old messages. Since PIR is anonymous in this fashion, it should not pose an issue other than the client directly connecting to this node (which could be logged/tracked etc). Not an ideal solution.

One way to help with the issue of a malicious node being connected to thousands of users (and the attacks they could carry out) would be to not allow clients to share connections with nodes they are already connected to. So if you had 4 nodes in total then the connections would look like this.

Node 1 - Node 2 - Node 3 - Node 4 - Node 1

This would actually make the network spread out better as well. The only exception to this would be if you had too few connections, then additional connections could be made until they are filled. However, the attacker could have more than one ip which would bypass this.


If they do not connect to your Node there is no chance in ever getting their IP.
Except that nodes share the ip's of all of their connections. So you would know what ip's you are not connected to. Once you connect to them then you would know which of their stored ip's you are not connected to, etc.

.dok
BM-2cTtoitr47Q7weyKr9pFX363YBRMQfBWzt

helpinghand

  • Newbie
  • *
  • Posts: 23
  • Karma: +6/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #10 on: May 21, 2013, 08:43:12 AM »
Quote
You took it correctly. I believe that Ayra meant that messages are dispersed to every client in the network and not that every client directly connects to every client and sends a copy of every message. Yes, that would be rediculous. Currently clients have about 8-50 connections from which they exchange messages with.

Whew glad to know that I took it correctly. I was really scratching my head wondering why everybody is getting everything so many times :D.

Quote
Quote
Bob sends Alice a message and it takes this route:

B -> C -> D -> A[1] -> F -> A[2] -> E -> A[3]

But that would require B, C, D, E, and F to either not be connected to each other, or not be connected via yet another client. There is no way to know what connections they have unless you are monitoring their lines/packets.

But if A[1] sends F a message, even if F is connected to other nodes that have the message, it seems we can rule F out as being the inserter (to steal freenet terminology) of the message, since nodes do not request messages they already have. It doesn't matter what connections they have, it matters what messages they have and when they have them in relation to other nodes.

Quote
I agree that solving the problem just by doing it faster isn't really a solution. However, it really is not that large of a problem. The pros and cons can be weighed but currently I don't see one being much different than the other.

The current solution of sleeping to protect from the decryption timing attack is probably not secure. Using the signaling system I mentioned with a bloom filter is fast and constant time, I highly suggest doing that instead of trying to decrypt everything. Here are the five stages of timing attack awareness:

http://rdist.root.org/2010/01/07/timing-independent-array-comparison/

1. The timing difference is too small to attack
2. I’ll just add a random delay to my function
3. I’ll add a deadline to my function and delay returning until it is reached
4. Ok, ok, I developed a constant-time function
5. Ok, I fixed those bugs. Are we done yet?

BitMessage is currently somewhere between stage 2 and 3, my proposed solution is somewhere between stage 4 and 5.

Quote
This would have more impact on a battery powered, or low processing power device but it really is not cpu intensive. Even in an interpreted language like Python. I would be interested to hear your thoughts on the Proof of Work method of preventing flood attacks.

Deriving shared secrets for and symmetrically decrypting thousands of messages * possibly multiple keys seems like it is pretty processor intensive versus querying a bloom filter.   

Quote
How would this work if I used multiple clients with the same addresses?

You would need to keep an up to date bloom filter or similar between all devices and clients. Alternatively you could create signals hundreds or thousands in advance for each of your contacts, and keep separate filters synched pretty well simply by using your private ECC key (which would need to be shared between clients anyway) and your contacts public ECC keys (ditto).

Quote
How would the signaling system work with broadcast messages?

Broadcasts apparently include a static address hash which more or less acts as a non-changing broadcast signal. This allows anybody to identify all messages that are part of a broadcast, but you don't want somebody to be able to identify all messages to Bob (otherwise you would just tag them with a static string as well, in which case all messages to Bob could be tagged with the static hash produced by your initial ECDH secret derivation, which would make synching multiple clients a bit easier).

Quote
I am not a fan of streams either but I do not know of a better way to handle scalability. The new streams are only used for new addresses when the parent stream is nearing full/full. Since there are default bootstrap servers, it would be difficult to corner the new users. The ability to change these servers is going to be added in an upcoming version so that mitigates the issues with centralized bootstrapping.

There are (much) better scaling PIR algorithms than BitMessage is using, but none of them are completely P2P like BitMessage is. Most of them involve a smaller number of distributed servers that store messages, with a much larger number of clients querying k-out-of-l of them to retrieve messages. Most offer the same privacy as everybody gets everything, so long as 1-out-of-k servers is not attacker controlled (where as everybody gets everything offers privacy even with only one single server, that is also attacker controlled).

Quote
That sounds like a good thing. No it is not the most efficient way to get a message between two people, if that was the goal then nothing would be encrypted among other things. I believe that the downfalls of this method are acceptable since they allow it to be so anonymous.

Imagine a more centralized network for a second. Let's say there are five PIR servers that clients connect to in order to retrieve their messages. With everybody gets everything, the messages are mirrored across the five servers, and clients connect to one or more of them and retrieve all messages. Let's say there are 1,000 messages and each is about 10 KB, and each client has 1 message for it. So each client retrieves 10,000 KB of data with everybody gets everything. Because it is everybody gets everything, all of the clients have an information theoretic anonymity guarantee, even if all of the servers are attacker controlled.

Now imagine the same general system, but instead of everybody gets everything from any combination of the servers, everybody participates in an algorithm with each of the servers that results in them getting a 10 KB message from each of the servers. When these 10 KB messages are cryptographically processed client side, they turn into the set of the messages for the specific querying client. So long as no more than 4 out of the 5 servers are compromised, the client has the same anonymity as they would have in an everybody gets everything system. That is the trade off between everybody gets everything and more sophisticated PIR systems: with everybody gets everything all 5 of the servers can be attacker controlled and the client still has perfect anonymity, but it took 10,000 KB of bandwidth for the client to get its messages. With a more sophisticated PIR system, the client can be deanonymized if all of the servers are attacker controlled, but it only took 50KB of data for the client to get all of its messages. Three orders of magnitude less bandwidth might be worth being slightly less secure.

Quote
As in, establish all new connections after sending connections? No.

That makes the GetData intersection attack even more effective then.

Quote
Well they don't all peer with each other directly (as you pointed out to Ayra) but they do peer in groups of ~8-50. How did you get 31.25 seconds?

This is actually good from an attackers perspective, because it means that it will take longer for messages to propagate throughout the network, which means there is more of a window of opportunity to query nodes for a message you received before they receive it.

Quote
I suppose with a client like that there is nothing to stop her from connecting to every client on the network (potentially), in which she could easily determine the routing of messages (including originator and recipient) unless I am missing something.

I believe that she can likely use a custom client like this to quickly deanonymize her targets. Determining recipient might be harder, but inserter shouldn't take too long with an intersection attack.


Quote
What keeps it from being required for a messenger system? You said yourself that it is " the only PIR technique that guarantees anonymity". So why make it something less than what it could be?

To reduce the required bandwidth by three orders of magnitude.

helpinghand

  • Newbie
  • *
  • Posts: 23
  • Karma: +6/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #11 on: May 21, 2013, 08:55:22 AM »
Atheros already stated somewhere, that the ACK Message can be disabled in future Versions. People who really do not want to be tracked then will disable this. Also you stated in another thread that you had issue signing in with tor and open HTTP Proxies.
If you want privacy just buy a proxy or VPN, also you have to expect, that people who do not want to be tracked will use TOR, your system works very quickly with 5 Nodes but with an increasing amount of nodes and an increasing amount of always online nodes the atacks will be difficult to do. There are many Services that are online 24x7 if there are at least two (for example an Echo Server and the Client you want to track) you probably will never nail it down to a single IP. if the user uses a service like bitmessage.ch his client will stay always on and the messages he sends and receives are getting lost between others.

And remember, always [CTRL]+[C] before hitting the Post Button!

I have implemented an awesome anonymity network, it does nothing but forward traffic on to Tor ;). I primarily analyzed the anonymity of BitMessage, if you look at it not as providing anonymity, but as a distributed messaging system without the goal of anonymity, then things are different.

You can DDoS groups of nodes at a time to artificially speed up intersection attacks like this. I use my Botnet to DDoS half of the BitMessage channel and see if Bob sends my ACK. If he does I DDoS half of the remaining half etc. Or DDoS one node at a time even.

helpinghand

  • Newbie
  • *
  • Posts: 23
  • Karma: +6/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #12 on: May 21, 2013, 08:56:51 AM »
I suppose with a client like that there is nothing to stop her from connecting to every client on the network (potentially), in which she could easily determine the routing of messages (including originator and recipient) unless I am missing something.
A Node does not send the Message to all connected Nodes at the same time, this is done more or less sequentially, so if A, B and C are connected (C is the bad node) you can get a message originating from A from client B, because of network latency or A getting occupied with another task before sending it to C itself. There is also the possibility, that the Message originated from D, which only had a connection to A and B. There are always clients out there you cannot connect to (yellow Icon). If they do not connect to your Node there is no chance in ever getting their IP.

But if I receive a message from Bob and Carol does not have it, I know that Carol did not originally insert the message to the network.

AyrA

  • BM-Bc7Rspa4zxAPy9PK26vmcyoovftipStp
  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1242
  • Karma: +74/-7
  • bitmessage.ch and timeservice operator
    • View Profile
    • AyrAs Homepage
Re: My Security Analysis of Bitmessage
« Reply #13 on: May 21, 2013, 09:01:14 AM »
Carol might juist have delivered the Message to Bob and sends it now to Dan, causing your Request to be in the queue.
My Address: BM-Bc7Rspa4zxAPy9PK26vmcyoovftipStp
Bitmessage Time Service (Subscribe): BM-BcbRqcFFSQUUmXFKsPJgVQPSiFA3Xash
Support the Multipart Message Declaration Draft for Bitmessage: https://bitmessage.org/forum/index.php/topic,1553.0.html
Free Bitmessage to E-Mail Gateway: https://bitmessage.ch

helpinghand

  • Newbie
  • *
  • Posts: 23
  • Karma: +6/-0
    • View Profile
Re: My Security Analysis of Bitmessage
« Reply #14 on: May 21, 2013, 09:13:22 AM »
Also. Forgive me for my simplicity in presentation but PIR is essentially retrieving everything to hide what it is that you were actually after.

That is one sort of PIR. Another fairly basic type works like this. Let's say that there are 3 servers, and each keeps a copy of a database containing three items.

10010
00101
11010

I want to obtain the item at position 0 (I know this because the index of the database is public). So first I generate two random bit strings the size of the total number of items in the database

010
110

the next bitstring needs to cause the first two to XOR together into 0 at all positions other than the position of the item I want

0 XOR 1 = 1 XOR 0 = 1
1 XOR 1 = 0 XOR 0 = 0
0 XOR 0 = 0 XOR 0 = 0

so my third string is 000, giving me 000, 010, 110

now I send each of the servers one of the bit strings and they XOR together items at positions marked by 1. The server sent 000 sends me nothing (00000), the server sent 010 sends me 00101 and the server sent 110 sends me 10010 XOR 00101

1 XOR 0 = 1
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
0 XOR 1 = 1

10111, 00101, 00000

now I xor these replies together

1 XOR 0 = 1
0 XOR 0 = 0
1 XOR 1 = 0
1 XOR 0 = 1
1 XOR 1 = 0

10010 = the item at the position I requested. Unless all three of the servers collude, they are incapable of determining which item I retrieved. This example makes it worse than everybody gets everything, but for a larger database it would require much less bandwidth (1 bit sent to each server for each message in the index, one fixed size message retrieved from each server for each request). This algorithm trades off bandwidth for processing power. There are *much* more sophisticated PIR algorithms with better properties than this one, but in addition to not really understanding the math behind them, I don't think I can type the math symbols required to give examples of them here :P.

Quote
As a Bitmessage client, you download everything from your connections and then sift through it yourself. Every application is both a client and a server for the network. I am almost positive that even after a client successfully identifies a messages as theirs, they continue to relay it to others. This makes the reading anonymous. The problem is in sending/writing.

Do you download everything or only things you do not already have? Anyway, everybody gets everything is information theoretically secure even if all servers are attacker controlled. The PIR I showed an example of above is information theoretically secure if one of the servers is not attacker controlled.

Quote
The could still be requested but when privacy is concerned but another solution to ensuring message delivery would be needed. Without an acknowledgement, a client has 2-2.5 days to connect or else their messages are deleted. The ~2 day limit is just the current preference. It would be easy to setup a few long-term storage servers that users could connect to for retrieval of old messages. Since PIR is anonymous in this fashion, it should not pose an issue other than the client directly connecting to this node (which could be logged/tracked etc). Not an ideal solution.

Everybody gets everything PIR is anonymous, but it doesn't mean anonymity compromising things cannot be built based off of it. If everybody gets everything and then they announce what they got to everybody, it is not the PIR that compromises anonymity, but anonymity is still compromised.
« Last Edit: May 21, 2013, 09:25:49 AM by helpinghand »