nadim/appliedcryptography
SHA256
1
Fork 0
Code Wiki Activity

Website: greatly improved materials viewing experience

Browse source
This commit is contained in:
Nadim Kobeissi 2025-06-26 13:13:47 +02:00
parent 4b6498ede3
commit d5a06032b0
Signed by: nadim
SSH key fingerprint: SHA256:o0JJHYcP8LVBoARMU+JjVbzJxL3HxW2F+C0yu/5zPgc
406 changed files with 159269 additions and 184 deletions
Download patch file Download diff file Expand all files Collapse all files

54
slides/1-4.tex
View file

@ -1441,7 +1441,7 @@
\begin{columns}[c]
\begin{column}{0.4\textwidth}
\begin{itemize}[<+->]
\item Luby and Rackoff proved that a 3-round Feistel cipher is indistinguishable from a pseudorandom permutation.\footnote{\url{https://appliedcryptography.page/papers/luby-rackoff.pdf}}
\item Luby and Rackoff proved that a 3-round Feistel cipher is indistinguishable from a pseudorandom permutation.\footnote{\url{https://appliedcryptography.page/papers/\#luby-rackoff}}
\item Can we also prove it using our provable security framework?
\end{itemize}
\end{column}
@ -1520,7 +1520,7 @@
\begin{columns}[c]
\begin{column}{0.4\textwidth}
\begin{itemize}
\item Luby and Rackoff proved that a 3-round Feistel cipher is indistinguishable from a pseudorandom permutation.\footnote{\url{https://appliedcryptography.page/papers/luby-rackoff.pdf}}
\item Luby and Rackoff proved that a 3-round Feistel cipher is indistinguishable from a pseudorandom permutation.\footnote{\url{https://appliedcryptography.page/papers/\#luby-rackoff}}
\item Can we also prove it using our provable security framework?
\item Yes, with the bad events proof technique!
\end{itemize}
@ -2130,31 +2130,31 @@
\end{frame}
\begin{frame}{AES: security and attacks over time}
\begin{columns}[c]
\begin{column}{0.5\textwidth}
\begin{itemize}[<+->]
\item AES has been heavily analyzed for over 20 years.
\item Best attacks against full AES have gradually improved:
\begin{itemize}[<+->]
\item 2011: Biclique attack (Bogdanov et al.) reduced complexity to $2^{126.1}$ for AES-128.
\item Various side-channel attacks developed (power analysis, cache timing).\footnote{This is the main way to attack AES in practice. Side-channel attacks will be discussed in more depth later in the course.}
\item Advances in meet-in-the-middle and related-key techniques.
\end{itemize}
\end{itemize}
\end{column}
\begin{column}{0.5\textwidth}
\begin{itemize}[<+->]
\item Despite these advances:
\begin{itemize}[<+->]
\item No practical attacks on full AES-128.
\item Best attacks still require $\approx 2^{126}$ operations.
\item At this complexity, attacks remain purely theoretical.
\item Would require resources far exceeding global computing power.
\end{itemize}
\item Even quantum computers offer only modest advantage (Grover's algorithm reduces security to $2^{64}$ operations).\footnote{More on quantum computers and how they affect cryptography later in the course.}
\end{itemize}
\end{column}
\end{columns}
\begin{columns}[c]
\begin{column}{0.5\textwidth}
\begin{itemize}[<+->]
\item AES has been heavily analyzed for over 20 years.
\item Best attacks against full AES have gradually improved:
\begin{itemize}[<+->]
\item 2011: Biclique attack (Bogdanov et al.) reduced complexity to $2^{126.1}$ for AES-128.
\item Various side-channel attacks developed (power analysis, cache timing).\footnote{This is the main way to attack AES in practice. Side-channel attacks will be discussed in more depth later in the course.}
\item Advances in meet-in-the-middle and related-key techniques.
\end{itemize}
\end{itemize}
\end{column}
\begin{column}{0.5\textwidth}
\begin{itemize}[<+->]
\item Despite these advances:
\begin{itemize}[<+->]
\item No practical attacks on full AES-128.
\item Best attacks still require $\approx 2^{126}$ operations.
\item At this complexity, attacks remain purely theoretical.
\item Would require resources far exceeding global computing power.
\end{itemize}
\item Even quantum computers offer only modest advantage (Grover's algorithm reduces security to $2^{64}$ operations).\footnote{More on quantum computers and how they affect cryptography later in the course.}
\end{itemize}
\end{column}
\end{columns}
\end{frame}
\begin{frame}[plain]

8
slides/1-5.tex
View file

@ -640,7 +640,7 @@
\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.pdf}}
\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}
@ -655,7 +655,7 @@
\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.pdf}}
\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}
@ -671,7 +671,7 @@
\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.pdf}}
\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
@ -1466,7 +1466,7 @@
\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.pdf}}
\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$.

6
slides/1-6.tex
View file

@ -541,7 +541,7 @@
\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.pdf}}
\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.
@ -907,7 +907,7 @@
\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.pdf}}
\item Proven to be maximally memory-hard!\footnote{\url{https://appliedcryptography.page/papers/\#scrypt-memory}}
\end{itemize}
\end{column}
\end{columns}
@ -1045,7 +1045,7 @@
\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.pdf}}
\item Provably insecure with any real hash function.\footnote{\url{https://appliedcryptography.page/papers/\#rom-methodology}}
\end{itemize}
\end{itemize}
\end{column}

2
slides/1-7.tex
View file

@ -627,7 +627,7 @@
\begin{columns}[c]
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{Games proven NP-hard\footnote{\url{https://appliedcryptography.page/papers/nintendo-hard.pdf}}}:
\item \textbf{Games proven NP-hard\footnote{\url{https://appliedcryptography.page/papers/\#nintendo-hard}}}:
\begin{itemize}
\item Super Mario Bros. 1–3, The Lost Levels, Super Mario World
\item Donkey Kong Country 1–3

2
slides/1-8.tex
View file

@ -845,7 +845,7 @@
\end{itemize}
\item \textbf{Real-world example:} Found in TLS-ECDH implementations (2015).
\begin{itemize}
\item Paper: ``Practical Invalid Curve Attacks on TLS-ECDH''\footnote{\url{https://appliedcryptography.page/papers/invalid-curve.pdf}}
\item Paper: ``Practical Invalid Curve Attacks on TLS-ECDH''\footnote{\url{https://appliedcryptography.page/papers/\#invalid-curve}}
\item Jager, Schwenk, and Somorovsky
\end{itemize}
\item \textbf{Prevention:} Always validate that points satisfy the correct curve equation.

16
slides/2-1.tex
View file

@ -1293,7 +1293,7 @@
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{Target}: TLS's CBC (Cipher Block Chaining) mode with HMAC
\item \textbf{The vulnerability}: Timing differences in MAC verification\footnote{\url{https://appliedcryptography.page/papers/lucky-thirteen.pdf}}
\item \textbf{The vulnerability}: Timing differences in MAC verification\footnote{\url{https://appliedcryptography.page/papers/\#lucky-thirteen}}
\begin{itemize}
\item TLS 1.0-1.2 used MAC-then-encrypt with CBC mode
\item Padding oracle attacks exploit timing differences
@ -1363,7 +1363,7 @@
\begin{columns}[c]
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{Full name}: Padding Oracle On Downgraded Legacy Encryption\footnote{\url{https://appliedcryptography.page/papers/google-poodle.pdf}}
\item \textbf{Full name}: Padding Oracle On Downgraded Legacy Encryption\footnote{\url{https://appliedcryptography.page/papers/\#google-poodle}}
\item \textbf{Target}: SSL 3.0 (ancient protocol from 1996)
\item \textbf{The setup}:
\begin{itemize}
@ -1437,7 +1437,7 @@
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{Discovered by}: Inria Prosecco team (future TLS 1.3 verifiers!)
\item \textbf{Core problem}: TLS handshake can be \textbf{resumed} with different certificates\footnote{\url{https://appliedcryptography.page/papers/triple-handshakes.pdf}}
\item \textbf{Core problem}: TLS handshake can be \textbf{resumed} with different certificates\footnote{\url{https://appliedcryptography.page/papers/\#triple-handshakes}}
\begin{itemize}
\item Client connects to Server A, establishes session
\item Session can be resumed with Server B using different certificate
@ -1503,7 +1503,7 @@
\begin{columns}[c]
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{Not a protocol flaw}: Implementation bug in OpenSSL\footnote{\url{https://appliedcryptography.page/papers/matter-heartbleed.pdf}}
\item \textbf{Not a protocol flaw}: Implementation bug in OpenSSL\footnote{\url{https://appliedcryptography.page/papers/\#matter-heartbleed}}
\item \textbf{The vulnerability}: Buffer over-read in heartbeat extension
\begin{itemize}
\item Heartbeat: ``keep-alive'' mechanism for TLS
@ -1602,7 +1602,7 @@
\begin{columns}[c]
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{Research by}: Inria Prosecco team (again!)\footnote{\url{https://appliedcryptography.page/papers/smack-tls.pdf}}
\item \textbf{Research by}: Inria Prosecco team (again!)\footnote{\url{https://appliedcryptography.page/papers/\#smack-tls}}
\item \textbf{Two major attack classes discovered}:
\begin{itemize}
\item \textbf{SMACK}: State Machine AttaCKs
@ -1803,7 +1803,7 @@
\begin{columns}[c]
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{Research team}: 14 researchers from 10 institutions\footnote{\url{https://appliedcryptography.page/papers/imperfect-dh.pdf}}
\item \textbf{Research team}: 14 researchers from 10 institutions\footnote{\url{https://appliedcryptography.page/papers/\#imperfect-dh}}
\item \textbf{Target}: Diffie-Hellman key exchange in TLS
\item \textbf{Two main attacks}:
\begin{itemize}
@ -1930,7 +1930,7 @@
\begin{columns}[c]
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{Researchers}: Karthikeyan Bhargavan and Gaëtan Leurent (Inria)\footnote{\url{https://appliedcryptography.page/papers/inria-sweet32.pdf}}
\item \textbf{Researchers}: Karthikeyan Bhargavan and Gaëtan Leurent (Inria)\footnote{\url{https://appliedcryptography.page/papers/\#inria-sweet32}}
\item \textbf{Target}: 64-bit block ciphers (3DES, Blowfish)
\item \textbf{Core vulnerability}: Birthday paradox in block cipher usage
\begin{itemize}
@ -2002,7 +2002,7 @@
\begin{columns}[c]
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{Researchers}: Karthikeyan Bhargavan and Gaëtan Leurent (Inria)\footnote{\url{https://appliedcryptography.page/papers/inria-collisions.pdf}}
\item \textbf{Researchers}: Karthikeyan Bhargavan and Gaëtan Leurent (Inria)\footnote{\url{https://appliedcryptography.page/papers/\#inria-collisions}}
\item \textbf{Novel attack class}: Hash collision attacks on protocol transcripts
\item \textbf{Core idea}:
\begin{itemize}

10
slides/2-2.tex
View file

@ -292,7 +292,7 @@
\begin{columns}[c]
\begin{column}{1\textwidth}
\begin{itemize}[<+->]
\item \textbf{The Discovery:} Certain key patterns create predictable initial states\footnote{\url{https://appliedcryptography.page/papers/rc4-ksa.pdf}}
\item \textbf{The Discovery:} Certain key patterns create predictable initial states\footnote{\url{https://appliedcryptography.page/papers/\#rc4-ksa}}
\item \textbf{Weak Key Pattern:} Keys of the form $(K_1, K_2, \ldots, K_n, 3, 255, \ldots)$
\begin{itemize}[<+->]
\item When byte 3 of the key is 3, and byte 4 is 255
@ -667,7 +667,7 @@
\begin{columns}[c]
\begin{column}{0.6\textwidth}
\begin{itemize}[<+->]
\item \textbf{The discovery:} RC4's biases are exploitable in TLS:\footnote{\url{https://appliedcryptography.page/papers/rc4-tls.pdf}}
\item \textbf{The discovery:} RC4's biases are exploitable in TLS:\footnote{\url{https://appliedcryptography.page/papers/\#rc4-tls}}
\begin{itemize}[<+->]
\item First 256 bytes of keystream heavily biased
\item Certain byte positions more predictable than others
@ -728,7 +728,7 @@
\item Took days or weeks to execute
\item Many dismissed it as theoretical
\end{itemize}
\item \textbf{Insight:} Target password verifiers, not cookies\footnote{\url{https://appliedcryptography.page/papers/rc4-attacks.pdf}}
\item \textbf{Insight:} Target password verifiers, not cookies\footnote{\url{https://appliedcryptography.page/papers/\#rc4-attacks}}
\begin{itemize}[<+->]
\item Basic Authentication sends passwords in every request
\item IMAP/SMTP use similar repeated authentication
@ -743,7 +743,7 @@
\item Exploit password character distributions
\item Use Mantin's ABSAB bias (positions 1-4)
\item Combine with dictionary attacks
\item Other attack papers use similar techniques, including to break WPA-TKIP, a successor to WEP!\footnote{\url{https://appliedcryptography.page/papers/rc4-biases.pdf}}
\item Other attack papers use similar techniques, including to break WPA-TKIP, a successor to WEP!\footnote{\url{https://appliedcryptography.page/papers/\#rc4-biases}}
\end{itemize}
\end{itemize}
\end{column}
@ -752,7 +752,7 @@
\begin{frame}{Mantin's ABSAB bias (2005)}
\begin{itemize}[<+->]
\item \textbf{The discovery:} Certain digraph patterns repeat with anomalous frequency\footnote{\url{https://appliedcryptography.page/papers/rc4-absab.pdf}}
\item \textbf{The discovery:} Certain digraph patterns repeat with anomalous frequency\footnote{\url{https://appliedcryptography.page/papers/\#rc4-absab}}
\begin{itemize}[<+->]
\item Pattern: Two characters repeat after a gap (e.g., ABAB, ABCAB)
\item Occurs when value 1 is used to update index $j$ in RC4

8
slides/2-3.tex
View file

@ -133,7 +133,7 @@
\begin{itemize}
\item \textbf{Usability nightmare}
\begin{itemize}
\item ``Why Johnny Can't Encrypt'' (1999) - landmark usability study\footnote{\url{https://appliedcryptography.page/papers/johnny-cant.pdf}}
\item ``Why Johnny Can't Encrypt'' (1999) - landmark usability study\footnote{\url{https://appliedcryptography.page/papers/\#johnny-cant}}
\item Key management too complex for average users
\item Easy to make catastrophic mistakes
\end{itemize}
@ -860,7 +860,7 @@
\begin{frame}{Enter HKDF: HMAC-based Key Derivation Function}
\begin{columns}[c]
\begin{column}{0.5\textwidth}
\textbf{Motivated by real needs:}\footnote{\url{https://appliedcryptography.page/papers/hkdf-scheme.pdf}}
\textbf{Motivated by real needs:}\footnote{\url{https://appliedcryptography.page/papers/\#hkdf-scheme}}
\begin{itemize}
\item OTR, TLS, IPsec all needed KDFs
\item Each had ad-hoc solutions
@ -1134,7 +1134,7 @@
\begin{frame}{Attacks on OTR version 2}
\begin{columns}
\begin{column}{0.5\textwidth}
\textbf{Version Rollback Attack}\footnote{\url{https://appliedcryptography.page/papers/otr-analysis.pdf}}
\textbf{Version Rollback Attack}\footnote{\url{https://appliedcryptography.page/papers/\#otr-analysis}}
\begin{itemize}
\item Version negotiation happens before authentication
\item Attacker can force use of older, weaker version
@ -1516,7 +1516,7 @@
\begin{columns}[c]
\begin{column}{1\textwidth}
\begin{center}
\Large \textbf{The Promise and Reality of Post-Compromise Security}\footnote{\url{https://appliedcryptography.page/papers/pcs-impossibility.pdf}}
\Large \textbf{The Promise and Reality of Post-Compromise Security}\footnote{\url{https://appliedcryptography.page/papers/\#pcs-impossibility}}
\end{center}
\vspace{1em}
\begin{itemize}