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?
