Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

github.com

Post reply on HN
Print view View original

111–120 of 122 posts

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#111

Post by leijurv »

smithcoin wrote: post #79

Leijurv, did you do any collaboration with Matt Bolan or did you guys independently discover this? I can only imagine the power of your two minds combined. Loved the video. Also laughed when I found out you named baritone for fit’s voice.

It was a one-way collaboration, in that we referenced their discoveries and code such as LattiCG https://github.com/mjtb49/LattiCG, but they were unaware of anything we were doing until now. https://twitter.com/admiral_stapler/status/17806748612594609...

Naming Baritone after Fit is actually a coincidence / joke, the repo github.com/cabaletta/baritone was the result of random brainstorming for something untaken. We only later realized it described Fit and thus added that to the readme :)

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#112

Post by Retr0id »

kbolino wrote: post #106
Retr0id wrote: post #95

Earlier quoted context omitted.

chacha12, a construction that's been around in one form or another since the '00s, runs at well under 1 cycle per byte on good hardware and still plenty fast on "bad" hardware https://bench.cr.yp.to/results-stream.html (iiuc just using SIMD, no special acceleration) But it doesn't really matter what things were like when the code was first written, it's about how it could be fixed in the present.

Video games do not generate large streams of data, they generate individual values on demand. Your link says, to generate 8 bytes, chacha12 on modern hardware needs 24-45 cpb. That's 192-360 cycles to generate enough bits for a pseudorandom double-precision floating-point number. Xoshiro256+ [1], a relatively high-quality generator for this purpose, can do it with 11 single-cycle ALU ops. So unoptimized xoshiro256+ s…

Generating random numbers into a refillable buffer is the standard for high-performance RNG, whether you're doing CSPRNG or not (it's how V8 uses xorshift, for example). "stop the world" is not a problem when the time to refill the buffer is still measured in nanoseconds.

There's nothing stopping you from having multiple CSPRNG instances, with deterministic seeds, if that's a design requirement.

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#113

Post by kbolino »

Retr0id wrote: post #112
kbolino wrote: post #106

Earlier quoted context omitted.

Video games do not generate large streams of data, they generate individual values on demand. Your link says, to generate 8 bytes, chacha12 on modern hardware needs 24-45 cpb. That's 192-360 cycles to generate enough bits for a pseudorandom double-precision floating-point number. Xoshiro256+ [1], a relatively high-quality generator for this purpose, can do it with 11 single-cycle ALU ops. So unoptimized xoshiro256+ s…

Generating random numbers into a refillable buffer is the standard for high-performance RNG, whether you're doing CSPRNG or not (it's how V8 uses xorshift, for example). "stop the world" is not a problem when the time to refill the buffer is still measured in nanoseconds. There's nothing stopping you from having multiple CSPRNG instances, with deterministic seeds, if that's a design requirement.

I ran a microbenchmark with Go 1.22, which ships with both ChaCha8 (a little faster than ChaCha12) and PCG (a little slower than xoshiro256+). On my M1 Mac, I'm seeing 2.3 ns/uint64 for PCG and 4.5 ns/uint64 for ChaCha8. Assuming 3.2 GHz clock speed, that puts them at about 1 and 2 cpb respectively. With a floating-point conversion in the mix, they ran at 4.0 and 4.5 (!) ns/float64 respectively. That's far better than I would have thought.

So yes, a good, slightly buffered (internal state seems to be 300 bytes) implementation of a (quasi-?)CSPRNG is pretty damn close to a decent quality non-cryptographic PRNG and likely fast enough for most video games on most hardware. Though, very few people write games in Go.

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#114

Post by handojin »

dzdt wrote: post #16
dzdt wrote: post #9

Back in 1999-2000 there was an "International RoShamBo Programming Competition" [1] where computer bots competed in the game of rock-paper-scissors. The baseline bot participant just selected its play randomly, which is a theoretically unbeatable strategy. One joke entry to the competition was carefully designed to beat the random baseline ... by reversing the state of the random number generator and then predicting…

The whole commentary about the "supermodified" class of competition entrants is making my laugh: > Nostradamus was written by Tim Dierks, a VP of Engineering at Certicom, who has a lot of expertise in cryptography. The program defeats the optimal player by reverse-engineering the internal state of the random() generator, which he states "was both easier and harder than I thought it would be". To be sporting, it then…

The whole is better than the sum of the parts. You have nostradamus which predicts the future, fork bot which plays all playable presents, and the psychic friends network which rewrites the past. All under the watchful eye of the matrix.

There's something beautiful here and you honestly couldn't make it up.

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#115

Post by pclmulqdq »

kbolino wrote: post #113
Retr0id wrote: post #112

Earlier quoted context omitted.

Generating random numbers into a refillable buffer is the standard for high-performance RNG, whether you're doing CSPRNG or not (it's how V8 uses xorshift, for example). "stop the world" is not a problem when the time to refill the buffer is still measured in nanoseconds. There's nothing stopping you from having multiple CSPRNG instances, with deterministic seeds, if that's a design requirement.

I ran a microbenchmark with Go 1.22, which ships with both ChaCha8 (a little faster than ChaCha12) and PCG (a little slower than xoshiro256+). On my M1 Mac, I'm seeing 2.3 ns/uint64 for PCG and 4.5 ns/uint64 for ChaCha8. Assuming 3.2 GHz clock speed, that puts them at about 1 and 2 cpb respectively. With a floating-point conversion in the mix, they ran at 4.0 and 4.5 (!) ns/float64 respectively. That's far better tha…

That's not quite a correct benchmark if I'm understanding what you benchmarked. Xoshiro and PCG need a chain of serial ops to generate a number, but not a lot of parallelism, letting the core do other stuff while it is working. ChaCha needs a lot of parallelism, and you are essentially saturating that core running it.

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#116

Post by kbolino »

pclmulqdq wrote: post #115
kbolino wrote: post #113

Earlier quoted context omitted.

I ran a microbenchmark with Go 1.22, which ships with both ChaCha8 (a little faster than ChaCha12) and PCG (a little slower than xoshiro256+). On my M1 Mac, I'm seeing 2.3 ns/uint64 for PCG and 4.5 ns/uint64 for ChaCha8. Assuming 3.2 GHz clock speed, that puts them at about 1 and 2 cpb respectively. With a floating-point conversion in the mix, they ran at 4.0 and 4.5 (!) ns/float64 respectively. That's far better tha…

That's not quite a correct benchmark if I'm understanding what you benchmarked. Xoshiro and PCG need a chain of serial ops to generate a number, but not a lot of parallelism, letting the core do other stuff while it is working. ChaCha needs a lot of parallelism, and you are essentially saturating that core running it.

The builtin benchmarking tool in Go runs with parallelism set to 2x the number of cores. That should make evident any code that scales poorly. It is a tunable parameter though; I can try 4x cores etc.

I also ran it on x86 (AMD Ryzen 5600X) and got similar results; everything ran faster on a 4.6 GHz chip, but ChaCha8 stayed around 2 cpb while PCG improved a little to about 0.7 cpb.

I do have a ~10-year-old Celeron NUC laying around that I could use to test older/lower-end hardware. I can also publish the (admittedly very simple) program I'm using.

It's also worth noting that cpb is still a measure of average throughput not variance or latency and while Go's buffered ChaCha8 implementation amortizes to 2 cpb, when the 32-element buffer exhausts, generating a new number is much more expensive than the previous 31 numbers. I wouldn't say the performance is good enough for every use case.

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#117

Post by kbolino »

kbolino wrote: post #116
pclmulqdq wrote: post #115

Earlier quoted context omitted.

That's not quite a correct benchmark if I'm understanding what you benchmarked. Xoshiro and PCG need a chain of serial ops to generate a number, but not a lot of parallelism, letting the core do other stuff while it is working. ChaCha needs a lot of parallelism, and you are essentially saturating that core running it.

The builtin benchmarking tool in Go runs with parallelism set to 2x the number of cores. That should make evident any code that scales poorly. It is a tunable parameter though; I can try 4x cores etc. I also ran it on x86 (AMD Ryzen 5600X) and got similar results; everything ran faster on a 4.6 GHz chip, but ChaCha8 stayed around 2 cpb while PCG improved a little to about 0.7 cpb. I do have a ~10-year-old Celeron NUC…

Ok, I was able to figure out a few more things. First of all, the benchmark runner does not necessarily exploit the parallelism of GOMAXPROCS out of the box. Second, GOMAXPROCS seems to default to 1x logical cores; I last ran it on a machine where logical cores = 2x physical cores. I adjusted the benchmark code to use RunParallel and adjusted the parallelism of each run.

Testing on Celeron J3455 @ 1.5 GHz (4 physical and logical cores) gave me PCG at 1.2 cpb and ChaCha8 at 2.6 cpb with cpu=1, but PCG stayed relatively constant across cpu=1,2,4,8 (worst was 1.8 cpb) while ChaCha8 slowed to 6.5 cpb at cpu=2 and 7.5 cpb at cpu=4 and cpu=8.

Back on my M1 Mac (8 logical and physical? cores), both ChaCha8 and PCG generally got better with more cores. ChaCha8 got down to 0.76 cpb at cpu=4 (then regressed a bit at cpu=8) while PCG got down to 0.26 cpb at cpu=8.

I don't think any of these results rule ChaCha8 out completely, though again I'm looking from the perspective of video games, which generally monopolize a machine while running.

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#118

Post by pclmulqdq »

kbolino wrote: post #117
kbolino wrote: post #116

Earlier quoted context omitted.

The builtin benchmarking tool in Go runs with parallelism set to 2x the number of cores. That should make evident any code that scales poorly. It is a tunable parameter though; I can try 4x cores etc. I also ran it on x86 (AMD Ryzen 5600X) and got similar results; everything ran faster on a 4.6 GHz chip, but ChaCha8 stayed around 2 cpb while PCG improved a little to about 0.7 cpb. I do have a ~10-year-old Celeron NUC…

Ok, I was able to figure out a few more things. First of all, the benchmark runner does not necessarily exploit the parallelism of GOMAXPROCS out of the box. Second, GOMAXPROCS seems to default to 1x logical cores; I last ran it on a machine where logical cores = 2x physical cores. I adjusted the benchmark code to use RunParallel and adjusted the parallelism of each run. Testing on Celeron J3455 @ 1.5 GHz (4 physical…

The important question to benchmark for small buffer sizes isn't actually cycles per byte, it's micro-ops per byte. You are sort of getting there by adding threads, but if you want to measure micro-ops per byte by measuring cycles per byte, your benchmarking code should run a number of parallel implementations of the generator on each thread (and stick to 1 thread per physical core, too). Each generator will have a "roof" where more generators per thread doesn't cost any more in terms of cycles/byte. I am assuming that for PCG, that roof is around 4-ish on an old CPU, and may be as high as 6 or 8 on your macbook, while the roof for ChaCha will be close to 1.

ChaCha exploits instruction-level parallelism to get speed. PCG doesn't - it has a chain of instructions that must be executed sequentially. That means that when the PCG generator executes, it leaves gaps in the instruction stream that can be filled with other instructions for the game. That means a slowdown in the game that is more significant than what your benchmark suggests.

I'm going to do this and write blog about it (although I don't have a macbook), so we may be able to compare results.

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#119

Post by kbolino »

pclmulqdq wrote: post #118
kbolino wrote: post #117

Earlier quoted context omitted.

Ok, I was able to figure out a few more things. First of all, the benchmark runner does not necessarily exploit the parallelism of GOMAXPROCS out of the box. Second, GOMAXPROCS seems to default to 1x logical cores; I last ran it on a machine where logical cores = 2x physical cores. I adjusted the benchmark code to use RunParallel and adjusted the parallelism of each run. Testing on Celeron J3455 @ 1.5 GHz (4 physical…

The important question to benchmark for small buffer sizes isn't actually cycles per byte, it's micro-ops per byte. You are sort of getting there by adding threads, but if you want to measure micro-ops per byte by measuring cycles per byte, your benchmarking code should run a number of parallel implementations of the generator on each thread (and stick to 1 thread per physical core, too). Each generator will have a "…

Ok this makes sense. There are only 4 FP/SIMD units in the M1 and I'm guessing just one in the Celeron.

I look forward to reading your blog about this.

Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG

#120

Post by eru »

thenewnewguy wrote: post #107
eru wrote: post #67

Earlier quoted context omitted.

They wanted to show that they didn't cheat. In general, you can pick a random seed at the start of the day, commit to it somewhere (eg publish a hash of it on the bitcoin blockchain, or just on your website), then use that seed in a cryptographically secure PRNG on your website all day, and at the end of the day you publish the seed you already committed to. This way people can check that you didn't cheat, but can't…

Wouldn't the most obvious method of cheating be the site owner peeking at other player's hands and/or the deck? Which this doesn't (and cannot) prevent? I guess I'm not sure what publicizing their PRNG is meant to prove. It shows they didn't cheat via a very specific type of cheating but there are several other potential cheating vectors.

> It shows they didn't cheat via a very specific type of cheating but there are several other potential cheating vectors.

Yes, and this is not the only anti-cheat method they had.

Post reply on HN