Cryptography
- signature entropy probabilistic-encryption
- Updated Tue, 28 Jun 2022 10:16:09 GMT
-
How to sign low-entropy messages?
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...
Solution
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.