What do the signature security abbreviations like EUF-CMA mean?

Question

From time to time, one stumbles across formal security definitions. This includes security definitions for signature schemes.

The most common ones are the *UF-* ones, advertising security against specific classes of attackers. Now these notions may not be that well-understood by many people so I ask hereby for a canonical answer, that explains what the following security notions mean. A (simple) description of the formal attack scenario is preferred.

Please don't restrict the answer to "you can chose this and if you can break it with this it isn't EUF-CMA". Please at least outline the formal attack (like f.ex. generate a new signature).

The following list is in order of strength for the same suffix (x)or prefix:

• UUF-KMA
• SUF-KMA
• EUF-KMA
• UUF-CMA
• SUF-CMA
• EUF-CMA

Answer 1

Notation.

Sets are represented using the calligraphic font and algorithms using the straight font. Throughout, $\Sigma:=(\mathsf{K},\mathsf{S},\mathsf{V})$ denotes a signature scheme on a key-space $\mathcal{K}$, message-space $\mathcal{M}$ and signature-space $\mathcal{S}$. Since only a single key-pair is involved in the discussion, to avoid cluttering, let's drop the security parameter, public key and secret key when invoking $\mathsf{S}$; similarly, let's drop the security parameter and public key while invoking $\mathsf{V}$. That is, we regard: $\mathsf{S}:\mathcal{M}\rightarrow\mathcal{S}$ and $\mathsf{V}:\mathcal{S}\times\mathcal{M}\rightarrow\{0,1\}$.

Security modelling

As in the case of encryption schemes, security is modelled for a signature scheme $\Sigma$ using a game between a challenger and an adversary $\mathsf{A}$ (a polynomial-time probabilistic machine). The game models a possible scenario where $\mathsf{A}$ tries to break $\Sigma$ using an attack when the challenger is using the scheme $\Sigma$. $\Sigma$ is said to be secure in the $\mathtt{break}$-$\mathtt{attack}$-model (i.e., $\mathtt{break}$-$\mathtt{attack}$-secure) if it is "difficult for any $\mathsf{A}$'' to $\mathtt{break}$ $\Sigma$ under $\mathtt{attack}$ (the precise definition is given in the end). Hence, for the case of signature schemes $\mathtt{break}\in${UF,SF,EF} and $\mathtt{attack}\in${KOA,CMA,KMA}---it is possible to consider any combination of these.

For ease of exposition, let's start with the description of the "weakest" model, called universal forgery (UF) under key-only attack (KOA).

1: UF-KOA$^{\mathsf{A}}_\Sigma(1^n)$	Universal Forgery (UF) under Key-Only Attack (KOA)

1. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

2. a. Challenge $\mathsf{A}$ on an arbitrary message $m^*\in\mathcal{M}$

   b. Receive as response (to the challenge) a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

That is, in the UF-KOA model, the adversary has forged on a message chosen by the challenger (i.e., a universal forgery) given just the public key (i.e., the key-only attack). In this model, the adversary has the hardest-possible task: it is given only the bare minimum required to forge---i.e., the public key---and has no choice on which message to forge on.

In practice, an adversary could have means to obtain more information than this---e.g., it might procure, through some channel, a signature issued by the signer. This is not captured by the UF-KOA model and hence the reason to deem it weak. There are two ways to strengthen it: one, we could make the task of the adversary easier (e.g., let it forge on a message of its own choice); and/or two, we could provide it more information (e.g., give it signatures on messages of its choice). Let's now take a look at a model, called UF under known-message attack (KMA), that does the latter.

2: UF-KMA$^{\mathsf{A}}_\Sigma(1^n)$	Universal Forgery (UF) under Known-Message Attack (KMA)

1. a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

   b. Sample $q=q(n)$ arbitrary messages $m_1,...,m_q\in\mathcal{M}$, and generate signatures $\sigma_i\leftarrow\mathsf{S}(m_i)$, $1\le i \le q$

2. a. Send the set $\{(m_1,\sigma_1),...,(m_q,\sigma_q)\}$ to $\mathsf{A}(1^n)$, and challenge it on an arbitrary message $m^*\not\in \{m_1,...,m_q\}$

   b. Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

Although $\mathsf{A}$ has to still produce a universal forgery, it now gets---unlike in the UF-KOA model---a bunch of signatures on messages it knows (the known-message attack). The model can be further strengthened by allowing $\mathsf{A}$ to query and obtain signatures on messages of its choice. This yields the model, given below, called UF under chosen-message attack (CMA).

3: UF-CMA$^{\mathsf{A}}_\Sigma(1^n)$	Universal Forgery (UF) under Chosen-Message Attack (CMA)

1. a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

   b. Initialise a set $\mathcal{M}'=\emptyset$.

2. If $\mathsf{A}$ queries for signature on a message $m\in\mathcal{M}$, responds with $\mathsf{S}(m)$, and add $m$ to $\mathcal{M}'$

3. a. Challenge $\mathsf{A}$ on an arbitrary message $m^*\not\in\mathcal{M}'$

   b. Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

Next, let's look at strengthening the model from the second aspect, i.e., by weakening the notion of what it means for an adversary to break the signature scheme. We go from universal forgery, which was discussed in the first experiment, to selective forgery (SF) and finally to existential forgery (EF) in the setting of KOA.

4: SF-KOA$^{\mathsf{A}}_\Sigma(1^n)$	Selective Forgery (SF) under Key-Only Attack (KOA)

1. Receive from $\mathcal{A}$ the commitment $m^*\in\mathcal{M}$: $\mathsf{A}$ has to forge on $m^*$ in the end

2. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

3. Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

Note that although $\mathcal{A}$ has to a priori commit to the message it forges on, it still has more freedom than in the UF-KOA game---for EF-KOA, this restriction is also lifted.

5: EF-KOA$^{\mathsf{A}}_\Sigma(1^n)$	Existential Forgery (EF) under Key-Only Attack (KOA)

1. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

2. Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

In a similar vein, it is possible to define the models $\mathtt{break}$-$\mathtt{attack}$ for $\mathtt{break}\in${SF,EF} and $\mathtt{attack}\in${KMA,CMA}. The strongest model of the lot---i.e., EF-CMA---is defined below as it is considered to be the model on which security of signature schemes should be based on.

6: EF-CMA$^{\mathsf{A}}_\Sigma(1^n)$	Existential Forgery (EF) under Chosen-Message Attack (CMA)

1. a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

   b. Initialise a set $\mathcal{M}'=\emptyset$.

2. If $\mathsf{A}$ queries for signature on a message $m\in\mathcal{M}$, respond with $\mathsf{S}(m)$, and add $m$ to $\mathcal{M}'$

3. Receive as output from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$ and $m^*\not\in\mathcal{M}'$

That is, in the EF-CMA-model, the adversary can obtain a bunch of signatures on messages it chooses adaptively, and, in the end, can forge on any fresh message. A stronger version of this definition ---called the strong EF-CMA (sEF-CMA)---is also considered desirable.

7: sEF-CMA$^{\mathsf{A}}_\Sigma(1^n)$	strong Existential Forgery (sEF) under Chosen-Message Attack (CMA)

1. a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

   b. Initialise a set $\mathcal{M}'=\emptyset$.

2. If $\mathsf{A}$ queries for signature on a message $m\in\mathcal{M}$, respond with $\sigma=\mathsf{S}(m)$, and add $(m,\sigma)$ to $\mathcal{M}'$

3. Receive as output from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$ and $(m^*,\sigma^*)\not\in\mathcal{M}'$

That is, the adversary can forge on a message on which it queried for a signature as long as the forgery is different from the one it received as a response to the query (i.e. a strong existential forgery).

P.S. (post scriptum)

1. Definition. A signature scheme is said to be $\mathtt{break}$-$\mathtt{attack}$-secure if for all probabilistic polynomial-time adversaries $\mathsf{A}$ $$\Pr[\mathsf{A}\ wins\ \mathtt{break}-\mathtt{attack}_\Sigma^{\mathsf{A}}(1^n)]=negl(n).$$ where $\mathtt{break}\in${UF,SF,EF} and $\mathtt{attack}\in${KOA,CMA,KMA}.

2. Although only signature schemes are discussed, the definitions can be easily adapted for message-authentication codes (MACs). In particular:

   1. As the key generation algorithm generates only the symmetric key $k$, in Step 1 of the security models, there no key to be handed over to $\mathsf{A}$. As a consequence, UF-KOA is difficult in an information-theoretic sense.

   2. Instead of querying for a signature on messages, $\mathsf{A}$ queries for tags.

3. There are other variants of attacks and breaks --- see [GMR], for example.

References

• [GMR88]: Goldwasser, Micali and Rivest. A digital signature scheme secure against adaptive chosen-message attacks. (PDF)
• [BN00] : Mihir Bellare and Chanathip Namprempre. Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm PDF