Signing many small messages with minimal overhead

Question

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).

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).