Signing different types of messages with the same asymmetric key

Question

I want to be able to sign different types of messages with the same asymmetric key. (For completeness, I am using Ed25519 for my signatures).

Why do I want to do this?

The same key is used to sign different types of messages. If I didn't use some method to differentiate between message types, an attacker might be able to ask me to sign one message of one type, and then use it as a message of another type.

Example crude solution

For a quick prototype, I used the following crude method.

To sign a message of type 1:

$\operatorname{Sign}[\text{key}](\text{"type1" }||\text{ message}_1)$

To sign a message of type 2:

$\operatorname{Sign}[\text{key}](\text{"type2" }||\text{ message}_2)$

I have a feeling that this is not the best way to get good separation between message types. This is especially true if one type string is a substring of another type string. I remember for example, that HMAC and hkdf use a more sophisticated mechanism (They don't just concatenate).

I don't want to reinvent the wheel here. Is there a common practice to solve this problem?

Answer 1

As long as the prefixes type1 type2 etc.. are distinct, of equal size, and consistently inserted before everything signed, what's proposed is perfectly fine, and common practice.

---

That prefixes are distinct and of equal size is a simple and foolproof (thus good) way to implement the necessary and sufficient requirement: no prefix shall be the start of another prefix.

If for some reason prefixes must be of different size, possible conventions insuring that this requirement is met include:

• The size in byte of the prefix is before the prefix, on 1 byte (Pascal string convention).
• A special terminating byte is at the end of all prefixes, and not used elsewhere in a prefix. Common choices include the byte 0x00 (C string convention) or a separator like :
• Using the hash (SHA-512/256) of distinct string prefixes, as proposed in comment. Since that's constant-size, the requirement boils down to using string prefixes that do not collide, and we do not even know how to make otherwise.

At the upper end of the complexity spectrum: everything signed could be per an appropriate ASN.1 grammar. Watch out for the complexity degenerating into interoperability issues, or even exploitable flaws.