DF-5694 — karc4random64() upper 32 bits are 0xffffffff half the time

File: sys/libkern/arc4random.c (pass-2 audit) Class: RNG correctness / C undefined behavior → entropy loss (CWE-190/191 + RNG) Verdict: reproduced (in the running kernel via KLD, and via exact-source userland harness)

Root cause (one paragraph)

karc4random64() (sys/libkern/arc4random.c:129-132) assembles its 64-bit word with

ret  = arc4_randbyte(d);
ret |= arc4_randbyte(d) << 8;
ret |= arc4_randbyte(d) << 16;
ret |= arc4_randbyte(d) << 24;      /* <-- BUG */
ret |= (uint64_t)arc4_randbyte(d) << 32;
...

arc4_randbyte() returns uint8_t, promoted to int. When the 4th byte is

= 0x80 (probability 1/2), byte << 24 sets bit 31 — not representable in int, UB per C11 6.5.7p4 — which real compilers (guest gcc 8.3, kernel built with the same) implement as shl wrap, yielding a negative int. The |= into the uint64_t ret converts that negative int modulo 2^64: sign extension — bits 32..63 all become 1. The subsequent |= (uint64_t) byte << 32..56 cannot clear them. Result: whenever byte3 >= 0x80, the upper 32 bits of karc4random64() are exactly 0xffffffff — 64-bit output carries only ~32.5 bits of entropy instead of 64. (karc4random() is unaffected: conversion to uint32_t truncates the sign extension away.)

Impact

• In-tree consumers: vm_map.c:4408 (mmap ASLR addend) and dev/drm/include/linux/random.h:49 (get_random_long() → i915 GTT randomization, i915_gem_gtt.c:3986).
• With the default RLIMIT_DATA of 32GB (vm_map.c:4374-4377), the biased draws all map to the top 4GB of the 32GB mmap randomization span: measured addend distribution 0.5625 (should be 0.125) in the top bucket, 0.0625 elsewhere; min-entropy 32.83 bits vs 35.00 ideal (~2.2 bits lost, 9x density concentration). Default vm.randomize_mmap=0 disables the consumer, so default-config impact is nil; operators who enable the hardening sysctl get the skewed distribution.

How to reproduce

Everything runs on the DragonFly guest (host has no toolchain here).

In-kernel (deployed generator) — KLD sampling

# build + load the sampler KLD (needs /usr/src in the guest)
cd /tmp/kld && make                      # Makefile + arc4samp.c from this dir
kldload ./arc4samp.ko
cat /dev/arc4srep                        # 2^20 karc4random64 draws, in-kernel
dd if=/dev/arc4s64 of=/tmp/s64.bin bs=1048576 count=16   # 2M k64 words
cc -O2 -o chk chk.c -lm && ./chk /tmp/s64.bin k64
dd if=/dev/arc4s32  of=/tmp/s32.bin  bs=1048576 count=64 # karc4random stream
dd if=/dev/arc4sbuf of=/tmp/sbuf.bin bs=1048576 count=64 # karc4random_buf
./chk /tmp/s32.bin && ./chk /tmp/sbuf.bin                # chi2 (should pass)

Userland exact-source harness (verbatim algorithm, getrandom-seeded)

cc -O2 -o arc4_harness arc4_harness.c -lm
./arc4_harness bias64 10000000           # P(top32==0xffffffff) ~ 0.5
./arc4_harness_fixed bias64 10000000     # PATCHED algorithm -> 0.0
./arc4_harness stats 536870912           # chi2 battery on k32+buf (passes)
./arc4_harness bias 4294967296           # 2^32 RC4 bias probes (negative)

Expected output

See run.log. Decisive lines:

karc4random64 draws=1048576
top32==0xffffffff: 524342 (0.5000; bug predicts ~0.5000)   <- in-kernel
k64 words=2097152 top32==0xffffffff: 1049617 (0.500496)    <- in-kernel stream
P(top32==0xffffffff) = 0.499919  ... bucket[7]: 0.562429   <- harness
PATCHED: P(top32==0xffffffff) = 0.000000 ... buckets 0.125 <- fix validated

Note: in every run, top32ones == b3high exactly — the bias fires if and only if byte3 >= 0x80 (causality, not correlation).

Fix

fix.diff (git-apply-able against sys/): cast every shifted byte to uint64_t in karc4random64(). Validated: patched algorithm yields P(top32==0xffffffff)=0.000000, uniform 0.125 buckets, 35.00-bit addend entropy, chi-square still passes.

DF-5694 — VERDICT

Status: reproduced (in the running deployed kernel, not just a model). Impact: RNG primitive defect — karc4random64() loses its upper 32 bits of entropy on exactly 1/2 of all draws; measurable ASLR degradation when vm.randomize_mmap=1 is enabled; C UB in kernel code. Confidence: certain.

What was measured

1. In-kernel (KLD arc4samp.ko, loaded into the live guest kernel, X86_64_GENERIC DragonFly 6.5-DEVELOPMENT, gcc 8.3): * /dev/arc4srep (2^20 karc4random64() draws, counted in-kernel): top32==0xffffffff at 0.4992 / 0.5000 across runs; and in every single run top32ones == b3high identically — the bias is exactly the event "4th byte >= 0x80". * /dev/arc4s64 stream, 2,097,152 words: 0.500496 biased. * Control: /dev/arc4s32 (64MB karc4random) and /dev/arc4sbuf (64MB karc4random_buf) both pass chi-square byte-frequency and digraph tests (z in [-1.34, +0.31]) — the defect is confined to the 64-bit assembly.
2. Userland exact-source harness (arc4_harness.c, algorithm copied verbatim from sys/libkern/arc4random.c:50-162, seeded from getrandom(2)): * bias64 10M: P(top32==0xffffffff) = 0.499919; P(both) identical. * Replication of the sole kernel consumer, vm_map.c:4408 (karc4random64() & 0x7fff...) % 32GB: top-4GB bucket 0.5625 (= 9/16, exactly as derived), other buckets 0.0625 (= 1/16), addend min-entropy 32.83 bits vs 35.00 ideal.

Why (mechanics, path:line)

sys/libkern/arc4random.c:132 ret |= arc4_randbyte(d) << 24; with uint64_t ret (declared :123): * arc4_randbyte (uint8_t) → int promotion; b << 24 for b >= 0x80 overflows int (UB, C11 6.5.7p4); compiler emits shl → bit 31 set → negative int value. * ret |= (int) converts the negative int to uint64_t modulo 2^64 → sign extension → 0xFFFFFFFF_xxxxxxxx. * Lines 133-136 OR bytes 4..7 into already-all-ones bits 32..63 — no effect. → upper half pinned to 0xffffffff with probability 1/2 (byte3 >= 0x80).

The 32-bit karc4random() (arc4random.c:114) has the same construct but uint32_t conversion truncates to the correct value — verified statistically clean (chi2 z=-0.77).

Consumer analysis (threat)

• sys/vm/vm_map.c:4408 — vm_map_hint() mmap randomization: addr += (karc4random64() & 0x7FFF...) % dsiz, dsiz = RLIMIT_DATA (default 32GB per vm_map.c:4374-4377 comment; verified rlimit 32GB in guest). Biased draws ⇒ addend = (b - 2^32) mod 2^35 ∈ top 4GB of span: 56.25% of placements in 1/8 of the window; ~2.2 bits min-entropy lost. Default vm.randomize_mmap=0 (vm_map.c:147) — dead path unless the operator enables this hardening sysctl. Live-kernel end-to-end probing with the sysctl enabled (aslr_probe.c/aslr2.c) additionally showed DF's first-fit hint resolution compresses placements into a ~3GB window regardless (a vm_mmap layout property outside this file's scope), so the net live ASLR delta from this bug is bounded by the addend skew above.
• sys/dev/drm/include/linux/random.h:49 — get_random_long() returns karc4random64() verbatim; used at i915_gem_gtt.c:3986 for GTT randomization on Intel graphics (module not loaded on this guest; the shim inherits the full bias).
• Any future/KLD consumer of the exported API gets 32.5 average bits per 64-bit draw.

Fix validation

fix.diff casts all four low shifts to (uint64_t) in karc4random64(). Applied to the exact-source harness (arc4_harness_fixed.c): P(top32==0xffffffff) = 0.000000 (10M draws), addend buckets 0.1248-0.1252, min-entropy 35.00 bits, chi-square unchanged (z=-0.18/-0.13). Kernel rebuild not performed (non-memory-corruption class; harness uses the byte-for-byte identical algorithm and the kernel compiler is the same gcc 8.3 with the same wrap-shift codegen observed in the KLD measurement).

Things checked and found CLEAN (negative results with weight)

• Byte/digraph chi-square on karc4random & karc4random_buf: pass in-kernel (64MB each) and harness (512MB): run.log.
• Mironov 3072-byte drop effectiveness: first-16K chi2 z=+1.18.
• Long-term RC4 bias probes at 2^32 bytes: Pr[Z==0] z=-0.34; lag1..8 digraph-repeat z in [-1.67,+1.18] — no distinguisher at feasible sizes.
• Post-boot read_random(key,32,1) always returns 32 (kern_nrandom.c:687-719 → subr_csprng.c:151-168 loop returns full count; CSPRNG_UNLIMITED never sleeps at :146) — the partial-r key[n%r] path never engages post-boot; no stack-garbage exposure beyond known DF-2243.
• All indices uint8_t → in-bounds; per-CPU state published after full init (arc4random.c:192, AP states pre-initialized on BSP mp_machdep.c:513); numruns bounded 16385, no overflow; no frees (no double-free); no copyin/copyout; reseed never sleeps (spinlock + UNLIMITED path).
• Redundant double 3072-byte discard at init (arc4random.c:76-77 + 189-190) — harmless waste only.

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.