# 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

```c
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

```sh
# 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)

```sh
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.