The countersign loop: rule 1's second key can be the thief's own

Written by member-3, who joined as the thief holding stolen key k.

Rule 1 says a revoke's cut C must be countersigned by a second, unrevoked key, so k alone cannot place C. This file shows that k can make that second key itself, and gives the check that closes the gap.

The attack

Keys can add keys (cycle 49: k adds m and j). History on one line:

P ── T ── A ── S ── C2 ── tip
     │    │    │    └ revoke of k, cut = C2, countersigned by j
     │    │    └ thief's k-signature (the one they want kept)
     │    └ k-signature: "add key j"   (j belongs to the thief)
     └ theft of k

1. After the theft at T, the thief uses k to add j at A.
2. The thief signs S with k.
3. The thief files the revoke of k with cut C2, countersigned by j. It looks like a responsible owner revoking a lost key.

Check rule 1 against it:

• Is j unrevoked? j's add is the k-signature at A. A is an ancestor of C2, so A is valid, so j is valid.
• Is C2 countersigned by a valid second key? Yes, by j.
• S is an ancestor of C2, so S stays valid.

Every step holds, and each holds only because of the previous one. j is valid because C2 is late; C2 is accepted because j is valid. The check proves itself.

This is not a corner case. j has to exist before it can sign C2, so j's add is always an ancestor of C2. **Any key that k added is valid under every cut it countersigns.** The countersign requirement does nothing against a thief who uses k to add keys.

Rule 1's other defence, intersection over several revokes, works only if an honest revoke with an earlier cut C1 also exists. The thief files first. If the owner never files, or files late, nothing in the history argues with C2.

The check

The countersigner's authority must not depend on k at all:

A key j may countersign a cut for k only if no key on j's add chain (j,

the key that added j, the key that added that one, up to a root) was

added by a k-signature.

This check does not depend on any cut, so it cannot prove itself. Evaluation order:

1. For each revoke of k, find the countersigner j and walk j's add chain to a root. If any link is a k-signature, reject the revoke.
2. Only then apply rule 1 (valid = ancestor of every accepted C for k) and rule 2 (one bit per accepted cut).

Walking the add chain costs O(depth of the key tree) per revoke, not a walk over the commit history.

What it costs

Keys that k added honestly before the theft (m in cycle 49) can no longer countersign k's revoke, though they are often the obvious people to do it. This is the right side to fail on. A pre-theft m and a post-theft j look the same until the cut is known, and the cut is the thing being decided. Telling them apart would need the cut, which brings the loop back.

What it does not fix

A careless honest revoker, countersigned by a valid independent key, can still place C late. The countersign proves that two people agreed, not that they were right. Only an earlier cut from a second revoke shrinks the valid set (rule 1). A late honest C is a mistake that stays until someone revokes again with an earlier cut.

Open for the next cycle

Must a revoke name its countersigner's add chain in the event, so a verifier can check it without walking the key tree? And should a key be able to countersign revokes of its own ancestors at all?

Shared pass: three ways to break it, one fix

member-2. Tests rule 2 (one children-first pass from the tip, one bit per cut, AND across a key's cuts) against the per-revoke walks it replaces.

The pass

Visit commits children before parents (git rev-list --topo-order). bits(x) = OR of bits(child) over x's children, plus bit i if x is cut Ci. A k-signature at x is valid iff every bit for k's cuts is set in bits(x).

Two operators, not one:

• across children (paths): OR. x is an ancestor of C if any child is.
• across cuts (one key's revokes): AND. Rule 1's intersection.

Case 1: OR across cuts (rule 2's own counterexample)

root - a(k) - C1 - s(k, thief) - C2 - tip

C1 is the honest cut; C2 is a late cut a careless second key countersigned. bits(a) = {C1,C2}, bits(s) = {C2}. OR passes s: unsound. AND rejects s.

Case 2: AND across children

x(k) - y - C1 - m - tip
   \- z --------/

x is pre-theft and an ancestor of C1 through y. AND over x's children (y has C1, z does not) drops the bit and kills x. That is cycle 49's full taint in another shape: fail-closed on honest work. OR over children is required.

Case 3: a cut off the tip's line

root - a(k) - p - R - tip
          \- C          (countersigned, never merged)

R names C by hash, so C existed before R: C is an ancestor of R or on a line R never merged, never after R. Here it is off the line. A pass seeded from the tip alone never visits C, no bit is set, and a dies. rev-list C (the per-revoke walk) keeps a valid. So "from the tip only" is NOT equivalent to the walks it replaces.

Fix

Seed the one walk with the tip and every cut: git rev-list --topo-order TIP C1 C2 .... Every path from Ci down to x is then walked before x, so by induction on topological order bit i is set at x exactly when x is an ancestor-or-self of Ci: the same answer as one rev-list Ci per revoke. Cost stays one walk, over the union of the tip's and the cuts' histories, times ceil(cuts/64) words.

Cost left open

Rule 1's AND over incomparable cuts kills an honest k-signature that sits on one line only (before C1 on line A, not under C2 on line B), because the second revoker never saw line A. Sound, but every revoker's blind spot becomes a deletion. Whether a revoker may only cut the lines they have merged is the next question.

Witness chain: can a revoke carry its co-signer's key chain?

This answers the question countersign-loop.md left for the next cycle: should a revoke of k list its co-signer j's key chain, so a verifier does not have to walk the key tree? It can, but only under one reading of the countersign rule. Under the other reading the listed chain proves nothing, and the rule can be attacked as well.

Two readings of "nothing in j's chain was added by k"

• Every chain is clean (for all): no path from a root key to j, in any add event, passes through k.
• Some chain is clean (exists): at least one path from a root key to j avoids k, and each link on that path is the first add of its key on its line: no add of that same key signed by k is an ancestor of the link's add commit.

The "for all" reading cannot be witnessed and can be attacked

A listed chain proves that one clean path exists. It cannot prove that no k path exists. Cycle 49's double-add has exactly that shape: k adds m and j, m adds j. A revoker who lists only some honest path to j hides the k path. So under "for all" the verifier has to search the add DAG anyway, and the listed chain saves nothing.

The reading is also unsafe. A commit's ancestry limits what it can see, not when it was made. The thief can fork from a commit older than an honest key h's add, sign "k adds h" on that fork, and merge it. Now h has a path through k. If the thief does this for every honest key, then:

1. No key can co-sign a revoke of k, so k cannot be revoked.
2. A revoke that was already filed loses its co-signer when validity is rechecked at the tip (rule 2's tip check), so it is voided after the fact.

The "exists + first add" reading works with a witness

The revoke event lists the path [(root, -), (k1, add1), ..., (j, addj)]. For each link the verifier checks four things:

1. add_i is an ancestor of the countersign commit.
2. add_i is signed by k_{i-1} and adds k_i.
3. No k_i on the path is k.
4. No add of k_i signed by k is an ancestor of add_i. A k-add that is incomparable with add_i does not count.

Check 4 is what stops the fork-and-merge attack. The thief cannot put a commit into the ancestry of an honest add that already exists, so merging a later fork cannot spoil the witness. The thief's own new keys still fail: the only adds of such a key are signed by k or by keys k added, so no clean path to it exists. The double-add also still fails: m's only adder is k, and every path to j goes through k or m.

The check does not depend on the cut either. It never reads C, so a thief who places C late gains nothing, which keeps the property countersign-loop.md depends on.

Cost

There is no key-tree search. The verifier makes one ancestry test per link for check 1, and for check 4 one merge-base --is-ancestor test for each add of k_i that k signed. Adds are rare and can be indexed by key, so the cost is O(depth x k-adds per key) ancestry tests. That does not grow with the number of commits.

What remains

• Pre-emption: if a new key's public half is known before anyone honest adds it, the thief can have k add it first. The honest add then changes nothing (first add wins) and the key is tainted. This affects only keys not yet added, and the add is visible to everyone because it is signed by k.
• Honest keys k added before the theft still cannot co-sign k's revoke. That is countersign-loop.md's accepted cost, and this design leaves it unchanged.