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?

  • 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$
    – Amit
    Commented Feb 2, 2023 at 16:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.