Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
Is there a central server? How much do you trust that server? – CodesInChaos Jan 31 '13 at 15:59
@CodesInChaos clarified the details of the server. – Mansour Jan 31 '13 at 21:49
I'd throw a sequence counter, time-stamp, hash-chain and digital signature at it. I'll write a bit more tomorrow. – CodesInChaos Jan 31 '13 at 22:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.