Notes - Computer Security MT24, Digital signatures

Created: November 04, 2024
Updated: January 09, 2025

Flashcards

What’s the relationship between MACs and digital signatures?
  • MACs: symmetric, require just one key $k$,
  • Digital signatures: asymmetric, require a public key and a private key.

@Define a digital signature.

Suppose:

  • $\mathcal K$ is a secret keyspace
  • $\mathcal K’$ is a public keyspace
  • $\mathcal S$ is a set of possible signatures
  • There is a method of generating secret-public key pairs $\langle k _ s, k _ v \rangle \in \mathcal K \times \mathcal K’$, where:
    • $k _ s$ is the “signing key”
    • $k _ v$ is the “verification key”

Then there are functions

\[\mathsf{SIGN} : \mathcal K \times \\{0, 1\\}^\ast \to \mathcal S\]

and

\[\mathsf{VER} : \mathcal K' \times \\{0, 1\\}^\ast \times \mathcal S \to \\{\mathbf{true}, \mathbf{false}\\}\]

with the property that

\[\mathsf{VER} _ {k _ v}(m', \mathsf{SIGN} _ {k _ s}(m)) = \begin{cases} \mathbf{true} &\text{if } m = m' \text{ and } \langle k_s, k_v \rangle \text{ are a secret-public key pair} \\\\ \mathbf{false} &\text{almost certainly otherwise} \end{cases}\]

@Define a key only attack (KOA) on digital signatures.

The attacker only has knowledge of the verification key $k _ v$.

@Define a known message attack (KMA) on digitial signatures.

The attacker knows $k _ v$ and a number of message-signature pairs $m _ i$ and $\mathsf{SIGN} _ {k _ s}(m _ i)$.

@Define a chosen message attack (CMA) on digital signatures, and describe two variants.

The attacker knows $k _ v$ and can choose a certain number of messages $m _ 1, \ldots, m _ n$ of which they can find the signature (excluding the signature for the message they wish to forge).

Variants:

  • Plain version: They have to decide on the messages they want signed all at once.
  • Adaptive version: The attacker is able to use the results of previous signatures to choose future messages to sign.

@Define a universal forgery (UF) of digital signatures.

A successful attack allows the attacker to sign any message they choose.

@Define a selective forgery (SF) of digital signatures.

A successful attack allows the attacker to sign any messages from a particular set of non-negligible size.

@Define existential forgery (EF) of digital signatures.

A successful attack allows the attacker to sign at least one message, not necessarily of their choosing.

There are several attack models against digital signatures:

  • KOAs, Key only attacks
  • KMAs, Known message attacks
  • CMAs, Chosen message attacks

and several levels of success:

  • UF, Universal forgery
  • SF, Selective forgery
  • EF, Existential forgery

What is the “gold standard” for the strength of a digital signature?

It’s secure against an EF even in a chosen message attack.

Digital signatures do not imply confidentiality by themselves, and instead need to be used in conjunction with encryption to communicate securely. What are three different approaches for combining encryption and authentication into one construction?
  1. Authenticate then Encrypt: $A \to B : E(m \parallel \mathsf{SIGN}(m))$ (used by SSL)
  2. Encrypt then Authenticate: $A \to B : E(m) \parallel \mathsf{SIGN}(E(m))$ (used by IPsec)
  3. Encrypt and Authenticate: $A \to B : E(m) \parallel \mathsf{SIGN}(m)$ (used by SSH)


Related posts