Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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

Therefore I briefly review the security models for digital signature schemes.

Goal of an adversary:

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 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 signature for a message, which has not been signed yet (the adversary typical has no control over the choice of this forged message).

  • Strong existential forgery: The adversary is able to produce a valid signature that has not yet been produced by the singing algorithm. In contrast to weak existential unforgeability, the message corresponding to the forged signature may already have been signed (but it produced a signature different from the forged signature).

Power of an adversary:

After defining the goals, we will take a closer look at the adversary and define his ability or power. 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.
  • 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 resp. 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.

Example:

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

Coming back to your question:

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

Hope this helps.

share|improve this answer
1  
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 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 :) –  DrLecter Feb 11 at 21:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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