Authenticated encryption with forged verification key

Question

Is it part of the (or a common) security model of symmetric authenticated encryption to prevent an adversary from exhibiting a decryption/verification key that makes a given genuine ciphertext verify, yet deciphers differently than it does with the key used to produce that ciphertext?

If not, are some common symmetric authenticated encryption schemes vulnerable to that, and under what hypothesis (known plaintext, chosen plaintext, known genuine encryption key..)?

The question comes in the context of determining if symmetric authenticated encryption followed by signature provides plaintext integrity verifiable by a third party, handed ciphertext, an alleged symmetric key, and ciphertext signature, and knowing the public key.

Answer 1

Suppose we had a 384-bit block cipher $B_k$. (Making this practical with a 512-bit block cipher like Threefish-512 is left as an easy exercise for the reader.)

For $k_0, k_1, m \in \operatorname{GF}(2^{128})$, define $H_{k_0,k_1}(m) = k_0 m + k_1$, a standard secure polynomial evaluation one-time MAC for a one-block message.

For nonce $n \in \operatorname{GF}(2^{384})$, plaintext $p \in \operatorname{GF}(2^{128})$, and key $k$, define $$F_{k,n}(p) = (p + k_2, H_{k_0,k_1}(p + k_2)),$$ where $$k_0 \mathbin\Vert k_1 \mathbin\Vert k_2 = B_k(n).$$

Under standard assumptions, $F_{k,n}$ should be a secure authenticated encryption scheme, on a limited message space, built roughly as an encrypt-then-MAC composition. Decryption is the obvious $F_{k,n}^{-1}(c, t) = c + k_2$, to be done only if $t = H_{k_0,k_1}(c)$.

Note that we can also phrase this as

\begin{align*} F_{k,n}(p) &= (c, t), \quad\text{where} \\ c &= p + k_2, \\ t &= k_0 p + k_0 k_2 + k_1. \end{align*}

Our task as an adversary, given legitimate ciphertext $c$ and tag $t$ (authenticated, say, by a signature), and forged plaintext $p'$, is to find $k'$ and $n'$ so that $F_{k',n'}(p') = (c, t)$. We obviously must have $k_2' = p' + c$; then

\begin{align*} t &= k_0' p' + k_0' k_2' + k_1' \\ &= k_0' p' + k_0' p' + k_0' c + k_1' \\ &= k_0' c + k_1', \end{align*}

so if we pick $k_0'$ arbitrarily we must have $k_1' = t + k_0' c$. If we further pick $k'$ arbitrarily, we then find that $n' = B_{k'}^{-1}(k_0' \mathbin\Vert k_1' \mathbin\Vert k_2') = B_{k'}^{-1}\bigl(k_0' \mathbin\Vert (t + k_0' c) \mathbin\Vert (p' + c)\bigr)$ will give the ciphertext and tag we desired.

If you were watching carefully, which you presumably were because you're not new to this game, you probably noticed that I granted myself the latitude to pick the nonce freely. Is that cheating? I don't know—it's not clear what the context of your question is, how it fits into a protocol. Certainly it would be foolish not to sign the nonce too, but maybe the nonce is implied as a message sequence number here, and the designer figured that it would be space- and bandwidth-efficient to omit it from the message on the wire and consequently also omitted it from the inputs to the signature.