Notes - Computer Security MT24, MACs
Flashcards
Definitions
@Define a keyed hash.
A function
\[h : \mathcal K \times \\{0, 1\\}^\ast \to \\{0, 1\\}^n\]with all the properties of a cryptographic hash function for each $k$, and with the additional property that it is difficult to find $k$ and $x$ such that $h _ k(x) = y$.
Given a MAC and a MAC verifier
\[\begin{aligned}
&\mathsf{MAC} : \mathcal K \times \\{0, 1\\}^\ast \to \mathcal D \\\\
&\mathsf{VER} : \mathcal K \times \\{0, 1\\}^\ast \times \mathcal D \to \\{\mathbf{true}, \mathbf{false}\\}
\end{aligned}\]
Alice can communicate a message and its digest to Bob. Can you explain its purpose in terms of integrity and authentication?
- Integrity: Bob can know almost certainly if the message has been modified.
- Authentication: If just Alice and Bob share the secret key, then Bob can know for sure that Alice originated the message. If Alice and Bob reveal the secret key, they can convince other parties that one of them originated the message, but not necessarily Alice.
How could you @define
\[\begin{aligned}
&\mathsf{MAC} : \mathcal K \times \\{0, 1\\}^\ast \to \mathcal D \\\\
&\mathsf{VER} : \mathcal K \times \\{0, 1\\}^\ast \times \mathcal D \to \\{\mathbf{true}, \mathbf{false}\\}
\end{aligned}\]
by using an $n$-bit block cipher and a cryptographic hash, and why is this not a good idea?
Take
\[\mathsf{MAC} _ k(m) := E _ k(h(m))\]and
\[\mathsf{VER} _ k(m, y) := (E _ k(h(m)) == y)\]Not a good idea since it involves both encryption and hashing, which can be slow and weaknesses in the encryption or hashing scheme translate to weaknesses in the MAC.
Perfect security
@Define a MAC (message authentication code) and a MAC verifier.
A MAC is a function
\[\mathsf{MAC} : \mathcal K \times \\{0, 1\\}^\ast \to \mathcal D\]where $\mathcal K$ is a secret keyspace and $\mathcal D$ is a set of possible digests.
A MAC verifier is a function
\[\mathsf{VER} : \mathcal K \times \\{0, 1\\}^\ast \times \mathcal D \to \\{\mathbf{true}, \mathbf{false}\\}\]A MAC computes a short digest $\mathsf{MAC} _ k(m)$ which together with a verifier can be used to detect any changes to either $k$ or $m$:
\[\mathsf{VER} _ k(m', \mathsf{MAC} _ {k'}(m)) = \begin{cases} \mathbf{true} &\text{if }m = m' \text{ and } k = k' \\\\ \mathbf{false} &\text{almost certainly otherwise} \end{cases}\]Given a MAC and a MAC verifier
\[\begin{aligned}
&\mathsf{MAC} : \mathcal K \times \\{0, 1\\}^\ast \to \mathcal D \\\\
&\mathsf{VER} : \mathcal K \times \\{0, 1\\}^\ast \times \mathcal D \to \\{\mathbf{true}, \mathbf{false}\\}
\end{aligned}\]
can you @define the notion of perfect security?
For all $k$, given a message $m$ and its digest $d = \mathsf{MAC} _ k(m)$, for any $m’ \ne m$ and any $d \in \mathcal D$,
\[\mathbb P[\mathsf{MAC} _ k(m') = d' \mid \mathsf{MAC} _ k(m) = d] = \frac{1}{|\mathcal D|}\]i.e. after seeing one digest, the probability of seeing any other digest of a message is still uniformly distributed.
CBC-MAC
@Define the CBC-MAC.
Suppose:
- $E _ k$ is a symmetric encryption function
- $IV$ is a public initialisation vector
Then:
- The CBC-MAC is just the last block of the ciphertext if the message is encrypted using CBC, i.e.
The CBC-MAC is defined by using the last block a message encrypted using a symmetric encryption function under the CBC block mode:
\[\begin{aligned}
\mathsf{CbcMAC} _ k\langle\rangle &= IV \\\\
\mathsf{CbcMAC} _ k\langle m _ 1, \ldots, m _ n\rangle &= E _ k(m _ n \oplus \mathsf{CbcMAC} _ k\langle m _ 1, \ldots, m _ {n-1} \rangle)
\end{aligned}\]
Given two digests
\[\begin{aligned}
d &= \mathsf{CbcMAC} _ k(m) \\\\
d' &= \mathsf{CbcMAC} _ k(m')
\end{aligned}\]
Can you describe a way to create a valid digest for another message (an existential attack)?
Split $m’$ into blocks $m’ = \langle m _ 1’, \ldots, m _ n’\rangle$. Then
\[\mathsf{CbcMAC} _ k(m \parallel (m _ 1' \oplus d \oplus IV) \parallel m _ 2' \parallel \cdots \parallel m _ n') = d'\]So we can find a digest for $m \parallel (m _ 1’ \oplus d \oplus IV) \parallel m _ 2’ \parallel \cdots \parallel m _ n’$ without knowing the key.
The CBC-MAC is defined by using the last block a message encrypted using a symmetric encryption function under the CBC block mode:
\[\begin{aligned}
\mathsf{CbcMAC} _ k\langle\rangle &= IV \\\\
\mathsf{CbcMAC} _ k\langle m _ 1, \ldots, m _ n\rangle &= E _ k(m _ n \oplus \mathsf{CbcMAC} _ k\langle m _ 1, \ldots, m _ {n-1} \rangle)
\end{aligned}\]
When signing an message encrypted using $E _ k$ and CBC, why would it be a mistake to use the same key for the MAC as for the encryption?
This means that the last cipher block is the MAC and hence is easily forgable.
MACs based on hashing
Can you @define some very basic (and insecure) MACs based on a cryptographic hash function?
A simple MAC is defined by
\[\mathsf{MAC} _ k(m) := h(m \parallel k)\]
Suppose that an attacker has found a collision in the underlying hash function $h$, so that
\[h(m) = h(m')\]
and that $h$ is built by iterating a compression function in a way that means $h(m \parallel m _ \text{tail})$ is predictable from $h(m)$. How can they use this hash collision to produce many MAC collisions?
@Define the HMAC.
The HMAC is defined by
\[\mathsf{HMAC} _ k(m) := h(k \parallel h(k \parallel m))\]
Can you summarise how the HMAC is secure?
“An attacker who can forge the HMAC function can, with the same effort, either find collisions in the has function even when the IV is random and secret, or compute an output of the compression function even with an IV that is random.”
Properties of MACs
Why do MACs not provide non-repudiation?
MACs require a symmetric key $k$. If Alice and Bob communicate and authenticate their communications with a MAC, they cannot prove to outsiders that one of them in particular is responsible for a message.
Consider the following protocol for message integrity:
- $A \to B$: $m \parallel h(m)$
- $B$ separates the message and accepts if the hash matches
What is wrong with this protocol?
An attacker who could modify the message could also modify the hash.