1300 lines
55 KiB
TeX
1300 lines
55 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.8: Elliptic Curves \&\\Digital Signatures}
|
|
\coverwebsite{https://appliedcryptography.page}
|
|
|
|
\begin{document}
|
|
\begin{frame}[plain]
|
|
\titlepage
|
|
\end{frame}
|
|
|
|
\section{Elliptic Curves: Theory}
|
|
|
|
\begin{frame}{Elliptic-curve cryptography}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Revolutionary introduction (1985):} Elliptic Curve Cryptography (ECC) transformed public-key cryptography.
|
|
\item \textbf{Superior efficiency:} More powerful than RSA and classical Diffie-Hellman.
|
|
\begin{itemize}
|
|
\item ECC with 256-bit key $\approx$ RSA with 4,096-bit key (security).
|
|
\item Significantly smaller key sizes for equivalent security.
|
|
\end{itemize}
|
|
\item \textbf{Mathematical foundation:} Operations on points of elliptic curves.
|
|
\begin{itemize}
|
|
\item Many curve types: simple/sophisticated, efficient/inefficient, secure/insecure.
|
|
\end{itemize}
|
|
\item \textbf{Adoption timeline:}
|
|
\begin{itemize}
|
|
\item Early 2000s: Standardization bodies.
|
|
\item 2005: OpenSSL support.
|
|
\item 2011: OpenSSH support.
|
|
\end{itemize}
|
|
\item \textbf{Current applications:} HTTPS, mobile phones, blockchain (Bitcoin, Ethereum).
|
|
\item \textbf{Based on ECDLP:} Elliptic Curve Discrete Logarithm Problem.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Why elliptic curve cryptography matters}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Key size efficiency:} ECC provides equivalent security with much smaller keys.
|
|
\begin{itemize}
|
|
\item 256-bit ECC key $\simeq$ 4,096-bit RSA key $\simeq$ 15,360-bit finite field DH.
|
|
\item Exponential security advantage as key sizes increase.
|
|
\end{itemize}
|
|
\item \textbf{Performance benefits:}
|
|
\begin{itemize}
|
|
\item Faster key generation, signing, and verification.
|
|
\item Lower computational overhead.
|
|
\item Reduced memory usage.
|
|
\end{itemize}
|
|
\item \textbf{Bandwidth efficiency:} Smaller certificates, signatures, and key exchanges.
|
|
\item \textbf{Mobile and IoT devices:} Critical for resource-constrained environments.
|
|
\begin{itemize}
|
|
\item Limited battery life.
|
|
\item Constrained processing power.
|
|
\item Minimal storage capacity.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{ECDH vs. finite field Diffie-Hellman}
|
|
\begin{columns}
|
|
\begin{column}{0.5\textwidth}
|
|
\textbf{Traditional Finite Field DH:}
|
|
\begin{itemize}[<+->]
|
|
\item Works in multiplicative group $\mathbb{Z}_p^*$
|
|
\item Security based on discrete log in $\mathbb{Z}_p^*$
|
|
\item Requires large primes (2048+ bits)
|
|
\item Key exchange: $g^{ab} \bmod p$
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\textbf{Elliptic Curve DH (ECDH):}
|
|
\begin{itemize}[<+->]
|
|
\item Works on elliptic curve group
|
|
\item Security based on ECDLP\footnote{Elliptic-curve discrete logarithm problem}
|
|
\item Requires smaller keys (256 bits)
|
|
\item Key exchange: $a \cdot (b \cdot G)$
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\vspace{0.5cm}
|
|
\textbf{ECDH advantages:}
|
|
\begin{itemize}
|
|
\item \textbf{Efficiency:} 10-40x faster than finite field DH for equivalent security.
|
|
\item \textbf{Scalability:} Performance gap widens with higher security levels.
|
|
\item \textbf{Standards compliance:} Widely adopted (TLS 1.3, Signal Protocol, etc.)
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Why finite field DH attacks don't work on ECDH}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Different mathematical structures:}
|
|
\begin{itemize}
|
|
\item Finite field DH: multiplicative group $\mathbb{Z}_p^*$ with multiplication.
|
|
\item ECDH: elliptic curve group with point addition (geometrically defined).
|
|
\end{itemize}
|
|
\item \textbf{Index calculus attack limitation:}
|
|
\begin{itemize}
|
|
\item Works on finite fields: factorize $g^x$ using small primes.
|
|
\item Fails on elliptic curves: no equivalent of ``small primes'' for points.
|
|
\item Elliptic curve points cannot be ``factorized'' in the same way.
|
|
\end{itemize}
|
|
\item \textbf{Subexponential vs. exponential algorithms:}
|
|
\begin{itemize}
|
|
\item Finite field DL: subexponential algorithms exist (index calculus variants).
|
|
\item ECDLP: only exponential algorithms known (Pollard's rho, brute force).
|
|
\end{itemize}
|
|
\item \textbf{Algebraic structure protection:}
|
|
\begin{itemize}
|
|
\item Elliptic curve addition is more ``rigid'' than modular multiplication.
|
|
\item Geometric constraints prevent many algebraic manipulation attacks.
|
|
\end{itemize}
|
|
\item \textbf{Result:} ECDH requires exponentially more work to break $\rightarrow$ smaller key sizes.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Very intuitively}
|
|
\begin{columns}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{clock_13.jpg}{Finite-field Diffie-Hellman's structure allows for certain mathematically efficient attacks.}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{persistence_of_memory.jpg}{Let's make that structure ``weirder'' using elliptic curves and avoid these attacks. Source: Salvador Dali}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{What is an elliptic curve?}
|
|
\begin{columns}
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Definition:} An elliptic curve is a curve on a plane—a set of points with $x$- and $y$-coordinates.
|
|
\item \textbf{Curve equations:} A curve's equation defines all the points that belong to that curve.
|
|
\item \textbf{Examples of curves:}
|
|
\begin{itemize}[<+->]
|
|
\item $y = 3$: horizontal line with vertical coordinate 3
|
|
\item $y = ax + b$: straight lines (with fixed $a$, $b$)
|
|
\item $x^2 + y^2 = 1$: circle of radius 1 centered on origin
|
|
\end{itemize}
|
|
\item \textbf{Key concept:} Points on a curve are $(x, y)$ pairs that satisfy the curve's equation.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\imagewithcaption{elliptic_curve_real.png}{An elliptic curve with the equation $y^2 = x^3 - 4x$.\\Source: Serious Cryptography}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{What is an elliptic curve?}
|
|
\begin{columns}
|
|
\begin{column}{0.6\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Weierstrass form:} In cryptography, elliptic curves typically have equation:
|
|
$$y^2 = x^3 + ax + b$$
|
|
\item \textbf{Shape parameters:} Constants $a$ and $b$ define the shape of the curve.
|
|
\item \textbf{Example:} The elliptic curve $y^2 = x^3 - 4x$
|
|
\begin{itemize}
|
|
\item Here: $a = 0$ and $b = -4$
|
|
\item Creates a characteristic symmetric curve
|
|
\end{itemize}
|
|
\item \textbf{Geometric properties:} Elliptic curves have special addition properties that make them useful for cryptography.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\imagewithcaption{elliptic_curve_real.png}{An elliptic curve with the equation $y^2 = x^3 - 4x$.\\Source: Serious Cryptography}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Elliptic curves over real numbers vs. integers}
|
|
\begin{columns}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{elliptic_curve_real.png}{Elliptic curve over the real numbers (includes negative numbers, decimals)...}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{elliptic_curve_integers.png}{Same elliptic curve over the integers (only whole positive numbers)}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Adding two points on an elliptic curve}
|
|
\begin{columns}
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item Point addition follows a simple geometric process:
|
|
\begin{itemize}
|
|
\item Draw the line that connects points $P$ and $Q$.
|
|
\item Find the other point where this line intersects the curve.
|
|
\item $R$ is the reflection of this intersection point with respect to the $x$-axis.
|
|
\end{itemize}
|
|
\item \textbf{Result:} Point $P + Q$ has the same $x$-coordinate as the intersection but the inverse $y$-coordinate.
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{elliptic_curve_add.png}{Adding two points on an elliptic curve.\\Source: Serious Cryptography}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Doubling a point on an elliptic curve}
|
|
\begin{columns}
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Point doubling:} When $P = Q$, adding $P$ and $Q$ is equivalent to computing $P + P = 2P$.
|
|
\item \textbf{Geometric process:}
|
|
\begin{itemize}
|
|
\item Can't draw a line between $P$ and itself.
|
|
\item Instead, draw the line tangent to the curve at point $P$.
|
|
\item Find where this tangent line intersects the curve.
|
|
\item $2P$ is the reflection of this intersection point with respect to the $x$-axis.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{elliptic_curve_double.png}{Doubling a point on an elliptic curve.\\Source: Serious Cryptography}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Remember this?}{We need an equivalent for elliptic curves}
|
|
\begin{itemize}[<+->]
|
|
\item The discrete logarithm problem:
|
|
\begin{itemize}
|
|
\item Given a finite cyclic group $G$, a generator $g \in G$, and an element
|
|
$h \in G$, find the integer $x$ such that $g^{x}=h$
|
|
\end{itemize}
|
|
\item In more concrete terms:
|
|
\begin{itemize}
|
|
\item Let $p$ be a large prime and let $g$ be a generator of the multiplicative
|
|
group $\mathbb{Z}_{p}^{*}$ (all nonzero integers modulo $p$).
|
|
\item Given:
|
|
\begin{itemize}
|
|
\item $g \in \mathbb{Z}_{p}^{*}$, $h \in \mathbb{Z}_{p}^{*}$
|
|
|
|
\item Find $x \in \{0, 1, \ldots, p-2\}$ such that $g^{x} \equiv h \pmod
|
|
{p}$
|
|
\end{itemize}
|
|
\item This problem is believed to be computationally hard when $p$ is large
|
|
and $g$ is a primitive root modulo $p$.
|
|
\begin{itemize}
|
|
\item ``Believed to be'' = we don't know of any way to do it that doesn't
|
|
take forever, unless we have a strong, stable quantum computer (Shor's
|
|
algorithm)
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Group structure of elliptic curves}
|
|
We need to define all these operations so that our elliptic curve have a group structure, allowing us to then use them as a new basis for Diffie-Hellman, and then do DH using point addition instead of modular multiplication.
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Closure property:} If points $P$ and $Q$ belong to a curve, then $P + Q$ also belongs to the curve.
|
|
\item \textbf{Associativity:} $(P + Q) + R = P + (Q + R)$ for any points $P$, $Q$, and $R$.
|
|
\item \textbf{Identity element:} The \emph{point at infinity} $\mathcal{O}$ such that $P + \mathcal{O} = P$ for any $P$.
|
|
\item \textbf{Inverse elements:} Every point $P = (x_P, y_P)$ has an inverse $-P = (x_P, -y_P)$ such that $P + (-P) = \mathcal{O}$.
|
|
\item Great! We have a group structure!
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Elliptic curves over finite fields}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Practical implementation:} Most elliptic curve cryptosystems work with coordinates modulo a prime $p$.
|
|
\begin{itemize}
|
|
\item Coordinates are numbers in the finite field $\mathbb{Z}_p$.
|
|
\item Same geometric operations, but computed modulo $p$.
|
|
\end{itemize}
|
|
\item \textbf{Security foundation:} Security depends on the \emph{cardinality} (number of points) on the curve.
|
|
\begin{itemize}
|
|
\item Analogous to how RSA security depends on the size of numbers used.
|
|
\item More points $\rightarrow$ harder discrete logarithm problem.
|
|
\end{itemize}
|
|
\item \textbf{Curve cardinality:} The number of points depends on:
|
|
\begin{itemize}
|
|
\item The specific curve equation (parameters $a$ and $b$).
|
|
\item The prime modulus $p$.
|
|
\item Can be computed using specialized algorithms.
|
|
\end{itemize}
|
|
\item \textbf{Why finite fields?} Infinite precision real numbers are impractical for computers.
|
|
\begin{itemize}
|
|
\item Finite field arithmetic is exact and efficient.
|
|
\item Discrete structure enables cryptographic security.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{The elliptic curve discrete logarithm problem (ECDLP)}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Remember the original DLP:} Given $g$, $h$, and prime $p$, find $x$ such that $g^x \equiv h \pmod{p}$.
|
|
\item \textbf{ECDLP is the elliptic curve version:}
|
|
\begin{itemize}
|
|
\item Given an elliptic curve and a base point $G$ on that curve,
|
|
\item Given another point $H$ on the same curve,
|
|
\item Find the integer $k$ such that $k \cdot G = H$.
|
|
\end{itemize}
|
|
\item \textbf{Why is this hard?}
|
|
\begin{itemize}
|
|
\item Easy direction: Given $k$ and $G$, computing $k \cdot G$ is efficient.
|
|
\item Hard direction: Given $G$ and $H = k \cdot G$, finding $k$ is very difficult.
|
|
\item No known efficient algorithms (except with quantum computers).
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Diffie-Hellman key agreement over elliptic curves}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Classical Diffie-Hellman recap:}
|
|
\begin{itemize}
|
|
\item Alice picks secret $a$, computes $A = g^a$, sends $A$ to Bob
|
|
\item Bob picks secret $b$, computes $B = g^b$, sends $B$ to Alice
|
|
\item Both compute shared secret: $A^b = B^a = g^{ab}$
|
|
\end{itemize}
|
|
\item \textbf{Elliptic Curve Diffie-Hellman (ECDH):}
|
|
\begin{itemize}
|
|
\item Alice picks secret $a$, computes $A = a \cdot G$, sends $A$ to Bob
|
|
\item Bob picks secret $b$, computes $B = b \cdot G$, sends $B$ to Alice
|
|
\item Both compute shared secret: $a \cdot B = b \cdot A = ab \cdot G$
|
|
\end{itemize}
|
|
\item \textbf{Key differences:}
|
|
\begin{itemize}
|
|
\item Exponentiation $g^x$ $\rightarrow$ Scalar multiplication $x \cdot G$
|
|
\item Modular arithmetic $\rightarrow$ Elliptic curve point operations
|
|
\item Generator $g$ $\rightarrow$ Base point $G$
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\section{Digital Signatures}
|
|
\begin{frame}{Digital signatures with elliptic curves}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Why elliptic curve signatures?} Same advantages as ECDH:
|
|
\begin{itemize}
|
|
\item Smaller signatures for equivalent security.
|
|
\item Faster generation and verification.
|
|
\item Better performance on mobile/IoT devices.
|
|
\end{itemize}
|
|
\item \textbf{Two main approaches:}
|
|
\begin{itemize}
|
|
\item \textbf{ECDSA:} Elliptic Curve Digital Signature Algorithm (1990s).
|
|
\item \textbf{EdDSA:} Edwards-curve Digital Signature Algorithm (2011).
|
|
\end{itemize}
|
|
\item \textbf{Real-world adoption:}
|
|
\begin{itemize}
|
|
\item ECDSA: Bitcoin, Ethereum, TLS, SSH.
|
|
\item Ed25519: OpenSSH, Signal Protocol, many modern systems.
|
|
\end{itemize}
|
|
\item \textbf{Key insight:} Replace RSA's modular exponentiation with elliptic curve point multiplication.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{ECDSA: The established standard}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Elliptic Curve Digital Signature Algorithm (ECDSA):}
|
|
\begin{itemize}
|
|
\item NIST standardized in the early 1990s.
|
|
\item Elliptic curve version of the Digital Signature Algorithm (DSA).
|
|
\item Widely adopted in blockchain and web security.
|
|
\end{itemize}
|
|
\item \textbf{Key components:}
|
|
\begin{itemize}
|
|
\item Private key: secret number $d$
|
|
\item Public key: elliptic curve point $P = d \cdot G$
|
|
\item Base point $G$ on agreed elliptic curve
|
|
\end{itemize}
|
|
\item \textbf{Security foundation:} Based on ECDLP hardness.
|
|
\item \textbf{Signature format:} Two numbers $(r, s)$
|
|
\begin{itemize}
|
|
\item For 256-bit curves: 512-bit total signature size.
|
|
\item Much smaller than equivalent RSA signatures.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{ECDSA signature generation}
|
|
\begin{columns}
|
|
\begin{column}{0.6\textwidth}
|
|
\textbf{Input:} Message $M$, private key $d$
|
|
\begin{enumerate}[<+->]
|
|
\item \textbf{Hash the message:} $h = \text{Hash}(M)$
|
|
\begin{itemize}
|
|
\item Use SHA-256, SHA-3, or similar
|
|
\item Interpret hash as number $h \in [0, n-1]$
|
|
\end{itemize}
|
|
\item \textbf{Generate random nonce:} Pick random $k \in [1, n-1]$
|
|
\item \textbf{Compute signature point:} $k \cdot G = (x, y)$
|
|
\item \textbf{Calculate $r$:} $r = x \bmod n$
|
|
\item \textbf{Calculate $s$:} $s = \frac{h + rd}{k} \bmod n$
|
|
\item \textbf{Output signature:} $(r, s)$
|
|
\end{enumerate}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\textbf{Critical requirement:}
|
|
\begin{itemize}[<+->]
|
|
\item Random $k$ must be:
|
|
\begin{itemize}
|
|
\item Cryptographically random
|
|
\item Different for every signature
|
|
\item Never reused
|
|
\end{itemize}
|
|
\item \textbf{Reusing $k$ = private key exposure!}
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{ECDSA signature verification}
|
|
\begin{columns}
|
|
\begin{column}{0.6\textwidth}
|
|
\textbf{Input:} Message $M$, signature $(r, s)$, public key $P$
|
|
\begin{enumerate}[<+->]
|
|
\item \textbf{Hash the message:} $h = \text{Hash}(M)$
|
|
\item \textbf{Compute modular inverse:} $w = \frac{1}{s} \bmod n$
|
|
\item \textbf{Calculate verification values:}
|
|
\begin{itemize}
|
|
\item $u = h \cdot w \bmod n$
|
|
\item $v = r \cdot w \bmod n$
|
|
\end{itemize}
|
|
\item \textbf{Compute verification point:} $Q = u \cdot G + v \cdot P$
|
|
\item \textbf{Check signature:} Accept if $Q_x = r$
|
|
\end{enumerate}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\textbf{Why this works:}
|
|
\begin{itemize}[<+->]
|
|
\item Mathematical relationship:
|
|
\begin{align*}
|
|
Q & = u \cdot G + v \cdot P \\
|
|
& = u \cdot G + v \cdot d \cdot G \\
|
|
& = (u + vd) \cdot G
|
|
\end{align*}
|
|
\item When signature is valid:
|
|
$$u + vd = k \bmod n$$
|
|
\item So $Q = k \cdot G$, giving $Q_x = r$
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{EdDSA: The modern alternative}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Background:} Built on Schnorr signatures (1989).
|
|
\begin{itemize}
|
|
\item Schnorr's patent prevented adoption until 2008.
|
|
\item Edwards-curve DSA developed by Bernstein et al. (2011).
|
|
\end{itemize}
|
|
\item \textbf{Key advantages over ECDSA:}
|
|
\begin{itemize}
|
|
\item \textbf{Deterministic:} No random number generation during signing.
|
|
\item \textbf{Faster:} Both signing and verification.
|
|
\item \textbf{Simpler:} Cleaner mathematical structure.
|
|
\item \textbf{Safer:} Eliminates randomness-related vulnerabilities.
|
|
\end{itemize}
|
|
\item \textbf{Design philosophy:} Avoid the pitfalls that plague ECDSA.
|
|
\item \textbf{Most popular instance:} Ed25519 (based on Curve25519).
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{EdDSA signature generation}
|
|
\textbf{Key insight:} Derive everything deterministically from private key and message.
|
|
\begin{columns}
|
|
\begin{column}{0.7\textwidth}
|
|
\textbf{Input:} Message $M$, private key $k$ (byte string)
|
|
\begin{enumerate}[<+->]
|
|
\item \textbf{Expand private key:} $a \parallel h = \text{Hash}(k)$
|
|
\begin{itemize}
|
|
\item $a$: actual signing scalar (first 256 bits)
|
|
\item $h$: randomness source (last 256 bits)
|
|
\end{itemize}
|
|
\item \textbf{Compute public key:} $A = a \cdot B$ (precomputed)
|
|
\item \textbf{Generate nonce deterministically:} $r = \text{Hash}(h \parallel M)$
|
|
\item \textbf{Compute signature point:} $R = r \cdot B$
|
|
\item \textbf{Compute signature scalar:} $S = r + \text{Hash}(R, A, M) \times a$
|
|
\item \textbf{Output signature:} $(R, S)$
|
|
\end{enumerate}
|
|
\end{column}
|
|
\begin{column}{0.3\textwidth}
|
|
\textbf{Benefits:}
|
|
\begin{itemize}[<+->]
|
|
\item No randomness needed
|
|
\item Same message = same signature
|
|
\item Immune to bad RNG
|
|
\item Faster (no modular inverse)
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{EdDSA signature verification}
|
|
\begin{columns}
|
|
\begin{column}{0.6\textwidth}
|
|
\textbf{Input:} Message $M$, signature $(R, S)$, public key $A$
|
|
\begin{enumerate}[<+->]
|
|
\item \textbf{Verify equation:} Check if:
|
|
$$S \cdot B = R + \func{hash}{R, A, M} \cdot A$$
|
|
\item \textbf{Accept signature if equation holds}
|
|
\end{enumerate}
|
|
\vspace{0.5cm}
|
|
\textbf{Why this works:}
|
|
\begin{itemize}[<+->]
|
|
\item From signing: $S = r + \func{hash}{R, A, M} \times a$
|
|
\item So: $S \cdot B = (r + \func{hash}{R, A, M} \times a) \cdot B$
|
|
\item $= r \cdot B + \func{hash}{R, A, M} \times a \cdot B$
|
|
\item $= R + \func{hash}{R, A, M} \times A$
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.4\textwidth}
|
|
\textbf{Performance benefits:}
|
|
\begin{itemize}[<+->]
|
|
\item No modular inverse computation
|
|
\item Two scalar multiplications (like ECDSA)
|
|
\item Simpler arithmetic
|
|
\item Better constant-time implementation
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Ed25519: The practical implementation}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Ed25519 = EdDSA + specific parameters:}
|
|
\begin{itemize}
|
|
\item Twisted Edwards curve based on Curve25519
|
|
\item SHA-512 as hash function
|
|
\item Optimized base point for efficiency
|
|
\end{itemize}
|
|
\item \textbf{Performance characteristics:}
|
|
\begin{itemize}
|
|
\item Signing: ~40-90 microseconds (modern CPUs)
|
|
\item Verification: ~100-200 microseconds
|
|
\item 64-byte signatures (512 bits)
|
|
\end{itemize}
|
|
\item \textbf{Security level:} ~128 bits (equivalent to 3072-bit RSA)
|
|
\item \textbf{Adoption milestones:}
|
|
\begin{itemize}
|
|
\item 2011: Initial specification
|
|
\item 2017: RFC 8032 standardization
|
|
\item 2023: Added to NIST FIPS 186-5
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{ECDSA vs. Ed25519: The comparison}
|
|
\begin{columns}
|
|
\begin{column}{0.5\textwidth}
|
|
\textbf{ECDSA:}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Pros:}
|
|
\begin{itemize}
|
|
\item Established standard (1990s)
|
|
\item Wide library support
|
|
\item Blockchain industry standard
|
|
\end{itemize}
|
|
\item \textbf{Cons:}
|
|
\begin{itemize}
|
|
\item Requires secure randomness
|
|
\item Slower verification
|
|
\item Complex implementation
|
|
\item Vulnerable to bad RNG
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\textbf{Ed25519:}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Pros:}
|
|
\begin{itemize}
|
|
\item Deterministic signing
|
|
\item Faster performance
|
|
\item Simpler implementation
|
|
\item Better security properties
|
|
\end{itemize}
|
|
\item \textbf{Cons:}
|
|
\begin{itemize}
|
|
\item Newer standard
|
|
\item Some validation inconsistencies
|
|
\item Less blockchain adoption
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\vspace{0.5cm}
|
|
\textbf{Recommendation:} Use Ed25519 for new projects unless ECDSA is specifically required.
|
|
\end{frame}
|
|
|
|
\section{Elliptic Curves: Practice}
|
|
|
|
\begin{frame}{Choosing the right elliptic curve}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Not all elliptic curves are created equal:} The mathematical structure of the curve directly impacts cryptographic security.
|
|
\item \textbf{Security implications:} Poor curve choice can make ECDLP much easier to solve.
|
|
\item \textbf{In practice:} You'll use established curves, but understanding what makes a curve safe helps you:
|
|
\begin{itemize}
|
|
\item Choose among available options.
|
|
\item Better understand associated risks.
|
|
\item Evaluate new curve proposals.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\begin{column}{0.5\textwidth}
|
|
\imagewithcaption{safecurves.png}{Elliptic curves have many distinct and complex security criteria.\\Source: \url{https://safecurves.cr.yp.to}}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Criteria for safe elliptic curves}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Group order security:} The number of points on the curve shouldn't factor into small numbers.
|
|
\begin{itemize}
|
|
\item If the order has small factors, ECDLP becomes much easier.
|
|
\item Attackers can use algorithms like Pohlig-Hellman to exploit small factors.
|
|
\end{itemize}
|
|
\item \textbf{Addition formula consistency:} Unified addition laws are preferred.
|
|
\begin{itemize}
|
|
\item Some curves require different formulas for $P + Q$ vs. $P + P$ (doubling).
|
|
\item Timing differences between these operations can leak information.
|
|
\item Secure curves use the same formula for all additions.
|
|
\end{itemize}
|
|
\item \textbf{Parameter transparency:} The origin of curve parameters should be clearly explained.
|
|
\begin{itemize}
|
|
\item Unknown parameter origins raise suspicion of backdoors.
|
|
\item ``Nothing up my sleeve'' numbers increase trust.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{NIST curves: The establishment standard}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Official standardization:} NIST standardized several curves in FIPS 186 (2000).
|
|
\begin{itemize}
|
|
\item ``Recommended Elliptic Curves for Federal Government Use''
|
|
\item Five prime curves working modulo prime numbers.
|
|
\item Ten binary polynomial curves (rarely used today).
|
|
\end{itemize}
|
|
\item \textbf{Most popular: P-256}
|
|
\begin{itemize}
|
|
\item Works modulo $p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$
|
|
\item Equation: $y^2 = x^3 - 3x + b$ (256-bit $b$ parameter)
|
|
\item Other sizes: P-192, P-224, P-384, P-521 (yes, 521 not 512!)
|
|
\end{itemize}
|
|
\item \textbf{Wide adoption:} Used in TLS, government systems, many commercial applications.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{The NIST controversy: Suspicious constants}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{The problem:} Only the NSA knows the true origin of the $b$ coefficient in NIST curves.
|
|
\item \textbf{NSA's explanation:} $b$ results from hashing a ``random-looking'' constant with SHA-1.
|
|
\begin{itemize}
|
|
\item P-256's $b$ comes from: \texttt{c49d3608 86e70493 6a6678e1 139d26b7 819f7e90}
|
|
\item But why this particular constant? Nobody knows.
|
|
\end{itemize}
|
|
\item \textbf{Community response:}
|
|
\begin{itemize}
|
|
\item Most experts don't believe the curves hide backdoors.
|
|
\item But the lack of transparency creates suspicion.
|
|
\item Led to development of alternative curves with transparent parameters.
|
|
\end{itemize}
|
|
\item \textbf{Post-Snowden era:} Increased scrutiny of NSA-designed cryptographic standards.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Curve25519: The performance revolution}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Created by Daniel J. Bernstein (2006):} Motivated by performance and security concerns.
|
|
\item \textbf{Performance advantages:}
|
|
\begin{itemize}
|
|
\item Faster than NIST curves.
|
|
\item Shorter keys for equivalent security.
|
|
\item Optimized for software implementation.
|
|
\end{itemize}
|
|
\item \textbf{Security improvements:}
|
|
\begin{itemize}
|
|
\item No suspicious constants—all parameters have clear origins.
|
|
\item Unified addition formula (same for $P + Q$ and $P + P$).
|
|
\item Resistant to timing attacks.
|
|
\end{itemize}
|
|
\item \textbf{Mathematical form:} $y^2 = x^3 + 486662x^2 + x$
|
|
\begin{itemize}
|
|
\item Works modulo $2^{255} - 19$ (closest prime to $2^{255}$).
|
|
\item Coefficient 486662 is the smallest integer satisfying security criteria.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Curve25519: From rebel to standard}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Widespread adoption:}
|
|
\begin{itemize}
|
|
\item WhatsApp end-to-end encryption
|
|
\item TLS 1.3 key exchange
|
|
\item OpenSSH connections
|
|
\item Signal Protocol
|
|
\item Many cryptocurrency systems
|
|
\end{itemize}
|
|
\item \textbf{Official recognition:} Added to NIST-approved curves in February 2023.
|
|
\begin{itemize}
|
|
\item SP 800-186: ``Recommendations for Discrete Logarithm-based Cryptography''
|
|
\item Took 17 years for official government approval!
|
|
\end{itemize}
|
|
\item \textbf{Trust through transparency:} Clear parameter origins make Curve25519 more trustworthy than NIST curves.
|
|
\item \textbf{Related: Ed25519} for digital signatures using the same curve.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Other curves in the ecosystem}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Legacy national standards:}
|
|
\begin{itemize}
|
|
\item \textbf{ANSSI curves (France):} Constants of unknown origin, no unified addition.
|
|
\item \textbf{Brainpool curves (Germany):} Similar issues to ANSSI curves.
|
|
\end{itemize}
|
|
\item \textbf{Modern alternatives:}
|
|
\begin{itemize}
|
|
\item \textbf{Curve41417:} Variant of Curve25519 with higher security (~200 bits).
|
|
\item \textbf{Ed448-Goldilocks:} 448-bit curve (RFC 8032, 2014).
|
|
\item \textbf{Aranha et al. curves:} Six high-security curves (rarely used).
|
|
\end{itemize}
|
|
\item \textbf{Ristretto initiative:} Technique for safe point representation.
|
|
\begin{itemize}
|
|
\item Constructs prime-order groups from non-prime-order curves.
|
|
\item Eliminates certain structural risks.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Practical curve selection guidance}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{For new projects:} Use Curve25519/Ed25519
|
|
\begin{itemize}
|
|
\item Excellent performance and security.
|
|
\item Transparent parameter generation.
|
|
\item Wide library support.
|
|
\item Now NIST-approved for government use.
|
|
\end{itemize}
|
|
\item \textbf{For government/compliance:} NIST P-256 is still widely accepted
|
|
\begin{itemize}
|
|
\item Required by some standards and regulations.
|
|
\item Well-audited implementations available.
|
|
\item Despite parameter concerns, no known weaknesses.
|
|
\end{itemize}
|
|
\item \textbf{Avoid:} Legacy curves with unknown parameter origins
|
|
\begin{itemize}
|
|
\item ANSSI, Brainpool curves.
|
|
\item Curves without unified addition laws.
|
|
\end{itemize}
|
|
\item \textbf{Future-proofing:} Consider post-quantum alternatives for long-term security.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{How things can go wrong}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{ECC complexity brings risks:} More parameters than RSA create a larger attack surface.
|
|
\item \textbf{Implementation vulnerabilities:}
|
|
\begin{itemize}
|
|
\item Side-channel attacks on big-number arithmetic.
|
|
\item Timing attacks when computation time depends on secret values.
|
|
\item Point validation failures.
|
|
\end{itemize}
|
|
\item \textbf{Design-level vulnerabilities:}
|
|
\begin{itemize}
|
|
\item Bad randomness in signature generation.
|
|
\item Invalid curve attacks on key exchange.
|
|
\item Inconsistent validation rules across implementations.
|
|
\end{itemize}
|
|
\item Let's examine three major categories of ECC vulnerabilities.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{ECDSA with bad randomness}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{ECDSA signing requires randomness:} Each signature uses a secret random number $k$.
|
|
$$s = \frac{h + rd}{k} \bmod n$$
|
|
\item \textbf{The catastrophic mistake:} Reusing the same $k$ for two different messages.
|
|
\item \textbf{Attack scenario:} If $k$ is reused:
|
|
\begin{itemize}
|
|
\item Attacker gets: $s_1 = \frac{h_1 + rd}{k}$ and $s_2 = \frac{h_2 + rd}{k}$
|
|
\item Compute: $s_1 - s_2 = \frac{h_1 - h_2}{k}$
|
|
\item Recover randomness: $k = \frac{h_1 - h_2}{s_1 - s_2}$
|
|
\item Recover private key: $d = \frac{sk - h}{r}$
|
|
\end{itemize}
|
|
\item \textbf{Why this is devastating:} Complete private key recovery from just two signatures.
|
|
\item \textbf{Prevention:} Always use cryptographically secure random number generation.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Case study: PlayStation 3 hack (2010)}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{The vulnerability:} Sony's PlayStation 3 reused the same $k$ value to sign different games.
|
|
\item \textbf{Discovery:} fail0verflow team at 27th Chaos Communication Congress.
|
|
\item \textbf{Attack process:}
|
|
\begin{itemize}
|
|
\item Collected ECDSA signatures from multiple PS3 games.
|
|
\item Noticed identical $r$ values (indicating same $k$).
|
|
\item Applied the mathematical attack to recover Sony's signing key.
|
|
\end{itemize}
|
|
\item \textbf{Consequences:}
|
|
\begin{itemize}
|
|
\item Attackers could sign any program to run on PS3.
|
|
\item Homebrew software and piracy became possible.
|
|
\item Sony had to revoke and update their entire signing infrastructure.
|
|
\end{itemize}
|
|
\item \textbf{Lesson:} Even major companies can make fundamental cryptographic mistakes.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Invalid curve attacks}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{The vulnerability:} ECDH implementations that don't validate input points.
|
|
\item \textbf{Mathematical insight:} Point addition formulas don't use the $b$ coefficient:
|
|
$$P + Q \text{ only depends on coordinates of } P, Q \text{ and coefficient } a$$
|
|
\item \textbf{Attack scenario:}
|
|
\begin{itemize}
|
|
\item Alice and Bob agree on curve and base point $G$.
|
|
\item Bob sends legitimate public key $bG$.
|
|
\item Alice sends point $P$ from a \emph{different, weaker} curve.
|
|
\item Bob computes ``shared secret'' $bP$ on the wrong curve.
|
|
\end{itemize}
|
|
\item \textbf{Why this works:} Addition formulas work the same way on the wrong curve.
|
|
\item \textbf{Attacker's advantage:} Choose $P$ from a curve with weak discrete logarithm.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Invalid curve attack: The mathematics}
|
|
\begin{columns}[c]
|
|
\begin{column}{1\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Attacker's strategy:} Choose point $P$ with small order on a weak curve.
|
|
\begin{itemize}
|
|
\item Small order means $kP = \mathcal{O}$ for relatively small $k$.
|
|
\item Bob computes $bP$, which also has small order.
|
|
\end{itemize}
|
|
\item \textbf{Attack execution:}
|
|
\begin{itemize}
|
|
\item Bob believes he computed shared secret $bP$.
|
|
\item He hashes $bP$ and uses result as encryption key.
|
|
\item Since $bP$ belongs to small subgroup, attacker can brute-force it.
|
|
\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 Jager, Schwenk, and Somorovsky
|
|
\end{itemize}
|
|
\item \textbf{Prevention:} Always validate that points satisfy the correct curve equation.
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Invalid curve attack prevention}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Point validation:} Before using any received point $P = (x, y)$:
|
|
$$\text{Check: } y^2 \stackrel{?}{=} x^3 + ax + b \pmod{p}$$
|
|
\item \textbf{Additional checks:}
|
|
\begin{itemize}
|
|
\item Verify point is not the point at infinity.
|
|
\item Ensure coordinates are in valid range $[0, p-1]$.
|
|
\item Check point has correct order (belongs to right subgroup).
|
|
\end{itemize}
|
|
\item \textbf{Implementation note:} Many libraries now perform validation automatically.
|
|
\item \textbf{Defense in depth:} Use curves with prime order (like Curve25519).
|
|
\begin{itemize}
|
|
\item Eliminates small subgroup attacks entirely.
|
|
\item Even invalid points can't exploit subgroup structure.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Why most elliptic curves aren't prime order}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Mathematical reality:} The number of points on a curve is rarely prime.
|
|
\begin{itemize}
|
|
\item For curve $y^2 = x^3 + ax + b$ over $\mathbb{F}_p$, the number of points is close to $p$.
|
|
\item Hasse's theorem: $|n - (p + 1)| \leq 2\sqrt{p}$ where $n$ is the number of points.
|
|
\item Getting exactly a prime number is statistically unlikely.
|
|
\end{itemize}
|
|
\item \textbf{Curve25519's structure:} Has $8 \times \ell$ points where $\ell$ is a large prime.
|
|
\begin{itemize}
|
|
\item Factor of 8 comes from the curve's mathematical structure.
|
|
\item Designers chose parameters to minimize cofactor while optimizing performance.
|
|
\item Trade-off: Accept small cofactor for better arithmetic efficiency.
|
|
\end{itemize}
|
|
\item \textbf{Why not search for prime-order curves?}
|
|
\begin{itemize}
|
|
\item Finding curves with prime order is computationally expensive.
|
|
\item Prime-order curves often have less efficient arithmetic.
|
|
\item Small cofactors (like 4 or 8) are manageable with proper protocols.
|
|
\end{itemize}
|
|
\item \textbf{Security implication:} Non-prime order enables small subgroup attacks if not handled carefully.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Understanding elliptic curve subgroups}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{What is a subgroup?} A subset of curve points that forms its own group.
|
|
\begin{itemize}
|
|
\item Contains the identity element (point at infinity $\mathcal{O}$).
|
|
\item Closed under addition: if $P, Q$ in subgroup, then $P + Q$ also in subgroup.
|
|
\item Every element has an inverse within the subgroup.
|
|
\end{itemize}
|
|
\item \textbf{Why do subgroups exist?} Most elliptic curves don't have prime order.
|
|
\begin{itemize}
|
|
\item If curve has $n$ points and $n = p \times q$, subgroups can exist.
|
|
\item Points of order $p$ form a subgroup of size $p$.
|
|
\item Points of order $q$ form a subgroup of size $q$.
|
|
\end{itemize}
|
|
\item \textbf{Example: Curve25519's structure}
|
|
\begin{itemize}
|
|
\item Total points: $8 \times \ell$ where $\ell$ is a large prime.
|
|
\item Has a subgroup of order 8 (small!).
|
|
\item Has a subgroup of order $\ell$ (large, secure).
|
|
\item Every point belongs to one of these subgroups.
|
|
\end{itemize}
|
|
\item \textbf{Security implication:} Attackers try to push operations into small subgroups where discrete log is easy.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Small subgroup attacks}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{How it works:}
|
|
\begin{itemize}
|
|
\item Attacker sends a point $P$ of small order (e.g., order 8).
|
|
\item Victim computes secret scalar multiplication: $s \cdot P$.
|
|
\item Result $s \cdot P$ also has small order (at most 8).
|
|
\item Attacker can brute-force to find $s \bmod 8$.
|
|
\end{itemize}
|
|
\item \textbf{Information leakage:} Each exchange reveals bits of the secret.
|
|
\begin{itemize}
|
|
\item With order-8 point: Learn 3 bits of secret.
|
|
\item Repeat with different small-order points.
|
|
\item Combine using Chinese Remainder Theorem.
|
|
\item Eventually recover full secret.
|
|
\end{itemize}
|
|
\item \textbf{Real-world example:} Curve25519 without proper validation.
|
|
\begin{itemize}
|
|
\item Has points of order 1, 2, 4, 8, $\ell$, $2\ell$, $4\ell$, $8\ell$.
|
|
\item Unvalidated ECDH can leak secret key bits.
|
|
\end{itemize}
|
|
\item \textbf{Defense:} Validate points belong to correct subgroup or use protocols that eliminate the threat.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Invalid curve attacks vs. small subgroup attacks}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Two distinct but related vulnerabilities:}
|
|
\begin{itemize}
|
|
\item Both exploit weak point validation.
|
|
\item Different mathematical foundations.
|
|
\item Different defense strategies.
|
|
\end{itemize}
|
|
\item \textbf{Invalid curve attacks:}
|
|
\begin{itemize}
|
|
\item Attacker sends point from a \emph{different curve} entirely.
|
|
\item Point satisfies $y^2 = x^3 + ax + b'$ with wrong $b'$ coefficient.
|
|
\item Exploits that addition formulas don't use $b$.
|
|
\item Defense: Verify $y^2 \stackrel{?}{=} x^3 + ax + b$ with correct $b$.
|
|
\end{itemize}
|
|
\item \textbf{Small subgroup attacks:}
|
|
\begin{itemize}
|
|
\item Attacker sends point from the \emph{correct curve}.
|
|
\item But point has small order (belongs to small subgroup).
|
|
\item Example: Point $P$ where $8P = \mathcal{O}$ instead of expected large order.
|
|
\item Defense: Verify point has correct order or use prime-order curves.
|
|
\end{itemize}
|
|
\item \textbf{Key insight:} Invalid curve = wrong equation; Small subgroup = wrong order.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Ed25519 validation inconsistencies}
|
|
\begin{columns}[c]
|
|
\begin{column}{1\textwidth}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Expectation:} One standard should mean identical behavior across implementations.
|
|
\item \textbf{Reality:} Ed25519 implementations have different validation criteria.
|
|
\item \textbf{The problem:} RFC 8032 doesn't fully specify validation requirements.
|
|
\begin{itemize}
|
|
\item How to validate signature point $R$.
|
|
\item How to validate public key point $A$.
|
|
\item How to verify the signature equation.
|
|
\end{itemize}
|
|
\item \textbf{Research findings:} Henry de Valence analyzed 15 Ed25519 implementations.\footnote{\url{https://hdevalence.ca/blog/2020-10-04-its-25519am/}}
|
|
\begin{itemize}
|
|
\item Each had different validation criteria.
|
|
\item Same signature could be valid in one implementation, invalid in another.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Real-world impact of validation differences}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Consensus failures:} In blockchain networks:
|
|
\begin{itemize}
|
|
\item Some nodes accept a signature, others reject it.
|
|
\item Breaks consensus protocol assumptions.
|
|
\item Can lead to network splits or transaction inconsistencies.
|
|
\end{itemize}
|
|
\item \textbf{Interoperability issues:} Systems using different libraries may disagree.
|
|
\item \textbf{Security implications:} Inconsistent validation can enable attacks.
|
|
\begin{itemize}
|
|
\item Malleability attacks.
|
|
\item Signature forgery in edge cases.
|
|
\end{itemize}
|
|
\item \textbf{The solution:} Standardization efforts like ZIP-215 (Zcash) aim to:
|
|
\begin{itemize}
|
|
\item Specify exact validation rules.
|
|
\item Ensure all implementations behave identically.
|
|
\item Prevent consensus failures.
|
|
\end{itemize}
|
|
\item \textbf{Lesson:} Cryptographic standards must be completely unambiguous.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Library selection: The ecosystem landscape}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Don't implement ECC from scratch:} Cryptographic implementations require years of hardening.
|
|
\item \textbf{Rust ecosystem:}
|
|
\begin{itemize}
|
|
\item \texttt{ring}: Fast, audited, used by major companies.
|
|
\item \texttt{p256}, \texttt{k256}: RustCrypto pure-Rust implementations.
|
|
\item \texttt{curve25519-dalek}: Ed25519/X25519 with extensive validation.
|
|
\end{itemize}
|
|
\item \textbf{Go ecosystem:}
|
|
\begin{itemize}
|
|
\item \texttt{crypto/elliptic}: Standard library (NIST curves).
|
|
\item \texttt{golang.org/x/crypto/curve25519}: Official X25519 implementation.
|
|
\item \texttt{filippo.io/edwards25519}: Modern Ed25519 with clear APIs.
|
|
\end{itemize}
|
|
\item \textbf{Selection criteria:}
|
|
\begin{itemize}
|
|
\item Active maintenance and security updates.
|
|
\item Independent security audits.
|
|
\item Constant-time guarantees.
|
|
\item Clear documentation and examples.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Performance considerations in practice}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Scalar multiplication is the bottleneck:} Operations like $k \cdot G$ dominate runtime.
|
|
\item \textbf{Precomputation strategies:}
|
|
\begin{itemize}
|
|
\item Store multiples of base point: $G, 2G, 4G, 8G, \ldots$
|
|
\item Sliding window methods for arbitrary points.
|
|
\item Trade memory for speed.
|
|
\end{itemize}
|
|
\item \textbf{Coordinate systems matter:}
|
|
\begin{itemize}
|
|
\item Affine coordinates: Simple but require expensive modular inverse.
|
|
\item Jacobian coordinates: Avoid inverse, faster for repeated operations.
|
|
\item Montgomery ladders: Optimal for X25519-style protocols.
|
|
\end{itemize}
|
|
\item \textbf{Real-world impact:}
|
|
\begin{itemize}
|
|
\item TLS handshake time directly affects user experience.
|
|
\item Mobile devices: battery life and thermal constraints.
|
|
\item IoT devices: limited computational resources.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Constant-time implementation: Why it matters}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{The threat:} Attackers can measure timing differences to extract secrets.
|
|
\item \textbf{Vulnerable patterns in ECC:}
|
|
\begin{itemize}
|
|
\item Conditional branches based on secret bits
|
|
\item Variable-time modular arithmetic
|
|
\item Memory access patterns that depend on secret data
|
|
\end{itemize}
|
|
\item \textbf{Example: Scalar multiplication timing}
|
|
\begin{itemize}
|
|
\item Binary method: \texttt{if (bit == 1) result += point}
|
|
\item Timing reveals which bits are 1 vs 0
|
|
\item After enough measurements, attacker recovers private key
|
|
\end{itemize}
|
|
\item \textbf{Defense:} Always perform the same operations regardless of secret values.
|
|
\item \textbf{Modern libraries handle this:} But you need to choose libraries that guarantee constant-time behavior.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Memory management and sensitive data}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{The problem:} Private keys in memory can be extracted by attackers.
|
|
\item \textbf{Attack vectors:}
|
|
\begin{itemize}
|
|
\item Memory dumps during crashes.
|
|
\item Swap files writing secrets to disk.
|
|
\item Cold boot attacks on RAM.
|
|
\item Process memory scanning.
|
|
\end{itemize}
|
|
\item \textbf{Defense strategies:}
|
|
\begin{itemize}
|
|
\item Zero memory immediately after use.
|
|
\item Use protected memory (mlock/VirtualLock).
|
|
\item Hardware security modules (HSMs) for high-value keys.
|
|
\item Minimize lifetime of secrets in memory.
|
|
\end{itemize}
|
|
\item \textbf{Language-specific considerations:}
|
|
\begin{itemize}
|
|
\item Rust: \texttt{zeroize} crate for secure memory clearing.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Testing elliptic curve implementations}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Standard test vectors:} Use RFC and NIST test cases to verify correctness.
|
|
\item \textbf{Cross-implementation testing:}
|
|
\begin{itemize}
|
|
\item Generate signatures with one library, verify with another.
|
|
\item Perform ECDH with different implementations.
|
|
\item Ensure interoperability across programming languages.
|
|
\end{itemize}
|
|
\item \textbf{Edge case testing:}
|
|
\begin{itemize}
|
|
\item Point at infinity handling.
|
|
\item Invalid curve points.
|
|
\item Malformed signature formats.
|
|
\item Zero and maximum values.
|
|
\end{itemize}
|
|
\item \textbf{Property-based testing:}
|
|
\begin{itemize}
|
|
\item Verify mathematical properties: $P + Q = Q + P$
|
|
\item Test with random inputs within valid ranges.
|
|
\item Ensure operations always produce valid outputs.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Real-world case study: WhatsApp's implementation}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Challenge:} Secure messaging for 2+ billion users across diverse devices.
|
|
\item \textbf{Solution:} Signal Protocol with Curve25519 and Ed25519.
|
|
\item \textbf{Implementation details:}
|
|
\begin{itemize}
|
|
\item X25519 for key agreement (ECDH).
|
|
\item Ed25519 for identity key signatures.
|
|
\item Custom optimizations for mobile platforms.
|
|
\item Cross-platform C library for consistency.
|
|
\end{itemize}
|
|
\item \textbf{Engineering considerations:}
|
|
\begin{itemize}
|
|
\item Battery life optimization on mobile devices.
|
|
\item Constant-time implementation to prevent side-channel attacks.
|
|
\item Extensive testing across iOS, Android, and desktop platforms.
|
|
\item Regular security audits by external firms.
|
|
\end{itemize}
|
|
\item \textbf{Lessons:} Real world requires balancing security, performance, and compatibility.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Real-world case study: TLS 1.3 performance}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Challenge:} Replace RSA key exchange with elliptic curve alternatives.
|
|
\item \textbf{Implementation impact:}
|
|
\begin{itemize}
|
|
\item X25519 ECDH: 40-100x faster than 2048-bit RSA key exchange.
|
|
\item Smaller certificates reduce network overhead.
|
|
\item Enables features like 0-RTT handshakes.
|
|
\end{itemize}
|
|
\item \textbf{Engineering challenges solved:}
|
|
\begin{itemize}
|
|
\item Constant-time implementation in BoringSSL.
|
|
\item Optimized assembly for common architectures.
|
|
\item Fallback implementations for edge cases.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Common implementation pitfalls}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Pitfall 1: Poor random number generation}
|
|
\begin{itemize}
|
|
\item Using \texttt{rand()} instead of cryptographic RNG.
|
|
\item Not seeding random generators properly.
|
|
\item Reusing random values (PlayStation 3 scenario).
|
|
\end{itemize}
|
|
\item \textbf{Pitfall 2: Skipping input validation}
|
|
\begin{itemize}
|
|
\item Not checking if points are on the correct curve.
|
|
\item Accepting points at infinity without proper handling.
|
|
\item Missing range checks on coordinates.
|
|
\end{itemize}
|
|
\item \textbf{Pitfall 3: Side-channel vulnerabilities}
|
|
\begin{itemize}
|
|
\item Conditional operations based on secret data.
|
|
\item Variable memory access patterns.
|
|
\item Timing differences in error handling.
|
|
\end{itemize}
|
|
\item \textbf{Prevention:} Use audited libraries, follow security guidelines, test extensively.
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Best practices for ECC implementation}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Library selection:}
|
|
\begin{itemize}
|
|
\item Choose libraries with security audit history.
|
|
\item Prefer constant-time implementations.
|
|
\item Ensure active maintenance and updates.
|
|
\end{itemize}
|
|
\item \textbf{Development practices:}
|
|
\begin{itemize}
|
|
\item Use standard curves (avoid custom parameters).
|
|
\item Implement comprehensive input validation.
|
|
\item Clear sensitive data from memory.
|
|
\item Use secure random number generation.
|
|
\end{itemize}
|
|
\item \textbf{Testing and deployment:}
|
|
\begin{itemize}
|
|
\item Test with standard vectors and edge cases.
|
|
\item Perform interoperability testing.
|
|
\item Monitor for timing analysis vulnerabilities.
|
|
\item Plan for cryptographic agility (algorithm migration).
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Digital signatures: real-world adoption patterns}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{ECDSA dominance:}
|
|
\begin{itemize}
|
|
\item Bitcoin, Ethereum, most cryptocurrencies.
|
|
\item TLS certificates (still common).
|
|
\item Legacy enterprise systems.
|
|
\end{itemize}
|
|
\item \textbf{Ed25519 growth:}
|
|
\begin{itemize}
|
|
\item OpenSSH default since 2014.
|
|
\item Signal Protocol messaging.
|
|
\item Modern certificate authorities.
|
|
\item New blockchain projects (Solana, etc.)
|
|
\end{itemize}
|
|
\item \textbf{Migration considerations:}
|
|
\begin{itemize}
|
|
\item Interoperability with existing systems.
|
|
\item Library availability in your ecosystem.
|
|
\item Compliance requirements.
|
|
\item Performance requirements.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Digital signatures: practical implementation guidelines}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{For ECDSA implementations:}
|
|
\begin{itemize}
|
|
\item Use cryptographically secure random number generator.
|
|
\item Never reuse nonce values.
|
|
\item Implement constant-time operations.
|
|
\item Validate all input points.
|
|
\end{itemize}
|
|
\item \textbf{For Ed25519 implementations:}
|
|
\begin{itemize}
|
|
\item Follow RFC 8032 specification carefully.
|
|
\item Handle validation edge cases consistently.
|
|
\item Use established libraries (libsodium, etc.)
|
|
\end{itemize}
|
|
\item \textbf{General best practices:}
|
|
\begin{itemize}
|
|
\item Don't implement from scratch.
|
|
\item Use constant-time libraries.
|
|
\item Test with standard vectors.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Looking forward: Implementation challenges}
|
|
\begin{itemize}[<+->]
|
|
\item \textbf{Post-quantum transition:} ECC implementations need migration paths.
|
|
\begin{itemize}
|
|
\item Hybrid classical/post-quantum systems.
|
|
\item Algorithm negotiation mechanisms.
|
|
\item Backward compatibility requirements.
|
|
\item Discussed in a future class topic!
|
|
\end{itemize}
|
|
\item \textbf{Formal verification:} Mathematical proofs of implementation correctness.
|
|
\begin{itemize}
|
|
\item Projects like Cryspen's HAX and Libcrux generate verified code.
|
|
\item Higher assurance for critical applications.
|
|
\item Trade-off between verification effort and deployment flexibility.
|
|
\item Discussed in a future class topic!
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{frame}
|
|
|
|
\begin{frame}[plain]
|
|
\titlepage
|
|
\end{frame}
|
|
\end{document}
|