[cryptography] Duplicate signature attacks (was: short signature scheme?)

David-Sarah Hopwood david-sarah at jacaranda.org
Tue Nov 9 21:04:22 EST 2010

On 2010-11-10 00:26, Jonathan Katz wrote:
> - Some people mentioned that 2^k security requires signatures of length 2k,
> presumably by analogy with hash functions.

To be precise, security against a "duplicate signature attack" (as defined
in <http://citeseer.ist.psu.edu/viewdoc/summary?doi=>) requires

The reason is just the obvious generic birthday attack: there are expected to
be collisions once on the order of 2^k signatures of length 2k bits have been
generated. (It does not matter that the signing function is randomized; the
success probability in finding a collision can be higher than for a
deterministic random oracle, but cannot be lower.)

> Although I see some intuition for
> thinking this, I don't see formally why this must be the case. (In particular,
> I don't see why it's an issue if two legitimately issued signatures happen to
> be the same, as long as they couldn't have been forged in advance.)

It's not a problem unless you're using a protocol that assumes that a
signature must be associated with a particular message.

For example, suppose that you have a system that uses countersigned
signatures to record that a piece of code has passed some verification
procedure. That is, the author of a piece of code signs it, presents it
to a verifier, and if the verifier is satisfied then they countersign the
signature. Later, the code is presented together with the countersigned
signature to another party, who will run it if both signatures are valid.

There is an implicit assumption here that the author's signature is valid
only for one piece of code, which is correct for some signature schemes
and not for others. You could argue quite convincingly that this is a
protocol design error (i.e. the verifier's signature should also have been
on the code itself), but it's not a totally implausible error.

David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20101110/44b5889c/attachment.asc>

More information about the cryptography mailing list