Exercises — Network security — DDoS, man-in-the-middle, replay attacks, countermeasures

• (a) Replay. Broken assumption: a valid message is valid only once. Note the attacker never decrypts anything — genuine bytes, faked freshness.
• (b) DDoS (distributed). Broken assumption: the server has enough resources for everyone. "Many machines" = distributed.
• (c) MITM (via ARP spoofing). Broken assumption: I'm talking directly to the real party.

• SYN cookies → DDoS (specifically SYN floods: don't allocate state until the client proves it's real).
• CA-signed certificate → MITM (authentication: bind the public key to the domain name).
• Nonce → Replay (freshness: a repeated nonce is rejected).

WHAT: we want the smallest $\lambda$ that makes occupied slots reach the ceiling $B$. WHY Little's Law: Little's Law says the average number of items inside a system is $L=\lambda W$, where $\lambda$ is the arrival rate and $W$ is the time each item spends inside (both defined in the symbol list above). Here an "item" is a half-open connection, its arrival rate is the SYN rate $\lambda$, and its time-inside is exactly the hold time, so $W=T$. Substituting gives $L=\lambda T$. It answers "how many things are in the system on average" from just rate × time-inside — no simulation needed. ${\lambda }_{\min }=\frac{B}{T}=\frac{512}{30}\approx 17.07\text{SYN/s}.$ So a trickle of ~18 spoofed SYNs per second already jams a naive server. That tiny number is exactly why SYN floods are dangerous — the attacker barely sweats.

(a) $A=\frac{c_s}{c_a}=\frac{3000\text{bytes}}{60\text{bytes}}=50$ (a pure bandwidth ratio — same unit top and bottom). (b) Reflected bandwidth $=A\times (\text{attacker bandwidth})=50\times 2\text{Mbit/s}=100\text{Mbit/s}$. WHY it matters: the victim sees $50\times$ the attacker's output, and the source IPs are innocent resolvers — you can't just blocklist the attacker.

• At $104.2$: $|104.2-100.0|=4.2\le 5$ → accept.
• At $106.2$: $|106.2-100.0|=6.2>5$ → reject (message is "too old", the capture has expired). WHY $\Delta$ exists: it's the trade-off dial — small $\Delta$ blocks replays faster but breaks under clock skew/network delay; large $\Delta$ tolerates lag but leaves a longer replay window.

• SYN cookies: the server holds no state, so effectively $B\to \infty$ (no queue to fill) → ${\lambda }_{\min }=B/T\to \infty$. Direction: ${\lambda }_{\min }$ rises without bound. The formula no longer applies; the flood can't exhaust memory it never used.
• Adaptive/short timeout (SYN-RECV recycling): the server drops the oldest half-open entries early, so effective $T$ shrinks. Since ${\lambda }_{\min }=B/T$, a smaller $T$ raises ${\lambda }_{\min }$ — the attacker must send faster to keep the queue full, because each slot frees sooner.
• Rate limiting (per source): treat it as an effective ceiling. If the limiter admits at most ${\lambda }_{\text{cap}}$ SYNs per source, then a single source must satisfy ${\lambda }_{\text{cap}}\ge B/T$ to collapse the queue — which it usually can't. Direction: the per-source ${\lambda }_{\min }=B/T$ is unchanged, but the rate any one source can actually deliver is capped below it, so a lone attacker can no longer reach ${\lambda }_{\min }$. To still hit $B/T$ in aggregate the attacker needs at least $\lceil (B/T)/{\lambda }_{\text{cap}}\rceil$ distinct sources — and spoofing/botnets supply exactly those many IPs, defeating naive per-IP limits. This is the loophole figure s01 highlights (green floor = the SYN-cookie fix that removes $B$ entirely).

Notation used below (defined before use):

• A shared secret $K$ is the single number two parties end up both knowing after a DH run; nobody who only reads the wire can compute it.
• The double-arrow $X\stackrel{\text{shared secret }K}{\leftrightarrow }Y$ is read as: "$X$ and $Y$ have completed a DH exchange and now jointly hold the secret $K$." It is a relationship label, not an equation — the arrow points both ways because a shared secret is symmetric (both sides hold the same $K$).

WHAT DH gives: each side sends a public value over the wire (Alice's and Bob's DH public values), and from the other side's public value plus its own private number it computes the shared secret. An eavesdropper who only reads the public values cannot derive that secret. So secrecy against a passive listener is real. WHY it still fails: Eve is active, not passive. She intercepts each public value and substitutes her own, running two separate DH exchanges. Below, $K_1$ and $K_2$ are the two resulting shared secrets (not the public values): $K_1$ is the secret Alice and Eve end up computing together, and $K_2$ is the secret Bob and Eve compute together. $\text{Alice}\stackrel{\text{shared secret }{K}_1}{\leftrightarrow }\text{Eve}\stackrel{\text{shared secret }{K}_2}{\leftrightarrow }\text{Bob}.$ Alice thinks $K_1$ is shared with Bob; Bob thinks $K_2$ is shared with Alice — but both secrets are actually held by Eve. Eve decrypts each message with the key for that side and re-encrypts with the other, relaying invisibly. Missing property: authentication. DH never asks "is this public value really from Bob?" The cure is to sign the DH public values (a certificate binds the key to an identity) — exactly what TLS handshake does using Public Key Infrastructure & Certificates.

(a) The "seen" set of used nonces grows forever (memory). If you clear it to save memory, a previously-used nonce becomes acceptable again → the old replay works. Pure nonce = perfect within one session but unbounded state. (b) Timestamps assume the client and server clocks agree (within $\Delta$). If an attacker can push the server's clock (e.g. spoof NTP) or if $\Delta$ is generous, a captured message stays "fresh" long enough to replay. Timestamps bound memory (no set) but trade it for a clock-trust assumption. Best practice: combine them — a short timestamp window plus a nonce set that only needs to remember nonces seen inside the current $\Delta$, keeping memory bounded.

Message: $m\Vert n\Vert t$ where

• $m$ = the actual request ("transfer ₹1000 to Bob"),
• $n$ = a fresh nonce (never reused),
• $t={\text{MAC}}_K(m\Vert n)$ = a tag over both the request and the nonce.

Server accept rule — all three must hold:

1. $t\stackrel{?}{=}{\text{MAC}}_K(m\Vert n)$ recomputed → proves integrity + authenticity (only a holder of $K$ could make it; $m$ untampered).
2. $n\notin \text{SeenSet}$ → proves freshness (not a replay).
3. On accept, insert $n$ into SeenSet.

WHY the MAC covers $n$ too: if the tag were only over $m$, Eve could swap in a new $n$, keep the old valid tag on $m$... but the tag wouldn't match $m\Vert n$ anymore — good. Conversely if we MAC'd $n$ alone, she could keep $n$ and change $m$. Binding both under one tag ties freshness to integrity. This uses Message Authentication Codes (MAC) & HMAC.

Challenge–response (request $m$ bound in, mandatory):

1. Server → Client: a fresh random challenge $r$. Why: $r$ is unpredictable, so a stored old response is useless; and the server owns freshness, so no unbounded client set is needed — $r$ is naturally single-use per session.
2. Client → Server: the pair $m\Vert {\text{MAC}}_K(r\Vert m)$. Why: the tag covers both the fresh challenge $r$ and the request $m$, so the client proves it knows $K$ right now, for this $r$, and $m$ cannot be tampered without breaking the tag. (Binding $m$ is required, not optional — otherwise an attacker who saw a valid ${\text{MAC}}_K(r)$ could attach any request to it.)
3. Server: recompute ${\text{MAC}}_K(r\Vert m)$ using the $r$ it just issued; accept iff it matches and $r$ is still outstanding, then discard $r$. Next session issues a new $r$ → yesterday's reply cannot verify.

Trade-off vs L4.1: costs one extra round-trip, but the server needs to remember only the currently outstanding challenges, not every nonce ever seen.

Keep one metric in mind: effort per request. $A=c_s/c_a$ is the ratio of the server's effort to the attacker's effort for one request; the attacker wins only when $A\gg 1$. SYN cookies drive $c_s\to$ ≈ $c_a$ by lowering $c_s$: the server encodes the connection state inside the initial sequence number it sends back, storing nothing. So a spoofed SYN now costs the server one cheap SYN-ACK computation and no held memory — $c_s$ collapses from "30 s of RAM" to "one hash." With $c_s$ now about as small as $c_a$, we get $A=c_s/c_a\approx 1$: the attacker no longer gains leverage; to hurt the server it must spend as much as the server does, which for a botnet is no longer a bargain. Proof-of-work / CAPTCHA drive $A\to 1$ by raising $c_a$: they force the client to burn CPU (solve a hash puzzle, PoW) or human time (read a CAPTCHA) before the server does its expensive work. Now $c_a$ balloons — say the puzzle costs the attacker as much as serving the request costs the server — so $A=c_s/c_a\approx 1$. A single attacker can no longer cheaply generate millions of costly requests, because each one now costs them real CPU or a human. The unifying idea: the attack lives entirely on $A\gg 1$. There are exactly two levers to force $A\to 1$ — shrink $c_s$ (cookies: don't do expensive work for unverified clients) or grow $c_a$ (PoW/CAPTCHA: make the client pay up front). Both destroy the asymmetry that made the flood profitable.

(a) Over-limit factor $=\frac{\lambda }{{\lambda }_{\min }}=\frac{200}{17.07}\approx 11.7\times$. The pre-fix queue is swamped almost twelve-fold — total collapse for real users. (b) With cookies there is no backlog queue to fill: state lives in the sequence number, freed automatically because it's never stored. $200$ SYN-ACK computations/sec is trivial CPU; there is no resource being exhausted, so the collapse condition $\lambda \ge B/T$ has no $B$ to reference. The attack's leverage ($A$) is gone.

Broken assumption of DDoS ::: server has enough resources for everyone. Broken assumption of MITM ::: I'm talking to the real party (authentication missing). Broken assumption of replay ::: a valid message is valid only once (freshness missing). SYN-flood collapse condition ::: $\lambda \ge B/T$. What SYN cookies change in $A=c_s/c_a$ ::: they slash $c_s$ (no held state) so $A\to 1$. What proof-of-work changes in $A=c_s/c_a$ ::: it grows $c_a$ so $A\to 1$. Why plain DH is MITM-vulnerable ::: it gives secrecy but not authentication of the public values. Two fields a MAC must cover to stop replay ::: the message $m$ and the nonce $n$, together.