Suppose you would like to prove authenticity of messages where the message space is small. Suppose the meaning of the message depends highly on the context, e.g. on time but also on events that are hard to encode, like political or social events. An extreme example would be a message space of "yes" or "no" (1 Bit), which are obviously context-dependent. Consider, e.g., the answer to the question: Do you love me? It also depends on who asked the question.

If you just use digital signatures, someone could just replay a pair of a message and a digital signature in a different context, giving it a completely different meaning, but still using someone else's correct signature.

How could you prevent these replay attacks?

I first thought of randomisation/salting, but all the probabilistic encryption schemes that I know use public salt, so an attacker could just re-use the salt as well.

Disclaimer: I'm not planning to build my own crypto. I'm just wondering how this problem could be solved, since to me, it doesn't seem so far away from reality...

  • 3
    $\begingroup$ You need to include sufficient context. e.g. when answering a question, you could quote the question, including metadata like who asked and when or include its hash. $\endgroup$ Sep 8, 2016 at 14:55
  • $\begingroup$ Yes... So basically that's adding entropy to the message. Is there yet another way? $\endgroup$
    – maya
    Sep 8, 2016 at 16:49
  • $\begingroup$ Sorry that I am currently confused by your 2nd paragraph. Did you mean someone else could do a faked digital signature of yours or what? (Wouldn't that imply that your private key were compromised?) I mean that your signature is appropriately done. $\endgroup$ Sep 8, 2016 at 16:53
  • $\begingroup$ Pardon. On re-reading I understand what you wanted. But without any context, with simply a yes/no, the message is certainly subject to replay attacks. However, any transaction of any value/significance must certainly contain in practice a definite reference (context). Otherwise misunderstandings could also occur with communications on paper. So your problem doesn't have any sensible solution in my view. $\endgroup$ Sep 8, 2016 at 17:26
  • $\begingroup$ @maya It's not about entropy, it's about messages being unambiguous on their own. $\endgroup$ Sep 8, 2016 at 18:24

2 Answers 2


Either you make sure that you use separate key (pairs) for each different purposes, or you simply include all possible context in the signature, including the entities.

So sign a message consisting of "Allice: Bob, do you love me? Bob: yes".

Note that it is not required to send all the data together with the signature, as long as you can regenerate the input.

Note that low entropy is not really the issue in your question. It's the amount of context that you sign. Low entropy is mainly a problem for random number generation and the functions that rely on it, such as the key pairs themselves.

  • $\begingroup$ Removed TLS example as the MAC is used over the messages rather than the signature; the signature is calculated over a restricted structure with client & server randoms. If somebody has a better example... I thought about XML-sig but that's not so easy to explain. $\endgroup$
    – Maarten Bodewes
    Sep 8, 2016 at 21:21

The problem is not really the fact that the message is low-entropy, but the fact that it's context-dependent.

How do I love thee? Let me count the ways…

Plenty of entropy, but still mostly the same problem as “yes”/“no”.

The way to solve this is to include all the relevant context in what is signed. A good protocol with integrity protection includes the following in each signed (or MACed) message:

  • “This is a message in protocol X”;
  • “This is a message from Alice”;
  • “This is a message to Bob”;
  • “This is a reply to message 7”;
  • “This is a reply to the message with the signature S7”;
  • the payload.

The first four may be omitted from the plaintext that gets signed because including S7 indirectly causes the signature of the new message to authenticate the whole history of the conversation, all the way to message 0 which does need to establish the instance of the protocol. With such a chain of signatures, verifying the authenticity of the latest message ensures the authenticity of the whole conversation.

Thus, whether directly or indirectly, authenticating a message verifies the context of that message.


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.