Provable security notes / X

Signatures, MACs, and unforgeability

Authentication is not confidentiality: the adversary wins by producing a valid object it should not be able to produce.

Signature and MAC security is expressed as a forgery game. The adversary is allowed to see authentic outputs, often adaptively, and must produce a new valid one.

EUF-CMA

For a signature scheme

\[\Sigma=(\mathsf{KeyGen},\mathsf{Sign},\mathsf{Verify}),\]

existential unforgeability under chosen-message attack gives the adversary signing-oracle access. After queries \(m_1,\ldots,m_q\), it outputs \((m^*,\sigma^*)\) and wins if

\[\mathsf{Verify}_{pk}(m^*,\sigma^*)=1 \quad\text{and}\quad m^*\notin\{m_1,\ldots,m_q\}.\]

Strong unforgeability also treats a new signature on an old message as a forgery.

EUF-CMA game between \(\mathcal C\) and \(\mathcal A\)

  1. \(\mathcal C\) runs \((pk,sk)\leftarrow\mathsf{KeyGen}(1^\lambda)\) and sends \(pk\) to \(\mathcal A\).
  2. \(\mathcal A\) adaptively queries a signing oracle. On query \(m_i\), \(\mathcal C\) returns \(\sigma_i\leftarrow\mathsf{Sign}_{sk}(m_i)\) and records \(m_i\).
  3. After any number of allowed signing queries, \(\mathcal A\) outputs \((m^*,\sigma^*)\).
  4. \(\mathcal A\) wins if \(\mathsf{Verify}_{pk}(m^*,\sigma^*)=1\) and \(m^*\) was never submitted to the signing oracle.

For SUF-CMA, the final pair \((m^*,\sigma^*)\) must be new; a new valid signature on an old message also counts as a win.

Textbook RSA signatures

Challenger \(\mathcal C\)
Adversary \(\mathcal A\)
\((pk,sk)\leftarrow\mathsf{KeyGen}(1^\lambda),\quad Q\leftarrow\emptyset\)
\((pk,\mathcal O_{\mathsf{Sign}})\)
\(m_i\leftarrow\mathcal A^{\mathcal O_{\mathsf{Sign}}}(pk,\mathsf T_{i-1})\)
\(m_i\)
\(\sigma_i\leftarrow\mathsf{Sign}_{sk}(m_i),\quad Q\leftarrow Q\cup\{m_i\}\)
\(\sigma_i\)
\((m^*,\sigma^*)\leftarrow\mathcal A^{\mathcal O_{\mathsf{Sign}}}(pk,\mathsf T_q)\)
\((m^*,\sigma^*)\)
\(\mathsf{EUF\text{-}CMA}^{\mathcal A}_{\Sigma}(1^\lambda):=\mathbf 1[\mathsf{Verify}_{pk}(m^*,\sigma^*)=1\land m^*\notin Q]\)

Textbook RSA signs by

\[\sigma=m^d\bmod N.\]

If \(\sigma_1\) signs \(m_1\) and \(\sigma_2\) signs \(m_2\), then

\[(\sigma_1\sigma_2)^e\equiv m_1m_2\pmod N.\]

This is a valid signature on a related message. In an EUF-CMA attack the related message must also be new, so the attacker chooses queried messages so that \(m_1m_2\) was not itself submitted to the signing oracle.

Hash-and-sign proof pressure

Hash-and-sign blocks the direct multiplicative relation by signing an encoded representative such as \(H(m)\). In the random oracle model, a reduction may program the hash value of the eventual forgery message. But it must still answer signing queries. If it guesses the wrong hash query or the adversary asks for a signature on the programmed point, the simulation may abort.

This is why signature bounds often contain hash-query and signing-query losses.

MACs

A MAC has a secret key shared by sender and receiver:

\[\tau\leftarrow\mathsf{Tag}_K(m), \qquad \mathsf{Verify}_K(m,\tau)\in\{0,1\}.\]

A MAC forgery game is analogous to EUF-CMA, but the adversary interacts with tagging and verification oracles under a symmetric key.

MAC unforgeability game

  1. \(\mathcal C\) samples \(K\leftarrow\mathsf{KeyGen}(1^\lambda)\).
  2. \(\mathcal A\) receives oracle access to \(O_{\mathsf{Tag}}(m)=\mathsf{Tag}_K(m)\). Some formulations also give a verification oracle.
  3. \(\mathcal C\) records every message submitted to the tag oracle.
  4. \(\mathcal A\) outputs \((m^*,\tau^*)\).
  5. \(\mathcal A\) wins if \(\mathsf{Verify}_K(m^*,\tau^*)=1\) and \(m^*\) was not previously tagged.

If a verification oracle is present, the game must state whether verification queries on previously tagged messages are ignored, answered, or counted separately. These details affect online guessing bounds.

Challenger \(\mathcal C\)
Adversary \(\mathcal A\)
\(K\leftarrow\mathsf{KeyGen}(1^\lambda),\quad Q\leftarrow\emptyset\)
\((\mathcal O_{\mathsf{Tag}},\mathcal O_{\mathsf{Verify}})\)
\(m_i\leftarrow\mathcal A^{\mathcal O_{\mathsf{Tag}},\mathcal O_{\mathsf{Verify}}}(\mathsf T_{i-1})\)
\(m_i\)
\(\tau_i\leftarrow\mathsf{Tag}_{K}(m_i),\quad Q\leftarrow Q\cup\{m_i\}\)
\(\tau_i\)
\((m^*,\tau^*)\leftarrow\mathcal A^{\mathcal O_{\mathsf{Tag}},\mathcal O_{\mathsf{Verify}}}(\mathsf T_q)\)
\((m^*,\tau^*)\)
\(\mathsf{UF\text{-}CMA}^{\mathcal A}_{\mathsf{MAC}}(1^\lambda):=\mathbf 1[\mathsf{Verify}_{K}(m^*,\tau^*)=1\land m^*\notin Q]\)

Tag length and verification queries

If the only attack is tag guessing and the tag has \(t\) bits, then \(q_v\) verification attempts give

\[\Pr[\mathsf{forge}]\le q_v2^{-t}.\]

This term is small only relative to the allowed verification budget. Online systems must count failed attempts, not only key length.

What to check

For authentication the central questions are: what counts as new, which oracle queries are allowed, whether messages are structured transcripts rather than raw strings, and whether the implementation compares tags and signatures without leaking timing information.