Authenticated Encryption

Authenticated encryption aims to satisfy both secrecy (encryption) and integrity (authentication) simultaneously. Let’s define the experiment:

unforgeable encryption experiment ${\text{Enc-Forge}}_{\mathcal{A},\Pi }(n)$:

• key $K$ is generated
• adversary $\mathcal{A}$ is given access to encryption oracle ${\text{Enc}}_k(\cdot )$.
• $\mathcal{A}$ outputs $c$. Let $m\leftarrow {\text{Dec}}_k(c)$, then
• $\mathcal{A}$ succeeds if $m\ne \perp$ and $m\notin \mathcal{Q}$.

$$\mathrm{Pr}[{\text{Enc-Forge}}_{\mathcal{A},\Pi }(n)=1]\le \text{negl}(n)$$

A private key encryption is AE scheme if it satisfies both CCA security and unforgeability. Let’s define two oracles:

• ${\text{Enc}}_k^0(\cdot )$: sends encryption of $0^{|m|}$ for any message $m$
• ${\text{Dec}}_{\perp }(\cdot )$: sends decryption error $\perp$ for any ciphertext $c$

Our goal is to not let adversary distinguish between correct oracle response and above two oracles. This guarantees that adversary can’t distinguish between encryption of $0^{|m|}$ and valid message $m$, ensures secrecy and also can’t decrypt any valid ciphertext, ensures integrity.

AE experiment ${\text{PrivK}}_{\mathcal{A},\Pi }^{\text{ae}}(n)$:

• key $K$ is generated
• uniform bit $b\in \{0,1\}$ is chosen
• adversary is given access to oracles:
  • if $b=0$, ${\text{Enc}}_k(\cdot ),{\text{Dec}}_k(\cdot )$
  • if $b=1$, ${\text{Enc}}_k^0(\cdot ),{\text{Dec}}_{\perp }(\cdot )$
• $\mathcal{A}$ outputs bit $b^{\prime }$
• $\mathcal{A}$ succeeds if $b=b^{\prime }$.

$\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{ae}}(n)=1]\le \frac{1}{2}+\text{negl}(n)$

• AE with AD (associated data) is possible when some data is public is needed to be sent with integrity only.
• CCA security and AE are separate notions, with an encryption that is CCA secure, we want secrecy but not integrity, AE targets both.
• with any encryption that is CCA secure and MAC that is strongly secure, AE scheme can be constructed.

Three constructions are possible when designing an AE:

• encrypt and authenticate: $c\leftarrow {\text{Enc}}_{K_e}(m)$ and $t\leftarrow {\text{Mac}}_{K_m}(m)$
  • TODO: prove this is not AE secure
• authenticate then encrypt: $t\leftarrow {\text{Mac}}_{K_m}(m)$ and $c\leftarrow {\text{Enc}}_{K_e}(m\Vert t)$
  • TODO: prove this is not AE secure
• encrypt then authenticate: $c\leftarrow {\text{Enc}}_{K_e}(m)$ and $t\leftarrow {\text{Mac}}_{K_m}(c)$
  • to forge a mac, adversary needs pair $⟨c,t^{\prime }⟩$ for original $c$, but strong security of MAC, makes this negligible, thus decryption oracle for AE scheme is useless and CCA security of AE reduces to CPA security of ${\Pi }_E$.

AE construction:

• $\text{Gen’}(1^n)\to (K_m,K_e)$: outputs two keys $K_m,K_e$
• ${\text{Enc}}^{\prime }(m)$: outputs $⟨c,t⟩$ where, $c\leftarrow {\text{Enc}}_{K_e}(m)$ and $t\leftarrow {\text{Mac}}_{K_m}(c)$
• ${\text{Dec}}^{\prime }(c,t)$: verifies $t\stackrel{?}{=}\text{Vrfy}(c)$, and outputs $m\leftarrow {\text{Dec}}_{K_m}(c)$.

Prove that if ${\Pi }_e$ is CPA secure ENC scheme and ${\Pi }_m$ is strongly secure MAC scheme, then above construction is AE scheme.

• you begin by first proving that if ${\Pi }_m$ is a strongly secure MAC, then probability of forgeability is negligible, i.e. probability of event that any new, valid pair $⟨c,t⟩$ is accepted is negligible.
  • This renders the decryption oracle useless, as only error will be sent to the adversary for any other pair for which it hasn’t already queried the encryption oracle.
  • This turns the CCA security of encryption scheme to CPA security.
  • denote this by $\mathrm{Pr}[\text{ValidQuery}]\le \text{negl}(n)$
  • create adversary ${\mathcal{A}}_m$ which is running $\text{Mac-sforge}$ experiment by attacking ${\Pi }_m$ and runs $\mathcal{A}$ as subroutine
  • Now, our goal is to prove that $\mathrm{Pr}[{\text{Mac-sforge}}_{{\mathcal{A}}_m,{\Pi }_m}=1]\le \mathrm{Pr}[\text{ValidQuery}]$, i.e. if $\mathcal{A}$ is successful in outputting a new, valid $⟨c,t⟩$, then ${\mathcal{A}}_m$ will be able to succeed in sforge experiment.
• Now, since $\mathrm{Pr}[\text{ValidQuery}]$ is negligible, then we prove that $\Pi$ is CCA-secure (CPA security), i.e. $\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{\text{cca}}=1]\le \mathrm{Pr}[\text{ValidQuery}]+\mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{cca}\wedge \overline{\text{ValidQuery}}]$
  • again run CPA experiment with adversary ${\mathcal{A}}_e$ running $\mathcal{A}$ as subroutine, answering encryption oracle queries and outputting errors for decryption oracle queries.
  • when ${\mathcal{A}}_e$ outputs $m_0,m_1$ then, $\mathcal{A}$ outputs exactly those message, get the challenge ciphertext $c$, and calculate $t\leftarrow {\text{Mac}}_{K_m}(c)$.
  • $\mathcal{A}$ output the same bit $b^{\prime }$ as output by $\mathcal{A}$.
  • then $\mathrm{Pr}[{\text{PrivK}}_{{\mathcal{A}}_e,{\Pi }_e}^{\text{cpa}}=1]\ge \mathrm{Pr}[{\text{PrivK}}_{\mathcal{A},\Pi }^{cca}\wedge \overline{\text{ValidQuery}}]$

AEADs

AES-GCM

ChaChaPoly1305

References

• Introduction to Modern Cryptography: Chapter 5
• A graduate course in applied cryptography: Chapter 9