Membership Enumeration Attack - An adversary who owns nymserver and monitors one distributor wins

[hopppy]

I see a number of attack mechanisms which are in many cases linked to the nymservers abilities, specifically its ability to link messages to a given nym and to determine when a nym has registered with it. These attacks all presume an attacker who is able to see the internal state of a nymserver, and who can either passively or actively monitor at least one distributor. Allow me to elaborate:

Pynchon gate aims to provide anonymity through two techniques; mixing for forward messages (including control messages) and PIR for message retrieval. Clients register with the nymserver over a mix network, preventing the nymserver from linking a given client's (Alice) IP address to her nym. After messages have arrived, the nymserver batches them into buckets and sends the bucket pool to a set of distributor nodes. The users client engages in a PIR protocol with the distributor nodes, allowing her to fetch her messages without revealing which messages she is interested in, thus allowing her to remain unlinked to her pseudonym. Pynchon Gate aims to provide anonymity so long as the mix network used for forward and control messages is not compromised, and at least one of the distributor nodes is honest.

I will now present a number of attacks that can be performed by an adversary who owns a users nymserver in addition to having the ability to monitor the IP addresses that use a single distributor node (either actively or passively). In the worst case such an attacker can, with a high degree of probability, deanonymize users by linking their IP addresses to their pseudonyms. In better cases, the attacker can still significantly reduce a given nyms potential IP address crowd size. This attacker 'strength' (owns nymserver and monitors one distributor node) is significantly less than the strength of the attackers Pynchon Gate aims to protect from (inability to defeat the anonymity properties of the mix network AND doesn't own ALL of the distributor nodes). These attacks assume that clients connect to distributor nodes from fixed IP addresses, or a series of linkable dynamically assigned IP addresses. This may not always be the case, for example users may use Tor or connect from random WiFi access points...however it seems that these scenarios are outside of the scope of Pynchon Gates threat model.

Attack One: 'Newly registered' crowd size + long term client IP address enumeration

Assume that Alice has recently registered a nym with a malicious nymserver owned by Mallory. Mallory is also able to monitor traffic to at least one of the distributor nodes. As Alice has sent her registration control message through a high latency mix network, she should maintain her anonymity provided that the mix network can withstand traffic analysis. After registering, Alice must engage in the PIR protocol once for every cycle. Obviously, if she waits until she actually has messages to begin participation in cycles, she will leak her identity or seriously diminish her crowd size. Although the nymserver can not link Alice's IP address to her registration control message due to the mix network, and the distributor nodes can not link Alice to her pseudonym due to the properties of the PIR protocol, Mallory can still greatly compromise her anonymity. Mallory would carry out his attack by keeping record of the IP addresses that regularly engage in the PIR protocol with distributor nodes, and observing that Alice's IP address began to engage in it shortly after the nym Alice was registered on his nymserver. The anonymity of the PIR protocol and mix network stands: This attack is concerned with correlating the set of new IP addresses engaging in the PIR cycles with newly registered nyms, not with breaking the properties the PIR protocol or performing traffic analysis against the remailer network.

At best, several new nyms will have registered in the same time frame as Alice, and Mallory will only be able to determine that the newly registered nyms belong to a set size consisting of the newly observed IP addresses engaging in the PIR protocol. At worst, Alice will be the only recently registered Nym, and Mallory will be able to with very high probability link her IP address to her pseudonym...even without compromising the anonymity properties of the PIR protocol or the mix networks used.

Attack Two: Nym incoming message volume drops to nothing + nym no longer participates in cycles = pwnt?

The second attack involves a patient attacker (still Mallory who owns a nymserver and monitors connections to a distributor node) who observes the volume of messages to the nym Alice over a period of time. If Alice ever stops participation in the system, it stands to reason that her contacts will stop sending her messages after they realize she never responds to them. As Mallory can observe the volume of messages arriving for the nym Alice and the set of IP addresses engaging in PIR cycles, he is thus likely able to correlate Alice's sudden and continued lack of participation in PIR cycles and the subsequent sudden decrease in messages sent to the nym Alice.

Attack Three: The vacation attack

Attack three is a slight modification of attack two. Imagine that Alice has gone to Antarctica for two months to conduct some scientific research. During her time in Antarctica she will not be able to engage in PIR cycles as she will not have access to high quality internet very frequently. It stands to reason that Alice will experience a drop in her number of received messages as she will not be present to reply to them and carry on normal back and forth conversation. Mallory may be able to correlate Alice's lack of participation in PIR cycles with the change in the volume of messages addressed to the nym Alice. Mallory s suspicion may be further confirmed when after returning from her vacation and continuing to engage in / catch up on PIR cycles, the Nym Alice once again begins receiving messages in a volume that indicates the nym holder is engaging in back and forth communications.

Attack Four: Message volume received : sent correlation

Attack four imagines a more powerful attacker than the previously described Mallory. In this scenario the attacker is assumed to be a GPA in the context of the mix network, in addition to owning a nymser‎ver. It is likely that a less powerful attacker who is only local passive at Alice's connection + owns the Nymserver is also in a position to carry this attack out. The nymserver is capable of determining the number of messages that are sent to the nym Alice in a given cycle. If we assume that Alice always responds to messages, it will be trivial for the attacker previously described to correlate the number of messages Alice's IP address sends through the mix network to the number of messages the Nym Alice has received at the Nymserver. Of course it is actually not likely that Alice will respond to every single message she receives, but I strongly suspect that some sort of an attack like this is possible.

Attack Five: Spam + Control Messages

A GPA who can consistently and massively spam a nym may be able to observe an increase in outgoing mix network messages from the user they spam, who must now send additional control messages through the mix network in order to receive her real non-spam messages. This increase in outgoing messages may be slight and will possibly be masked by the users natural variance in sending outgoing messages, but some statistical attack based on the users average amount of outgoing messages + their outgoing messages when a particular pseudonym has been spammed may be possible. This attack is even more likely to be useful if the attacker has already greatly narrowed Alice's crowd size with attack number one.

Solutions:

I imagine that clients should begin to participate in the PIR protocol for some random number of cycles prior to actually registering with the nymserver, this should reduce the abilities of attack number one to link Alice's IP address to the nym Alice. Of course she would also need to send dummy Mixminion messages, and if nobody registers a nym in the time frame she is still out of luck. Additionally, clients should continue to engage in PIR cycles for some period of time after they quit replying to messages (quit using the system), to protect from attack number two.

Some of these attacks may be somewhat outside of the scope of Pynchon Gate (although they are still certainly applicable to it), however I believe particularly attack number one and two are directly related to the design of Pynchon Gate, and that the minimal countermeasure of join/quit 'cover cycles' should be added to the spec. Attack number two and three may be generally applicable to any system which entails communication, as an attacker who can enumerate the entire networks participants (distributor nodes) and the activity of a pseudonym using the system will always be able to correlate a clients lack of participation with the lack of activity of a pseudonym. Attack four may be seen as more of an attack against mix networks than Pynchon gate, and cover traffic seems to be the best solution to it...however it is certainly exasperated by a nymservers ability to precisely determine the message volume to a given nym.