% hashing-deep.tex — hashing as one subject across its uses: hash tables
% (SipHash, seeds, HashDoS, collisions, rehash), cryptographic hashes and the
% birthday bound, consistent hashing, password hashing, HMAC, Bloom filters.
% Sources: docs/memos/cs-hashing-deep.md, docs/memos/security-crypto-fundamentals.md
% (Q10-Q16), checked against docs/school/notes/knowledge-gaps-2026-09-23.md.
% Password-hash parameters: OWASP Password Storage Cheat Sheet.
% Tables in general: cs/data-structures.tex. CryptoKit API: cs/crypto-cryptokit.tex.
% Build ONLY with: tools/print/print-sheet.py <this>.tex --dry-run
% @source: hiot monorepo, docs/school/sheets/cs/hashing-deep.tex — the SOURCE OF TRUTH; a copy anywhere else (e.g. artur.gurgul.pro) is regenerated from it, never edited
% @labels: area=cs kind=concept level=senior platform=general new=no round=missing-2026-09-25 topic=algorithms,data,security
% @tags: siphash, hashdos, birthday-bound, robin-hood-hashing, consistent-hashing, virtual-nodes, bloom-filter, sha-256, length-extension, hmac, argon2id, password-hashing
\documentclass[8pt]{extarticle}
\usepackage{printup-sheet}
\usepackage{array}

\lstdefinelanguage{SwiftSheet}{
  morekeywords={protocol,class,final,struct,enum,func,var,let,weak,init,import,
    if,else,return,guard,self,nil,try,await,async,throws,private,some,static,inout,
    true,false,AnyObject,Void,String,Bool,Int,Data},
  sensitive=true, morecomment=[l]{//}, morecomment=[s]{/*}{*/}, morestring=[b]"}
\lstset{basicstyle=\ttfamily\scriptsize, aboveskip=2pt, belowskip=2pt}

\newcommand\ct[1]{\texttt{#1}}
\tikzset{
  c/.style={cell, minimum width=3.4mm, minimum height=4mm, font=\ttfamily\tiny, inner sep=0pt},
  hd/.style={font=\bfseries\small, text=sheetBlue, anchor=west},
  l/.style={font=\tiny, text=black!75, align=center, inner sep=1pt},
  vn/.style={circle, fill=#1, draw=#1!70!black, inner sep=0pt, minimum size=3.2mm, font=\sffamily\tiny\bfseries, text=white},
  ky/.style={rectangle, fill=black!65, inner sep=0pt, minimum size=1.6mm},
}

\begin{document}

\sheettitle{Hashing, deep — tables, crypto, rings, passwords, Bloom}{cs · memo}

\oneliner{A hash maps arbitrary input to a fixed-size value. \textbf{Table
hashes} want speed + uniformity and a \textbf{secret seed} against flooding
(Swift: SipHash, reseeded per process); \textbf{cryptographic hashes} want
one-wayness and collision resistance (SHA-256); \textbf{password hashes} want
to be \textbf{slow and memory-hard}; a \textbf{MAC} needs a key. Choosing the
wrong family is the classic mistake.}

\vspace{2pt}
\noindent\begin{tikzpicture}[sheet]
  % ===== consistent hashing ring
  \node[hd] at (-0.1,2.1) {Consistent hashing + virtual nodes};
  \def\R{1.05}
  \draw[thick, sheetGrey] (1.5,0.6) circle (\R);
  \foreach \a/\n/\col in {20/A1/sheetBlue,80/B1/sheetGreen,140/C1/sheetOrange,200/A2/sheetBlue,260/B2/sheetGreen,320/C2/sheetOrange}
    \node[vn=\col] (\n) at ($(1.5,0.6)+(\a:\R)$) {\n};
  \node[vn=sheetRed] (D) at ($(1.5,0.6)+(290:\R)$) {D};
  \foreach \a/\k in {50/k1,110/k2,305/k3,230/k4} \node[ky] (\k) at ($(1.5,0.6)+(\a:\R)$) {};
  \draw[->, thin, sheetBlue] ($(1.5,0.6)+(50:0.82)$) arc (50:24:0.82);
  \draw[->, thin, sheetGreen] ($(1.5,0.6)+(110:0.82)$) arc (110:84:0.82);
  \draw[->, thin, sheetGreen] ($(1.5,0.6)+(230:0.82)$) arc (230:264:0.82);
  \draw[->, thick, sheetRed] ($(1.5,0.6)+(305:0.72)$) arc (305:294:0.72);
  \draw[->, thin, dashed, sheetGrey] ($(1.5,0.6)+(305:1.28)$) arc (305:262:1.28);
  \node[l] at ($(1.5,0.6)+(50:1.3)$) {k1}; \node[l] at ($(1.5,0.6)+(110:1.3)$) {k2};
  \node[l] at ($(1.5,0.6)+(230:1.3)$) {k4}; \node[l] at ($(1.5,0.6)+(318:1.45)$) {k3};
  \node[l, align=center] at (1.5,0.6) {0 … 2\textsuperscript{64}$-$1\\key → next node\\clockwise};
  \node[l, anchor=west, align=left] at (2.9,1.2) {each server =\\many points\\(vnodes)};
  \node[l, anchor=west, align=left, text=sheetRed] at (2.85,-0.35) {add D: only k3\\moves (was B2)\\$\sim$K/N keys};
  \draw[sheetGrey!50] (4.25,2.3) -- (4.25,-0.75);
  % ===== Bloom filter
  \node[hd] at (4.3,2.1) {Bloom filter: m bits, k hashes};
  \foreach \i in {0,...,15} {
    \pgfmathparse{(\i==2||\i==4||\i==7||\i==11||\i==13)?1:0}
    \ifnum\pgfmathresult=1 \node[c, fill=sheetBlue!25] (b\i) at (4.55+0.36*\i,0.75) {1};
    \else \node[c] (b\i) at (4.55+0.36*\i,0.75) {0}; \fi
    \node[l] at (4.55+0.36*\i,0.45) {\i}; }
  \node[l, text=sheetBlue] (cat) at (5.3,1.65) {add ``cat''};
  \node[l, text=sheetBlue] (dog) at (8.0,1.65) {add ``dog''};
  \foreach \t in {2,7,13} \draw[->, thin, sheetBlue] (cat) -- (b\t.north);
  \foreach \t in {4,7,11} \draw[->, thin, sheetBlue!60] (dog) -- (b\t.north);
  \node[l, text=sheetGreen!50!black, align=left, anchor=west] (cow) at (4.3,-0.25) {``cow'' → 2, 11, \textbf{14}: a 0\\⇒ \textbf{definitely not} present};
  \node[l, text=sheetRed, align=left, anchor=west] (ant) at (7.0,-0.25) {``ant'' → 2, 4, 13: all 1\\⇒ ``maybe'' = \textbf{false positive}};
  \draw[->, thin, sheetGreen!50!black] (cow.north east) -- (b14.south);
  \draw[sheetGrey!50] (10.4,2.3) -- (10.4,-0.75);
  % ===== password hashing pipeline
  \node[hd] at (10.45,2.1) {Storing a password};
  \node[box, font=\tiny, minimum width=13mm] (pw) at (11.2,1.35) {password};
  \node[box, font=\tiny, minimum width=13mm, draw=sheetGreen, fill=sheetGreen!8] (salt) at (11.2,0.75) {salt: 16 random B\\per user, stored};
  \node[box, font=\tiny, minimum width=13mm, draw=sheetRed, fill=sheetRed!6] (pep) at (11.2,0.05) {pepper: secret,\\in KMS, not DB};
  \node[box, font=\tiny, draw=sheetOrange, fill=sheetOrange!12, minimum height=16mm, text width=17mm] (ar) at (13.55,0.75) {\textbf{Argon2id}\\m = 19 MiB\\t = 2, p = 1\\slow on purpose:\\$\sim$tens of ms};
  \draw[flow] (pw.east) -- (ar.west |- pw.east);
  \draw[flow] (salt.east) -- (ar.west |- salt.east);
  \draw[flow, dashed] (pep.east) -- (ar.west |- pep.east);
  \node[l, font=\ttfamily\tiny, anchor=west, align=left] at (14.7,1.2) {\$argon2id\$v=19\\\$m=19456,t=2,p=1\\\$<salt>\$<hash>};
  \draw[flow] (ar.east) -- (14.75,0.75);
  \node[l, anchor=west, align=left] at (14.7,0.35) {one string: algorithm,\\params, salt → upgrade\\on next login};
  \node[l, anchor=west, align=left, text=sheetRed] at (10.45,-0.55) {attacker with the DB must pay the cost \emph{per guess, per user}};
\end{tikzpicture}

\begin{multicols}{2}
\footnotesize\setstretch{1.0}

\section{What makes a hash good}
\begin{itemize}
  \item \textbf{Deterministic} (within its seed), \textbf{uniform} (keys spread
        evenly over buckets), \textbf{avalanche} (flip 1 input bit → $\sim$half the
        output bits flip, so near-identical keys don't cluster), \textbf{fast}
        (O(key length)).
  \item \textbf{Table hashes}: FNV, Murmur, xxHash (fast, unkeyed → floodable);
        \textbf{SipHash} (Aumasson \& Bernstein 2012) is a fast \emph{keyed} PRF
        built to stop flooding. Swift's \ct{Hasher} uses SipHash-1-3, keyed by a
        \textbf{random per-process seed} (\ct{SWIFT\_DETERMINISTIC\_HASHING=1} to
        pin it in tests).
  \item \textbf{HashDoS} (28C3, 2011): an attacker who knows an unkeyed hash
        posts thousands of keys that collide → every insert walks one chain →
        O(n\textsuperscript{2}) CPU from one request. The secret seed makes the
        collision set unpredictable. Cost: \ct{hashValue} and \ct{Set} order change
        every launch.
\end{itemize}

\section{Collisions — normal, then resolved}
\begin{itemize}
  \item \textbf{Birthday bound}: with $m$ possible values, a collision is
        likely after $\sim\!\sqrt{m}$ items: $P \approx 1 - e^{-n^2/2m}$. 23 people →
        50\,\%; a 64-bit hash → $\sim$2\textsuperscript{32} (4 billion) items;
        UUIDv4 (122 random bits) → $\sim$2.7$\times$10\textsuperscript{18}. SHA-256
        collision work = 2\textsuperscript{128}, not 2\textsuperscript{256}.
  \item \textbf{Chaining} (list per bucket; Java \ct{HashMap} turns a chain of
        $\ge$8 into a red-black tree). \textbf{Open addressing}: linear probing
        (cache-friendly, primary clustering), quadratic, double hashing,
        \textbf{Robin Hood} (steal the slot from a key nearer its home — evens
        probe lengths), \textbf{cuckoo} (2 tables, O(1) worst-case lookup).
        Deletion needs \textbf{tombstones} or backward shift.
  \item \textbf{Rehash}: at load $\alpha$ $\approx$ 0.75 (Swift: 3/4) double
        and re-insert all — O(n) once, O(1) amortised, a visible \emph{latency
        spike}. Redis rehashes \textbf{incrementally} (two tables, move a few buckets
        per op).
  \item \textbf{Consistent hashing}: \ct{hash(key) \% N} remaps $\sim$all keys
        when N changes; the ring moves $\sim$K/N. 100–200 vnodes per server smooth
        load and spread a dead node's keys over \emph{all} survivors. Alternatives:
        \textbf{rendezvous} (highest random weight), \textbf{jump hash} (no memory,
        numbered buckets only).
\end{itemize}

\section{Example — Hashable right, and a stable hash}
\begin{lstlisting}[language=SwiftSheet]
struct User: Hashable {
  let id: Int; var displayName: String         // not identity
  static func == (a: User, b: User) -> Bool { a.id == b.id }
  func hash(into h: inout Hasher) { h.combine(id) }  // SAME fields as ==
}
// hashValue changes per launch: never persist it. A stable key:
import CryptoKit
let name = SHA256.hash(data: Data(url.absoluteString.utf8))
  .map { String(format: "%02x", $0) }.joined()  // cache file name
\end{lstlisting}

\columnbreak

\section{Cryptographic hashes}
{\scriptsize
\begin{tabular}{@{}>{\raggedright\arraybackslash}p{22mm}>{\raggedright\arraybackslash}p{27mm}>{\raggedright\arraybackslash}p{19mm}@{}}
\toprule
\textbf{property} & \textbf{attacker cannot…} & \textbf{SHA-256 cost}\\
\midrule
preimage & find $x$ from $H(x)$ & 2\textsuperscript{256}\\
second preimage & given $x$, find $x' \neq x$, same $H$ & 2\textsuperscript{256}\\
collision & find \emph{any} pair $x \neq y$ & 2\textsuperscript{128} (birthday)\\
\bottomrule
\end{tabular}}
\textbf{MD5}: collisions in seconds; \textbf{SHA-1}: public collision 2017
(SHAttered). Both dead for signatures/integrity; fine only as checksums.
SHA-256 / SHA-512 are Merkle–Damgård → \textbf{length extension}: from
$H(k \Vert m)$ anyone computes $H(k \Vert m \Vert pad \Vert m')$. SHA-3 and
BLAKE2/3 don't have it.

\section{MAC: HMAC vs a plain hash}
A plain hash proves integrity only against \emph{accidents} — anyone can
recompute it. \textbf{HMAC}$(K,m) = H\big((K \oplus opad) \Vert H((K \oplus ipad)
\Vert m)\big)$: only a key holder can make or check the tag, and the nesting
defeats length extension. Compare tags in \textbf{constant time}
(CryptoKit \ct{isValidAuthenticationCode}), never with \ct{==}.

\section{Password hashing — slow on purpose}
{\scriptsize
\begin{tabular}{@{}>{\raggedright\arraybackslash}p{12mm}>{\raggedright\arraybackslash}p{27mm}>{\raggedright\arraybackslash}p{30mm}@{}}
\toprule
\textbf{function} & \textbf{OWASP minimum} & \textbf{note}\\
\midrule
\textbf{Argon2id} & m=19\,MiB, t=2, p=1 & PHC winner; memory-hard; first choice\\
scrypt & N=2\textsuperscript{17}, r=8, p=1 & memory-hard\\
bcrypt & cost $\ge$ 10 & CPU only; input cut at \textbf{72 bytes}\\
PBKDF2 & 600\,000 $\times$ HMAC-SHA256 & FIPS; GPU-friendly, weakest\\
\bottomrule
\end{tabular}}
SHA-256 does $\sim$10\textsuperscript{10} guesses/s on one GPU; Argon2id a handful
per core — that ratio \emph{is} the defence. \textbf{Salt} (unique, public) kills
rainbow tables and same-password-same-hash; \textbf{pepper} (secret, outside
the DB) makes a DB-only leak uncrackable. Hash on the \textbf{server}.

\section{Bloom filter}
$m$ bits, $k$ hash functions. No false negatives, tunable false positives:
$p \approx (1-e^{-kn/m})^k$; best $k = (m/n)\ln 2$; \textbf{1\,\% ≈ 9.6 bits per
item, k = 7}. No delete (counting Bloom filter can). Use: skip a disk/network
lookup for keys that surely aren't there (LSM-tree databases, CDN caches).

\section{Interview traps}
\begin{itemize}
  \trap{Persisting \ct{hashValue} / asserting \ct{Set} order — changes per launch.}
  \trap{\ct{hash(into:)} using a field \ct{==} ignores, or mutating a key after
        insertion → lost or duplicate entries.}
  \trap{SHA-256(password), even salted — too fast. And $H(key \Vert msg)$ is not a MAC.}
  \trap{``A hash is encryption'' — no key, no inverse. ``Collision = 2\textsuperscript{256}'' — it's 2\textsuperscript{128}.}
\end{itemize}

\section{Remember}
\textbf{Tables: fast + seeded. Integrity: SHA-256. Authenticity: HMAC.
Passwords: Argon2id + salt. Membership at scale: Bloom.}

\section{Likely questions}
\begin{enumerate}
  \item Why is Swift's hash seeded? — HashDoS; so never persist it.
  \item Why vnodes? — even load; a dead node's keys spread over all.
  \item Bloom says yes? — maybe; says no — definitely no.
  \item SHA-256 for a \ct{Dictionary}? — too slow; seeded SipHash already stops flooding.
  \item Why HMAC, not $H(k \Vert m)$? — length extension forges the latter.
  \item Store passwords? — Argon2id, per-user salt, PHC string; re-hash on login when params rise.
\end{enumerate}

\end{multicols}

\noindent{\footnotesize\color{sheetGrey}\textit{Related:} data-structures ·
designing-data-structures · crypto-cryptokit · keychain-secure-enclave ·
distributed-system-design (sharding)}

\end{document}