Formal threat model for GitHub gist discoverability, and its connection to capability URLs.

gist-discoverability.md

Gist discoverability as a search problem

Notes from a conversation: if I post a gist, what's the probability an adversary can find it? And how does this connect to object capabilities?

1. Setup

A user $U$ posts a gist $G$ at time $t_0$ with:

• Content $C$ — files, text $T$, possibly identifiers (emails, keys, function names)
• Visibility $v \in {\textsf{public}, \textsf{secret}}$ — GitHub doesn't offer truly private gists outside Enterprise
• Identifier $\mathrm{id}(G)$ — a 32-hex-char string ($\approx 2^{128}$ space) in the URL gist.github.com/{user}/{id}

An adversary $\mathcal{A}$ wants to retrieve $G$ (or just $C$) by time $t_0 + \Delta$. We characterize $\mathcal{A}$ by:

• Prior knowledge $K$ — e.g., they know $U$'s handle, a keyword in $C$, or possess a leaked URL
• Resources $R$ — rate-limited API budget, compute, archive access, ability to subpoena, etc.
• Goal $\Phi$ — targeted (find this gist) vs. content-class (find any gist matching predicate $\phi$)

The quantity of interest:

$$P_{\text{find}}(\mathcal{A}; G, \Delta) = \Pr[\mathcal{A} \text{ outputs } G \mid K, R, v, t_0, \Delta].$$

2. Channels of leakage

A gist becomes reachable through a union of (roughly independent) channels ${Ch_i}$:

$$P_{\text{find}} = 1 - \prod_i \big(1 - P_i(\mathcal{A})\big).$$

Channel	Public $G$	Secret $G$
GET /users/{U}/gists listing	enumerable	excluded
/gists/public firehose (live + ~3000 backlog)	~real-time	—
GHArchive (every public GistEvent since 2011, in BigQuery)	permanent	—
gist.github.com keyword search	indexed	—
Google / Bing / Kagi web index	if crawlable	only if URL leaked into a crawled page
Brute-force id enumeration	n/a	$\approx 2^{-128}$ per query
Referer leaks, screenshots, browser sync, paste history	possible	possible
Subpoena / GitHub insider	yes	yes

Secret-gist privacy is essentially URL-capability security: knowledge of the URL ≡ access. There is no access control beyond unguessability.

3. Per-channel cost models

Public listing (targeted, $K$ = know user). $P = 1$, cost $\Theta(n_U / 100)$ API calls.

Public firehose (untargeted scrape). Backlog cap means $P \to 0$ for $\Delta$ exceeding the firehose retention window unless $\mathcal{A}$ was streaming continuously since $t_0$. With continuous streaming, $P = 1$ at ~1 req/sec.

GHArchive. Removes the streaming requirement: any public gist event is recoverable for arbitrary $\Delta$. Cost: a few BigQuery dollars. This is the dominant capability for "find anything public, ever."

Content search by predicate $\phi$. GitHub's gist search is shallow; the realistic adversary uses GHArchive + their own indexer over fetched contents. Recall $\approx 1$ for keyword $\phi$; cost dominated by fetching candidates (5000/hr authenticated, 60/hr anonymous).

Brute force on secret id. $P \approx Q / 2^{128}$ for $Q$ queries. Negligible: even at $10^9$ guesses/sec, expected time $\sim 10^{22}$ years.

URL leakage. The only meaningful attack on secret gists, and not a search problem — it's a side-channel. Probability depends on $U$'s handling: pasting in chat, embedding in a public page, sharing via tools that log Referer. Hard to bound a priori; empirically nonzero and dominated by user behavior.

4. Adversary models, ranked

1. Passive untargeted observer — wants any gist matching $\phi$.

   • Public: $P_{\text{find}} \approx 1$ via GHArchive + fetch. This is how secret-scanning bots find leaked AWS keys within minutes.
   • Secret: $P_{\text{find}} \approx 0$.

2. Targeted observer (knows $U$) — wants $U$'s gists.

   • Public: $P = 1$ trivially.
   • Secret: $P \approx 0$ from GitHub alone; reduces to URL-leak probability.

3. Content-targeted adversary (knows distinguishing string $s \in C$).

   • Public: $P \to 1$ once GHArchive ingests $t_0$ (lag: minutes to an hour).
   • Secret: $P \approx 0$ unless $s$ also appears in a crawled page that links to the gist.

4. URL-capability adversary (has the secret link). Sources: scraped Slack/Discord exports, paste sites, browser history, stolen device. $P = 1$ for both visibilities. This is the realistic threat model for secret gists.

5. Legal/insider (subpoena, GitHub employee). $P = 1$ regardless.

5. Headline result

$$ P_{\text{find}} \approx \begin{cases} 1 & v = \textsf{public} \text{ and } \mathcal{A} \text{ has GHArchive-class resources} \\ P_{\text{leak}}(U) & v = \textsf{secret},\ \mathcal{A} \text{ external} \\ 1 & \mathcal{A} \text{ insider/legal} \end{cases} $$

The interesting quantity is $P_{\text{leak}}(U)$ — the probability that the user themselves exposes the secret URL through some side channel. That's a behavioral parameter, not a cryptographic one. The 128-bit id only buys security against brute force, which was never the threat.

Practical implication: "Secret" gists are confidentiality-by-capability, not by access control. If you treat the URL as a bearer token, they're as private as the weakest channel they pass through. If you need real access control, gists are the wrong primitive — use a private repo.

---

6. Connection to object capabilities

This is almost exactly the capability URL (a.k.a. "web-key" or "swiss-number URL") pattern. Canonical references:

• Tyler Close, "Web-Key: Mashing with Permission" (W2SP / WWW 2008). The foundational paper: an unguessable URL fragment is a capability in the object-capability sense; possession ≡ authority, no ambient access control needed. The right citation for what gist secret-IDs actually are.

• W3C TAG Finding, "Capability URLs" (Jeni Tennison, 2014). Less formal, more practitioner-facing. Enumerates the leak channels you'd want in $P_{\text{leak}}$: Referer headers, browser history sync, server logs, accidental sharing, search-engine indexing if linked. The empirical companion to Close.

• Mark Miller, "Robust Composition" (PhD thesis, 2006); Miller / Yee / Shapiro, "Capability Myths Demolished" (2003). The general object-capability theory. The bridge to URLs: an unguessable URL behaves as an unforgeable reference as long as the URL stays confidential.

Empirics on gists/paste-sites specifically

• Meli, McNiece, Reaves, "How Bad Can It Git? Characterizing Secret Leakage in Public GitHub Repositories" (NDSS 2019). Quantifies the content-targeted adversary against the public firehose; shows it's devastating — keys get scraped within minutes. truffleHog, gitleaks, and GitHub's own secret-scanning are the operational instantiations.

Where the literature is thinner

The framing above — adversary-model-indexed probability of discovery as a function of channels and resources — is more implicit than explicit in the cap-URL literature, which tends to argue qualitatively ("URLs leak through these channels, design accordingly") rather than putting a $P_{\text{find}}$ on it. The closest formal treatments:

• OAuth bearer-token threat models (RFC 6819, "OAuth 2.0 Threat Model and Security Considerations") — same shape, more enumerated threat catalogue.
• Privacy literature on "practical obscurity" (Reidenberg and others, post-US DOJ v. Reporters Committee) — different vocabulary, but the underlying observation that "technically public but hard to find" collapses under modern indexing is the same phenomenon, on the public-gist side.

The summary

A secret gist URL is a bearer capability with no revocation primitive other than deleting the gist, no attenuation, and no audit trail of delegation. All the classic cap-URL critiques apply. The GHArchive-class adversary on the public side is the dual problem — no capability needed; the namespace itself is enumerable.