| 1 | package idear |
| 2 | |
| 3 | import ( |
| 4 | "net" |
| 5 | "net/http" |
| 6 | "net/netip" |
| 7 | "sync" |
| 8 | "time" |
| 9 | ) |
| 10 | |
| 11 | // RateLimit bounds how often ONE client may hit idear's two public |
| 12 | // routes. Both of them read a secret: GET /invitations/{token} answers |
| 13 | // questions about an invitation to anyone holding the token, and POST |
| 14 | // /invitations/{token} spends one. An unauthenticated lookup of a |
| 15 | // secret that answers as fast as the network allows is a free oracle, |
| 16 | // so the limiter is not optional and there is no way to switch it off |
| 17 | // — only to widen it. |
| 18 | // |
| 19 | // The defaults are a token bucket of Burst requests that refills one |
| 20 | // token every Every: twenty at once, then one every three seconds |
| 21 | // (twenty a minute sustained). A person opening their invitation link |
| 22 | // and posting it never notices; a script walking the 2^256 token space |
| 23 | // gets twenty guesses a minute out of one address, which is not a |
| 24 | // meaningful improvement on none. |
| 25 | type RateLimit struct { |
| 26 | // Burst is how many requests a client may make back to back. |
| 27 | // Default 20. |
| 28 | Burst int |
| 29 | |
| 30 | // Every is how long one token takes to come back. Default 3s. |
| 31 | Every time.Duration |
| 32 | |
| 33 | // Max is the ceiling on how many clients are tracked at once — |
| 34 | // the memory bound. Default 4096. |
| 35 | // |
| 36 | // When the table is full, idear first drops every bucket that has |
| 37 | // refilled to Burst (such a bucket is indistinguishable from a |
| 38 | // client that has never been seen, so dropping it costs nothing |
| 39 | // and forgives nobody). If it is STILL full, the request is |
| 40 | // REFUSED rather than admitted: on a route whose whole job is to |
| 41 | // slow down guessing, an overflowing table is evidence of the |
| 42 | // attack the limiter exists for, and failing open there would |
| 43 | // make Max the way around the limit. The cost is that a wide |
| 44 | // enough spray can lock out real invitees for as long as it lasts |
| 45 | // — stated so it is a decision and not a surprise. |
| 46 | // |
| 47 | // A routed IPv6 allocation (a /48 or /56) can supply thousands of |
| 48 | // the distinct keys this table tracks from ONE attacker; see |
| 49 | // clientIP for the sizing this implies for Max. |
| 50 | Max int |
| 51 | } |
| 52 | |
| 53 | const ( |
| 54 | defaultRateBurst = 20 |
| 55 | defaultRateEvery = 3 * time.Second |
| 56 | defaultRateMax = 4096 |
| 57 | ) |
| 58 | |
| 59 | // limiter is the bounded in-memory token bucket behind RateLimit. One |
| 60 | // per *Handlers, so it is per-process and NOT shared between replicas: |
| 61 | // two instances behind a load balancer give a client two budgets. That |
| 62 | // is a real weakening and it is accepted, because the alternative is a |
| 63 | // database write on every unauthenticated request — which is the |
| 64 | // resource the limiter is trying to protect. |
| 65 | type limiter struct { |
| 66 | burst float64 |
| 67 | every time.Duration |
| 68 | max int |
| 69 | |
| 70 | // now is the clock, injectable so a test can prove the refill |
| 71 | // without sleeping through it. |
| 72 | now func() time.Time |
| 73 | |
| 74 | mu sync.Mutex |
| 75 | buckets map[string]*bucket |
| 76 | } |
| 77 | |
| 78 | type bucket struct { |
| 79 | tokens float64 |
| 80 | seen time.Time |
| 81 | } |
| 82 | |
| 83 | func newLimiter(rl RateLimit) *limiter { |
| 84 | if rl.Burst <= 0 { |
| 85 | rl.Burst = defaultRateBurst |
| 86 | } |
| 87 | if rl.Every <= 0 { |
| 88 | rl.Every = defaultRateEvery |
| 89 | } |
| 90 | if rl.Max <= 0 { |
| 91 | rl.Max = defaultRateMax |
| 92 | } |
| 93 | return &limiter{ |
| 94 | burst: float64(rl.Burst), |
| 95 | every: rl.Every, |
| 96 | max: rl.Max, |
| 97 | now: func() time.Time { return time.Now() }, |
| 98 | buckets: make(map[string]*bucket), |
| 99 | } |
| 100 | } |
| 101 | |
| 102 | // allow spends one token for key, reporting whether the request may |
| 103 | // proceed. It is safe for concurrent use: the two public routes are |
| 104 | // exactly where concurrent unauthenticated traffic arrives. |
| 105 | func (l *limiter) allow(key string) bool { |
| 106 | l.mu.Lock() |
| 107 | defer l.mu.Unlock() |
| 108 | |
| 109 | now := l.now() |
| 110 | b, ok := l.buckets[key] |
| 111 | if !ok { |
| 112 | if len(l.buckets) >= l.max { |
| 113 | l.sweep(now) |
| 114 | } |
| 115 | if len(l.buckets) >= l.max { |
| 116 | // Fail closed. See RateLimit.Max. |
| 117 | return false |
| 118 | } |
| 119 | b = &bucket{tokens: l.burst, seen: now} |
| 120 | l.buckets[key] = b |
| 121 | } else { |
| 122 | l.refill(b, now) |
| 123 | } |
| 124 | if b.tokens < 1 { |
| 125 | return false |
| 126 | } |
| 127 | b.tokens-- |
| 128 | return true |
| 129 | } |
| 130 | |
| 131 | // refill credits a bucket for the time since it was last touched, |
| 132 | // capped at burst. |
| 133 | func (l *limiter) refill(b *bucket, now time.Time) { |
| 134 | if elapsed := now.Sub(b.seen); elapsed > 0 { |
| 135 | b.tokens += float64(elapsed) / float64(l.every) |
| 136 | if b.tokens > l.burst { |
| 137 | b.tokens = l.burst |
| 138 | } |
| 139 | } |
| 140 | b.seen = now |
| 141 | } |
| 142 | |
| 143 | // sweep drops every bucket that has refilled to full. A full bucket |
| 144 | // carries no state a fresh one would not have, so this frees memory |
| 145 | // without forgiving anybody: a client mid-penalty is never swept. |
| 146 | // |
| 147 | // Called only when the table is at Max, which is why there is no |
| 148 | // background goroutine here — a limiter with no traffic needs no |
| 149 | // sweeper, and a *Handlers must not leak one for the life of the |
| 150 | // process. |
| 151 | func (l *limiter) sweep(now time.Time) { |
| 152 | for k, b := range l.buckets { |
| 153 | l.refill(b, now) |
| 154 | if b.tokens >= l.burst { |
| 155 | delete(l.buckets, k) |
| 156 | } |
| 157 | } |
| 158 | } |
| 159 | |
| 160 | // size is the number of tracked clients — for the test that proves the |
| 161 | // table is actually bounded. |
| 162 | func (l *limiter) size() int { |
| 163 | l.mu.Lock() |
| 164 | defer l.mu.Unlock() |
| 165 | return len(l.buckets) |
| 166 | } |
| 167 | |
| 168 | // clientIP is the default rate-limit key: the client's NETWORK, not |
| 169 | // its address. |
| 170 | // |
| 171 | // It is "per-IP-ish" and not per-person on purpose — there is nobody |
| 172 | // to identify on an unauthenticated route. |
| 173 | // |
| 174 | // THE FOLD TO /64 IS THE WHOLE POINT, and keying on the bare address |
| 175 | // was a defect rather than a simplification. Every IPv6 host is handed |
| 176 | // a /64: that is 2^64 source addresses, free to rotate, one per |
| 177 | // request. Keyed on the address, each one is an unseen client with a |
| 178 | // fresh burst, so the per-client limit does not exist at all — and it |
| 179 | // is worse than a limit that merely leaks. Folding to the /64 gives a |
| 180 | // SINGLE-/64 attacker one bucket, which is what it should always have |
| 181 | // had. |
| 182 | // |
| 183 | // It does not give a ROUTED attacker one bucket. A /48 or /56 — |
| 184 | // ordinary residential and business allocations, not an exotic |
| 185 | // stretch — carries 65,536 or 16,384 distinct /64s respectively, and |
| 186 | // every one folds to a different key. That is easily enough to fill |
| 187 | // a default-sized (4,096-entry) table on its own, at which point |
| 188 | // allow FAILS CLOSED and refuses every UNSEEN client on the table: |
| 189 | // real invitees, and orphans, whose only healing path is |
| 190 | // POST /invitations/{token}. One machine holding a /56 can hold an |
| 191 | // instance in that state indefinitely. Failing closed is still the |
| 192 | // right direction on a guessing-slowdown; the /64 fold is still |
| 193 | // strictly better than keying on the bare address (2^64 keys instead |
| 194 | // of 2^16). It is not, by itself, enough to assume one attacker means |
| 195 | // one bucket. |
| 196 | // |
| 197 | // Size RateLimit.Max with that in mind: it bounds MEMORY, not |
| 198 | // attacker-controlled prefixes, so raising it only buys headroom |
| 199 | // against a /48-or-wider spray, never immunity from one — the fold is |
| 200 | // fixed at /64 and is not configurable. An app that expects hostile |
| 201 | // IPv6 traffic should set Max well past the default (each entry is a |
| 202 | // handful of words, so a table sized in the hundreds of thousands |
| 203 | // costs low-single-digit megabytes) and treat the fail-closed path as |
| 204 | // a real operational outcome to monitor for, not a theoretical one. |
| 205 | // |
| 206 | // IPv4 is used whole (a /32), which is the same rule read the same |
| 207 | // way: the smallest unit an operator is routinely handed. Folding |
| 208 | // IPv4 further would put a whole CGNAT or campus behind one bucket. |
| 209 | // IPv4-mapped v6 addresses (::ffff:203.0.113.9) are unmapped first, |
| 210 | // so one client cannot hold two budgets by switching representation. |
| 211 | // |
| 212 | // Behind a reverse proxy EVERY request arrives from the proxy's |
| 213 | // address and they would share a single bucket, which turns the |
| 214 | // limiter into a global one and locks out real invitees; an app in |
| 215 | // that shape must set HandlerConfig.ClientKey to read its own TRUSTED |
| 216 | // forwarding header. idear never reads X-Forwarded-For (or any other |
| 217 | // forwarding header) itself, because a header idear cannot verify is |
| 218 | // a header an attacker can spoof to mint unlimited budgets — the |
| 219 | // exact failure the /64 fold exists to prevent, handed over for free. |
| 220 | // TestClientIPIgnoresForwardingHeaders pins that. |
| 221 | func clientIP(r *http.Request) string { |
| 222 | host, _, err := net.SplitHostPort(r.RemoteAddr) |
| 223 | if err != nil { |
| 224 | // No port: a unix socket, or a test. Use it whole rather than |
| 225 | // dropping it, so it still keys to something. |
| 226 | host = r.RemoteAddr |
| 227 | } |
| 228 | addr, err := netip.ParseAddr(host) |
| 229 | if err != nil { |
| 230 | return host |
| 231 | } |
| 232 | // The zone ("fe80::1%eth0") is the local interface, not the |
| 233 | // client, and would split one client's budget in two. |
| 234 | addr = addr.WithZone("") |
| 235 | if addr.Is4() || addr.Is4In6() { |
| 236 | return addr.Unmap().String() |
| 237 | } |
| 238 | prefix, err := addr.Prefix(64) |
| 239 | if err != nil { |
| 240 | return addr.String() |
| 241 | } |
| 242 | return prefix.String() |
| 243 | } |
| 244 | |
amadan