Live data from Hacker News

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

github.com

101–110 of 122 posts

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

#101
post #71

Earlier quoted context omitted.

> don't make the game fun the fun is no longer the game in an anarchy server. It's in beating other play's strategies - which actually makes it quite close to a real war in the physical world. For example, the 2b2t minecraft wars between factions involve logistics, misinformation and intelligence (such as spies, fakes etc). It's no longer just minecraft. But that's what makes it fun and interesting.

Yeah but that's not fun, that's tedious work 99% of the time that culminates in some rare fun.

> tedious work 99% of the time that culminates in some rare fun

Welcome to the multiplayer gaming, especially games like Minecraft or ARK.

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

#102

Earlier quoted context omitted.

That's me! Thanks for pulling up the quote from long ago: > "With his obvious technical skill, and his "cheat early and often" attitude, Tim could have a promising career as an AI programmer in the computer games industry. :)" Instead took a path of security, authoring the TLS RFC and principal engineer in Google security. Thanks for the flashback.

I had to checkout your Git after this awesome reply. Gotta love Hacker News. I had a cool vision for “tag play” … I visualize mini RFID records on a turn table that tell Roku what to play.

DJs have timecoded vinyl records that do something like this, even allowing the DJ to scratch the mp3 that is being played.

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

#103
post #65
post #60

Earlier quoted context omitted.

I remember someone doing the same to an online poker site that had helpfully documented its PRNG in a laudable attempt at transparency. (And the transparency got them an improvement in their security in the end.)

I'm surprised they don't use some form of hardware based RNG. I assume there's many good reasons https://en.wikipedia.org/wiki/Hardware_random_number_generat...

> don't use some form of hardware based RNG

I've always wondered: why aren't ADCs (e.g. mic input) and temperature sensors considered a good source of entropy, particularly if the lower bits are taken?

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

#104

Earlier quoted context omitted.

Yeah but that's not fun, that's tedious work 99% of the time that culminates in some rare fun.

> tedious work 99% of the time that culminates in some rare fun Welcome to the multiplayer gaming, especially games like Minecraft or ARK.

Online games without hacks are usually fun the whole time, even Minecraft SMP. Lots of people play those casually.

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

#105
post #10

Earlier quoted context omitted.

I also quite liked the idea of a true anarchy server (from a gameplay perspective), but on 2b2t in practice this looked like a lot of the n-word being said in chat, so I stopped playing.

You can avoid this using chatfilters. Players who spam slurs are not worth talking to anyway. But I agree that there are far better anarchy servers than 2b around.

Hypothetically if lots of players ran those kind of filters, a team could gain a benefit by including slurs in all their communications I guess, which would be an odd result.

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

#106
post #95
post #89

Earlier quoted context omitted.

We may be at the point where CSPRNGs are viable for video game randomness, but that wasn't the case 10+ years ago especially when factoring in compatibility with 20-year-old hardware (high-end PCs from ca 2004 could play Minecraft). Even so, a non-crypto PRNG can generally compute a new random number in 2-4 ALU ops. With SIMD optimization, that can amortize to under 1 cycle per byte, which means it takes under a nano…

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+ should be 17 times faster than optimized chacha12 on the best hardware. This is a classic latency vs. throughput issue.

Now, maybe you could optimize the use of a CSPRNG here by filling large buffer(s) and sampling values from them. Some warm-up time could go a long way. However, I fear that you would run into one or more of the following problems:

- stop-the-world pause to refill the buffer (e.g. single buffer, no threading)

- synchronization delays from mutex locks (e.g. ring buffer refilled from a background thread)

- high memory usage (e.g. rotating pool of buffers, atomically swapped)

Needless to say, none of these solutions is anywhere near as simple to implement as a non-cryptographic PRNG.

Now let's consider determinism. Video games generally use a lot of differently seeded instances of the same PRNG algorithm to provide random numbers in different parts of the simulation. Since each part may demand random numbers at different rates, it's hard to replace several independent PRNGs with a single PRNG without compromising determinism. In the 4096 bytes necessary to run one instance of chacha12 at its maximum efficiency, you can fit 128 instances of xoshiro256+ or 512 instances of splitmix64 [2].

[1] = https://prng.di.unimi.it/xoshiro256plus.c

[2] = https://github.com/svaarala/duktape/blob/master/misc/splitmi...

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

#107
post #67
post #65

Earlier quoted context omitted.

I'm surprised they don't use some form of hardware based RNG. I assume there's many good reasons https://en.wikipedia.org/wiki/Hardware_random_number_generat...

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.

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

#108

Earlier quoted context omitted.

You can avoid this using chatfilters. Players who spam slurs are not worth talking to anyway. But I agree that there are far better anarchy servers than 2b around.

Hypothetically if lots of players ran those kind of filters, a team could gain a benefit by including slurs in all their communications I guess, which would be an odd result.

or just use discord

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

#109
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…

There are CSPRNG constructions based on AES that would probably be appropriate, but they are still a huge performance hit. PCG, Xorshift, Xoshiro, and the like are all about 50x faster than the fastest CSPRNGs in sustained throughput, and also have smaller state and much less spinup time.

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

#110
post #65

Earlier quoted context omitted.

I'm surprised they don't use some form of hardware based RNG. I assume there's many good reasons https://en.wikipedia.org/wiki/Hardware_random_number_generat...

https://www.random.org/

Or, if you don't want to trust the source, https://drand.love/
Post reply on HN