I have a distributed system where each client writes many small messages, roughly the size of messages in a chat system, e.g. ~100-200 bytes each. I want each message to be signed so that we know for sure who sent each message, but the overhead of an RSA signature on each message is huge, so I need another approach.

One idea would be to sign the first message like normal, and include a hash of a random value. Then, in the next message, include that random value and a new hash of another random value. Each message "unlocks" the previous message's hash, showing that they were authored by the same client. Using a bcrypt/scrypt/argon2 hash with a work factor to meet about 10ms would mean that the random value could be kept small, say 64bit. Each message also has a unique id, which would be used as a salt. This is a huge improvement in overhead, but I have no real idea how secure such a system would be. Also, messages store ordering information, so once a message has been "unlocked", that random value cannot be used to "sign" a second message.

Some messages would contain encrypted fields, using some form of hybrid encryption. The servers only need signed metadata, not the actual messages.

I'd say this is a great example of where "don't roll your own 1. distributed system 2. crypto" applies. I've got the distributed system part, but I need your help with the crypto.

How can I sign many small messages (tens of thousands) with as little size overhead as possible, while still being secure? I've got 50MB of RAM and about 10ms of cpu time for decryption of each message. The client must be able to sign, encrypt and send messages without getting a response from the recipient(s).

  • $\begingroup$ You should clarify whether your overhead is CPU time, message size or both. $\endgroup$ Commented Nov 19, 2016 at 1:51
  • $\begingroup$ Message size. It says "size overhead" but it could've been clearer. $\endgroup$ Commented Nov 19, 2016 at 8:31

1 Answer 1


Then, in the next message, include that random value and a new hash of another random value.

What would prevent someone from taken that valid 'next message', replacing the contents with their own message, and keeping the random value in place?

You could define a hash chain by hashing the entire message to come up with the previous value, but this would imply that when you sent the initial message, you already knew all the other messages at that time; that's unlikely to be a workable assumption.

Alternatives that immediately come to mind:

  • Use ECDSA (or EdDSA) signatures; those are only 64 bytes (for 128 bit security)

  • Consider using the Tesla protocol to do the authentication; it works similar to yours, except the actual signature comes at the end, not the beginning (and the receiver isn't sure that the messages are authentic until it receives that final message).

  • $\begingroup$ Good thing I didn't roll my own crypto! Sending the signature at the end is not practical since that would mean that the receiver has to wait for the last message, defeating the whole point of sending many small messages instead of batching them together. $\endgroup$ Commented Nov 19, 2016 at 11:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.