Assume we have a public message board where anyone can send a message to. If plain messages are used, anyone can impersonate anyone. The goal is to disallow impersonations. We can use public key cryptography and users have access to secure means of distributing their public key (e.g. their personal website). There is a central server but it can't be trusted. The server is just as likely to perform a man in the middle attack as any other entity. The server's only job is to broadcast each message received to all recipients.
Users can enter and leave the room at any time. Also, apart from public keys of other trusted users, they won't be able to remember anything else from last visit when they enter the room again. However, they can track everything that happens while they're in the room.
The only way that I can think to stop users from replaying past messages in order to impersonate the target user, is to include a strictly increasing number in each message and sign the entire message using the private key. Receiving users can keep track of the last number and ensure the next message has a number larger. The problem is, what number do we pick for the first message? I thought a UTC timestamp would do it, but there is no reliable way to ensure everyone's clock is synced.
Another idea I had was for users currently in the room to challenge new users with random strings, but this doesn't scale well. Say there are 100 users currently in the room and another user comes in. The new user has to answer 100 challenges before being able to send a message others can trust.
Any ideas?
