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.<p>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]<p>[1] <a href="https://web.archive.org/web/20180719050311/http://webdocs.cs.ualberta.ca/~darse/rsbpc2.html" rel="nofollow">https://web.archive.org/web/20180719050311/http://webdocs.cs...</a><p>[2] <a href="https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc" rel="nofollow">https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc</a>
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) <a href="https://news.ycombinator.com/item?id=40045377">https://news.ycombinator.com/item?id=40045377</a><p>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. <a href="https://youtu.be/TM7SutJyDCk" rel="nofollow">https://youtu.be/TM7SutJyDCk</a>
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?
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.
Pretty cool exploit.<p>The idea of a free for all bug abusing server is pretty neat, a whole ‘nother level of the game.<p>I guess this is what “actually fighting” (rather than just using in-game battling mechanics) would look like if the metaverse really happened ever.
Just watched the video on this! It's definitely a cautionary tale of having your random sources interact - applicable to so many important systems.<p>I often find myself sharing the rng in my code for performance reasons, but stories like this definitely make me pause.
The video on this is amazing: <a href="https://www.youtube.com/watch?v=maMpMOnIJDE" rel="nofollow">https://www.youtube.com/watch?v=maMpMOnIJDE</a>. I had no idea how sophisticated the community was.
Even better, this style of RNG cracking has even been done <i>in-game</i>:<p><a href="https://youtu.be/FPmQ0rnJjNc?si=tTFObcfZ-ILanL_A" rel="nofollow">https://youtu.be/FPmQ0rnJjNc?si=tTFObcfZ-ILanL_A</a>
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):<p><a href="https://www.youtube.com/watch?v=FPmQ0rnJjNc" rel="nofollow">https://www.youtube.com/watch?v=FPmQ0rnJjNc</a>
This appears to be a State Compromise Extension Attack (<a href="https://en.wikipedia.org/wiki/Random_number_generator_attack" rel="nofollow">https://en.wikipedia.org/wiki/Random_number_generator_attack</a>) which is something that PRNGs that are not CSPRNGs can be subject to.<p>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.
I loved playing on 2b2t, until it got too popular all of the sudden when a YouTuber did a video on it.<p>2b2t (an anarchy servers in genral) are Minecraft the way it is meant to be played.
reminds me of phase space plots of weak tcp isn rng<p><a href="https://lcamtuf.coredump.cx/oldtcp/tcpseq.html" rel="nofollow">https://lcamtuf.coredump.cx/oldtcp/tcpseq.html</a><p><a href="https://lcamtuf.coredump.cx/newtcp/" rel="nofollow">https://lcamtuf.coredump.cx/newtcp/</a>
Yo Leijurv this is so sick! As a fellow game hacker this sort of stuff is super inspiring.<p>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.<p>Ever since we watched the nocom one I’ve wondered what you do professionally - are you in the infosec space?<p>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!
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.
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.