# Authenticated encryption with forged verification key

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.

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.

• Note that RFC 5116 on AEAD ciphers has this section included: "The nonce is authenticated internally to the algorithm, and it is not necessary to include it in the AD input. The nonce MAY be included in P or A if it is convenient to the application." Can you somehow include or reference the "standard assumptions" you are referring to? Note: I don't particularly like that RFC, I may want to actually comment on it. Commented Feb 6, 2018 at 15:47
• This is almost certainly secure in the ideal cipher model for $B_k$, and it's probably also secure when $B_k$ is a pseudorandom permutation family, but I don't have a security reduction for either one. Note that the scenario is not that the ciphertext (and maybe, or maybe not, nonce) is authenticated with $k$, the symmetric key in this protocol, but rather that the ciphertext and the tag are authenticated with something like a signature outside this protocol. Does that signature cover all nonsecret inputs to the AEAD decrypt routine, or just the ciphertext and tag? fgrieu didn't say. Commented Feb 6, 2018 at 17:03