# DF-3111 evidence pack — HAMMER1 ALG1 namekey iteration-range overflow

## Finding
`hammer_direntry_namekey()` (sys/vfs/hammer/hammer_subs.c:943-1035, ALG1
branch) returns namekeys up to `0x7fffffffffff0000` while advertising
`max_iterations = 0x00ffffff`, without guaranteeing that
`key + max_iterations` stays in the positive (signed) key space. Every
consumer computes the directory hash-chain scan end with an unchecked
signed addition:

* `cursor.key_end.key += max_iterations` — sys/vfs/hammer/hammer_vnops.c:1234
  (`hammer_vop_nlookup`), :2014 (`hammer_vop_nrename`),
  :3324 (`hammer_dounlink` via nremove/nlink/ncreate whiteout path)

For a crafted filename whose ALG1 namekey is in the "wrap zone"
(`key > 0x7fffffffff000000`), the addition overflows int64 and `key_end`
becomes **negative**. `hammer_btree_iterate()` (sys/vfs/hammer/hammer_btree.c:216,
:277) then rejects every chain element after the first
(`hammer_btree_cmp(key_end, elm) < 0` → ENOENT), and the in-memory record
scan (`hammer_mem_first`/`hammer_rec_scan_cmp`) is truncated the same way.
The collision chain is effectively cut to a single element.

## Exploit (unprivileged local user, any writable ALG1 directory — i.e. any
directory created on a HAMMER1 fs of version >= 6)

The ALG1 hash is crc32-based and CRC-32 over a 4-byte message is a GF(2)
bijection, so a user can *solve* for filenames in the wrap zone
(`solver.h`): force the segment-crc sum to `0x7fffffff` (top hash bucket)
via a 4-byte inverted suffix, brute-force 3 alphabet bytes to land the
whole-name crc in the wrap zone. Two **distinct** names with the identical
47-bit key form a colliding pair.

1. create `nameA` → stored at key K (first chain element; still findable)
2. create `nameB` (same key K) → create-time uniqueness loop bumps it to K+1
3. from then on, every lookup of `nameB` positions at nameA's record (first
   element ≥ K), bcmp fails, `hammer_btree_iterate` clamps the scan with the
   wrapped key_end → **ENOENT**, although the dirent exists on disk
4. `unlink`/`rename` of `nameB` fail forever (persist across unmount/reboot);
   `ls` keeps listing the phantom name (`readdir` scans to `HAMMER_MAX_KEY`)
5. every re-create after a namecache miss leaks **another** unremovable
   dirent+inode at K+2, K+3, … → unremovable disk-space exhaustion

## Build (guest)
```sh
cc -O2 -o /root/trig /root/trig.c        # includes solver.h
cc -O2 -o /root/recheck /root/recheck.c
```

## Run (guest, as root; both binaries drop to uid/gid 65534 themselves)
```sh
sh /root/run.sh
```
`run.sh`: makes a 4G image, `newfs_hammer -f` (version 7 ⇒ ALG1), mounts on
/mnt, then:
* STAGE 1 `/root/trig /mnt/t` — creates the pair as nobody; `unlink nameB`
  already returns ENOENT while `readdir` lists it
* STAGE 2 — sync, umount, mount (flush + cold namecache)
* STAGE 3 `/root/recheck /mnt/t` — durable proof:
  `stat nameB → ENOENT`, `unlink nameB → ENOENT`, readdir lists nameB,
  5 re-creates leak a 2nd unremovable dirent

## Expected output (vulnerable kernel)
```
persist stat   nameB : No such file or directory   <-- POISONED (dirent exists on disk)
persist unlink nameB : No such file or directory   <-- UNREMOVABLE
after 5 re-creates   : readdir nameB cnt = 2 (was 1)   <-- LEAK
```
(see run.log; note `stat nameB` right after create can succeed through the
positive namecache entry — stage 1 documents this; stage 3 is cold-cache.)

## Fix validation
`fix.diff` clamps `*max_iterationsp` in `hammer_direntry_namekey()` so
`key + max_iterations <= INT64_MAX`. Apply to /usr/src in the guest,
`make nativekernel`, reboot, re-run: `nameB` resolves normally and
`unlink nameB` succeeds (see fix_run.log / VERDICT.md).

## Files
* `solver.h`    — shared GF(2) CRC-32 inversion + exact ALG1 replica + pair search
* `trig.c`      — stage-1 trigger (unprivileged)
* `recheck.c`   — stage-3 durable/persistence check (unprivileged)
* `run.sh`      — end-to-end reproduction script
* `run.log`     — full untrimmed output of the decisive run
* `env.txt`     — guest uname, fs version, mount state
* `fix.diff`    — the verified fix (authored after reproduction; never applied to sys/)