Impressively, there's Mess Detector, a machine built in Minecraft itself that predicts the internal state of the rng, using the position a lit tnt (instead of a block drop):
Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
81–90 of 122 posts
Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
#82Earlier quoted context omitted.
This is a bug in how Minecraft does things, not a bug in the generator itself (which has long been known to be vulnerable to such things).
Yeah, there is a big class of "RNG bugs" where someone uses a non-cryptographic RNG for secure things, not realizing that those things are supposed to be secure. The classic example of these is a password manager that gave out recovery codes using a PRNG. This is in that class.
While a CSPRNG would have solved this problem, it also would've created a new one: much slower chunk loading and random item placement, which would have greatly slowed down the game simulation, and thus tanked framerate and playability. As it turns out, the right solution is to use multiple, isolated non-cryptographic random number generators with distinct state. That way, even though you can guess the state of one of them, it doesn't give you any insight into the others.
Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
#83Earlier quoted context omitted.
I haven't played Minecraft for many years but I'd argue the way it's supposed to be play is an old version from like 10 years ago with a tech modpack like Tekkit. Back then, there were open servers where communities built cities with no grief prevention because people trusted each other.
When I was a kid, I ran a public server with Logblock and anticheat but no other plugins, so it was basically vanilla for anyone who wanted to play nice. People loved it.
Public servers with e.g. coreprotect for rollbacks are still around. Most people play nice, but when somebody doesn't their acts can be reverted without impacting anybody else. It's a lot of fun if you can get the right team of admins/janitors to keep it running.
Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
#84I loved playing on 2b2t, until it got too popular all of the sudden when a YouTuber did a video on it. 2b2t (an anarchy servers in genral) are Minecraft the way it is meant to be played.
I haven't played Minecraft for many years but I'd argue the way it's supposed to be play is an old version from like 10 years ago with a tech modpack like Tekkit. Back then, there were open servers where communities built cities with no grief prevention because people trusted each other.
if so, you'd be making a poor argument
Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
#85Back 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…
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.
Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
#86Earlier quoted context omitted.
Yeah, there is a big class of "RNG bugs" where someone uses a non-cryptographic RNG for secure things, not realizing that those things are supposed to be secure. The classic example of these is a password manager that gave out recovery codes using a PRNG. This is in that class.
While a CSPRNG would have solved this problem, it also would've created a new one: much slower chunk loading and random item placement, which would have greatly slowed down the game simulation, and thus tanked framerate and playability. As it turns out, the right solution is to use multiple, isolated non-cryptographic random number generators with distinct state. That way, even though you can guess the state of one o…
Modern CSPRNGs can generate numbers at GB/s, I find it hard to believe it would slow the game down in a measurable way.
The "right" solution you describe sounds overcomplicated and error-prone (now you need to think carefully about which domains are separated) compared to just using a CSPRNG.
Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
#87Earlier quoted context omitted.
While a CSPRNG would have solved this problem, it also would've created a new one: much slower chunk loading and random item placement, which would have greatly slowed down the game simulation, and thus tanked framerate and playability. As it turns out, the right solution is to use multiple, isolated non-cryptographic random number generators with distinct state. That way, even though you can guess the state of one o…
Modern CSPRNGs can generate numbers at GB/s, I find it hard to believe it would slow the game down in a measurable way. The "right" solution you describe sounds overcomplicated and error-prone (now you need to think carefully about which domains are separated) compared to just using a CSPRNG.
> The "right" solution you describe sounds overcomplicated and error-prone
It's not particularly. At program start-up, you seed the original PRNG. Then, you generate N numbers from the original PRNG and use those to seed N other PRNGs, then throw away the original PRNG. You don't need to think carefully about domains, you just create a new PRNG for everything you need a random number for. This makes your game easier to debug in a deterministic way, because now reproducing the behavior of one specific action that involves randomness no longer depends on every other action that involves randomness.
Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
#88Earlier quoted context omitted.
Yeah, there is a big class of "RNG bugs" where someone uses a non-cryptographic RNG for secure things, not realizing that those things are supposed to be secure. The classic example of these is a password manager that gave out recovery codes using a PRNG. This is in that class.
While a CSPRNG would have solved this problem, it also would've created a new one: much slower chunk loading and random item placement, which would have greatly slowed down the game simulation, and thus tanked framerate and playability. As it turns out, the right solution is to use multiple, isolated non-cryptographic random number generators with distinct state. That way, even though you can guess the state of one o…
The problem of dealing with randomness is about figuring out how to use CSPRNGs (and TRNGs) as little as possible, but not too little. CSPRNGs can get to a couple of GB/sec on a core, so they're not all that bad, but non-secure PRNGs are over an order of magnitude faster. I would assume that most of those things (eg chunk generation/loading) don't need secure RNG at all.
Sharding your RNGs by player is also an option for some games, and can be easier.
Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
#89Earlier quoted context omitted.
While a CSPRNG would have solved this problem, it also would've created a new one: much slower chunk loading and random item placement, which would have greatly slowed down the game simulation, and thus tanked framerate and playability. As it turns out, the right solution is to use multiple, isolated non-cryptographic random number generators with distinct state. That way, even though you can guess the state of one o…
Modern CSPRNGs can generate numbers at GB/s, I find it hard to believe it would slow the game down in a measurable way. The "right" solution you describe sounds overcomplicated and error-prone (now you need to think carefully about which domains are separated) compared to just using a CSPRNG.
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 nanosecond to generate a new 32-bit number. I'm not sure even the best hardware-accelerated CSPRNG on modern hardware can quite say the same just yet.
Re: Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
#90Earlier quoted context omitted.
If "random" implies "contains no information", then it is indeed a bug in anything calling itself a "random number generator". But that's just my opinion. The world is free to use the word however it wants.
“Random” means something closer to “contains maximal information”…
One way of thinking about it is that each bit has maximal information because knowing the entire previous history should give you no information about what the next bit will be ahead of it being revealed.