14 ms·
Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
- P529 2y ago[flagged]
- metalbunny 2y ago[flagged]
- CERNoholic 2y agoThe video looks very much like a particle collider’s detector output.
- ZeWaka 2y agoJust 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 2y agoI 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.
- IshKebab 2y agoPretty much all serious software uses PRNG at some point. Unless you mean you use CSPRNG, which is the easy fix.
- iforgotpassword 2y agoYeah it's obviously biased to the field you work in. And I'm aware that libs im using use some form of randomness, be it for uuid-gen, entropy for SSL or whatnot, but I seriously can't remember the last time I called rand() and friends directly for anything.
- adra 2y agoHi about pulling a sample of good random every N invocations to still allow for fast PRNG but to ideally defeat these schemes. Maybe use the real signals RNL value to seed the PRNG. Just a thought.
- pclmulqdq 2y agoI 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 2y agoIf 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.
- zzzzzzzzzz10 2y agoYou can make much more by selling items on 2b. This is not little payout, it sounds to me like one of the most significant exploits in anarchy minecraft history, possibly even more than nocom.
- pclmulqdq 2y agoRNG vulnerabilities are usually really bad in terms of the systems they compromise. It often means exposure of keys, huge numbers of jailbroken devices, or something similar. Making at most tens of thousands of dollars in Minecraft with one is sort of cute and fun in comparison. Of course, I could be underestimating this by a lot.
- saagarjha 2y agoThis 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).
- pclmulqdq 2y agoYeah, 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.
- NoMoreNicksLeft 2y agoOh 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?
- bee_rider 2y agoPretty 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.
- asddubs 2y agoI 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.
- zzzzzzzzzz10 2y agoYou 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.
- asddubs 2y agoYeah, I'm good just not hanging out in the same place as people like that
- bee_rider 2y agoHypothetically 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.
- asddubs 2y agoor just use discord
- hatsunearu 2y agothe 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.
- dzdt 2y agoBack 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.ualberta.ca/~darse/rsbpc2.html https://web.archive.org/web/20180719050311/http://webdocs.cs... [2] https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc
- dzdt 2y agoThe 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.
- bingaling 2y agoreminds me of phase space plots of weak tcp isn rng https://lcamtuf.coredump.cx/oldtcp/tcpseq.html https://lcamtuf.coredump.cx/oldtcp/tcpseq.html https://lcamtuf.coredump.cx/newtcp/ https://lcamtuf.coredump.cx/newtcp/
- leijurv 2y agoI believe that may be the spectral test https://en.wikipedia.org/wiki/Spectral_test https://en.wikipedia.org/wiki/Spectral_test which I mentioned in the explanation when showing the lattices visually
- chc4 2y agoLLL 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 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 https://youtu.be/TM7SutJyDCk
- squigz 2y ago> some sort of black magic > which I can almost pretend to understand if I squint This is me and all cryptography :D
- tptacek 2y agoSean 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-with-lll-reduction-on-truncated-lcg-schemes https://crypto.stackexchange.com/questions/37836/problem-wit...
- pbsd 2y agoPersonally I think https://crypto.stackexchange.com/a/86548 https://crypto.stackexchange.com/a/86548 is a better answer. It turns the LCG state recovery into a hidden number-like problem, and works out the solution that way. It is easy to go from there to (EC)DSA key recovery.
- lyu07282 2y agoThere is also some Rng manipulation to make blocks always drop the maximum, explained here: https://youtu.be/ZcdN1wCJPqM?t=390 https://youtu.be/ZcdN1wCJPqM?t=390
- dzogchen 2y agoI 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 2y agoI 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.
- OsrsNeedsf2P 2y agoTo be fair, there are still servers like that. Last week I was on the largest ReIndev mod server, beautiful architecture for as long as you walked, none protected by any means
- nottorp 2y agoFully unprotected is a lot of work for the mods when the occasional griefer does find the server. Easier to have some form of land ownership/permission system for builds.
- hot_gril 2y agoWhen 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.
- lupusreal 2y agoPublic 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.
- John_da 2y ago[flagged]
- lxe 2y agoThe video on this is amazing: https://www.youtube.com/watch?v=maMpMOnIJDE https://www.youtube.com/watch?v=maMpMOnIJDE. I had no idea how sophisticated the community was.
- ajcp 2y agoThe narration in this video is so over-the-top you'd think they were talking about Stuxnet or something. I love it.
- leijurv 2y agoYes, absolutely :) that's why we went to FitMC to make the video, he always delivers.
- ro_bit 2y agoBetween nocom and this I'm sure at least a dozen people who had no idea about reverse engineering are going to eventually have a career in it thanks to his videos, even if I find them incredibly cheesy. His videos have a habit of reaching and engrossing all sorts of people who otherwise wouldn't really care about minecraft server exploits, and maybe that will inspire some of them to learn more Thanks for the writeup!
- ben_bai 2y agoYeah 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 https://www.youtube.com/watch?v=ea6py9q46QU and https://www.youtube.com/watch?v=GaRurhiK-Lk https://www.youtube.com/watch?v=GaRurhiK-Lk
- er4hn 2y agoThis appears to be a State Compromise Extension Attack (https://en.wikipedia.org/wiki/Random_number_generator_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.
- niederman 2y agoEven better, this style of RNG cracking has even been done in-game: https://youtu.be/FPmQ0rnJjNc?si=tTFObcfZ-ILanL_A https://youtu.be/FPmQ0rnJjNc?si=tTFObcfZ-ILanL_A
- danielwmayer 2y agoYo 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!
- maxitoo 2y ago[flagged]
- sdwvit 2y agoSome 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.
- lawrenceyan 2y agoWhat level of compute would you need realistically to start doing things like this irl instead of in Minecraft I wonder?
- moritonal 2y agoLove 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.
- smithcoin 2y agoLeijurv, 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 2y agoIt was a one-way collaboration, in that we referenced their discoveries and code such as LattiCG https://github.com/mjtb49/LattiCG https://github.com/mjtb49/LattiCG, but they were unaware of anything we were doing until now. https://twitter.com/admiral_stapler/status/1780674861259460918 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 :)
- skitter 2y agoImpressively, 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 https://www.youtube.com/watch?v=FPmQ0rnJjNc