mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
62 lines
2.4 KiB
TeX
62 lines
2.4 KiB
TeX
\section{Why Fuzz Cryptographic Code}
|
|
|
|
|
|
\subsection{The Problem with Test Vectors}
|
|
|
|
Cryptographic implementations are typically tested against known-answer tests (KATs):
|
|
standardized input/output pairs from the specification. KATs verify that the code
|
|
produces correct output for specific inputs. They do not verify:
|
|
|
|
\begin{itemize}[nosep]
|
|
\item Behavior at boundary values (zero, one, $q - 1$, $q$, $q + 1$).
|
|
\item Behavior with malformed inputs (wrong length, invalid encoding).
|
|
\item Absence of panics or undefined behavior.
|
|
\item Consistency: $\text{decrypt}(\text{encrypt}(m)) = m$ for all $m$.
|
|
\item Algebraic properties: associativity, commutativity, distributivity.
|
|
\end{itemize}
|
|
|
|
\subsection{Property-Based Testing}
|
|
|
|
Property-based testing (PBT) inverts the test structure. Instead of specifying inputs
|
|
and expected outputs, you specify \emph{properties} that must hold for all inputs. The
|
|
framework generates random inputs and checks the properties.
|
|
|
|
\begin{definition}[Property]
|
|
A property is a universally quantified assertion: $\forall x \in D.\; P(x)$, where $D$
|
|
is the input domain and $P$ is a predicate.
|
|
\end{definition}
|
|
|
|
Examples of cryptographic properties:
|
|
\begin{itemize}[nosep]
|
|
\item \textbf{Round-trip}: $\text{decrypt}(k, \text{encrypt}(k, m)) = m$
|
|
\item \textbf{Determinism}: $\text{hash}(x) = \text{hash}(x)$
|
|
\item \textbf{Length preservation}: $|\text{NTT}(a)| = |a|$
|
|
\item \textbf{Commutativity}: $\text{NTT}(a \cdot b) = \text{NTT}(a) \otimes \text{NTT}(b)$
|
|
\item \textbf{Idempotence}: $\text{NTT}(\text{INTT}(\text{NTT}(a))) = \text{NTT}(a)$
|
|
\end{itemize}
|
|
|
|
\subsection{Fuzzing vs.\ Property-Based Testing}
|
|
|
|
\begin{table}[H]
|
|
\centering
|
|
\small
|
|
\begin{tabular}{@{}lll@{}}
|
|
\toprule
|
|
& \textbf{Property-Based Testing} & \textbf{Fuzzing} \\
|
|
\midrule
|
|
Input generation & Type-aware random & Mutational, coverage-guided \\
|
|
Oracle & Explicit property & Crash / sanitizer \\
|
|
Shrinking & Yes (minimal failing input) & Corpus minimization \\
|
|
Coverage feedback & Usually no & Yes \\
|
|
Typical runs & 1,000--100,000 & Millions--billions \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\caption{PBT vs.\ fuzzing. Modern tools blend both approaches.}
|
|
\end{table}
|
|
|
|
Go's \texttt{testing.F} provides coverage-guided fuzzing with type-aware seed corpora.
|
|
Foundry provides both random (fuzz) and coverage-guided (invariant) modes. We use all
|
|
of them.
|
|
|
|
%% ============================================================
|