# Relation between attack and attack model for signatures

I would like to know: What is the relationship between an attack and an attack model.

For example, let $\Pi$ be the Lamport signature scheme. This signature has it's security based on the 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 a chosen-message-attack.

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

-

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).

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 '14 at 21:41