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

[dzdt]

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 with 100% accuracy what the random player would play.

Edit: the random-reversing bot was "Nostradamus" by Tim Dierks, which was declared the winner of the "supermodified" class of programs in the First International RoShamBo Programming Competition. [2]

[1] https://web.archive.org/web/20180719050311/http://webdocs.cs...

[2] https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc

[timdierks]

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.

[joshu]

I submitted the optimally bad entrant the first year, cheesebot.

https://web.archive.org/web/20180719050236/http://webdocs.cs...

[dzdt]

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 plays optimally against all other opponents.

> Fork Bot was based on an idea that Dan Egnor came up with a few minutes after hearing about the contest. Since "library routines are allowed", his elegant solution was to spawn three processes with fork(), have each one make a different move, and then kill off the two that did not win. This was implemented by Andreas Junghanns in about 10 lines of code. Unfortunately, since all three moves lost to the Psychic Friends Network after the first turn, the program exited and the remainder of that match was declared forfeited.

> The Psychic Friends Network is a truly hilarious piece of obfuscated C, written by Michael Schatz and company at RST Corporation. Among other things, it uses an auxiliary function to find good karma, consults horoscopes, cooks spaghetti and (mystic) pizza to go with various kinds of fruit, #defines democrats as communists, and undefines god. We're still trying to figure out exactly what it is doing with the stack frame, but we do know that it never scores less than +998 in a match, unless it is playing against a meta-meta-cheater.

> The Matrix was written by Darse Billings, who holds the prestigious title of "Student for Life", and recently started the PhD programme at the University of Alberta. The RoShamBo program defeated every opponent with a perfect score, based on the simple principle "There is no spoon".

> Since The Matrix is also the tournament program, it has complete access to all other algorithms, data structures, and output routines, and is therefore unlikely to ever be overtaken. As a result, this category is hereby declared to be solved, and thus retired from future competitions.

[eru]

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.)

[bagels]

So, it was using a pseudorandom generator?

[chc4]

LLL lattice reduction is the same algorithm that can be used for cracking PuTTY keys from biased nonces from the CVE a few days ago. 'tptacek explained a bit about the attack (and links to a cryptopals problem for it, which I can almost pretend to understand if I squint) https://news.ycombinator.com/item?id=40045377

In a similar vein, the SciCraft minecraft server had a creeper farm which used some sort of black magic setup in order to deterministically manipulate an RNG state to trigger a "random" lightning strike at a specific block every frame in order to get better creeper drops. https://youtu.be/TM7SutJyDCk

[tptacek]

Sean and Kelby do a much better job of describing what LLL is, but this is maybe the best explanation of why LLL is that I've ever read. In all three cases, you only need basic linear algebra, if that (Kelby wants you to grok Gram-Schmidt, which is like just before the midterm of an undergrad linear algebra 101).

I really don't have words for how great this post is. It made my week.

Later

A really concise explanation of the same process you can step through in Python:

https://crypto.stackexchange.com/questions/37836/problem-wit...

[lyu07282]

There is also some Rng manipulation to make blocks always drop the maximum, explained here:

https://youtu.be/ZcdN1wCJPqM?t=390

[squigz]

> some sort of black magic

> which I can almost pretend to understand if I squint

This is me and all cryptography :D

[NoMoreNicksLeft]

Oh god. You just wake up one morning, to see blocks in the sky that weren't there the night before, ghostly and foglike, until a moment later they're visible as redstone and observer and slime, and you can see the dropping infinite TNT. All because the server gave away your position. You can still escape it, there might even be a few seconds to grab what you can out of the chest and run, or to build an obsidian shelter, but that's about it. Not enough time to build a precisely aimed cannon and you couldn't get the elevation right anyway. Maybe if you had an elytra and some rockets you could go sabotage, even then there's this big worldeater hole just 16 chunks away. Have they lava trapped all the nearby nether portals?

[pclmulqdq]

I have seen a lot of interesting and funny RNG issues, but this is one of the most sophisticated exploits for the least payout. A wonderful work of art.

[sebzim4500]

If they had sold the items they could have probably made some money (maybe $1000s?). Still a small payout considering the amount of work, of course.

[ryanisnan]

Indeed! I love seeing how the seemingly innocuous decisions by Mojang devs are being abused here, so freaking cool.

[bee_rider]

Pretty cool exploit.

The idea of a free for all bug abusing server is pretty neat, a whole ‘nother level of the game.

I guess this is what “actually fighting” (rather than just using in-game battling mechanics) would look like if the metaverse really happened ever.

[hatsunearu]

the combat in 2b2t does not look like regular minecraft either.

because of a long history of duped high value items, PvP is just simply spamming ender crystals which deals massive damage when broken, and the defense is just how many "totems of undying" you have which absorbs lethal damage.

of course all the hacked clients automate placing ender crystals, reloading totems and identifying weak/strong locations so you're following those guidance to spam damage.

a little before that there were hacked +32,767 damage swords that will insta kill you that was patched out by the server.

[orbital-decay]

> The idea of a free for all bug abusing server is pretty neat, a whole ‘nother level of the game.

Balance converging around bugs and exploits is pretty typical for all PvP sandbox games with cutthroat gameplay, even if not allowed by the server. ARK: Survival Evolved and Eve Online are infamous for having huge clans (thousands of players) willing to go extreme lengths at metagaming and bug exploitation. It isn't always that rosy, ARK had certain mechanisms to dox players and their multiple Steam accounts, which I believe led to a few spillovers of the ingame relations to the real life during the Great War. Sometimes it's very basic stuff though, like building a huge tower and breaking it upon being raided, DoSing the server and crashing it, after which it rolls back to a previous backup made 10-20 min ago, making your base very hard to raid if you have active players. (an ancient thing that was fixed many years ago)

Rust (the PvP game, not the language) also had the policy of encouraging players to spread and publish bugs and exploits on YouTube, but with the different aim - so that the devs would notice and patch those faster. This resulted in a pretty robust game that is extremely hard to exploit without resorting to actual external hacks.

[hot_gril]

An in-between is Super Smash Bros Melee, where a lot of tournament-legal ingame tactics rely on bugs. But only ones you can exploit manually with a regular controller, not actual hacking, and also one exploit called Wobbling got banned in 2019 (note that this is a 2001 game).

[asddubs]

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.

[dontupvoteme]

>The idea of a free for all bug abusing server is pretty neat, a whole ‘nother level of the game.

Isn't this basically any non-VAC CS 1.6 server?

[ZeWaka]

Just watched the video on this! It's definitely a cautionary tale of having your random sources interact - applicable to so many important systems.

I often find myself sharing the rng in my code for performance reasons, but stories like this definitely make me pause.

[iforgotpassword]

I think I never used PRNG in any serious software, but it surprised me as intuitively I would've assumed that using the same RNG in as many places as possible would make it harder to perform such an attack, because it would make it less likely you can observe enough places at which it is updated, but this was a pretty impressive and fun demonstration that this is false.

[lxe]

The video on this is amazing: https://www.youtube.com/watch?v=maMpMOnIJDE. I had no idea how sophisticated the community was.

[ajcp]

The narration in this video is so over-the-top you'd think they were talking about Stuxnet or something. I love it.

[ben_bai]

Yeah the Minecraft and MC anarchy community is insane.

If you found this amazing, take a look at this, it'll blow your mind.

https://www.youtube.com/watch?v=ea6py9q46QU and https://www.youtube.com/watch?v=GaRurhiK-Lk

[niederman]

Even better, this style of RNG cracking has even been done in-game:

https://youtu.be/FPmQ0rnJjNc?si=tTFObcfZ-ILanL_A

[skitter]

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):

https://www.youtube.com/watch?v=FPmQ0rnJjNc

[er4hn]

This appears to be a State Compromise Extension Attack (https://en.wikipedia.org/wiki/Random_number_generator_attack) which is something that PRNGs that are not CSPRNGs can be subject to.

At this point it feels like having PRNGs be defaults is just not that safe of a thing to offer in libraries. Like defaulting to allow TLSv1.0 or blowfish in 2024.

[dzogchen]

I 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.

[cedws]

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.

[immibis]

I assure you Notch did not mean to make a game of RNG reverse engineering.

[bingaling]

reminds me of phase space plots of weak tcp isn rng

https://lcamtuf.coredump.cx/oldtcp/tcpseq.html

https://lcamtuf.coredump.cx/newtcp/

[leijurv]

I believe that may be the spectral test https://en.wikipedia.org/wiki/Spectral_test which I mentioned in the explanation when showing the lattices visually

[moritonal]

Love how it's basically the Dark Forest logic at play. The only true way to live is to hide your location and not give off signals.

[danielwmayer]

Yo Leijurv this is so sick! As a fellow game hacker this sort of stuff is super inspiring.

My girlfriend and I watch all the fitmc videos even though neither of us play minecraft, and love the ones detailing your insane tooling the most.

Ever since we watched the nocom one I’ve wondered what you do professionally - are you in the infosec space?

With the amount of math and computer science knowledge you put into your work I would guess more in algorithmic trading or something like that. No worries if you don’t want to answer, just curious!

[leijurv]

I'm just a regular SWE! Infosec or algorithmic trading - maybe someday.

[sdwvit]

Some extra piece of background: 2b2t is a famous server for people trying to build great structures and then for other people to snipe their locations and grief said great structures. So this exploit makes a lot of sense.

[smithcoin]

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.

[leijurv]

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 :)

[CERNoholic]

The video looks very much like a particle collider’s detector output.

[lawrenceyan]

What level of compute would you need realistically to start doing things like this irl instead of in Minecraft I wonder?