# How can we prevent duplicate key attacks on digital signatures

A limitation digital signatures is that for a given signature σ of a message m corresponding to a public key pk, an adversary could generate a pk', sk' that produces a signature σ' for m, such that σ' = σ. How can we create a signing function and verification function that is resistant to this attack?

• Actually, your question lacks an important aspect in cryptography; What is the power of the adversary? polynomially bounded or not bounded? Commented Apr 7, 2022 at 19:37

DSKS attacks belong to a class of attacks on signature schemes that break « exclusive ownership ». A property that is not guaranteed by standard EUF-CMA security.

One solution to this is the BUFF construction. It is very much similar to what Boneh-Shoup recommends. In short, given a signature key pair $$(sk,pk)$$ to sign $$m$$, first compute $$h = H(m,pk)$$, then $$\sigma = Sig(sk,h)$$. The signature is $$(h, \sigma)$$. Verification compares the hashes and validates the signature.

The BUFF construction offers more features than exclusive ownership; the paper talks about them.

• Interesting, but it increases the signature size. Aren't $\mathsf{Sig}(sk,(pk\mathbin\|m))$ or $\mathsf{Sig}(sk,(pk\mathbin\|H(m)))$ fine against DSKS attacks, with no size penalty?
– fgrieu
Commented Apr 7, 2022 at 15:52
• @fgrieu, yeah that works too. I guess I failed to convey that this was an was an alternative with further features. Commented Apr 7, 2022 at 16:30
• Actually, this still doesn't prevent the attacker as OP requested since the OP did not restrict the power of the adversary. In this case, they still can find such $(pk,pk)$ pair if possible. Commented Apr 7, 2022 at 19:04
• @kelalaka, it’s true that an unbounded adversary can recover the key pair itself. I think it’s fair to interpret the question as considering bounded adversaires as seems appropriate to signatures and DSKS attacks. Commented Apr 7, 2022 at 20:45

I think that kind of attack is only possible when you have a "formula" for calculating signature from private key and message hash that can be inverted - choose a signature and a message and calculate the private key. Various variants of Schnoor's and ElGamel signature schemes has this property.

The easiest solution I can think of is to use a hash-based signature such as some variant of the XMSS, LMS, and SPHINCS signature scheme.

According to Dan Boneh and Victor Shoup's A Graduate Course in Applied Cryptography:

it is quite easy to immunize a signature scheme against DSKS attacks: the signer simply attaches his or her public key to the message before signing the message. The verifier does the same before verifying the signature. This way, the signing public key is authenticated along with the message (see Exercise 13.5). Attaching the public key to the message prior to signing is good practice and is recommended in many real-world applications.