UCA-1: keyless verify never runs Rekor Merkle inclusion proof

[avrabe]

Surfaced by STPA-Sec analysis recorded in docs/security/stpa-keyless-2026-05-25.md, section 4 — UCA-1. PR #136 (v0.9.1) closed two other findings from that report; this is a remaining gap.

What's missing

`KeylessVerifier::verify` calls only `RekorKeyring::verify_set` (`signer.rs:612`). The Merkle inclusion proof verifier exists at `rekor_verifier.rs:724` and a wrapper at `format.rs:437`, but neither is ever called from the production verify path.

Verification trail:

• `grep -n 'verify_inclusion_proof\|verify_rekor_inclusion\|verify_entry' src/lib/src/signature/keyless/signer.rs` → 0 hits.
• `grep -rn 'verify_rekor_inclusion'` → only the definition (`format.rs:452`) and a unit test (`format.rs:787`).

Why it matters

Rekor's SET attests "Rekor signed this `(body, integratedTime, logID, logIndex)` tuple at some point." It does not prove inclusion in the Merkle tree. A misbehaving Rekor instance, a Rekor key compromise, or a Rekor operator producing parallel "side log" entries that are signed but never integrated would still pass `verify_set`. SLSA L4 non-falsifiability is dropped.

Cross-ref

Strengthens the prior audit's C-5 finding (which framed this as "inclusion-proof failures silently downgraded to SET-only fallback"). The actual code is stronger than C-5 stated: there is no inclusion-proof attempt at all, so nothing to fall back from.

Suggested fix

After `verify_set` succeeds at `signer.rs:612`, also call:

```rust
verifier.verify_inclusion_proof(&keyless_sig.rekor_entry)?;
```

Cache the verified inclusion proof in the same cache slot. See also UCA-4 (#TBD) — cache-consumption semantics need fixing in the same change for the inclusion-proof bypass and the cache-skip bypass not to compose.

Acceptance

• New step in `KeylessVerifier::verify` between `verify_set` and `verify_artifact_binding` (or fold into the existing Rekor block).
• Test: end-to-end fixture with a tampered `inclusion_proof` field must reject with `VerificationFailed`.
• Test: missing `inclusion_proof` must reject (fail-closed).
• CHANGELOG entry under next patch release.

[avrabe]

Reclassified: the verifier is broken against current Rekor, not just unwired

Attempted in the v0.9.2 branch (PR #141) to wire KeylessSignature::verify_rekor_inclusion() into KeylessVerifier::verify immediately after verify_set. The CI "Sign & Verify Example" job (a real keyless sign→verify round-trip against production Sigstore) then failed at the verify step:

Rekor SET verified successfully
Rekor error: Computed root hash does not match expected root.
  Computed: a3dd3a1be9da7a8b9f3dfc93f42a07a77fe495d897898427ae6961c830b93bc9
  Expected: b32b6966d032d8b67dd6a1176d8b512ea0f503547ae753c215bf8ba80a50a406

For a freshly signed, legitimately integrated entry (Rekor log index 1672253805, shard log2025-1.rekor.sigstore.dev). The signing path does capture the inclusion proof (rekor.rs:build_rekor_entry_from_response fail-closes if it's missing), so this is not a missing-proof problem — the verifier recomputes the wrong Merkle root from a valid proof.

Root cause (likely)

The log2025-* shard hostname indicates Sigstore's Rekor v2 / tiled-log migration. The leaf-index → Merkle-path mapping (and/or the RFC 6962 leaf-hash derivation from the body) that RekorKeyring::verify_inclusion_proof / merkle::verify_inclusion_proof use no longer matches the live log. The verifier had never been on the production verify path, so this latent breakage was never observed.

Consequence for this issue

The suggested fix ("just call verify_inclusion_proof after verify_set") is insufficient — it assumed the verifier was correct and merely unwired. It is not. Enabling it fail-closed rejects all legitimate keyless signatures (DoS), which is strictly worse than the silent UCA-1 gap.

Decision: UCA-1 is descoped from v0.9.2 (which ships UCA-4 #139 + UCA-5 #140). This issue stays open and is reclassified from "wire in the existing verifier" to "fix the inclusion-proof verifier against Rekor v2 tiled logs, then wire it in". Acceptance must include the "Sign & Verify Example" round-trip passing.

Note the CI job "Rekor Verification Tests (Fresh Data)" does not catch this — it runs --ignored with continue-on-error: true against hardcoded data, so it neither gates nor exercises a fresh end-to-end proof.

[avrabe]

Root-cause investigation (why the verifier computes the wrong root against log2025-*)

Researched the Rekor v2 / rekor-tiles format against the observed failure (SET verifies; merkle::verify_inclusion_proof computes root a3dd3a1b… ≠ proof root b32b6966… for a fresh entry). The merkle math in merkle.rs is textbook RFC 6962 and is not the bug — the inputs are derived the Rekor v1 way, which is wrong for the tiled log.

What Rekor v2 (rekor-tiles / Trillian-Tessera) changed

1. Leaf-hash preimage. rekor-tiles verifies with a caller-provided entry hash rather than SHA256(0x00 || CanonicalizedBody). Clients must reconstruct the entry body and JSON-canonicalize it before hashing; the leaf is not simply the server-returned body field. Our verifier does compute_leaf_hash(base64_decode(entry.body)) = the v1 formula over the server body → wrong leaf → wrong root.
2. Coordinates come from the checkpoint, not the proof JSON. v2: log_index from TransparencyLogEntry.log_index; root hash + tree size parsed from a verified C2SP checkpoint (multi-signature, signed-note key IDs). Our code reads proof.root_hash / proof.tree_size / proof.log_index from the entry's proof JSON and treats the checkpoint as optional.
3. Proofs are no longer served by an API — clients fetch tiles and compute the proof. Our bundle carries a proof shaped like the old API response.

Exact code that assumes v1

• rekor_verifier.rs:~754 — leaf_hash = merkle::compute_leaf_hash(base64_decode(entry.body)) (v1 preimage).
• rekor_verifier.rs:790-800 — root/tree-size read from proof.* instead of the verified checkpoint.
• merkle.rs:107 verify_inclusion_proof(proof.log_index, proof.tree_size, …) — fed v1-derived coordinates.

Fix design (for a focused session)

1. Derive the leaf hash per rekor-tiles (reconstruct + RFC 8785-canonicalize the entry, then Tessera/RFC6962 leaf hash). Confirm the exact preimage against sigstore/rekor-tiles pkg/verify + sigstore-go pkg/verify/tlog.
2. Verify the C2SP checkpoint signature first, then take root/tree-size from it; use TransparencyLogEntry.log_index.
3. Keep the RFC 6962 walk in merkle.rs (it's correct) but feed it the checkpoint-derived coordinates.
4. Version-detect: keep the v1 path for rekor.sigstore.dev legacy entries, add the v2 path for log2025-*.

The real unblocker (makes this locally testable)

Today this can only be validated via the CI `Sign & Verify Example` job (no local OIDC), which is why v0.9.2 descoped it. First step of the fix should be committing a real v2 keyless bundle as a test fixture — then `verify_rekor_inclusion` becomes unit-testable locally, exactly like the UCA-2 tests. I've already captured one real v2 inclusion proof + C2SP checkpoint + canonicalized body from the v0.9.3 SLSA attestation (rekor tree `1193050959916656506`, treeSize 1807686925) that can seed the fixture.

Status: stays open, now scoped from "wire in the verifier" → "port the inclusion-proof path to rekor-tiles (leaf hash + checkpoint-sourced coordinates), fixture-first so it's locally testable." Not a blind change — it's fail-closed, so a wrong port is a DoS on all keyless verify.

Sources: Rekor v2 GA, sigstore/rekor-tiles, rekor-tiles CLIENTS.md, rekor-tiles verify pkg.