In the definition of existential unforgeability, there is no detail about the following questions.

In general, can we suppose that a signer is also a possible adversary ? When generating a signature, can we suppose that the signer behaves well ?

More precisely, suppose that a signer is able to generate a signature which is valid for an other document of his choice. Despite this, for a correctly generated signature, suppose that the signature scheme used is secure when considering an adversary which is not the signer, that is to say, this adversary is unable to generate a signature for any other document. Is this signature scheme really considered secure ?

What are the standard (conventional) hypothesis about that ?

I update in reaction to the comment:

In fact,

  1. if the signer behaves well, then the signature is unforgeable (for the signer or any adversary which is not the signer).
  2. if the signer misbehaves, then the signature is forgeable (for the signer, without using the key, and for any adversary).

Is this king of scheme considered secure in the sense of existential forgeability ? can we suppose that the signer behaves well ?

  • $\begingroup$ It depends on what you mean. If the secret key is necessary to find the second document, then it is fine. If you know the secret key, you can already sign anything you want. However, if it is possible to find the second document given only the original message, signature and public key, then the scheme is trivially forgeable. $\endgroup$ – Maeher Feb 10 '14 at 19:33
  • $\begingroup$ Thank you @Maeher. The secret key is \textbf{not} necessary to find the second document. $\endgroup$ – Dingo13 Feb 10 '14 at 19:43
  • 1
    $\begingroup$ @Dingo13 what do you mean by "misbehaves"? Btw. didn't you ask a quite similar question already? $\endgroup$ – DrLecter Feb 10 '14 at 20:02
  • 3
    $\begingroup$ There are versions of signatures in which the signer is a possible adversary, although that property is not called unforgeability. $\:$ See fail-stop signatures, undeniable signatures, and unconditionally secure signatures. $\;\;\;$ $\endgroup$ – user991 Feb 10 '14 at 22:19
  • 1
    $\begingroup$ @fgrieu this seems only to be a desirable property in some scenarios as Ricky pointed out. I am not aware of any rigorous formal definition of such a property for conventional digital signatures. At least for plain hash-then-sign signatures such a signer who efficiently can do this, can be used as oracle to break the used hash function. $\endgroup$ – DrLecter Feb 13 '14 at 8:36

The standard definition of existential forgery allows the adversary to ask and obtain the signature of any message she wants, and claim success if she can exhibit (with sizable odds) any acceptable (message, signature) pair, for any message for which she did not ask signature.

Update: There is also strong existential unforgeability, where the adversary should not be able to exhibit any acceptable (message, signature) pair for which she did not obtain that signature by asking for the signature of that message. For a use case making the headlines where that strong makes a huge difference, see these links.

Note: in a signature scheme with message recovery, any fraction of the message embedded in the signature needs not be exhibited by the adversary, and is as obtained by the verifier for the purpose of comparison to what the adversary submitted.

Corrected: If "a signer is able to generate a signature which is valid for an other document (that is, message) of his choice", then that scheme is vulnerable to existential forgery. The adversary obtains the signature of the first message, submits that signature unchanged together with the second message, and wins with 100% odds the existential forgery game. Oh no, only the signer could do this, using access to the private key!

Existential forgery is the strongest a strong theoretical criteria for signature. However, it assumes that the signer does not misbehave beside allowing the signature of arbitrary messages; in particular, it is assumed that the signer (or the Smart Card used for signature) does not leak the private key only uses the private key as prescribed, and properly implements every step in the algorithm, like generating truly random numbers.

Update: This spot-on comment by Ricky Demer gives names of security criteria for signatures protected from some attacks by the signer / private key holder.

Update: as pointed by DrLecter in a comment, the standard way to model the signer for a scheme secure against existential forgery (we also say: secure under chosen message attack) is as an oracle that accepts any message and outputs its signature. That oracle is assumed to implement the signature scheme exactly as specified. For more details, I refer to DrLecter's thesaurus of signature security models.

| improve this answer | |
  • 1
    $\begingroup$ By modeling the signer as a signing oracle which can be queried by the adversary. $\endgroup$ – DrLecter Feb 10 '14 at 20:13
  • 1
    $\begingroup$ @Dingo13 that depends on the model you are working in. if you consider existential unforgeability against (adaptively) chosen message attacks (the standard and strongest security notion), then the adversary can choose an arbitrary message of its choice and submit it to the oracle. if you consider existential unforgeability against random message attacks, then the oracle randomly (typically unfiformly at random) samples a message for the adversary, i.e., the message can not be controlled by the adversary. In any case, the oracle returns an honestly computed signature for the respective message. $\endgroup$ – DrLecter Feb 10 '14 at 20:21
  • 1
    $\begingroup$ cont. you may also look at this related answer which makes the attack/model stuff more explicit. $\endgroup$ – DrLecter Feb 10 '14 at 20:27
  • 1
    $\begingroup$ "In any case, the oracle returns an honestly computed signature for the respective message." If the signing oracle seems perfect, in practice, if the signer has to choose pseudorandom numbers, he could choose numbers of his choice, and in this case the scheme is no secure. Not ? What kind of model I have to choose in this case ? $\endgroup$ – Dingo13 Feb 10 '14 at 20:28
  • 1
    $\begingroup$ @Dingo If you take ElGamal or Schnorr signatures, producing two signatures with respect to the same randomness for different messages allows to extract the secret signing key. You are right, that is a problem, but it is not covered by any unforgeability notion. $\endgroup$ – DrLecter Feb 10 '14 at 20:34

As already discussed by @fgrieu in his answer and myself in the comments of your question and his answer, the standard notion of security of digital signature schemes, namely (strong) existential unforgeability under adaptively chosen message attacks (UF-CMA), does not cover the case you are concerned about.

At least for hash-then-sign signatures built upon a trapdoor permutation (as RSA), such a signer who efficiently can do this, can be used as an oracle to break the collision resistance of the used hash function.

Nevertheless, it kept me thinking if there is a standard notion which could be applied to any signature scheme and if this has been considered somewhere.

In the Crypto'02 paper Flaws in Applying Proof Methodologies to Signature Schemes, Stern et al. introduce a property which covers exactly the aspect you are targeting in your question (however this is not a commonly investigated property in the design of signature schemes).

Essentially, it is a formalization of the non-repudiation property, which requires that an adversary that is in possession of the secret signing key (and potentially is also able to influence the key generation process) will not be able to produce two messages with the same signature, a so called duplicate signature in their language. Consequently, this attack indeed considers the signer as an adversary.

In Section 4 of the paper, they provide an attack on ECDSA which produces such a duplicate signature, i.e., a signature valid for two distinct messages. if the adversary can control the key generation process used to produce the actual signing key.

Just as a side note, Stern et al. in the same paper also introduce a property denoted as malleability, which is today known strong unforgeability, i.e., it ensures that an adversary (holding the public key) cannot even produce a new signature for a previously obtained signed message. This notion for instance cannot be satisfied by randomizable signatures (such as Camenisch Lysyanskaya signatures), which allow to transform a signature $\sigma$ for some message $m$ into another signature $\sigma'\neq \sigma$ for the same $m$ without requiring the secret signing key.

| improve this answer | |
  • $\begingroup$ Thanks @DrLecter, this notion of (non ?)-malleability from Stern (also known strong unforgeability) is the same notion as UF-CMA ? $\endgroup$ – Dingo13 Feb 27 '14 at 8:48
  • $\begingroup$ @Dingo13 The standard UF-CMA notion could be called weak unforgeability, as the attackers goal is to output a signature for a message for which he has not already seen a signature. In strong unforgeability, the adversary already suceeds when producing a signature that has not been produced before (this forgery can be for a message for which he has already seen a signature before). So it is a stronger notion as the usual UF-CMA security notion. $\endgroup$ – DrLecter Feb 27 '14 at 8:51
  • $\begingroup$ Thanks @DrLecter, the term strong unforgeability is quite recent... This notion of "non-malleability"(="strong UF-CMA") is always valid in secret key settings ? $\endgroup$ – Dingo13 Feb 27 '14 at 8:58
  • $\begingroup$ @Dingo13 yes. What do you mean by "same secret key settings"? $\endgroup$ – DrLecter Feb 27 '14 at 8:59
  • $\begingroup$ I mean that for secret key cryptography the notions used are the same, and we have always "non-malleability"="strong UF-CMA" $\endgroup$ – Dingo13 Feb 27 '14 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.