Signature over MAC value for a random key

Question

Would it be possible to create a signature scheme like this: $ \DeclareMathOperator{Gen}{Gen_{\Mac}} \DeclareMathOperator{Mac}{Mac} \DeclareMathOperator{Sign}{Sign} \DeclareMathOperator{F}{F} \DeclareMathOperator{H}{H} $

$$k_d = \Gen$$ $$m_d = \Mac(k_d, M)$$ $$S = \big(k_d, \Sign(K_{priv}, m_d)\big)$$

So instead of a hash, you'd use a random key.

I know that $$H = \big(k_d, \Mac(k_d, M)\big)$$ is not necessarily secure as you'd give the adversary the ability to choose any key. However, in this case the result is signed as well.

If it isn't secure, are there ways to make it secure? For instance, I could imagine RSA that contains the $k_d$ and recovers it using message recovery. Or ECDSA where an additional hash is calculated over $k_d$ and $m_d$.

Primary goal is to make a faster signature generation by replacing a slower hash with a possible faster MAC such as GMAC.

Answer 1

Would it be possible to create a signature scheme like this:

As I understand it, your proposal is that the signature consists of the MAC key, along with the signed MAC value of the message.

In general, this would not be secure, for two reasons:

• For many MACs, it is not difficult, if you know the key, to find a second message with the same MAC as an existing one.

• It is not part of the MAC assumptions that it is difficult to find a second key and message pair that MACs to a specific value.

MACs that would not be secure due to these properties include CMAC and GMAC.

If it isn't secure, are there ways to make it secure?

Well, if you limited yourself to, say, HMAC or KMAC, it would be secure (as long as you didn't truncate the MAC excessively); however that's largely because these two MACs are largely hashes (with some key bits sprinkled in), and signing a hash is safe. These two MACs are, in fact, collision resistant, even if you select the key (which is a rather stronger assumption than is assumed by the standard MAC security properties).

On the other hand, if the goal is to use a faster MAC rather than a slower hash, this suggestion would help you a great deal. The problem, in this case, with GMAC, is that if you know the key, GMAC doesn't actually give you any cryptographical properties; creating first preimages (for example) is actually quite easy...