3
$\begingroup$

So I've been visiting a security lecture at my university and they introduced the concept of Chaum's mixes to us and how replay attacks can compromise the anonymity granted by a mixnet.

It is explained that by adding a random string to the encryption of message X an attacker cannot simply guess a message Y in order to confirm K(X) = K(Y) or X = Y, respectively. I thought this is done in order to make encryption indeterministic and therefore avoid replay attacks.

However, later on, it was mentioned that some dedicated database or mixes themselves need to keep track of all messages sent over the mixnet in order to avoid replay messages. That seems to me as if there are two countermeasures against replay attacks - the random string and the database that keeps track. Why would the random string not be enough?

I've read through the entire paper by Chaum called "Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms" where he introduced the concept of mixes. However, he argues exactly the same way as described above and I just don't understand it.

Why are random strings not enough? Because over a long period of time, collisions are bound to happen with pseudorandom strings? If I would use timestamps and attached them to my message, would that solve the problem or would I still need a database that needs to keep track of every message that has ever been sent over the mixnet?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It sounds to me that the DB tracking of the random numbers is a good thing to do if you are concerned that your randomness sources / generation methods are not so great. With nonces for example which play a similar role, we usually trust them only on the basis of their entropy (e.g. if the nonce has enough bits it is assumed to be okay) and we usually don't store them for later comparisons. Also, I don't know enough about mixnet, but note that the problem with nonces increases the longer you use the same key in a session (or even across multiple sessions) - perhaps that's relevant here $\endgroup$ Commented Feb 2, 2023 at 16:02

1 Answer 1

Reset to default
1
$\begingroup$

Nowadays ciphertext indistinguishability is reasonably expected from any modern cryptosystem, so you can expect that $K(X) \neq K(Y)$ even for $X = Y$ without having to append random string $R$. This was not the case when the paper Untraceable electronic mail, return addresses, and digital pseudonyms was written, so it is stated explicitly:

If $X$ is simply encrypted with $K$, then anyone could verify a guess that $Y = X$ by checking whether $K(Y) = K(X)$. This threat can be eliminated by attaching a large string of random bits $R$ to $X$ before encrypting.

However, for mix networks it is not enough that legitimate messages are indistinguishable. An attacker can also observe the network traffic and reinject the messages later. If mixes are allowed to process the same message twice, an attacker interested in learning the destination of some message can inject it in two independent batches and find the message that appears in the output of the mix for both batches. By repeating such replay attack against the next mix, an attacker can trace the message to its destination.

This is why the paper says:

Thus, an important function of a mix is to ensure that no item is processed more than once. This function can be readily achieved by a mix for a particular batch by removing redundant copies before outputting the batch. If a single mix is used for multiple batches, then one way that repeats aross batches can be detected is for the mix to maintain a record of items used in previous batches.

Note that while Chaumian mixes are important in anonymity research, this particular design is not considered secure today. In particular, it is not secure against $n - 1$ attack described in the paper From a Trickle to a Flood: Active Attacks on Several Mix Types, 2002.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.