Intervals above 125 bits silently produce wrong keys instead of erroring

[Dileep-Kumar-5]

Summary

Exceeding the documented 125-bit interval limit does not fail. It produces wrong private keys with no error, no warning and no crash, while reporting normal progress the whole time.

The README states the limit ("This program is limited to a 125bit interval search") but not the failure mode, so a run above it looks healthy and its output is worthless. Related: #154, #122.

Cause

HashTable.h packs the travelled distance into 128 bits:

typedef struct {
  int128_t  x;    // Poisition of kangaroo (128bit LSB)
  int128_t  d;    // Travelled distance (b127=sign b126=kangaroo type, b125..b0 distance
} ENTRY;

126 bits of magnitude. Distances span the interval width, so a wider interval overflows — and HashTable::Convert() masks the excess away rather than rejecting it:

D->i64[1] = d->bits64[1] & 0x3FFFFFFFFFFFFFFFULL;

The entry is then indistinguishable from a valid one. On collision it yields a wrong key.

Reproduce

Puzzle #140's published range and public key (2^139 interval):

80000000000000000000000000000000000
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
031F6A332D3C5C4F2DE2378C012F429CD109BA07D69690C6C701B6BB87860D6640

./kangaroo -gpu -d 16 -w w140.kcp -wi 20 in140.txt     # let it run, then stop
./kangaroo -t 4 -wcheck w140.kcp

Result on current master:

interval	DPs stored	-wcheck
2^119 (#120)	17,088	100.000% OK
2^139 (#140)	376,836	0.024% OK — 376,747 corrupt

2^119 is inside the cap and is fine, so this is specifically the over-limit path. Nothing in the 2^139 run's output distinguishes it from the 2^119 run.

Why it matters

Every currently unsolved kangaroo-able puzzle is above the limit — #135 is a 2^134 interval, #140 is 2^139 — so anyone pointing this tool at them today is accumulating corrupt data and cannot tell.

Note for anyone arriving from #154

Chunking the range into sub-intervals below the cap is correct, but expensive. Kangaroo costs ~K·√W, so splitting W into m chunks costs m·K·√(W/m) = √m times more work. The 512 chunks suggested in #154 is √512 ≈ 23× the work of searching 2^134 in one pass. It is a workaround, not a fix.

Fix

PR #158 widens the distance field to 256 bits (254 bits of magnitude, intervals to 253 bits) and makes over-range distances exit(-1) instead of truncating. Same input as above: 100.000% OK. It also fixes a CUDA 13 build break — cudaDeviceProp::computeMode was removed, so GPUEngine.cu does not compile against a current toolkit at all.

Minimal alternative if the format change is unwanted: add a startup check that refuses an interval wider than 125 bits. Failing loudly costs nothing and turns silently-wrong output into an error message.

🤖 Generated with Claude Code

[Dileep-Kumar-5]

For anyone hitting this before the fix lands upstream, a working build is here:

https://github.com/Dileep-Kumar-5/Kangaroo (branch feat/256bit-distance-field, also the default branch)

Same code as #158. Two ways to use it:

Just want to stop being silently wrong. Build it as-is. The default build is byte-compatible with upstream — identical ENTRY (32 bytes), ITEM (56), KSIZE (10), DP packet (40), and the original work-file and protocol magics, so it reads and writes your existing work files and talks to unpatched peers. The only behavioural change is that an over-range interval now stops:

HashTable::Convert: travelled distance exceeds 126 bits.
Interval is too large for the DP entry format (max 125 bits).
Rebuild with -DWIDE_DIST for intervals up to 253 bits.
Aborting rather than storing a truncated distance.

Want to actually search above 125 bits. Build with -DWIDE_DIST (or uncomment WIDE_DIST in Constants.h) for a 254-bit magnitude, intervals to 253 bits. Costs ~50% more DP RAM and 4-7% throughput; work files and the protocol are not interchangeable with a default build, and a mismatch is refused by magic rather than misparsed.

Verified on an RTX 3050 Laptop (sm_86, CUDA 13.3.73), all DP validity via -wcheck:

interval	default build	-DWIDE_DIST
2^119 (#120)	100.000%	100.000%
2^134 (#135)	refuses, exit 255	100.000%
2^139 (#140)	refuses, exit 255	100.000%

versus master's 0.024% at 2^139.

Note it also carries the CUDA 13 build fix from #160 — without that, GPUEngine.cu does not compile against a current toolkit at all, so a fresh clone of master will not build a GPU binary today regardless of this issue.

To be clear about status: this is my branch, not blessed by the maintainer, and #158 is unreviewed. Read the diff before trusting it with a long run. If it gets merged upstream, use upstream.