1657 lines
61 KiB
TeX
1657 lines
61 KiB
TeX
\documentclass[aspectratio=169, lualatex, handout]{beamer}
|
|
\makeatletter\def\input@path{{theme/}}\makeatother\usetheme{cipher}
|
|
|
|
\title{Applied Cryptography}
|
|
\author{Nadim Kobeissi}
|
|
\institute{American University of Beirut}
|
|
\instituteimage{images/aub_white.png}
|
|
\date{\today}
|
|
\coversubtitle{CMPS 297AD/396AI\\Fall 2025}
|
|
\coverpartname{Part 1: Provable Security}
|
|
\covertopicname{1.5: Chosen-Plaintext \& Chosen-Ciphertext Attacks}
|
|
\coverwebsite{https://appliedcryptography.page}
|
|
|
|
\begin{document}
|
|
\begin{frame}[plain]
|
|
\titlepage
|
|
\end{frame}
|
|
|
|
\section{Chosen-Plaintext Attacks}
|
|
|
|
\begin{frame}{CPA Security}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\definitionbox{Security Against Chosen-Plaintext Attacks (CPA Security)}{
|
|
Let $\Sigma$ be an encryption scheme, and let $\Sigma.\mathcal{C}(\ell)$ denote the set of possible ciphertexts for plaintexts of length $\ell$. If $\Sigma$ supports only plaintexts of a single length, we can simply write $\Sigma.\mathcal{C}$ to denote the entire set of ciphertexts.\footnote{i.e. ``just forget about the length''.}\\[0.5em]
|
|
|
|
$\Sigma$ has security against \textbf{chosen-plaintext attacks} if the following two libraries are indistinguishable:
|
|
}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\sslinked{
|
|
\sslibrary{\Sigma}{cpa-real}{
|
|
$K \twoheadleftarrow \Sigma.\mathcal{K}$\\[1em]
|
|
\sslibrarysubroutine{cpa.enc}{M}{
|
|
$C \coloneq \Sigma.\texttt{Enc}(K, M)$\\
|
|
return $C$
|
|
}{1}
|
|
}{0.8}
|
|
}{\approxeq}{
|
|
\sslibrary{\Sigma}{cpa-rand}{
|
|
\sslibrarysubroutine{cpa.enc}{M}{
|
|
$C \twoheadleftarrow \Sigma.\mathcal{C}(|M|)$\\
|
|
return $C$
|
|
}{1}
|
|
}{0.8}
|
|
}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Why CPA security matters}
|
|
\begin{itemize}[<+->]
|
|
\item CPA security means: \textit{``even if I let you encrypt any message you want, you can't obtain any distinguisher regarding my scheme.''}
|
|
\item \textbf{Why this matters in real life:}
|
|
\begin{itemize}[<+->]
|
|
\item Attackers often can trick systems into encrypting data they choose.
|
|
\item Without CPA security, seeing these encryptions could reveal your secrets.
|
|
\item Example: If bank transactions always encrypt to the same ciphertexts, attackers could identify your purchases.
|
|
\end{itemize}
|
|
\item The only thing that's allowed to leak is the length of messages/ciphertext.
|
|
\item Most modern encryption is designed to have this important property.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Message length: not important, not unimportant}
|
|
\begin{itemize}[<+->]
|
|
\item Even with CPA security, the \textbf{length} of messages is still leaked.
|
|
\item This seemingly minor leak can reveal surprising information:
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Encrypted VoIP calls}: Length patterns can reveal which language is spoken.
|
|
\item \textbf{Encrypted web traffic}: Sizes of requests/responses identify websites.
|
|
\item \textbf{Encrypted messages}: Length patterns can reveal the type of content (document, image, etc.)
|
|
\item \textbf{Encrypted commands}: Length often reveals which command was issued.
|
|
\end{itemize}
|
|
\item Mitigation typically involves padding messages to fixed lengths or standard increments.
|
|
\item This is why many secure protocols use fixed-size packets or add random padding.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CPA security is why we avoid deterministic encryption}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Deterministic encryption will always fail CPA security!
|
|
\item If the same message always encrypts to the same ciphertext:
|
|
\begin{itemize}
|
|
\item Attacker can recognize repeat messages.
|
|
\item Can build a ``dictionary'' of known plaintexts.
|
|
\item etc.
|
|
\end{itemize}
|
|
\item ECB mode is a classic example of insecure deterministic encryption.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{center}
|
|
\ssprogram{}{
|
|
$M \twoheadleftarrow \mathcal{M}$\\
|
|
$C_1 \coloneq \func{cpa.enc}{M}$\\
|
|
$C_2 \coloneq \func{cpa.enc}{M}$\\
|
|
return $C_1 == C_2$
|
|
}{1}
|
|
\end{center}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Non-deterministic encryption isn't hard...}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item AES-CTR turns AES into a non-deterministic PRF...
|
|
\item AES-GCM even turns it into a non-deterministic authenticated cipher...\footnote{More on these later. An authenticated cipher is one where the ciphertext can't be modified by the adversary without that being detected.}
|
|
\item We can just as easily make a PRF non-deterministic:
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\sssubroutine{enc}{K, M}{
|
|
$R \twoheadleftarrow \bits^\lambda$\\
|
|
$S \coloneq F(K, R) \oplus M$\\
|
|
return $R\|S$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{...but it can be fragile}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item We switch M and R's places in \lib{}{cpa-real}'s encryption function.
|
|
\item Is the scheme still secure?
|
|
\item \textbf{No!}
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\sslinked{
|
|
\sslibrary{}{cpa-real}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cpa.enc}{M}{
|
|
$R \twoheadleftarrow \bits^\lambda$\\
|
|
$S \coloneq F(K, \hl{M}) \oplus \hl{R}$\\
|
|
return $R\|S$
|
|
}{1}
|
|
}{1}
|
|
}{\overset{?}{\approxeq}}{
|
|
\sslibrary{}{cpa-rand}{
|
|
\sslibrarysubroutine{cpa.enc}{M}{
|
|
$R\|S \twoheadleftarrow \bits^{2\lambda}$\\
|
|
return $R\|S$
|
|
}{1}
|
|
}{1}
|
|
}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{The Golden Rule of PRFs}
|
|
\definitionbox{The Golden Rule of PRFs}{
|
|
If a PRF $F$ is being used as a component in a larger construction $H$, then security usually rests on how well $H$ can ensure distinct inputs to $F$.
|
|
}
|
|
\begin{itemize}[<+->]
|
|
\item When analyzing PRF security, focus on input uniqueness.
|
|
\item Repeated inputs to a PRF create exploitable patterns.
|
|
\item Even if $F$ is secure, $H$ can be broken if it causes $F$ to receive duplicate inputs.
|
|
\item Don't try to directly distinguish $F$'s outputs from uniform.
|
|
\item Instead, exploit how $H$ uses $F$ incorrectly.
|
|
\item Find input patterns that force collisions within $F$.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{...but it can be fragile}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}
|
|
\item $F(K, M)$ is now constant.
|
|
\item \prob{\prog{}\link\lib{}{cpa-real} \Rightarrow \texttt{true}} $ = 1$
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\sslinked{
|
|
\ssprogram{}{
|
|
$M \twoheadleftarrow \mathcal{M}$\\
|
|
$R_1\|S_1 \coloneq \func{cpa.enc}{M}$\\
|
|
$R_2\|S_2 \coloneq \func{cpa.enc}{M}$\\
|
|
return $S_1 \oplus S_2 == R_1 \oplus R_2$
|
|
}{0.8}
|
|
}{\link}{
|
|
\sslibrary{}{cpa-real}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cpa.enc}{M}{
|
|
$R \twoheadleftarrow \bits^\lambda$\\
|
|
$S \coloneq F(K, \hl{M}) \oplus \hl{R}$\\
|
|
return $R\|S$
|
|
}{1}
|
|
}{0.8}
|
|
}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{AES is a block cipher}{Reminder}
|
|
\begin{itemize}[<+->]
|
|
\item AES takes a 16-byte input, produces a 16-byte output.
|
|
\item Key can be 16, 24 or 32 bytes. \pause
|
|
\item OK, so what if we want to encrypt more than 16 bytes? \pause
|
|
\item \textbf{Proposal}: split the plaintext into 16 byte chunks, encrypt
|
|
each of them with the same key.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Block cipher examples}
|
|
\begin{columns}
|
|
\begin{column}{0.33\textwidth}
|
|
\imagewithcaption{tux_plaintext.png}{What we start with}
|
|
\end{column}
|
|
\pause
|
|
\begin{column}{0.33\textwidth}
|
|
\imagewithcaption{tux_encrypted_ecb.png}{What we get}
|
|
\end{column}
|
|
\pause
|
|
\begin{column}{0.33\textwidth}
|
|
\imagewithcaption{tux_encrypted_ctr.png}{What we actually want}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{AES by itself is deterministic}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.7\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item AES as a block cipher is inherently \textbf{deterministic}:
|
|
\begin{itemize}
|
|
\item $\texttt{AES}(K, M) = C$ will always produce the same $C$.
|
|
\item This makes raw AES fail CPA security.
|
|
\end{itemize}
|
|
\item What makes AES secure in practice?
|
|
\begin{itemize}
|
|
\item \textbf{Block cipher modes} (CBC, CTR, GCM) add randomness/state using ``initialization vectors''
|
|
\begin{itemize}
|
|
\item IV is fancy name for ``random bytes used once''.\footnote{Also referred to as ``nonces'' for ``number used once'', although in some block cipher modes such as AES-CBC, they can technically be used multiple times without problems.}
|
|
\end{itemize}
|
|
\item IVs ensure the same plaintext encrypts differently each time.
|
|
\end{itemize}
|
|
\item Without a proper mode, AES is like ECB mode: predictable patterns
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.3\textwidth}
|
|
\begin{center}
|
|
\ssprogram{AES}{
|
|
$K \twoheadleftarrow \bits^{\lambda}$\\
|
|
$M \twoheadleftarrow \mathcal{M}$\\[0.5em]
|
|
$C_1 \coloneq \texttt{AES}(K, M)$\\
|
|
$C_2 \coloneq \texttt{AES}(K, M)$\\[0.5em]
|
|
$C_1 == C_2$
|
|
}{0.85}
|
|
\end{center}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Block cipher modes of operation}
|
|
\bigimagewithcaption{block_cipher_modes.png}{Source: Wikipedia}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CBC mode: a closer look}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item CBC (Cipher Block Chaining) uses previous ciphertext to randomize current block.
|
|
\item Requires a random initialization vector (IV).
|
|
\item Each block's encryption depends on all previous blocks.
|
|
\item Changes to one block affect all subsequent ciphertext blocks.
|
|
\item Sequential encryption (can't parallelize).
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\sssubroutine{Enc}{K, M_1\|\cdots\|M_\ell}{
|
|
$C_0 \twoheadleftarrow \bits^\lambda$\\
|
|
$\text{for } i=1 \text{ to } \ell:$\\
|
|
$\quad C_i \coloneq F(K, C_{i-1} \oplus M_i)$\\
|
|
$\textbf{return } C_0\|C_1\|\cdots\|C_\ell$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CBC mode: a closer look}
|
|
\vspace{-0.3cm}
|
|
\bigimagewithcaption{cbc_with_dec.pdf}{Source: The Joy of Cryptography}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CTR mode: a closer look}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item CTR (Counter) mode turns a block cipher into a stream cipher.
|
|
\item Uses a nonce ($C_0$) plus a counter to create unique inputs to $F$.
|
|
\item Each block's encryption is independent of other blocks.
|
|
\item Highly parallelizable (unlike CBC).
|
|
\item The nonce must never be reused with the same key.
|
|
\item Widely used in modern protocols (TLS, SSH, etc.)
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\sssubroutine{Enc}{K, M_1\|\cdots\|M_\ell}{
|
|
$C_0 \twoheadleftarrow \bits^\lambda$\\
|
|
$\text{for } i=1 \text{ to } \ell:$\\
|
|
$\quad C_i \coloneq F(K, C_0 + i - 1) \oplus M_i$\\
|
|
$\textbf{return } C_0\|C_1\|\cdots\|C_\ell$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CTR mode: a closer look}
|
|
\bigimagewithcaption{ctr_with_dec.pdf}{Source: The Joy of Cryptography}
|
|
\end{frame}
|
|
|
|
\section{Chosen-Ciphertext Attacks}
|
|
|
|
\begin{frame}{Introducing chosen-ciphertext attacks}
|
|
\begin{itemize}[<+->]
|
|
\item Imagine this scenario at your company:
|
|
\begin{itemize}[<+->]
|
|
\item You discover a bug: software crashes when decrypting ciphertexts that yield plaintexts with null characters.
|
|
\item You think: ``We never encrypt messages with null bytes, so no problem!''
|
|
\end{itemize}
|
|
\item An attacker can:
|
|
\begin{itemize}[<+->]
|
|
\item Send specially crafted ciphertexts to your system
|
|
\item Observe which ones crash your software (contain null bytes) and which don't
|
|
\item Use this information to completely break your encryption scheme!
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Introducing chosen-ciphertext attacks}
|
|
\begin{itemize}
|
|
\item This is a \textbf{chosen-ciphertext attack} (CCA):
|
|
\begin{itemize}[<+->]
|
|
\item Attacker can submit arbitrary ciphertexts for decryption.
|
|
\item System leaks information about the decryption results (the crash).
|
|
\item Even small information leaks can completely compromise security.
|
|
\item All encryption schemes we've seen so far are vulnerable to this!
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Format-oracle attacks \& malleability}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Scenario: victim using CTR mode decryption reveals if result contains a null character.
|
|
\item Information can leak through crashes, error messages, or behavior differences.
|
|
\item A single yes/no bit of information can be enough to break encryption!
|
|
\item Malleability: many encryption schemes allow attackers to make predictable changes to plaintexts by modifying ciphertexts.
|
|
\item CTR mode is especially vulnerable because XOR allows targeted bit-flipping.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\sssubroutine{nulloracle}{C}{
|
|
$M \coloneq \texttt{CTR.Dec}(K, C)$\\
|
|
if $M$ contains $\bit{0}\bit{0}$ character:\\
|
|
$\quad$ return $\texttt{true}$\\
|
|
else return $\texttt{false}$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Why is it called \func{nulloracle}{c}?}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}
|
|
\item In mythology and colloquial language:
|
|
\begin{itemize}
|
|
\item An oracle was a mystic who answered questions on behalf of the gods.
|
|
\item Often gave enigmatic answers requiring interpretation.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\vspace{-0.4cm}
|
|
\bigimagewithcaption{oracle_painting_zoom.jpg}{\textit{The Oracle} by Camillo Miola, 1880\footnote{Absolutely beautiful painting, well-worth viewing in high resolution: \url{https://upload.wikimedia.org/wikipedia/commons/9/94/Camillo_Miola_\%28Biacca\%29_-_The_Oracle_-_72.PA.32_-_J._Paul_Getty_Museum.jpg}}}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Why is it called \func{nulloracle}{c}?}
|
|
\begin{itemize}[<+->]
|
|
\item In cryptography and computer science:
|
|
\begin{itemize}
|
|
\item An oracle is an algorithm that solves a specific problem.
|
|
\item You can query it but can't see its internal workings.
|
|
\item Oracles are often used as theoretical tools in security proofs.
|
|
\end{itemize}
|
|
\item Our \func{nulloracle}{c} reveals only:
|
|
\begin{itemize}
|
|
\item Whether a decrypted ciphertext contains null (\bit{0}\bit{0}) characters.
|
|
\item Just a single bit of information (yes/no).
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Null-oracle attack}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item An adversary who has access to \func{nulloracle}{C} can efficiently compute \texttt{Dec}$(K, C)$ for any $C$!
|
|
\item Yes, it really is enough.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\sssubroutine{nulloracle}{C}{
|
|
$M \coloneq \texttt{CTR.Dec}(K, C)$\\
|
|
if $M$ contains $\bit{0}\bit{0}$ character:\\
|
|
$\quad$ return $\texttt{true}$\\
|
|
else return $\texttt{false}$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CTR mode is malleable}{Defining malleability}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\definitionbox{Malleability}{
|
|
An encryption scheme is \textbf{malleable} if, given an encryption $C$ of an unknown plaintext $M$, it is possible to create a new ciphertext $C' \neq C$ where $M' = \texttt{Dec}(K, C')$ is somehow related to $M$, so that $M'$ reveals some information about $M$.
|
|
}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item In CTR mode: $C_i = F(K, C_0 + i - 1) \oplus M_i$
|
|
\item Flipping a bit in $C_i$ flips exactly the same bit in $M_i$.
|
|
\item Attackers can make targeted modifications without knowing the key.
|
|
\item Example: change ``transfer \$100'' to ``transfer \$900'' by modifying just one byte.
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CTR mode is malleable}{Defining malleability}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}
|
|
\item In CTR mode: $C_i = F(K, C_0 + i - 1) \oplus M_i$
|
|
\item Flipping a bit in $C_i$ flips exactly the same bit in $M_i$.
|
|
\item Attackers can make targeted modifications without knowing the key.
|
|
\item Example: change ``transfer \$100'' to ``transfer \$900'' by modifying just one byte.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{ctr_dec.pdf}{CTR mode decryption.\\Source: The Joy of Cryptography}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CTR mode is malleable}{Defining malleability}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}
|
|
\item In CTR mode: $C_i = F(K, C_0 + i - 1) \oplus M_i$
|
|
\item Flipping a bit in $C_i$ flips exactly the same bit in $M_i$.
|
|
\item Attackers can make targeted modifications without knowing the key.
|
|
\item Example: change ``transfer \$100'' to ``transfer \$900'' by modifying just one byte.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{ctr_dec_delta.pdf}{CTR mode decryption.\\Source: The Joy of Cryptography}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CTR mode is malleable}{The attack}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Suppose adversary captures ciphertext $C$ and wants to find plaintext $M = \texttt{Dec}(K, C)$.
|
|
\item Let's focus on discovering just the last byte of $M$.
|
|
\item If the last byte of $M$ is $b$, then $M = M' \| b$.
|
|
\item What if we modify the ciphertext by XORing the last byte with $b$?
|
|
\item This would turn the last byte of the plaintext into all zeros (null byte)!
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{align*}
|
|
C \oplus (\ldots \bit{0}\bit{0} \| b) & \text{ decrypts to:} \\
|
|
& M \oplus (\ldots \bit{0}\bit{0} \| b) \\
|
|
& = (M' \| b) \oplus (\ldots \bit{0}\bit{0} \| b) \\
|
|
& = M' \| (b \oplus b) \\
|
|
& = M' \| \bit{0}\bit{0}
|
|
\end{align*}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CTR mode is malleable}{Finding one byte}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Problem: We don't know $b$ in advance!
|
|
\item Solution: Try all 255 possible values for $b$.
|
|
\item For each guess $g$, we:
|
|
\begin{itemize}
|
|
\item Create $C' = C \oplus (\ldots \bit{0}\bit{0} \| g)$
|
|
\item Send $C'$ to the \func{nulloracle}{}
|
|
\item If oracle returns \texttt{true}, then $g = b$!
|
|
\end{itemize}
|
|
\item When we find the right value, we've discovered the last byte of $M$.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{center}
|
|
Try these ciphertexts:\\
|
|
$C \oplus (\ldots \bit{0}\bit{0} \| \bit{0}\bit{1})$\\
|
|
$C \oplus (\ldots \bit{0}\bit{0} \| \bit{0}\bit{2})$\\
|
|
$C \oplus (\ldots \bit{0}\bit{0} \| \bit{0}\bit{3})$\\
|
|
$\vdots$\\
|
|
$C \oplus (\ldots \bit{0}\bit{0} \| \bit{f}\bit{e})$\\
|
|
$C \oplus (\ldots \bit{0}\bit{0} \| \bit{f}\bit{f})$
|
|
\end{center}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CTR mode is malleable}{Finding all bytes}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item We can use the same approach for any byte in the plaintext.
|
|
\item To find the $i$-th byte:
|
|
\begin{itemize}
|
|
\item Create a string of all zeros
|
|
\item Set only the $i$-th byte to our guess $g$
|
|
\item XOR this with the ciphertext
|
|
\item Query the oracle
|
|
\end{itemize}
|
|
\item By repeating for all bytes, we can recover the entire plaintext!
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\ssprogram{null-oracle}{
|
|
$n := |C_1\|\cdots\|C_{\ell}|$\\
|
|
$M := ""$\\
|
|
\\
|
|
for $i = 1$ to $n$:\\
|
|
$\quad$ for each $b \in \{\bit{0}\bit{1}, \ldots, \bit{f}\bit{f}\}$:\\
|
|
$\quad\quad$ $\Delta := (\bit{0}\bit{0})^n$\\
|
|
$\quad\quad$ $\Delta[i] := b$\\
|
|
$\quad\quad$ if $\func{nulloracle}{C \oplus (0^\lambda \| \Delta)}$:\\
|
|
$\quad\quad\quad$ $M := M \| b$\\
|
|
$\quad\quad\quad$ next $i$\\
|
|
return $M$
|
|
}{0.8}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CTR mode is malleable}{The power of chosen-ciphertext attacks}
|
|
\begin{itemize}[<+->]
|
|
\item With just 255 queries per byte, we can completely decrypt any ciphertext!
|
|
\item For context: decrypting a 1KB file would take about 250,000 queries.
|
|
\item This is extremely practical for an attacker.
|
|
\item All from a single bit of information about the plaintext (contains null or not).
|
|
\item This attack works because:
|
|
\begin{itemize}
|
|
\item CTR mode is malleable (we can make predictable changes to plaintext)
|
|
\item The system leaks a tiny bit of information about decrypted plaintexts
|
|
\item Together, these flaws completely break the encryption
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Is the null-oracle attack just brute-force?}
|
|
\begin{itemize}[<+->]
|
|
\item Yes and no!
|
|
\item It's brute-force on each byte independently:
|
|
\begin{itemize}
|
|
\item To recover $n$-byte plaintext: at most $255n$ oracle queries
|
|
\item True brute-force on entire plaintext: $255^n$ (exponentially worse!)
|
|
\end{itemize}
|
|
\item For a 16-byte message:
|
|
\begin{itemize}
|
|
\item Null-oracle attack: ~4,080 queries (16 \times 255)
|
|
\item True brute-force: ~$10^{38}$ queries ($255^{16}$)
|
|
\end{itemize}
|
|
\item This attack is exponentially more efficient than traditional brute-force.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Can we just rate-limit the number of queries?}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Rate-limiting might help, but:
|
|
\begin{itemize}
|
|
\item It only increases attack time, doesn't prevent it.
|
|
\item Attackers can be patient or use multiple accounts.
|
|
\item Legitimate users suffer from the rate-limiting.
|
|
\end{itemize}
|
|
\item Better approach: cryptographic solutions!
|
|
\begin{itemize}
|
|
\item Fix the fundamental vulnerability, not just limit its exploitation.
|
|
\item Create systems that are mathematically proven to resist chosen-ciphertext attacks.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\imagewithcaption{yoda_meme.jpg}{}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Is fixing the null-byte bug enough?}
|
|
\begin{itemize}[<+->]
|
|
\item The null-character bug is just one example of a broader class of attacks.
|
|
\item Format-oracle attacks can exist without implementation bugs!
|
|
\item They only need:
|
|
\begin{itemize}[<+->]
|
|
\item A system that accepts untrusted ciphertexts
|
|
\item Decrypts them
|
|
\item Behaves differently based on the decryption result
|
|
\item In a way the attacker can observe
|
|
\end{itemize}
|
|
\item This behavior can come from:
|
|
\begin{itemize}[<+->]
|
|
\item Accidental bugs (null-byte crashes)
|
|
\item Intentional features (error messages, timing differences)
|
|
\item Normal application logic (web app behaving differently based on decrypted data)
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Real-world format-oracle attacks}{Padding oracle}
|
|
\begin{columns}[c]
|
|
\begin{column}{1\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item CBC mode requires padding to handle plaintexts that aren't block-aligned.
|
|
\item Many implementations crash when encountering invalid padding.
|
|
\item This exposes an oracle that tells attackers: ``Does $\texttt{Dec}(K, C)$ have valid padding?''
|
|
\item Attackers can systematically exploit this to decrypt arbitrary ciphertexts.
|
|
\item Has led to major vulnerabilities in SSH and SSL/TLS protocols.
|
|
\item Example: POODLE attack against SSL 3.0 affected millions of websites.\footnote{\url{https://appliedcryptography.page/papers/\#google-poodle}}
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Real-world format-oracle attacks}{Timing side-channel}
|
|
\begin{columns}[c]
|
|
\begin{column}{1\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Victim interprets plaintext as a number $n$ and performs $n$ operations.
|
|
\item Attackers can measure how long the system takes to respond.
|
|
\item Response time reveals approximate numerical values inside $\texttt{Dec}(K, C)$.
|
|
\item Extremely subtle - even microsecond differences can leak information.
|
|
\item Successfully used to break older SSH and SSL/TLS implementations.
|
|
\item Example: Lucky Thirteen attack against TLS revealed message contents through timing differences.\footnote{\url{https://appliedcryptography.page/papers/\#lucky-thirteen}}
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Real-world format-oracle attack}{Apple iMessage}
|
|
\begin{columns}[c]
|
|
\begin{column}{1\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Older Apple iMessage versions used gzip compression.
|
|
\item System responded differently when a ciphertext decrypted to:
|
|
\begin{itemize}
|
|
\item A valid gzip file (processed normally)
|
|
\item An invalid gzip file (error reported)
|
|
\end{itemize}
|
|
\item This created an oracle revealing: ``Is $\texttt{Dec}(K, C)$ a valid gzip file?''\footnote{\url{https://appliedcryptography.page/papers/\#jhu-imessage}}
|
|
\item Attackers who understood the gzip format could exploit this to:
|
|
\begin{itemize}
|
|
\item Silently recover private messages
|
|
\item Bypass encryption entirely
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Real-world format-oracle attack}{XML format Oracles}
|
|
\begin{itemize}[<+->]
|
|
\item Many systems decrypt data expecting valid XML format.
|
|
\item If decrypted data isn't valid XML, system returns an error.
|
|
\item This exposes an oracle: ``Is $\texttt{Dec}(K, C)$ valid XML?''
|
|
\item XML has complex syntax rules that attackers can exploit.
|
|
\item Can allow complete decryption of arbitrary ciphertexts.
|
|
\item Similar attacks exist for other formats (JSON, HTML, etc.)
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{I thought CTR mode was secure?}{CPA vs. CCA security}
|
|
\begin{itemize}[<+->]
|
|
\item CTR mode \textit{is} secure against chosen-plaintext attacks (CPA-secure).
|
|
\begin{itemize}
|
|
\item It uses randomness to ensure identical messages encrypt differently each time.
|
|
\item The adversary cannot distinguish encryptions of known plaintexts.
|
|
\end{itemize}
|
|
\item But CPA security isn't enough in many real-world scenarios!
|
|
\begin{itemize}
|
|
\item CPA security only considers attackers who can request encryptions.
|
|
\item It doesn't protect against attackers who can submit chosen ciphertexts.
|
|
\end{itemize}
|
|
\item In the null-oracle attack:
|
|
\begin{itemize}
|
|
\item The victim decrypts ciphertexts chosen by the adversary.
|
|
\item Even leaking one bit about the plaintext (contains nulls or not) is fatal.
|
|
\item CPA security doesn't model or prevent this type of attack.
|
|
\end{itemize}
|
|
\item This is why we need stronger security notions (CCA security).
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CCA Security}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\definitionbox{Security Against Chosen-Ciphertext Attacks (CCA Security)}{
|
|
An encryption scheme $\Sigma$ has security against \textbf{chosen-ciphertext attacks} if the following two libraries are indistinguishable:
|
|
}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\sslinked{
|
|
\sslibrary{\Sigma}{cca-real}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cca.enc}{M}{
|
|
$C \coloneq \Sigma.\texttt{Enc}(K, M)$\\
|
|
return $C$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{cca.dec}{C}{
|
|
return $\Sigma.\texttt{Dec}(K, C)$
|
|
}{1}
|
|
}{0.7}
|
|
}{\approxeq}{
|
|
\sslibrary{\Sigma}{cca-rand}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cca.enc}{M}{
|
|
$C \twoheadleftarrow \Sigma.\mathcal{C}(|M|)$\\
|
|
$\mathcal{D}[C] \coloneq M$\\
|
|
return $C$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{cca.dec}{C}{
|
|
if $\mathcal{D}[C]$ defined: return $\mathcal{D}[C]$\\
|
|
return $\Sigma.\texttt{Dec}(K, C)$
|
|
}{1}
|
|
}{0.7}
|
|
}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Remember our CPA-secure encryption scheme?}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}
|
|
\item Not CCA-secure!
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\sssubroutine{enc}{K, M}{
|
|
$R \twoheadleftarrow \bits^\lambda$\\
|
|
$S \coloneq F(K, R) \oplus M$\\
|
|
return $R\|S$
|
|
}{2}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Remember our CPA-secure encryption scheme?}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.3\textwidth}
|
|
\begin{itemize}
|
|
\item Not CCA-secure!
|
|
\item In other words, we can trivially distinguish between these libraries:
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.7\textwidth}
|
|
\sslinked{
|
|
\sslibrary{}{cca-real}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cca.enc}{M}{
|
|
$R \twoheadleftarrow \bits^\lambda$\\
|
|
$S \coloneq F(K, R) \oplus M$\\
|
|
return $R\|S$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{cca.dec}{R\|S}{
|
|
$M \coloneq F(K, R) \oplus S$\\
|
|
return $M$
|
|
}{1}
|
|
}{0.9}
|
|
}{\cancel{\approxeq}}{
|
|
\sslibrary{}{cca-rand}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cca.enc}{M}{
|
|
$R\|S \twoheadleftarrow \bits^{2\lambda}$\\
|
|
$\mathcal{D}[R\|S] \coloneq M$\\
|
|
return $R\|S$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{cca.dec}{R\|S}{
|
|
if $\mathcal{D}[R\|S]$ defined: return $\mathcal{D}[R\|S]$\\
|
|
$M \coloneq F(K, R) \oplus S$\\
|
|
return $M$
|
|
}{1}
|
|
}{0.9}
|
|
}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Malleability strategy}
|
|
To break the CCA security of a scheme:
|
|
\begin{enumerate}
|
|
\item Study the decryption algorithm of the scheme. It often helps to draw a schematic diagram.
|
|
\item See whether any changes to a ciphertext make a \textit{predictable} change to the plaintext.
|
|
\item Formalize an attack in which the adversary:
|
|
\begin{enumerate}
|
|
\item Requests the encryption of a chosen plaintext,
|
|
\item Modifies the ciphertext as above,
|
|
\item Asks for the modified ciphertext to be decrypted.
|
|
\end{enumerate}
|
|
\end{enumerate}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Malleability once again}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}
|
|
\item Not CCA-secure!
|
|
\item Here's a distinguisher:
|
|
\end{itemize}
|
|
\imagewithcaption{prf_enc_malleable}{Source: The Joy of Cryptography}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\ssprogram{}{
|
|
$M \twoheadleftarrow \bits^\lambda$\\
|
|
$\Delta := \text{arbitrary, nonzero, $\lambda$-bit string}$\\
|
|
$R\|S \coloneq \func{cca.enc}{M}$\\
|
|
$M' \coloneq \func{cca.dec}{R\|(S \oplus \Delta)}$\\
|
|
return $M' == M \oplus \Delta$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Another example}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}
|
|
\item Let's try a harder challenge.
|
|
\end{itemize}
|
|
\imagewithcaption{prf_enc_2}{Source: The Joy of Cryptography}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\sslibrary{}{cca-real}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cca.enc}{M}{
|
|
$R \twoheadleftarrow \bits^\lambda$\\
|
|
$S \coloneq F(K, R) \oplus F(K, M)$\\
|
|
return $R\|S$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{cca.dec}{R\|S}{
|
|
$M \coloneq F^{-1}(K, F(K, R) \oplus S)$\\
|
|
return $M$
|
|
}{1}
|
|
}{0.85}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Another example}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.3\textwidth}
|
|
\begin{itemize}
|
|
\item Let's try a harder challenge.
|
|
\end{itemize}
|
|
\imagewithcaption{prf_enc_2}{Source: The Joy of Cryptography}
|
|
\end{column}
|
|
\begin{column}{0.7\textwidth}
|
|
\sslinked{
|
|
\sslibrary{}{cca-real}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cca.enc}{M}{
|
|
$R \twoheadleftarrow \bits^\lambda$\\
|
|
$S \coloneq F(K, R) \oplus F(K, M)$\\
|
|
return $R\|S$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{cca.dec}{R\|S}{
|
|
$M \coloneq F^{-1}(K, F(K, R) \oplus S)$\\
|
|
return $M$
|
|
}{1}
|
|
}{0.85}
|
|
}{\cancel{\approxeq}}{
|
|
\sslibrary{}{cca-rand}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cca.enc}{M}{
|
|
$R\|S \twoheadleftarrow \bits^{2\lambda}$\\
|
|
return $R\|S$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{cca.dec}{R\|S}{
|
|
if $\mathcal{D}[R\|S]$ defined: return $\mathcal{D}[R\|S]$\\
|
|
$M \coloneq F^{-1}(K, F(K, R) \oplus S)$\\
|
|
return $M$
|
|
}{1}
|
|
}{0.85}
|
|
}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Frankenstein strategy}
|
|
Try the following approach in a chosen-ciphertext attack:
|
|
\begin{enumerate}
|
|
\item Request two separate encryptions of chosen plaintexts; it often helps to use the same plaintext.
|
|
\item Mix and match parts of the resulting ciphertexts to obtain two Frankenstein ciphertexts.
|
|
\item Ask for the Frankenstein ciphertexts to be decrypted, and see whether anything interesting happens.
|
|
\end{enumerate}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Another example}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}
|
|
\item Not CCA-secure!
|
|
\item Here's a distinguisher:
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\ssprogram{}{
|
|
$M \twoheadleftarrow \bits^\lambda$\\
|
|
$R_1\|S_1 \coloneq \func{cca.enc}{M}$\\
|
|
$R_2\|S_2 \coloneq \func{cca.enc}{M}$\\
|
|
$M_1^* \coloneq \func{cca.dec}{R_1\|S_2}$\\
|
|
$M_2^* \coloneq \func{cca.dec}{R_2\|S_1}$\\
|
|
return $M_1^* == M_2^*$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\subsection{Message Authentication Codes}
|
|
|
|
\begin{frame}{Symmetric primitive example: hash functions}{Reminder}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.55\textwidth}
|
|
\definitionbox{Hash Function Properties}{
|
|
\begin{itemize}\item Takes input of \textbf{any size}[<+->]
|
|
\item Produces output of \textbf{fixed size}
|
|
\item Is \textbf{deterministic} (same input $\rightarrow$ same output)
|
|
\item Even a \textbf{tiny change} in input creates completely different output
|
|
\item Is \textbf{efficient} to compute\end{itemize}
|
|
}
|
|
\end{column}
|
|
\begin{column}{0.45\textwidth}
|
|
\begin{tcolorbox}
|
|
[colback=black!5!white,colframe=ciphergray] $\mathsf{SHA256}(\texttt{hello}) =$ \\ \texttt{2cf24dba5fb0a30e26e83b2ac5}\\ \texttt{b9e29e1b161e5c1fa7425e7304}\\
|
|
\texttt{3362938b9824}
|
|
|
|
$\mathsf{SHA256}(\texttt{hullo}) =$ \\ \texttt{7835066a1457504217688c8f5d}\\
|
|
\texttt{06909c6591e0ca78c254ccf174}\\ \texttt{50d0d999cab0}
|
|
\end{tcolorbox}
|
|
\textcolor{cipherprimary}{\textbf{Note:} \small One character change $\rightarrow$
|
|
completely different hash!}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Expected properties of a hash function}{Reminder}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Collision resistance}: computationally infeasible to find
|
|
two different inputs producing the same hash.
|
|
\item \textbf{Preimage resistance}: given the output of a hash function,
|
|
it is computationally infeasible to reconstruct the original input.
|
|
\item \textbf{Second preimage resistance}: given an input and an output,
|
|
it's computationally infeasible to find another different input
|
|
producing the same output.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\imagewithcaption{sha2.png}{SHA-2 compression function. Source: Wikipedia}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Hash functions: what are they good for?}{Reminder}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Password storage}: Store the hash of the password on the server,
|
|
not the password itself. Then check candidate passwords against the hash.
|
|
\item \textbf{Data integrity verification}: Hash a file. Later hash it
|
|
again and compare hashes to check if the file has changed, suffered storage
|
|
degradation, etc.
|
|
\item \textbf{Proof of work}: Server asks client to hash something a lot of
|
|
times before they can access some resource. Useful for anti-spam, Bitcoin
|
|
mining, etc.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Message authentication codes}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\definitionbox{Message Authentication Code (MAC)}{
|
|
A MAC is a cryptographic function that takes a key $K$ and a message $M$ and produces a tag $T$ that authenticates the message. Only someone with the same key can verify the tag.
|
|
}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item A MAC provides \textbf{integrity} and \textbf{authenticity} for messages.
|
|
\item Unlike hash functions, MACs require a secret key
|
|
\item MACs address the malleability problem we saw with encryption schemes. Without a MAC, attackers could modify ciphertexts.
|
|
\item A secure MAC should be unforgeable, even after seeing MACs for chosen messages.
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{PRFs as MACs}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.4\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item A pseudorandom function (PRF) can be used directly as a MAC!
|
|
\item The MAC key is the PRF key $K$.
|
|
\item To authenticate a message $X$:
|
|
\begin{itemize}
|
|
\item Compute the tag $T = F(K, X)$
|
|
\item Send both $X$ and $T$ to the recipient
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{flushright}
|
|
\sslinked{
|
|
\sslibrary{}{mac-real}{
|
|
$K \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{mac.guess}{X, Y}{
|
|
return $Y == F(K, X)$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{mac.reveal}{X}{
|
|
return $F(K, X)$
|
|
}{1}
|
|
}{0.75}
|
|
}{\approxeq}{
|
|
\sslibrary{}{mac-ideal}{
|
|
\sslibrarysubroutine{mac.guess}{X, Y}{
|
|
if $L[X]$ undefined: return $\texttt{false}$\\
|
|
return $Y == L[X]$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{mac.reveal}{X}{
|
|
if $L[X]$ undefined: $L[X] \twoheadleftarrow \bits^\lambda$\\
|
|
return $L[X]$
|
|
}{1}
|
|
}{0.75}
|
|
}
|
|
\end{flushright}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{From CPA to CCA security}{The Encrypt-then-MAC approach}
|
|
\begin{itemize}[<+->]
|
|
\item CPA security isn't enough in the real world.
|
|
\item We need protection against chosen-ciphertext attacks.
|
|
\item Solution: combine encryption with a MAC!.
|
|
\item \textbf{Encrypt-then-MAC}:
|
|
\begin{itemize}
|
|
\item Encrypt the message normally.
|
|
\item Compute a MAC tag of the \textit{ciphertext}.
|
|
\item Send both ciphertext and tag.
|
|
\item Receiver verifies the tag before decrypting.
|
|
\end{itemize}
|
|
\item This prevents adversaries from creating valid modified ciphertexts.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Encrypt-then-MAC: formal construction}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.45\textwidth}
|
|
\definitionbox{Encrypt-then-MAC Construction}{
|
|
Let $\Sigma$ be an SKE scheme and $F$ be a PRF with output length $\lambda$ whose domain includes $\Sigma.\mathcal{C}$.
|
|
Define a new encryption scheme:
|
|
\begin{align*}
|
|
\mathcal{K} & = \Sigma.\mathcal{K} \times \bits^\lambda \\
|
|
\mathcal{M} & = \Sigma.\mathcal{M} \\
|
|
\mathcal{C}(\ell) & = \Sigma.\mathcal{C}(\ell) \times \bits^\lambda
|
|
\end{align*}
|
|
}
|
|
\end{column}
|
|
\begin{column}{0.55\textwidth}
|
|
\sssubroutine{Enc}{(K_e, K_m), M}{
|
|
$C \coloneq \Sigma.\texttt{Enc}(K_e, M)$\\
|
|
$T \coloneq F(K_m, C)$\\
|
|
return $C\|T$
|
|
}{1}
|
|
\sssubroutine{Dec}{(K_e, K_m), C\|T}{
|
|
if $F(K_m, C) \neq T$: return $\texttt{err}$\\
|
|
return $\Sigma.\texttt{Dec}(K_e, C)$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{CCA security of Encrypt-then-MAC}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.45\textwidth}
|
|
\definitionbox{CCA Security Claim}{
|
|
If $\Sigma$ is a CPA-secure encryption scheme and $F$ is a secure PRF, then the Encrypt-then-MAC construction is CCA-secure.
|
|
}
|
|
\begin{itemize}[<+->]
|
|
\item Key insight: \textbf{the MAC prevents tampering}
|
|
\item Without the MAC key, adversary can't create valid tags.
|
|
\item \textbf{Decryption oracle only returns plaintexts for ciphertexts with valid tags.}
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.55\textwidth}
|
|
\sslinked{
|
|
\sslibrary{}{cca-real}{
|
|
$K_e \twoheadleftarrow \Sigma.\mathcal{K}$\\
|
|
$K_m \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cca.enc}{M}{
|
|
$C \coloneq \Sigma.\texttt{Enc}(K_e, M)$\\
|
|
$T \coloneq F(K_m, C)$\\
|
|
return $C\|T$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{cca.dec}{C\|T}{
|
|
if $F(K_m, C) \neq T$: return $\texttt{err}$\\
|
|
return $\Sigma.\texttt{Dec}(K_e, C)$
|
|
}{1}
|
|
}{0.65}
|
|
}{\approxeq}{
|
|
\sslibrary{}{cca-rand}{
|
|
$K_e \twoheadleftarrow \Sigma.\mathcal{K}$\\
|
|
$K_m \twoheadleftarrow \bits^\lambda$\\[1em]
|
|
\sslibrarysubroutine{cca.enc}{M}{
|
|
$C \twoheadleftarrow \Sigma.\mathcal{C}(|M|)$\\
|
|
$T \twoheadleftarrow \bits^\lambda$\\
|
|
$\mathcal{D}[C\|T] \coloneq M$\\
|
|
return $C\|T$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{cca.dec}{C\|T}{
|
|
if $\mathcal{D}[C\|T]$ defined: return $\mathcal{D}[C\|T]$\\
|
|
if $F(K_m, C) \neq T$: return $\texttt{err}$\\
|
|
return $\Sigma.\texttt{Dec}(K_e, C)$
|
|
}{1}
|
|
}{0.65}
|
|
}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Combining MACs and encryption}
|
|
\begin{itemize}[<+->]
|
|
\item Not every way of combining a MAC and CPA-secure encryption achieves CCA security.
|
|
\item There are three common approaches to combining them:
|
|
\begin{itemize}
|
|
\item \textbf{Encrypt-then-MAC}: Encrypt message, then MAC the ciphertext.
|
|
\item \textbf{Encrypt-and-MAC}: Encrypt message and MAC the plaintext separately.
|
|
\item \textbf{MAC-then-encrypt}: MAC the plaintext, then encrypt both message and tag.
|
|
\end{itemize}
|
|
\item Only one approach guarantees CCA security when using any CPA-secure encryption.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Encrypt-then-MAC}{CCA-secure}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{MAC verifies ciphertext integrity} before decryption.
|
|
\item Prevents attackers from submitting modified ciphertexts.
|
|
\item \textbf{Always CCA-secure} if encryption is CPA-secure and MAC is secure.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\sssubroutine{Enc}{(K_e, K_m), M}{
|
|
$C \coloneq \Sigma.\texttt{Enc}(K_e, M)$\\
|
|
$T \coloneq F(K_m, C)$\\
|
|
return $C\|T$
|
|
}{1}
|
|
\sssubroutine{Dec}{(K_e, K_m), C\|T}{
|
|
if $F(K_m, C) \neq T$: return $\texttt{err}$\\
|
|
return $\Sigma.\texttt{Dec}(K_e, C)$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Encrypt-and-MAC}{Not even CPA-secure!}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{MAC is computed on the plaintext}
|
|
\item Same plaintext always produces same tag, leaking equality information.
|
|
\item \textbf{Not even CPA-secure}, let alone CCA-secure.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\sssubroutine{Enc}{(K_e, K_m), M}{
|
|
$C \coloneq \Sigma.\texttt{Enc}(K_e, M)$\\
|
|
$T \coloneq F(K_m, M)$\\
|
|
return $C\|T$
|
|
}{1}
|
|
\sssubroutine{Dec}{(K_e, K_m), C\|T}{
|
|
$M \coloneq \Sigma.\texttt{Dec}(K_e, C)$\\
|
|
if $F(K_m, M) \neq T$: return $\texttt{err}$\\
|
|
return $M$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{MAC-then-encrypt}{It's complicated}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Tag is hidden inside the ciphertext}
|
|
\item Whether this is CCA-secure depends on the specific encryption scheme.
|
|
\item \textbf{Not generally CCA-secure} for all CPA-secure encryption schemes.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\sssubroutine{Enc}{(K_e, K_m), M}{
|
|
$T \coloneq F(K_m, M)$\\
|
|
$C \coloneq \Sigma.\texttt{Enc}(K_e, M\|T)$\\
|
|
return $C$
|
|
}{1}
|
|
\sssubroutine{Dec}{(K_e, K_m), C}{
|
|
$M\|T \coloneq \Sigma.\texttt{Dec}(K_e, C)$\\
|
|
if $F(K_m, M) \neq T$: return $\texttt{err}$\\
|
|
return $M$
|
|
}{1}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Encrypt + MAC security comparison}
|
|
\begin{center}
|
|
\begin{tabular}{|l|c|c|}
|
|
\hline
|
|
\textbf{Construction} & \textbf{CPA-secure?} & \textbf{CCA-secure?} \\
|
|
\hline
|
|
Encrypt-then-MAC & Yes & Yes \\
|
|
\hline
|
|
Encrypt-and-MAC & No & No \\
|
|
\hline
|
|
MAC-then-encrypt & Yes & Maybe \\
|
|
\hline
|
|
\end{tabular}
|
|
\end{center}
|
|
\vspace{1em}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Encrypt-then-MAC} is the safest option.
|
|
\item \textbf{Encrypt-and-MAC} should never be used.
|
|
\item \textbf{MAC-then-encrypt} requires case-by-case analysis.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\subsection{Authenticated Encryption}
|
|
|
|
\begin{frame}{Authenticated Encryption: beyond CCA security}
|
|
\begin{itemize}[<+->]
|
|
\item CCA security is stronger than CPA security, but still not the gold standard.
|
|
\item CCA security says: adversary-generated ciphertexts won't reveal useful information.
|
|
\item But CCA security doesn't require that they decrypt to \texttt{err}.
|
|
\item For many applications, we want a stronger guarantee:
|
|
\begin{itemize}
|
|
\item Only key-holders can create valid ciphertexts.
|
|
\item All other ciphertexts should be rejected as invalid.
|
|
\end{itemize}
|
|
\item This property is called \textbf{Authenticated Encryption (AE)}.
|
|
\item Authenticated encryption provides both confidentiality and authenticity.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Authenticated Encryption: formal definition}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.4\textwidth}
|
|
\definitionbox{Authenticated Encryption}{
|
|
A SKE scheme $\Sigma$ is a secure authenticated encryption (AE) scheme if the following two libraries are indistinguishable:
|
|
}
|
|
\end{column}
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{flushright}
|
|
\sslinked{
|
|
\sslibrary{\Sigma}{ae-real}{
|
|
$K \twoheadleftarrow \Sigma.\mathcal{K}$\\[1em]
|
|
\sslibrarysubroutine{ae.enc}{M}{
|
|
return $\Sigma.\texttt{Enc}(K, M)$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{ae.dec}{C}{
|
|
return $\Sigma.\texttt{Dec}(K, C)$
|
|
}{1}
|
|
}{0.75}
|
|
}{\approxeq}{
|
|
\sslibrary{\Sigma}{ae-rand}{
|
|
\sslibrarysubroutine{ae.enc}{M}{
|
|
$C \twoheadleftarrow \Sigma.\mathcal{C}(|M|)$\\
|
|
$\mathcal{D}[C] \coloneq M$\\
|
|
return $C$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{ae.dec}{C}{
|
|
if $\mathcal{D}[C]$ defined: return $\mathcal{D}[C]$\\
|
|
else: return $\texttt{err}$
|
|
}{1}
|
|
}{0.75}
|
|
}
|
|
\end{flushright}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{AE vs. CCA security}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Key difference: \textbf{how we handle adversary-created ciphertexts}.
|
|
\item In \lib{\Sigma}{ae-rand}, any ciphertext not created by the library always decrypts to \texttt{err}.
|
|
\item In \lib{\Sigma}{cca-rand}, such ciphertexts could decrypt to anything (not necessarily \texttt{err}).
|
|
\item So AE requires:
|
|
\begin{itemize}
|
|
\item Adversary cannot tell real from random ciphertexts (as in CPA)
|
|
\item Adversary cannot create new valid ciphertexts (authentication)
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item AE is \textbf{strictly stronger} than CCA security.
|
|
\item Every AE scheme is CCA-secure, but not every CCA-secure scheme is an AE.
|
|
\item Making the distinction explicit helps us design better protocols.
|
|
\item AE is what you should aim for in practice.
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{How Encrypt-then-MAC achieves AE}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Remember our Encrypt-then-MAC construction:
|
|
\begin{itemize}
|
|
\item Encrypt the plaintext: $C \coloneq \Sigma.\texttt{Enc}(K_e, M)$
|
|
\item MAC the ciphertext: $T \coloneq F(K_m, C)$
|
|
\item Send both: $C\|T$
|
|
\end{itemize}
|
|
\item It achieves AE security because:
|
|
\begin{itemize}
|
|
\item Without $K_m$, adversary can't forge valid tags.
|
|
\item Any ciphertext not created by the system will fail MAC verification.
|
|
\item MAC verification failures lead to \texttt{err}.
|
|
\end{itemize}
|
|
\item The proof is nearly identical to CCA security proof.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\definitionbox{AE Security of Encrypt-then-MAC}{
|
|
Encrypt-then-MAC is a secure AE, if the underlying $\Sigma$ is a CPA-secure SKE and $F$ is a secure PRF.
|
|
}
|
|
\vspace{0.5em}
|
|
\definitionbox{AE implies CCA}{
|
|
If an encryption scheme $\Sigma$ is a secure AE, then it is also CCA-secure.
|
|
}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Authenticated Encryption: in practice}
|
|
\begin{itemize}[<+->]
|
|
\item Modern cryptographic protocols almost always use authenticated encryption.
|
|
\item Common AE implementations:
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{AES-GCM} (Galois/Counter Mode): most widely used, combines CTR mode with a MAC.
|
|
\item \textbf{ChaCha20-Poly1305}: popular alternative to AES-GCM, especially on devices without AES hardware.
|
|
\item \textbf{AES-CBC + HMAC-SHA256}: older approach, uses Encrypt-then-MAC with AES in CBC mode.
|
|
\end{itemize}
|
|
\item Important implementation rule: \textbf{verify before decrypt}!
|
|
\begin{itemize}[<+->]
|
|
\item Always check the MAC before decrypting.
|
|
\item Prevents timing side-channels based on decryption behavior.
|
|
\item Helps protect against padding oracle attacks and similar vulnerabilities.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{AES-GCM: Galois/Counter Mode}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item AES-GCM (Galois/Counter Mode) is the most widely used AEAD scheme.
|
|
\item Combines AES in CTR mode (for encryption) with GMAC (for authentication).
|
|
\item Extremely efficient:
|
|
\begin{itemize}
|
|
\item Single pass over the data.
|
|
\item Parallelizable.
|
|
\item Hardware acceleration widely available.
|
|
\end{itemize}
|
|
\item Used in: TLS 1.2/1.3, IPsec, SSH, and many other protocols.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\begin{center}
|
|
\sssubroutine{AES-GCM.Enc}{K, N, A, M}{
|
|
$H \coloneq \texttt{AES}(K, 0^{128})$\\
|
|
$\text{for } i=0 \text{ to } \lceil|M|/128\rceil-1:$\\
|
|
$\quad C_i \coloneq M_i \oplus \texttt{AES}(K, N\|i)$\\
|
|
$T \coloneq \texttt{GHASH}_H(A, C) \oplus$\\
|
|
$\quad\quad \texttt{AES}(K, N\|0)$\\
|
|
$\textbf{return } C\|T$
|
|
}{0.87}
|
|
\end{center}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{AES-GCM: Galois/Counter Mode}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Inputs}:
|
|
\begin{itemize}
|
|
\item Key $K$ (128, 192, or 256 bits)
|
|
\item Nonce $N$ (usually 96 bits)
|
|
\item Associated data $A$ (optional)
|
|
\item Plaintext $M$
|
|
\end{itemize}
|
|
\item \textbf{Encryption process}:
|
|
\begin{itemize}
|
|
\item AES-CTR for confidentiality.
|
|
\item GHASH (Galois field multiplication) for authentication.
|
|
\end{itemize}
|
|
\item Authentication tag $T$ protects both ciphertext and associated data.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{gcm.pdf}{Source: The Joy of Cryptography}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{AES-GCM: Galois/Counter Mode}
|
|
\begin{columns}[c]
|
|
\begin{column}{1\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Security strengths}:
|
|
\begin{itemize}
|
|
\item Provides confidentiality, integrity, and authenticity
|
|
\item Formally proven secure (assuming AES is secure)
|
|
\item Fast and widely trusted
|
|
\end{itemize}
|
|
\item \textbf{Critical implementation requirements}:
|
|
\begin{itemize}
|
|
\item \textbf{Never reuse a nonce} with the same key!
|
|
\item A repeated nonce can lead to complete loss of confidentiality and authentication
|
|
\item 96-bit nonces are recommended (other sizes are less efficient)
|
|
\item Authentication tag should be at least 128 bits long
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Key commitment in authenticated encryption}
|
|
\begin{columns}[c]
|
|
\begin{column}{1\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Key commitment}: a ciphertext should only decrypt to a valid plaintext under the key used to generate it.
|
|
\item Most AEAD schemes (including AES-GCM) don't guarantee this property!\footnote{\url{https://appliedcryptography.page/papers/\#key-commitment}}
|
|
\item Attack scenario:
|
|
\begin{enumerate}
|
|
\item Attacker creates special ciphertext $C$.
|
|
\item When decrypted with key $K_1$: harmless message.
|
|
\item When decrypted with key $K_2$: malicious content!
|
|
\item Enables plausible deniability, content smuggling, etc.
|
|
\end{enumerate}
|
|
\item Practical impact:
|
|
\begin{itemize}
|
|
\item Attacker can create ciphertexts that decrypt differently under different keys.
|
|
\item Enables attacks in multi-recipient contexts.
|
|
\item Affects real applications (e.g., messaging, encrypted files).
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{ChaCha20-Poly1305}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item ChaCha20-Poly1305 is a modern AEAD construction:
|
|
\begin{itemize}
|
|
\item ChaCha20 stream cipher for encryption.
|
|
\item Poly1305 MAC for authentication.
|
|
\end{itemize}
|
|
\item Designed by Daniel J. Bernstein.\footnote{Does the class want to hear about Bernstein vs. United States?}
|
|
\item Key characteristics:
|
|
\begin{itemize}
|
|
\item No table lookups (better resistance to timing attacks)
|
|
\item Excellent performance on devices without AES hardware.
|
|
\end{itemize}
|
|
\item Widely used in TLS 1.3, Signal, WireGuard...
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\begin{center}
|
|
\sssubroutine{ChaCha20-Poly1305.Enc}{K, N, A, M}{
|
|
$\text{key}_p \coloneq \texttt{ChaCha20}(K, N, 0)_{0..31}$\\
|
|
$C \coloneq M \oplus \texttt{ChaCha20}(K, N, 1)$\\
|
|
$\text{data} \coloneq \text{pad}(A) \| \text{pad}(C) \|$\\
|
|
$\quad\quad \text{len}(A) \| \text{len}(C)$\\
|
|
$T \coloneq \texttt{Poly1305}_{\text{key}_p}(\text{data})$\\
|
|
$\textbf{return } C\|T$
|
|
}{0.87}
|
|
\end{center}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Comparing AEAD implementations}
|
|
\begin{center}
|
|
\begin{tabular}{|l|c|c|c|}
|
|
\hline
|
|
\textbf{Property} & \textbf{AES-GCM} & \textbf{ChaCha20-Poly1305} & \textbf{AES+HMAC} \\
|
|
\hline
|
|
Performance (HW accel.) & Excellent & Good & Good \\
|
|
\hline
|
|
Performance (no accel.) & Poor & Excellent & Moderate \\
|
|
\hline
|
|
Security level & 128-256 bits & 256 bits & 128-256 bits \\
|
|
\hline
|
|
Side-channel resistance & Moderate & Excellent & Moderate \\
|
|
\hline
|
|
Parallelizable & Yes & Partially & No \\
|
|
\hline
|
|
Nonce sensitivity & Very high & High & Moderate \\
|
|
\hline
|
|
Overhead & Low (single pass) & Low (single pass) & Higher (two pass) \\
|
|
\hline
|
|
Implem. complexity & Moderate & Low & High \\
|
|
\hline
|
|
\end{tabular}
|
|
\end{center}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Replay attacks}{Step 1: Alice sends original message}
|
|
\bigimagewithcaption{aead_scenario_1.pdf}{Source: The Joy of Cryptography}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Replay attacks}{Step 2: Attacker replays message in a different context}
|
|
\bigimagewithcaption{aead_scenario_2.pdf}{Source: The Joy of Cryptography}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Replay attacks}{Authenticated encryption didn't save us}
|
|
\begin{itemize}
|
|
\item Even with authenticated encryption, context matters!
|
|
\item Scenario: Alice sends Bob encrypted commands.
|
|
\begin{itemize}
|
|
\item Each ciphertext contains Alice's genuine intent.
|
|
\item Bob trusts any ciphertext that decrypts successfully.
|
|
\end{itemize}
|
|
\item Vulnerability: An adversary can replay legitimate ciphertexts.
|
|
\begin{itemize}
|
|
\item Alice once sent ``Delete temporary files''.
|
|
\item Adversary replays it when Alice meant to say ``Display files''.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Associated data}
|
|
\begin{itemize}[<+->]
|
|
\item Solution 1: Include context in the plaintext
|
|
\begin{itemize}
|
|
\item ``\texttt{ACTION: DISPLAY}'' before the actual message.
|
|
\item Inefficient - increases message size.
|
|
\item Both parties already know the context.
|
|
\end{itemize}
|
|
\item Better solution: Associated Data (AD)
|
|
\begin{itemize}
|
|
\item Context that sender and receiver already know.
|
|
\item Used during encryption and decryption.
|
|
\item Doesn't increase ciphertext size.
|
|
\end{itemize}
|
|
\item How it works:
|
|
\begin{itemize}
|
|
\item $\texttt{Enc}(K, A, M) \rightarrow C$ where $A$ is associated data.
|
|
\item $\texttt{Dec}(K, A, C) \rightarrow M$ or $\texttt{err}$
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{AEAD: formal definition}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\definitionbox{AEAD}{
|
|
An encryption scheme $\Sigma$ with associated data is a secure authenticated encryption with associated data (AEAD) scheme if the following two libraries are indistinguishable:
|
|
}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{flushright}
|
|
\sslinked{
|
|
\sslibrary{\Sigma}{aead-real}{
|
|
$K \twoheadleftarrow \Sigma.\mathcal{K}$\\[1em]
|
|
\sslibrarysubroutine{aead.enc}{A, M}{
|
|
return $\Sigma.\texttt{Enc}(K, A, M)$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{aead.dec}{A, C}{
|
|
return $\Sigma.\texttt{Dec}(K, A, C)$
|
|
}{1}
|
|
}{0.75}
|
|
}{\approxeq}{
|
|
\sslibrary{\Sigma}{aead-rand}{
|
|
\sslibrarysubroutine{aead.enc}{A, M}{
|
|
$C \twoheadleftarrow \Sigma.\mathcal{C}(|M|)$\\
|
|
$\mathcal{D}[A, C] \coloneq M$\\
|
|
return $C$
|
|
}{1}\\[1em]
|
|
\sslibrarysubroutine{aead.dec}{A, C}{
|
|
if $\mathcal{D}[A, C]$ defined:\\
|
|
\quad return $\mathcal{D}[A, C]$\\
|
|
else: return $\texttt{err}$
|
|
}{1}
|
|
}{0.75}
|
|
}
|
|
\end{flushright}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Usefulness of AEADs}
|
|
\begin{itemize}[<+->]
|
|
\item AEAD (Authenticated Encryption with Associated Data) scheme guarantees:
|
|
\begin{itemize}
|
|
\item Ciphertexts reveal nothing about plaintexts (confidentiality).
|
|
\item Only ciphertexts created by the legitimate sender will decrypt without error (authenticity).
|
|
\item Decryption only succeeds when the correct associated data is used (context binding).
|
|
\end{itemize}
|
|
\item What to use as associated data?
|
|
\begin{itemize}
|
|
\item Protocol information: ``\texttt{DISPLAY}'' vs ``\texttt{DELETE}''.
|
|
\item Session identifiers or timestamps.
|
|
\item Previous messages in the conversation.
|
|
\item Any contextual information both parties already know.
|
|
\end{itemize}
|
|
\item Use as much associated data as relevant - it's cryptographically ``free''!
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Solution: use associated data to provide context}
|
|
\bigimagewithcaption{aead_scenario_4.pdf}{Source: The Joy of Cryptography}
|
|
\end{frame}
|
|
|
|
\begin{frame}[plain]
|
|
\titlepage
|
|
\end{frame}
|
|
\end{document}
|