\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.6: Collision-Resistant Hash Functions}
\coverwebsite{https://appliedcryptography.page}

\begin{document}
\begin{frame}[plain]
	\titlepage
\end{frame}

\section{Defining Hash Functions}

\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}{Hash function collisions}
	\begin{columns}[c]
		\begin{column}{0.55\textwidth}
			\definitionbox{Hash Function Collision}{
				A \textbf{collision} occurs when two different inputs produce the same hash output:
				$x \neq y$ but $H(x) = H(y)$
			}
			\begin{itemize}[<+->]
				\item Collisions \textbf{must exist} due to the pigeonhole principle:
				      infinitely many possible inputs map to a finite set of outputs.
				\item A secure hash function makes finding collisions \textbf{computationally infeasible}.
			\end{itemize}
		\end{column}
		\begin{column}{0.45\textwidth}
			\begin{tcolorbox}[colback=black!5!white,colframe=ciphergray]
				\textbf{Collision Example:}

				\vspace{0.2cm}

				\texttt{Input 1: document.pdf}\\
				$\mathsf{SHA256} = \texttt{a1b2c3...}$

				\vspace{0.2cm}

				\texttt{Input 2: malware.exe}\\
				$\mathsf{SHA256} = \texttt{a1b2c3...}$

				\vspace{0.2cm}

				\textcolor{cipherprimary}{\textbf{Problem:} \small Attacker could substitute malware.exe for document.pdf without detection!}
			\end{tcolorbox}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Hash function collisions}
	\begin{columns}[c]
		\begin{column}{0.55\textwidth}
			\definitionbox{Hash Function Collision}{
				A \textbf{collision} occurs when two different inputs produce the same hash output:
				$x \neq y$ but $H(x) = H(y)$
			}
			\begin{itemize}[<+->]
				\item If an attacker can find collisions, they could substitute malicious data
				      that produces the same hash as legitimate data.
				\item The \textbf{birthday paradox} shows collisions are found faster than
				      expected (after $\approx 2^{n/2}$ attempts for an $n$-bit hash).
			\end{itemize}
		\end{column}
		\begin{column}{0.45\textwidth}
			\begin{tcolorbox}[colback=black!5!white,colframe=ciphergray]
				\textbf{Collision Example:}

				\vspace{0.2cm}

				\texttt{Input 1: document.pdf}\\
				$\mathsf{SHA256} = \texttt{a1b2c3...}$

				\vspace{0.2cm}

				\texttt{Input 2: malware.exe}\\
				$\mathsf{SHA256} = \texttt{a1b2c3...}$

				\vspace{0.2cm}

				\textcolor{cipherprimary}{\textbf{Problem:} \small Attacker could substitute malware.exe for document.pdf without detection!}
			\end{tcolorbox}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{$\mathsf{PRF}: F_{k}= X \rightarrow Y$}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\begin{itemize}
				\item We want the mapping to be:
				      \begin{itemize}
					      \item One-way
					      \item ``Randomized''
					      \item Relations between inputs not reflected in outputs
				      \end{itemize}
			\end{itemize}
		\end{column}

		\begin{column}{0.8\textwidth}
			\begin{tikzpicture}[scale=0.38]
				% Define colors
				\definecolor{domaingreen}{RGB}{102, 170, 68}
				\definecolor{rangegreen}{RGB}{170, 187, 136}
				\definecolor{circlecolor}{RGB}{235, 137, 85}
				\definecolor{purplearrow}{RGB}{160, 78, 160}
				\definecolor{redarrow}{RGB}{237, 50, 36}

				% Input space (domain) X - made square
				\draw[dashed, thick, domaingreen, fill=domaingreen]
				(0,0) rectangle (8,8);
				\node[text width=6.5cm, align=center, font=\normalsize]
				at
				(4,-0.8)
				{Size: infinite!};
				\node[font=\small] at (4,9) {Input space (domain) $X$};

				% Output (range) Y - made square - moved more to the right
				\draw[thick, rangegreen, fill=rangegreen] (15,2) rectangle (20,7);
				\node[text width=4cm, align=center, font=\normalsize]
				at
				(17.5,1.2)
				{Size: fixed};
				\node[font=\small] at (17.5,8.5) {Output (range) $Y$};
				% Input dots - adjusted positions for square domain
				\filldraw[circlecolor] (2,7) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,7) -- (16.2,6.4);
				\pause
				\filldraw[circlecolor] (16.2,6.4) circle (0.3);
				\pause

				\filldraw[circlecolor] (3,6) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(3,6) -- (18.6,5.3);
				\pause
				\filldraw[circlecolor] (18.6,5.3) circle (0.3);
				\pause

				\filldraw[circlecolor] (2,5) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,5) -- (16.8,4.2);
				\pause
				\filldraw[circlecolor] (16.8,4.2) circle (0.3);
				\pause

				\filldraw[circlecolor] (4,3.5) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(4,3.5) -- (18.4,3.2);
				\pause
				\filldraw[circlecolor] (18.4,3.2) circle (0.3);
				\pause

				\filldraw[circlecolor] (2,2) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,2) -- (17.1,2.7);
				\pause
				\filldraw[circlecolor] (17.1,2.7) circle (0.3);
				\pause

				\filldraw[circlecolor] (3,1) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, ultra thick, redarrow]
				(3,1) -- (16.8,4.2);
				\node[redarrow, font=\scriptsize\bfseries, rotate=14]
				at
				(10,3)
				{Collisions are inevitable};
			\end{tikzpicture}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Birthday paradox}
	\begin{columns}[c]
		\begin{column}{1\textwidth}
			\begin{itemize}[<+->]
				\item In a classroom of 50 students, what's the probability that at least two share a birthday?
				      \begin{itemize}
					      \item 2\%?
					      \item 20\%?
					      \item 50\%?
					      \item 97\%?
				      \end{itemize}
				\item Many people guess around 15-20\%, but the actual probability is about 97\%!
				\item This is counterintuitive because \textbf{we're not looking for a specific birthday - we're looking for \textit{any} match among all possible pairs}.
				\item With 50 students, we have $\binom{50}{2} = 1,225$ possible pairs to check!\footnote{$\binom{50}{2}$ is a binomial coefficient. It means: \textit{``how many ways can I choose two different items from a set of 50?''}}
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Birthday paradox}
	\begin{itemize}[<+->]
		\item With just 23 people, probability exceeds 50\%
		\item Formula for $n$ people:
		      \begin{align*}
			      P = 1 - \frac{365!}{(365-n)! \cdot 365^n}
		      \end{align*}
		\item Implication: Finding collisions in a space of size $N$ happens with roughly $\sqrt{N}$ samples.
		\item This is why many cryptographic systems need large output spaces!
	\end{itemize}
\end{frame}

\begin{frame}{Birthday probabilities}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item Many cryptographic algorithms fail if two executions sample the same random value.
				\item General question: If we take $q$ independent uniform samples from a set of $N$ items, what's the probability some value is chosen more than once?
				\item This probability is called $\func{birthday}{q,N}$
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\begin{align*}
				\func{birthday}{q,N} = 1 - \prod_{i=1}^{q-1} \left(1 - \frac{i}{N}\right)
			\end{align*}
			\begin{itemize}[<+->]
				\item Surprisingly high probability!
				\item With $q \approx 1.2\sqrt{N}$, probability $\approx 0.5$
				\item For birthdays: only need 23 people for $>50\%$ chance
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Example hash functions}{From historical to modern}
	\begin{itemize}[<+->]
		\item \textbf{Historical/broken hash functions:}
		      \begin{itemize}
			      \item \textbf{MD4} (1990): 128-bit, completely broken, collisions found instantly
			      \item \textbf{MD5} (1992): 128-bit, collisions found in 2004, still widely misused
			      \item \textbf{SHA-0} (1993): 160-bit, withdrawn shortly after release
			      \item \textbf{SHA-1} (1995): 160-bit, practical collisions demonstrated in 2017
		      \end{itemize}
		\item \textbf{Current standard hash functions:}
		      \begin{itemize}
			      \item \textbf{SHA-2 family} (2001): SHA-224, SHA-256, SHA-384, SHA-512
			      \item \textbf{SHA-3 family} (2015): Based on the Keccak sponge construction
		      \end{itemize}
		\item \textbf{Modern alternatives:}
		      \begin{itemize}
			      \item \textbf{BLAKE2} (2012): Faster than MD5, more secure than SHA-3
			      \item \textbf{BLAKE3} (2020): Highly parallelizable, extremely fast
		      \end{itemize}
	\end{itemize}
\end{frame}

\section{Attacks on Hash Functions}

\begin{frame}{What about attacks on hash functions?}
	\begin{itemize}[<+->]
		\item Despite their security properties, hash functions can be vulnerable.
		\item We'll explore key attack strategies:
		      \begin{itemize}
			      \item Precomputation attacks using rainbow tables.
			      \item Birthday attacks exploiting the birthday paradox.
			      \item Ways attackers try to find collisions.
		      \end{itemize}
		\item Then we'll discuss countermeasures like salting.
		\item We'll then show additional attacks on hash function, and discuss their practical evolution.
	\end{itemize}
\end{frame}

\begin{frame}{Precomputation attacks}{Why salts matter}
	\begin{itemize}[<+->]
		\item Consider a server storing hashes of users' passwords.
		\item With \textbf{unsalted} hashes, an attacker can:
		      \begin{itemize}
			      \item Pre-compute hashes of common passwords.
			      \item Create a dictionary mapping $H(\texttt{password}) \rightarrow \texttt{password}$.
			      \item Instantly crack common passwords after a breach.
		      \end{itemize}
		\item All hard work is done \textbf{before} the attack.
		\item Results can be \textbf{reused} against any system using the same hash function.
	\end{itemize}
\end{frame}

\begin{frame}{Rainbow tables}
	\definitionbox{Rainbow Tables}{
		\textbf{Rainbow tables} are specialized data structures that store precomputed hash values to efficiently crack passwords with minimal computation during the actual attack.
	}
	\begin{itemize}[<+->]
		\item Represent a time-memory tradeoff for password cracking.
		\item Store chains of hashes rather than individual hash-password pairs.
		\item Can crack any password within the table's character set and length parameters.
		\item Completely defeated by properly salted hashes.
	\end{itemize}
\end{frame}

\begin{frame}{Salt in hash functions}{Preventing precomputation attacks}
	\definitionbox{Hash Salt}{
		A \textbf{salt} is a random value that is concatenated with the input before hashing:
		$H(S \| X)$ where $S$ is the salt and $X$ is the original input.
	}
	\begin{itemize}[<+->]
		\item The salt doesn't need to be secret, but should be:
		      \begin{itemize}
			      \item Random and unique for each input.
			      \item Long enough to prevent precomputation ($\geq 16$ bytes).
			      \item Stored alongside the hash value.
		      \end{itemize}
		\item Salting prevents attackers from using precomputed tables (rainbow tables) to find hash values.
		\item Without salt, same inputs always hash to same outputs, enabling reusable attacks.
	\end{itemize}
\end{frame}

\begin{frame}{Practical applications of salting}{Real-world examples}
	\begin{itemize}[<+->]
		\item \textbf{Web application user accounts}
		      \begin{itemize}
			      \item Different users with same password have different hashes.
			      \item Breach of one site doesn't compromise accounts on others.
		      \end{itemize}
		\item \textbf{Password reset tokens}
		      \begin{itemize}
			      \item Salt + timestamp prevents token reuse.
			      \item Each reset request generates unique token.
		      \end{itemize}
		\item \textbf{API key generation}
		      \begin{itemize}
			      \item Salting ensures unique keys even for similar services.
			      \item Allows key rotation without pattern recognition.
		      \end{itemize}
		\item \textbf{Database record anonymization}
		      \begin{itemize}
			      \item Different salts for different datasets prevent correlation attacks.
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Hash functions in the real world}
	\begin{itemize}[<+->]
		\item Hash functions you encounter ``in the wild'' are \textbf{standardized} as \textbf{unsalted} functions.
		\item They have only a single input argument: a string to be hashed.
	\end{itemize}
\end{frame}

\begin{frame}{How salt neutralizes precomputation}
	\begin{itemize}[<+->]
		\item With salted hashes, precomputation becomes useless:
		      \begin{itemize}
			      \item Attacker doesn't know the salts until they've already breached the system.
			      \item Can't precompute $H(S \| X)$ without knowing $S$.
		      \end{itemize}
		\item Using \textbf{different} salt for each user:
		      \begin{itemize}
			      \item Forces attacker to choose which user to attack.
			      \item Attacking two victims requires twice the effort.
			      \item No more ``attack all users for the price of one''.
		      \end{itemize}
		\item Even if attacker obtains both hash and salt, they still need to brute-force each password individually.
	\end{itemize}
\end{frame}

\begin{frame}{Length extension attacks}{SHA-1 and SHA-2 vulnerability}
	\definitionbox{Length Extension Attack}{
		A \textbf{length extension attack} allows an attacker who knows $H(M)$ to calculate $H(M \| P)$ for some padding $P$ without knowing $M$ itself.
	}
	\begin{itemize}[<+->]
		\item Affects hash functions built using the Merkle-Damgård construction:
		      \begin{itemize}
			      \item SHA-1, SHA-256, SHA-512, MD5, and others
			      \item Not SHA-3 (which uses the sponge construction)
		      \end{itemize}
		\item An attacker who knows $H(\texttt{message})$ and the length of $\texttt{message}$ can compute $H(\texttt{message} \| \texttt{padding} \| \texttt{extra\_data})$.
		\item This can break naive authentication schemes using $H(\texttt{secret} \| \texttt{message})$.
	\end{itemize}
\end{frame}

\begin{frame}{Length extension attacks}{Real-world implications}
	\begin{itemize}[<+->]
		\item Consider a web API using:
		      \begin{itemize}
			      \item URL: \texttt{api.com/data?val=foo\&hash=123abc}
			      \item Hash calculated as: $H(\texttt{secret} \| \texttt{val=foo})$
			      \item Server verifies request by checking if hash matches
		      \end{itemize}
		\item An attacker can:
		      \begin{itemize}
			      \item Take a valid \texttt{hash} value
			      \item Compute a new hash for \texttt{val=foo\&malicious=true}
			      \item Without knowing the secret!
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{The Merkle-Damgård construction}{SHA-1, SHA-2}
	\begin{columns}[c]
		\begin{column}{0.45\textwidth}
			\begin{itemize}[<+->]
				\item Key components:
				      \begin{itemize}
					      \item Message is padded to a multiple of block size.
					      \item Split into fixed-size blocks.
					      \item Processes blocks sequentially through a compression function.
					      \item Each step combines previous state with current block.
				      \end{itemize}
				\item If compression function is collision-resistant, so is the hash function.
			\end{itemize}
		\end{column}
		\begin{column}{0.55\textwidth}
			\imagewithcaption{merkle_damgard.pdf}{Source: The Joy of Cryptography}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{The Sponge construction}{SHA-3, BLAKE}
	\begin{columns}[c]
		\begin{column}{0.55\textwidth}
			\begin{itemize}[<+->]
				\item Two phases:
				      \begin{itemize}
					      \item \textbf{Absorbing}: Input blocks are XORed into the state and processed.
					      \item \textbf{Squeezing}: Output blocks are extracted from the state.
				      \end{itemize}
				\item Naturally resistant to length extension attacks.
				\item Versatile: Can produce output of any desired length.
			\end{itemize}
		\end{column}
		\begin{column}{0.45\textwidth}
			\imagewithcaption{sponge.png}{Source: The Hash Function BLAKE (by Jean-Philippe Aumasson)}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{HMAC: Protection against length extension}
	\definitionbox{HMAC}{
		\textbf{HMAC} (Hash-based Message Authentication Code) is a specific construction for calculating a message authentication code (MAC) using a cryptographic hash function and a secret key.
	}
	\begin{align*}
		\textsf{HMAC}(K, m) = H((K \oplus opad) \| H((K \oplus ipad) \| m))
	\end{align*}
	\begin{itemize}[<+->]
		\item $opad$ and $ipad$ are fixed padding values.
		\item This nested construction defeats length extension attacks.
		\item Widely used in TLS, IPsec, and other security protocols.
		\item Provides both integrity and authentication.
	\end{itemize}
\end{frame}

\begin{frame}{Xiaoyun Wang's MD5 Collision}
	\begin{columns}[c]
		\begin{column}{1\textwidth}
			\begin{itemize}[<+->]
				\item In 2004, Chinese researcher Xiaoyun Wang demonstrated the first practical MD5 collision.
				\item Presented at the CRYPTO 2004 rump session, causing a sensation in the cryptographic community.
				\item Interesting backstory: Wang's team initially got confused by endianness issues.
				\item The Chinese translation of Bruce Schneier's ``Applied Cryptography'' had incorrectly translated the MD5 algorithm.
				\item The translation got the byte ordering (endianness) wrong, making their early collision attempts fail.
				\item Once corrected, they succeeded in breaking MD5 much faster than expected.
				\item This discovery accelerated the migration away from MD5 in security applications.
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{MD5 Chosen-Prefix Collision}{Attacking certificate authorities}
	\begin{columns}[c]
		\begin{column}{1\textwidth}
			\begin{itemize}[<+->]
				\item In 2008, researchers created a rogue CA certificate using MD5 collisions.
				\item Exploited weaknesses in how certificates were issued by a legitimate CA.
				\item By predicting serial numbers and timestamps, they crafted a malicious certificate with the same MD5 hash.
				\item Created a fake Certificate Authority that browsers would trust!
				\item Demonstrated at the 25th Chaos Communication Congress.
				\item Led to MD5 being rapidly phased out for digital signatures.
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{SHA-1 Collision Attack (SHAttered)}{The first practical SHA-1 collision}
	\begin{columns}[c]
		\begin{column}{1\textwidth}
			\begin{itemize}[<+->]
				\item In 2017, Google and CWI Amsterdam researchers demonstrated the first practical collision for SHA-1.\footnote{\url{https://appliedcryptography.page/papers/\#shattered-sha1}}
				\item Created two different PDF files with identical SHA-1 hashes.
				\item Required about 6,500 CPU years and 110 GPU years of computation.
				\item Cost estimate: approximately \$110,000 using cloud computing.
				\item Proved that SHA-1 should no longer be used for security-critical applications.
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Multi-Collision Attacks}
	\definitionbox{Multi-Collision}{
		A \textbf{multi-collision} is a set of $k$ distinct inputs that all hash to the same output value.
	}
	\begin{itemize}[<+->]
		\item Joux's 2004 multi-collision attack:
		      \begin{itemize}
			      \item Finding $2^n$ colliding messages requires only about $n$ times the work of finding a single collision.
			      \item For a 128-bit hash, finding $2^{64}$ collisions takes only about 64 times more work than finding one collision.
			      \item Much more efficient than expected from the birthday paradox!
		      \end{itemize}
		\item Implications:
		      \begin{itemize}
			      \item Concatenating two hash functions ($H_1 \| H_2$) provides much less security than expected.
			      \item Influences modern hash function design.
		      \end{itemize}
	\end{itemize}
\end{frame}

\section{Password Hashing}

\begin{frame}{Password-based authentication}{Common use of hash functions}
	\begin{itemize}[<+->]
		\item Passwords are the most common authentication mechanism.
		\item Server must verify if a user's password is correct.
		\item Different methods for password storage:
		      \begin{itemize}[<+->]
			      \item Storing in the clear (extremely bad)
			      \item Encryption (also bad)
			      \item Unsalted hashing (better, but problematic)
			      \item Salted hashing (good practice)
			      \item Specialized password hashing (best practice)
		      \end{itemize}
		\item We compare methods by asking: what happens if the server is compromised?
	\end{itemize}
\end{frame}

\begin{frame}{Storing passwords in the clear}{The worst approach}
	\begin{columns}[c]
		\begin{column}{0.55\textwidth}
			\begin{itemize}[<+->]
				\item Server simply stores exact passwords
				\item Password verification is trivial:
				      \begin{itemize}
					      \item User enters password $P'$
					      \item Server checks if $P' == P$
				      \end{itemize}
				\item If server is compromised, attacker immediately learns all passwords.
				\item Users often reuse passwords across sites, compounding the damage.
			\end{itemize}
		\end{column}
		\begin{column}{0.45\textwidth}
			\begin{tcolorbox}[colback=black!5!white,colframe=ciphergray]
				\textbf{Database Storage:}

				\vspace{0.2cm}

				\texttt{username: alice}\\
				\texttt{password: secret123}

				\vspace{0.2cm}

				\texttt{username: bob}\\
				\texttt{password: password1}

				\vspace{0.3cm}

				\textcolor{cipherprimary}{\textbf{Problem:} \small Attacker who accesses the database instantly has everyone's actual passwords!}
			\end{tcolorbox}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Encrypting passwords}{A common mistake}
	\begin{columns}[c]
		\begin{column}{0.55\textwidth}
			\begin{itemize}[<+->]
				\item Some systems try to encrypt passwords:
				      \begin{itemize}
					      \item Store $\texttt{Enc}(K, P)$ instead of $P$.
					      \item Decrypt when verifying login.
				      \end{itemize}
				\item Problem: The decryption key $K$ must be accessible to the server.
				\item If an attacker compromises the server, they get both:
				      \begin{itemize}
					      \item The encrypted passwords.
					      \item The decryption key.
				      \end{itemize}
				\item Result: Encryption adds no security!
			\end{itemize}
		\end{column}
		\begin{column}{0.45\textwidth}
			\begin{tcolorbox}[colback=black!5!white,colframe=ciphergray]
				\textbf{Encrypted Password Storage:}

				\vspace{0.2cm}

				\texttt{username: alice}\\
				\texttt{password: A7F3D92C...}

				\vspace{0.2cm}

				\texttt{decryption\_key: 5B8E1...}

				\vspace{0.3cm}

				\textcolor{cipherprimary}{\textbf{Problem:} \small Server needs the key to verify passwords, so attacker gets the key too!}
			\end{tcolorbox}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Unsalted password hashing}{A basic approach}
	\begin{columns}[c]
		\begin{column}{0.55\textwidth}
			\begin{itemize}[<+->]
				\item For a user with password $P$, the server stores $h = H(P)$.
				\item On login, server checks if $H(P') == h$.
				\item Advantages over cleartext:
				      \begin{itemize}
					      \item Attacker doesn't immediately get passwords.
					      \item Must spend effort guessing and hashing.
				      \end{itemize}
				\item Problems:
				      \begin{itemize}
					      \item Vulnerable to precomputation (rainbow tables).
					      \item Same password = same hash for all users.
				      \end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{0.45\textwidth}
			\begin{tcolorbox}[colback=black!5!white,colframe=ciphergray]
				\textbf{Unsalted Hash Storage:}

				\vspace{0.2cm}

				\texttt{username: alice}\\
				\texttt{hash: 5f4dcc3b5aa...}

				\vspace{0.2cm}

				\texttt{username: bob}\\
				\texttt{hash: 5f4dcc3b5aa...}

				\vspace{0.3cm}

				\textcolor{cipherprimary}{\textbf{Problem:} \small Alice and Bob have the same password (visible from identical hashes)!}
			\end{tcolorbox}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Limitations of unsalted hashing}
	\begin{itemize}[<+->]
		\item Attacker's work can be \textbf{precomputed}:
		      \begin{itemize}
			      \item Generate lookup tables before compromising the server.
			      \item Rainbow tables provide time-memory tradeoff.
		      \end{itemize}
		\item Same effort cracks multiple accounts:
		      \begin{itemize}
			      \item If users have same password, they have same hash.
			      \item Cracking 1,000 accounts may be no harder than cracking one.
		      \end{itemize}
		\item Common passwords are instantly recognized:
		      \begin{itemize}
			      \item $H(\texttt{password123})$ is well-known.
			      \item Attacker doesn't even need to compute hashes for common passwords.
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Salted password hashing}{The proper approach}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\definitionbox{Salted Hash Authentication}{
				For a user with password $P$, the server stores:
				\begin{itemize}
					\item A random salt $S$ (unique per user)
					\item The hash value $h = H(S \| P)$
				\end{itemize}
				To verify a login with password $P'$, the server checks if $H(S \| P') == h$.
			}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{tcolorbox}[colback=black!5!white,colframe=ciphergray]
				\small
				\textbf{Salted Hash Storage:}

				\vspace{0.2cm}

				\texttt{username: alice}\\
				\texttt{salt: 8a7b3c...}\\
				\texttt{hash: e8f74d...}

				\vspace{0.2cm}

				\texttt{username: bob}\\
				\texttt{salt: 2c9d5e...}\\
				\texttt{hash: 9f82e1...}

				\vspace{0.3cm}

				\textcolor{cipherprimary}{\textbf{Note:} \scriptsize Even if Alice and Bob have the same password, they'll have different hashes!}
			\end{tcolorbox}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Benefits of salted hashing}
	\begin{itemize}[<+->]
		\item Prevents precomputation attacks:
		      \begin{itemize}
			      \item Rainbow tables become useless.
			      \item Attacker must compute hashes after server compromise.
		      \end{itemize}
		\item Requires unique effort per user:
		      \begin{itemize}
			      \item Each password must be attacked individually.
			      \item Cracking 1,000 accounts requires 1,000 times the effort.
		      \end{itemize}
		\item Same passwords produce different hashes:
		      \begin{itemize}
			      \item Identical passwords across users aren't visible.
			      \item Doesn't leak information about password reuse.
		      \end{itemize}
		\item \textbf{Always salt your password hashes!}
	\end{itemize}
\end{frame}

\begin{frame}{Specialized password hashing functions}{Beyond regular hash functions}
	\begin{itemize}[<+->]
		\item Regular cryptographic hash functions (SHA-2, SHA-3) are designed to be \textbf{fast}.
		\item But password hashing, slower is better!
		      \begin{itemize}
			      \item Makes attacks more expensive.
			      \item Users don't notice milliseconds of delay.
			      \item Attackers trying billions of guesses definitely notice.
		      \end{itemize}
		\item Simple approach: Iterate the hash function thousands of times.
		      \begin{itemize}
			      \item $H(S, H(S, ... H(S,P)...))$ with many iterations.
			      \item \textbf{Obsolete examples}: PBKDF2.
			      \item \textbf{Modern examples}: Argon2, Scrypt
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{PBKDF2: Password-Based Key Derivation Function 2}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\definitionbox{PBKDF2}{
				\textbf{PBKDF2} (Password-Based Key Derivation Function 2) is a key derivation function that applies a pseudorandom function (like HMAC) to the input password along with a salt to produce a derived key.
			}
			\begin{itemize}[<+->]
				\item Key components:
				      \begin{itemize}
					      \item \textbf{Password}: Secret input.
					      \item \textbf{Salt}: Provides randomization.
					      \item \textbf{Iteration count}: Controls computational cost.
					      \item \textbf{PRF}: Usually HMAC-SHA1 or HMAC-SHA256.
				      \end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\begin{tcolorbox}[colback=black!5!white,colframe=ciphergray]
				\small
				\begin{align*}
					U_1 & = PRF(Password, Salt || Int(1))        \\
					U_2 & = PRF(Password, U_1)                   \\
					U_3 & = PRF(Password, U_2)                   \\
					\vdots                                       \\
					U_c & = PRF(Password, U_{c-1})               \\
					T_1 & = U_1 \oplus U_2 \oplus ... \oplus U_c \\
				\end{align*}
			\end{tcolorbox}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Why not PBKDF2?}{Vulnerable to specialized hardware}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item \textbf{Problem}: Attackers can build specialized hardware.
				      \begin{itemize}
					      \item ASICs can compute hashes millions of times faster.
					      \item Iteration alone isn't enough protection.
				      \end{itemize}
				\item \textbf{Solution}: Memory-hard functions
				      \begin{itemize}
					      \item Require significant amount of memory.
					      \item Hardware specialization offers less advantage.
					      \item Both attackers and defenders use similar memory tech.
				      \end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\imagewithcaption{gpu_farm.jpg}{A GPU farm, likely built to mine Bitcoin, but which can also be used to do a lot of hashing really fast (Bitcoin mining is just calcualting a lot of SHA-256 hashes!)}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Blockchain and hash functions}
	\begin{itemize}[<+->]
		\item Bitcoin and blockchain technology rely heavily on hash functions:
		      \begin{itemize}
			      \item \textbf{Proof-of-work}: Finding partial hash collisions (leading zeros).
			      \item \textbf{Merkle trees}: Efficient verification of large datasets.
			      \item \textbf{Block chaining}: Each block contains the hash of the previous block.
		      \end{itemize}
		\item Miners try to find inputs that produce hashes with specific properties.
		\item The extreme computational cost of Bitcoin mining (~90 TWh/year) demonstrates hash function security.
		\item Bitcoin mining consumes more electricity than many countries.
	\end{itemize}
\end{frame}

\begin{frame}{Scrypt: A memory-hard password hashing function}
	\definitionbox{Scrypt}{
		\textbf{Scrypt} is a password-based key derivation function designed to be computationally and memory-intensive, making it resistant to hardware acceleration attacks.
	}
	\begin{itemize}[<+->]
		\item Created by Colin Percival in 2009 specifically to make attacks costly.
		\item Key components:
		      \begin{itemize}
			      \item \textbf{PBKDF2}: Initial and final mixing of password and salt.
			      \item \textbf{ROMix}: Core memory-hard function.
			      \item \textbf{BlockMix}: Based on Salsa20/8 core function.
		      \end{itemize}
		\item{Parameters:}
		      \begin{itemize}
			      \item \texttt{N}: CPU/memory cost
			      \item \texttt{r}: Block size
			      \item \texttt{p}: Parallelization
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Why Scrypt is memory-hard}
	\begin{columns}[c]
		\begin{column}{1\textwidth}
			\begin{itemize}[<+->]
				\item Scrypt enforces memory hardness through its ROMix function:
				      \begin{itemize}
					      \item Creates a large array of pseudorandom values (often many MB).
					      \item Each new value depends on previous values in unpredictable patterns.
					      \item Forces the entire array to be stored in memory during computation.
				      \end{itemize}
				\item Memory hardness creates multiple benefits:
				      \begin{itemize}
					      \item GPUs/ASICs have limited memory per processing unit.
					      \item Memory is expensive and scales poorly on specialized hardware.
					      \item Time-memory tradeoffs are possible but highly unfavorable.
					      \item Using less memory makes computation exponentially slower.
				      \end{itemize}
				\item Even with custom hardware, attackers face similar costs to defenders.
				\item Proven to be maximally memory-hard!\footnote{\url{https://appliedcryptography.page/papers/\#scrypt-memory}}
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Password cracking speeds}{The importance of slow hashing}
	\begin{itemize}[<+->]
		\item Modern hardware can compute hash functions at astonishing speeds.
		\item A single high-end GPU can compute:
		      \begin{itemize}
			      \item MD5: 25+ billion hashes/second
			      \item SHA-1: 10+ billion hashes/second
			      \item SHA-256: 2+ billion hashes/second
			      \item bcrypt (cost 12): 20,000 hashes/second
			      \item Scrypt: <1,000 hashes/second
		      \end{itemize}
		\item This is why specialized password hashing algorithms are essential.
		\item The stark speed difference (billions vs. thousands) is a critical security factor.
	\end{itemize}
\end{frame}

\begin{frame}{Best practices for password hashing}
	\begin{itemize}[<+->]
		\item Use a dedicated password hashing function (not raw SHA-256).
		\item Always use random, unique salts (at least 16 bytes).
		\item Store salts alongside hashes - they don't need to be secret.
		\item Consider modern memory-hard functions like Scrypt.
		      \begin{itemize}
			      \item Tune parameters based on your server capabilities.
			      \item Aim for 0.5-1 second processing time per hash.
		      \end{itemize}
		\item Keep your hashing mechanism current:
		      \begin{itemize}
			      \item Cryptographic advice changes as attacks improve.
			      \item Be prepared to migrate to stronger algorithms.
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{``Migrate to stronger algorithms?''}
	\begin{itemize}[<+->]
		\item Cryptographic algorithms have limited lifespans:
		      \begin{itemize}
			      \item New attacks emerge over time.
			      \item Computing power continuously increases.
			      \item Quantum computers threaten some algorithms.
		      \end{itemize}
		\item \textbf{Protocol agility} refers to a system's ability to:
		      \begin{itemize}
			      \item Support multiple cryptographic algorithms.
			      \item Negotiate which algorithm to use.
			      \item Transition smoothly as algorithms are deprecated.
		      \end{itemize}
		\item Challenges with protocol agility:
		      \begin{itemize}
			      \item Complexity leads to implementation errors.
			      \item Downgrade attacks target weakest supported option.
			      \item Backward compatibility vs. security tradeoffs.
		      \end{itemize}
		\item We'll talk a lot more about all of this in Part 2 of the course.
	\end{itemize}
\end{frame}

\section{The Random Oracle Model}

\begin{frame}{Hash functions can't be truly pseudorandom}
	\begin{itemize}[<+->]
		\item Any deterministic algorithm cannot produce truly random output.
		\item Hash functions only statistically approximate pseudorandomness:
		      \begin{itemize}
			      \item They attempt to distribute outputs uniformly across their range,
			      \item They aim to make outputs appear uncorrelated with inputs,
			      \item But they remain deterministic functions.
		      \end{itemize}
		\item But we analyze hash functions as if they were truly random oracles!
		      \begin{itemize}
			      \item This creates a gap between theory and implementation.
			      \item Implementations can only ever approximate ideal properties.
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{The Random Oracle Model}
	\definitionbox{Random Oracle Model}{
		The \textbf{Random Oracle Model} is a theoretical framework that models hash functions as truly random functions that can be queried by all parties.
	}
	\begin{itemize}[<+->]
		\item A random oracle is an idealized black box that:
		      \begin{itemize}
			      \item Responds to new queries with truly random outputs.
			      \item Consistently returns the same output when queried with the same input.
			      \item Can be accessed by all parties (both honest and adversarial).
		      \end{itemize}
		\item Provides a mathematical abstraction that's easier to analyze than actual hash functions
	\end{itemize}
\end{frame}

\begin{frame}{Using the Random Oracle Model}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item Used to prove security of cryptographic protocols:
				      \begin{itemize}
					      \item Allows rigorous mathematical analysis.
					      \item Simplifies proofs that would otherwise be intractable.
					      \item Many important schemes are proven secure in this model.
				      \end{itemize}
				\item Example: OAEP for RSA encryption.
				\item Provides confidence in schemes before deployment.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item \textbf{Proving in the ROM:}
				      \begin{enumerate}
					      \item Replace hash function with random oracle
					      \item Show adversary has negligible advantage.
					      \item Conclude the scheme is secure (assuming the hash function behaves like a random oracle).
				      \end{enumerate}
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Limitations of the Random Oracle Model}
	\begin{columns}
		\begin{column}{1\textwidth}
			\begin{itemize}[<+->]
				\item \textbf{Gap between theory and practice}:
				      \begin{itemize}
					      \item No real hash function can perfectly implement a random oracle.
					      \item Schemes secure in the RO model might be insecure when implemented with real hash functions.
				      \end{itemize}
				\item \textbf{Artificial counterexamples exist}:
				      \begin{itemize}
					      \item Researchers have constructed schemes that are:
					      \item Provably secure in the RO model, but,
					      \item Provably insecure with any real hash function.\footnote{\url{https://appliedcryptography.page/papers/\#rom-methodology}}
				      \end{itemize}
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}[plain]
	\titlepage
\end{frame}
\end{document}