Week 10: Privacy and anonymity

What is privacy?

A state in which one is not observed or disturbed by others

- anonymity (unobservability of our actions when they occur)

- data protection (ensuring that our collected data is not distributed and used in undesired ways)

- confidentiality of information that you don't want to share

What is anonymity?

a condition in which your true identity is not known

It refers to the unobservability of our actions when they occur

What is the anonymity set?

The group of people such that your actions (sending, receiving, communication relationships) cannot be distinguished from the actions of anyone else in the group

What are the 5 classes on the anonymity set spectrum?

Absolute anonymity

Beyond suspicion - nobody can really guess

Probable innocence (50% chance)

Exposed

Provably exposed - publicly known

What are the relationships between privacy and confidentiality?

Privacy includes the idea of keeping information confidential but also encompasses the state of not being observed and having control over one's data

What are unlinkability and unobservability in the context of anonymity?

Unlinkability means that an action and an identity are no more related after observing communication than they were before

Unobservability is a stronger condition where an observer cannot even tell whether a certain action took place or not

What are the applications of privacy and anonymity?

- hiding online transactions, web browsing from governments, marketers and archivists

- whistle-blowers, confidential business negotiations

- electronic currency where purchases are unlinkable to identity

- anonymous e-voting, censorship-resistant publishing

What are types of anonymity attacks?

Passive traffic analysis

Active traffic analysis

Compromising network nodes

What is a countermeasure to an attack on compromised network nodes?

Assume that some fraction of nodes are good but do not trust individual nodes

What is the requirement for anonymity and unobservability in a network?

Use pseudonyms to anonymise the sender and/or receiver

Evaluation of using pseudonyms

It is lightweight and avoids linkability of the sender and receivers, but giving names to hosts and resolving these names into identities is problematic

How can we use proxies to anonymise sender/receiver interactions?

The client and server will communicate through a proxy, so that they do not know the other party's identity

The client sends its packets to the proxy and the server broadcasts packets in an anonymity group

What are the weaknesses of using proxies to anonymise interactions?

The proxy knows everything, so the attacker can just compromise the proxy instead

Attackers can observe conversations via the proxy

What is a solution to the weaknesses of using a proxy for anonymous interactions?

Cascading proxy chains

Mix networks

What is a cascading proxy chain?

When traffic goes through a sequence of pre-determined proxies

What is a mix network?

Mix networks are mechanisms for building an anonymous channel. Messages are sent through a sequence of mixes. The sender chooses the mix path to send the item across

What is a mix?

a special type of server that receives, shuffles, and forwards encrypted messages.

What are mixes designed to do?

It's designed to obscure the connection between sender and recipient.

What are some key requirements for mixes to foil traffic analysis?

- Work with uniformly sized items (messages split or padded)

- Hide the order of arrival by outputting items in batches, potentially using fixed or random ordering

- Block repeated information by filtering duplicates or including timestamps

- Require sufficient traffic from a large anonymity set

What is a mixnet?

An arbitrary network of mixes

What is the pseudonym used to anonymise the identity of a mix?

Its public key

How does sending traffic through a single mix work?

The mix receives encrypted messages from multiple senders

Each incoming message is decrypted with the mix's private key to reveal the intended recipient, message and padding

What is the weakness of using a single mix?

If you compromise the mix, you know everything about the network traffic - so you need to lessen this by having a mix network or cascaded mixes

How does sending a message across a mix network work?

The sender chooses a mix path to send a message M to a receiver with address B

Because the sender knows each mix node in the mix path, they encrypt their message using the public key of each node in reverse (i.e. mix N then N-1 then ... then mix 1)

This multilayered encrypted message is sent to each mix node 1 - N

Each mix node uses their private key to decrypt and retrieve the next inner layer, containing the address of the next mix

At the last mix N, the mix sends the message to the recipient's address

During encryption in a mix, what is the content of each encrypted message?

The message, the address of the next node to go to in the mix, and a random padding string

What is the function of the random padding string from an encrypted message in a mix network?

To prevent an attacker correlating the input and output of a mix based on the message size

What can we do to ensure even more anonymity between the sender and the receiver?

Make the return address of the sender anonymous

How can we make return addresses untraceable?

(Assuming there is only one mix)

The sender will encrypt their address and a random padding string r1 with the mix's public key along with a fresh public key for the specific interaction

Through the mix, the receiver receives the message and the public key

The receiver generates and encrypts its response and a padding string r0 with the public key it was given

The return address and r1 are decrypted with the mix's private key, and the response is encrypted again with the secret r1 to mask the correlation between the input and output

The sender receives the response, and because it knows the public key and r1, it can decrypt the response

What makes a good mix?

A mix with multiple administrator domains

Diversity in jurisdictions

Public transparency of mixes, and auditing

Decentralising and distributing trust between mixes

How can a mix network prevent tracing a message attack?

The mix can inject more dummy traffic in order to add noise and prevent the attacker tracing the message

How can a mix network prevent replay attacks?

The mix can have a replay filter, where duplicates and replays of a message are filtered out and not processed

What are the advantages of mix networks?

Very high degree of anonymity

Cryptography is used in a novel way

Why do mix networks provide a high degree of anonymity?

There is no correlation between the mix input and output, and if we have enough dummy traffic, the anonymity set is the entire network

What are the disadvantages of mix networks?

Computationally expensive to do public key encryption and decryption

Overhead with creating dummy traffic

High latency which is ok for mail sending but not anonymous web browsing

How can we eliminate the overhead from dummy traffic generation in a mix network?

If our network has a high anonymity set, or if the network already generates enough communication

What is an n-1 attack?

An active attack where the attacker knows n-1 of the n messages put into a mix, so they can identify and trace the honest message across the network to link its sender and receiver

How does an attacker know the n-1 messages sent in a network in an n-1 attack?

They may be controlling the n-1 messages by knowing its contents and destinations, or they might have sent those messages themselves

What are countermeasures to n-1 attacks?

Sending heartbeat messages, injecting dummy messages, creating RGBmixes

What is a heartbeat message?

Red traffic, where mixes send anonymous messages to themselves through the network - this helps the mix detect if it is being flooded with black traffic

What is black traffic?

User or attacker messages

What is green traffic?

Dummy messages

When would you inject dummy traffic?

When the rate of heartbeat return is suspiciously low - injecting dummy traffic increases the number of honest messages in the mix and increases the anonymity set

What is an RBGmix?

Identifying traffic in three colours: red, green and black

Only the mix can tell what traffic is what type

What is onion routing?

A technique to hide the message source with random routing

How does onion routing work?

The sender chooses a random sequence of routers, and controls the length of the path

The routing info for each link is encrypted with the router's public key, so each router only learns the identity of the next router

What is the basic principle of the Dining Cryptographer's protocol?

A group of diners want to establish if one of them paid for the meal anonymously or if an outsider is paying

Each diner flips a coin and shows it to their left neighbour only

Each diner announces whether their neighbour's coin and their coin are the same

If the diner is the payer, they will lie

How is the payer determined in a three-person Dining Cryptographer's protocol?

If an odd number of people said that their coins are the "same", then an outsider paid

If an even number of people said the coins are the same, one of the diners has paid

But a non-diner cannot distinguish who out of the other two paid for the meal!

What is the proof for the Dining Cryptographer's protocol?

The result of each diner (whether the coins are the same or not) is a boolean value, their coin is XORed with their neighbour's coin (0 or 1)

The liar will flip their result, i.e. they XOR their result with 1

The total result is an XOR of each diner's result

Because the table is circular, then the value of each diner's coin appears exactly 2 times so this produces the result 0

If an outsider paid, then the result stays as 0

If one of the diners paid, then the liar's result produces an overall result of 1 (0 XOR 1)

But because XOR is commutative, any non paying diner has no idea who lied

How can we extend the Dining Cryptographer's protocol to a group of size N?

Each user in the group generates a random bit and sends it to their neighbour

Each user announces their own bit XORed with their neighbour's bit

The sender will XOR this result with their individual message bit

The overall message bit is the XOR of all the announcements - nobody knows the sender of the message so there is anonymity

What is the Dining Cryptographer's protocol with a group of size N known as?

Superposed sending