# Relation between attack and attack model for signatures

What is the relationship between an attack and an attack model?

For example, let $$\Pi$$ be the Lamport signature scheme. This signature has its security based on any one-way function. The Grover algorithm, an attack, inverts this function with complexity $$\mathrm{O}(2^{n/3})$$. Furthermore, there are algorithms that try to forge a signature, known as adversaries. Depending on the way they act, we choose an attack model such as the chosen-message-attack model.

Is there any relationship between this model and the attack described above?

• It is not entirely clear what you mean. Could you please clarify it a bit? In the last sentence you say "this model," which refers to the chosen-message-attack model. You refer to an attack, with must be some party using Grover's algorithm. So your question must be: Is there any relationship between the chosen-message-attack model and some party using Grover's algorithm. Is that a correct characterization of your inquiry? Thank you. Jan 30, 2021 at 13:01

I hope I got your point and try to answer your question. Actually, if I understand you right, then what you call an attack actually means an adversary acting in a specific attack model.

To clarify this, we need to review the security models for digital signature schemes and when we have discussed this we can clarify issues. Basically, we have to discuss what an adversary tries to achieve and which environment is given to him.

We start by discussing the goals of an adversary beginning with the strongest and ending up with the weakest attack goal.

• Total break: The adversary is able to obtain the secret signing key. Thus, he is then able to impersonate the signer by signing arbitrary messages in the name of the signer.

• Selective forgery: The adversary is able to produce valid signatures for some selected messages or a particular class of messages.

• (Weak) Existential forgery: The adversary is able to produce at least one valid signature for a message, for which he has not been given a signature yet (the adversary typically has no control over the choice of this forged message).

• Strong existential forgery: The adversary is able to produce a valid signature different from any signature he has seen. In contrast to weak existential unforgeability, the message corresponding to the forged signature may already have been signed. Think of a second valid signature for a message that has already been signed (signatures that are publicly re-randomizable - such as Camenisch Lysyanskaya signatures - can never achieve this level).

After defining the goals, we will take a closer look at the adversary and define his ability or power. This basically defines the environment he is acting in. Thereby, we start with the weakest and end up with the strongest one.

• Key-only attack: The adversary solely knows the public-key corresponding to the secret signing key of the signer.

• Known-message attack: The adversary has additionally access to a list of message-signature pairs from the signer, whereas he has no influence on the choice of the messages.

• Random-message attack: The adversary can obtain signatures for message, whereas the adversary has no control how the messages are chosen (they are randomly chosen by the signer).
• Chosen-message attack: The adversary has access to a list of message-signature pairs, whereas the messages were chosen by the adversary before attempting to break the signature scheme.
• Adaptively chosen-message attack: The adversary is able to adaptively choose the messages which are signed by the signer during the attack. Thus, he may choose messages depending on the public-key of the signer and also previous messages or signatures, which were obtained during the attack. In other words, the adversary can use the signer as a signing black-box (oracle) throughout the entire attack.

Security as a combination of goals and power:

Now, the combination of the goal and the power of an adversary gives the type of security of a specific scheme. In general, a digital signature scheme is said to be secure if the most powerful adversary cannot even achieve the weakest goal.

Secure Signatures:

In the notation introduced above, a digital signature scheme is considered secure if it is existentially unforgeable under adaptively chosen-message attacks. Typically, here, existentially unforgeable refers to weak existential unforgeability (but there are also some signature schemes whose security is proved with respect to strong existential unforgeability).

Actually, what you describe as an attack, is a total break under a key-only attack. Or you may see it as an adversary mounting an attack (key-only) with this goal (total break).

• Sometime, the adversary's goal is, given a signature, to produce a different signature of the same message (say, also given). E.g. in RSA, perhaps $s+N$ is just as valid as $s$ (sometime they have the same bit length). Or simply adding a leading 0 could do. Or changing uppercase to lowercase in hexadecimal. Or... Such mundane things become a real issue in some protocols, where signatures get re-signed, or hashed, see this. That seems to missing in your interesting thesaurus.
– fgrieu
Feb 11, 2014 at 21:41
• @fgrieu yes, of course, this is what is called strong existential unforgeability. Thanks, I will add this one and also take random message attacks into account :) Feb 11, 2014 at 21:43