Homework 2: Computing the properties of anonymity systems
Exercise 1: Consider the network log of several rounds a mix-net, including a sender (Alice), and fifty possible receivers, as might have been captured by a network-level adversary. Find the three most likely recipients of Alice's messages.
Exercise 2: Consider the log, as may have been captured by a network-level adversary, of a high-latency anonymous communication network with a number (4) of mixes, senders and receivers. We see that each sender (S0-S19) has sent one message, and each receiver (R0-R19) has received a single message. It is known that each sender has routed his message through exactly three mixes, and the mixes do not repeat on the paths. The log shows, which senders sent their messages to which mixes, how the messages moved between mixes during the intermediate rounds (i.e. how many messages went from each mix to any other mix), and which receivers received their messages from which mix.
Find the entropy of the distribution of possible recipients of S3. Also find the entropy of the distribution of possible senders to R14.
Suppose now that the adversary had corrupted the mix M0. The log additionally shows, how M0 routed the messages during each of their three passes through the mixes. Find the same entropies, if the adversary additionally knows how M0 routed the messages.
Exercise 3: Consider a dining cryptographers network with six parties, P0 to P6, with the following key-sharing graph. They run a round of the DC-net protocol, and broadcast values (8-bit messages) which are given in the same file. What was the anonymously broadcast value?
But the adversary had corrupted parties P1 and P4, they keys they had shared with other parties were the following. With the knowledge of these keys, is it possible that P5 was the party who sent the original message?
Exercise 4: A set of 100 users (number 0 - 99) have set up a Crowds system among themselves. Alas, they have set it up wrong, such that each query will result in the generation of a new path. There are three users (no. 15, 63, and 89) whose jondos are corrupt and are collaborating with each other. They are keeping logs, and have identified a set of 100 queries, the paths of which have passed through them. They have made sure that these 100 queries have the same initiator - indeed, this should not be too difficult to figure out, because the queries are not encrypted in Crowds. In the log, each row corresponds to one query, and its path, as it is visible to the three corrupt jondos. The log from each path is a sequence of triples, where the middle element identifies the corrupt jondo that is seeing the query, and the other two elements are the ID of the jondo that the message came from, and the jondo to which it was sent next (if it was next sent to the actual web server, then this is denoted by "WS"). Find, which user was the initiator of these queries.
Additional terms:
- The homework is individual. You are expected to do your own thinking.
- Write a document, where you do not just give the answers, but also explain how the answers were obtained.
- If you will be late, please alert the lecturer in advance.
Deadline: April 21st, 2021, 23:59 EEST.
Delivery:: upload through the course website (see below)
2. Homework 2: Anonymous communications