# DF-3111 VERDICT — hammer_direntry_namekey ALG1 iteration-range overflow

## Status: REPRODUCED (durable, unprivileged, persistent on disk)
## Impact: local DoS / filesystem poisoning (unremovable dirents, unremovable
##          space leak) — no memory corruption; medium severity

## Root cause (line-traced)

`hammer_direntry_namekey()` — sys/vfs/hammer/hammer_subs.c:943-1035:

* ALG1 (fs version >= 6, hammer_inode.c:858-862) builds
  `key = (crcx & 0x7fffffff) << 32 | ((crc ^ crc<<16) & 0xffff0000)` and
  returns `*max_iterationsp = 0x00ffffff` (subs.c:1002-1024).
* Nothing enforces `key + max_iterations <= INT64_MAX`: the maximal key is
  `0x7fffffffffff0000`.
* Consumers compute the hash-chain scan end with an unchecked signed add:
  * hammer_vnops.c:1233-1234 (`hammer_vop_nlookup`)
  * hammer_vnops.c:2013-2014 (`hammer_vop_nrename`)
  * hammer_vnops.c:3323-3324 (`hammer_dounlink` → nremove/nlink/whiteout)
  `cursor.key_end.key += max_iterations;`
* For a namekey > `0x7fffffffff000000` this wraps key_end NEGATIVE
  (int64 overflow). `hammer_btree_cmp` is signed, so
  `hammer_btree_iterate()` (hammer_btree.c:216 internal, :277 leaf) rejects
  every element after the first with `r < 0 → ENOENT`; the in-memory chain
  scan (`hammer_mem_first` → `hammer_rec_scan_cmp`) is truncated the same
  way. The directory hash chain is cut to its first element.
* `btree_search()`/`hammer_btree_extract` position/extract by `key_beg`
  only, so the FIRST chain element (and exact-key matches) still resolve —
  this is why `nameA` (slot K) keeps working while the collision-bumped
  `nameB` (slot K+1) becomes invisible.

## Why a user can craft such names (no kernel primitives needed)

ALG1's crcx is an integer sum of CRC-32s over separator-split segments, and
CRC-32 over a 4-byte message is a GF(2) bijection. `solver.h` inverts it to
force the segment sum to `0x7fffffff` (top bucket) and brute-forces 3
alphabet bytes to land the whole-name crc in the wrap zone
(`(crc ^ crc<<16) & 0xffff0000 >= 0xff010000`). 1722 wrap-zone names exist
in that tiny search space alone; two distinct names with the identical
47-bit key form the colliding pair (deterministic):
* nameA `6161616146712e0702dfbf` key=0x7fffffffff180000
* nameB `61616c6a33712e0a09aabf` key=0x7fffffffff180000
* key_end = key + 0xffffff = 0x800000000017ffff (negative)

## Reproduction (full log: run.log; guest DragonFly 6.5-DEVELOPMENT,
## HAMMER1 version 7 image via newfs_hammer -f, /mnt/t mode 1777,
## all PoC steps run as uid/gid 65534)

1. `open(nameA, O_CREAT)` → OK, stored at K.
2. `open(nameB, O_CREAT)` → OK; create-time uniqueness loop
   (hammer_object.c:705-716 `hammer_ip_lookup` + `++key`) bumps it to K+1.
3. `unlink(nameB)` → **ENOENT although readdir lists the entry**
   (both pre-flush and post-flush).
4. sync + umount + mount (cold namecache, dirents on disk):
   * `stat(nameA)` → OK (first chain element)
   * `stat(nameB)` → **ENOENT — POISONED**
   * `unlink(nameB)` → **ENOENT — permanently UNREMOVABLE**
   * `readdir` lists nameB (readdir scans to HAMMER_MAX_KEY,
     hammer_vnops.c:1715-1716) — phantom entry
   * 5 more `open(nameB, O_CREAT)` → **leaks a 2nd unremovable dirent+inode**
     (each namecache-missed re-create appends K+2, K+3, … forever)
5. `ls -la` shows two identical phantom names that stat ENOENT.

Persistence: the state is durable on disk — every future lookup of nameB on
any mount computes the same wrapped key_end → the entry can never be removed
by any API (rm, rename, mv -i, undelete tools) for the life of the
filesystem; the containing directory can never become empty. An unprivileged
user can repeat this at will (one ~11-byte filename each) to consume
unremovable dirent+inode space. Note: a `stat` immediately after create can
succeed through the positive namecache entry — the durable cold-cache state
is what matters (stage 3 of run.log).

## Non-issues checked and killed in this file (pass 2)

* hammer_btree_cmp (hammer_btree.c:~3995 family): pure relational compares,
  no subtraction/shift arithmetic — no signed-wrap family. Clean.
* hammer_time_to_timespec / hammer_timespec_to_time (subs.c:795-809): on
  x86_64 (time_t/unsigned long 64-bit) no 2038/2106 truncation; nsec math
  bounded < 1e9. Negative tv_sec via utimensat only produces a garbage
  uint64 mtime (representation, no OOB). Clean.
* Lock helpers: hammer_lock_downgrade (:244-268) / hammer_unlock (:271-302)
  clear `lowner` while still holding EXCLUSIVE — benign by construction
  (competing hammer_lock_ex/sh paths check EXCLUSIVE first); upgrade
  EDEADLK discipline already verified by the cursor audit (:215-234);
  hammer_ref/ref_interlock overflow needs 2^28 refs (KKASSERT-guarded).
* hammer_str_to_tid (:1044-1092): lax ":%05d" parse (strtoul skips
  whitespace/sign) is self-inflicted name parsing; pfs_to_lo() masks
  (hammer_btree.h:147-149). No memory safety impact.
* hammer_blockdemarc hpanic (:1119-1129): all callers (vnops.c:411-413,
  :836, :3121-3127) guard offset1 < HAMMER_XDEMARC by construction.
* hammer_to_unix_xid unaligned/aliasing access (:781-785): benign on x86.

## Fix

`fix.diff` clamps `*max_iterationsp` in hammer_direntry_namekey() so
`key + max_iterations <= INT64_MAX` (both ALG0 and ALG1 covered; ALG0 could
not wrap on its own — max key 0x7fffffff00000000 + 0xffffffff lands exactly
on INT64_MAX — but the clamp is cheap defense in depth).

Fix validation: applied to /usr/src in the guest, `make nativekernel`,
rebooted into the patched kernel, re-ran the exact PoC — see fix section
below (fix_run.log): nameB resolves normally and `unlink nameB` succeeds;
no poisoning, no leak.

## Fix status (batch validation)
Applied with the 36 sibling fix.diffs of this batch in findings/poc/_batch41/all_fixes.patch; single in-guest `make -j6 nativekernel KERNCONF=X86_64_GENERIC` completed RC=0 with zero errors under -Werror (full log: findings/poc/_batch41/fix_build8.log). Behavior A/B intentionally skipped for this Info-tier item.