MAC security construction question

MAC security construction question

Guest (guest) 31 Jan 2020 12:12

Hi,

I saw a construction that given CPA secure encryption scheme, you construct a MAC scheme as follows:
$Auth_{sk}(m) = Enc_{sk}(m)$

The question was either it's secure or not.

The answer that it's not, and the solution was to create a new encryption scheme E' such that for every key (sk) the text $0^n$ is encoded to $0^n$ with some negligible probability. Then, an adversary can simply generate $(0^n, 0^n)$ as a forgery.

I don't see why this is correct, because it will only happen with negligible probability (by the definition of E').

What am I missing here?

Thanks!

Re: MAC security construction question

nbitansky 31 Jan 2020 16:59

You didn't describe what is the verification algorithm. Assuming it's decryption, the attack you described works with probability one.

Guest (guest) 31 Jan 2020 17:10

Why? The attack will work only if sk (which is unknown) actually encodes $0^n$ to $0^n$.
Assuming some random sk, the probability that it happens is negligible by definition of E'.

nbitansky 31 Jan 2020 17:14

As you described yourself: "every secret key $sk$ encodes $0^n$ to $0^n$ with negligible probability (over the encryption randomness)".

Guest (guest) 31 Jan 2020 18:43

I'm sorry but I still don't understand how it will work with probability one.

The adversary will generate $(m^*, t^*) = (0^n, 0^n)$ as forgery. The verifier will check that it's actually true that $E_{sk}(0^n) = 0^n$, but that's only true with negligible probability. So $Pr[Ver_{sk}(m^*, t^*) = 1] \leq \mu(n)$, which is a secure MAC.

nbitansky 31 Jan 2020 19:25

Verification is defined by decryption, and $0^n$ decrypts to $0^n$ (with probability $1$).

Guest (guest) 31 Jan 2020 21:02

But it's a forge, the attacker doesn't really know that's true, he just guesses it (no queries are made to the oracle). Why do you claim it's true? $E_{sk}(0^n)$ might also be something else than $0^n$ with non-negligible probability (and then $D_{sk}(0^n)$ would be something different from $0^n$ which will fail the attacker).

nbitansky 01 Feb 2020 05:56

Decryption is deterministic and is determined by the ciphertext alone (in this case $0^n$). The fact that the underlying plaintext (in this case also $0^n$) has multiple different encryptions does not change that (these other ciphertext will also decrypt to $0^n$, but may look differently).

Guest (guest) 01 Feb 2020 06:35

But who says that the underlying plaintext is also $0^n$? That's what I don't understand here. The adversary forged that tuple of $(m^*=0^n, t^*=0^n)$. I claim that $Pr[D_{sk}(t^*) \neq 0^n] > 1 - \mu(n)$, hence the adversary will fail with non-negligible probability.

nbitansky 01 Feb 2020 07:51

$D_{sk}$ is a deterministic operation so the probability is one or zero. The scheme is constructed so that it is one.

Let's add more details:
Take any CPA-secure scheme $(E',D')$ and now construct a new scheme $(E,D)$ that is defined as follows: $E$ uses randomness of size $\ell+n$ where $\ell$ is the amount of randomness used by $E$, we'll parse the randomness used by $E$ as two random strings $r,r'$ of respective lengths $n,\ell$. Define $E_{sk}(m;r,r')$: if $m=0^n,r=1^n$, output $0^n$, else output $E'_{sk}(m;r')$. Define $D_{sk}(ct)$ as follows: if $ct=0^n$ output $0^n$, else output $D'_{sk}(ct)$.

Assuming that $E'$ doesn't encrypt length-$n$ plaintexts into $0^n$, the scheme is perfectly correct (this assumption is w.l.og, can always pad with 1). It's also secure, as except with negligible probability it's identical to $E$. If you define a MAC where authentication of $m$ is a random encryption $E_{sk}(m)$, and verification of $m,ct$ is checking whether $D_{sk}(ct) = m$, you get an insecure MAC —- the attacker that outputs $0^n,0^n$ wins with probability 1.

Guest (guest) 01 Feb 2020 08:09

Now I got it. Thank you very much!
(The original scheme had no randomness, that's why I failed to understand it so far)

nbitansky 01 Feb 2020 08:36

A CPA-secure encryption cannot be deterministic (we talked about it).