[HN Gopher] Randar: A Minecraft exploit that uses LLL lattice re...
___________________________________________________________________
Randar: A Minecraft exploit that uses LLL lattice reduction to
crack server RNG
Author : leijurv
Score : 182 points
Date : 2024-04-17 17:42 UTC (1 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| ZeWaka wrote:
| 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 wrote:
| 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.
| IshKebab wrote:
| Pretty much all serious software uses PRNG at some point.
| Unless you mean you use CSPRNG, which is the easy fix.
| iforgotpassword wrote:
| Yeah 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 wrote:
| Hi 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 wrote:
| 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 wrote:
| 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.
| NoMoreNicksLeft wrote:
| 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?
| bee_rider wrote:
| 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.
| asddubs wrote:
| 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.
| hatsunearu wrote:
| 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 wrote:
| _> 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.
| dzdt wrote:
| 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
| dzdt wrote:
| 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.
| rhaps0dy wrote:
| I was very curious about the Psychic Friends Network. One can
| find the code here
| (https://github.com/MrValdez/Roshambo/blob/master/rsb-
| iocaine...), and it's easy to deobfuscate substantially by
| running it through the C preprocessor.
|
| I believe it works as follows: - It plays randomly for the
| first 998 turns
| (https://github.com/MrValdez/Roshambo/blob/master/rsb-
| iocaine...): this line is "if (*turn < trials - 2) return
| libra ? callback() : random() % 3;", and "libra" is
| initalized to (int) NULL, i.e. zero, on every invocation.
|
| - In the last 2 turns, it uses `find_goodkarma` to comb
| through the stack to find where the variables that match its
| history and the opponents' history are stored. These the
| stack arrays p1hist and p2hist
| (https://github.com/MrValdez/Roshambo/blob/master/rsb-
| iocaine...)
|
| They're easy to find because they contain 998 known values
| each in a ~random sequence of (0, 1, 2), and they're just
| upwards of the stack from the current invocation of the
| Psychic Friends Network.
|
| `find_goodkarma` simply increments a pointer until the whole
| sequence of 998 values matches the known history.
|
| - Then, it rewrites the history to make itself win. These
| lines (https://github.com/MrValdez/Roshambo/blob/master/rsb-
| iocaine...) never get executed, then these lines
| (https://github.com/MrValdez/Roshambo/blob/master/rsb-
| iocaine...) tally up draws so far (libra), wins (cancer) and
| losses (scorpio).
|
| This line makes sure its move is the opponents' move +1 mod
| 3, which is the winning move:
| https://github.com/MrValdez/Roshambo/blob/master/rsb-
| iocaine...
|
| Then, these lines repeat the same trick for the number of
| wins and losses. It checks whether it's p1 or p2 by comparing
| the addresses of the win/loss arrays, and then overwrites the
| wins/losses appropriately using `pizza`
| https://github.com/MrValdez/Roshambo/blob/master/rsb-
| iocaine...
|
| in the end it returns an arbitrary value (the address of
| `good_hand` mod 3).
|
| It was fun to follow but the result is kind of boring :)
| timdierks wrote:
| 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.
| timvdalen wrote:
| Only on Hacker News!
| joshu wrote:
| I submitted the optimally bad entrant the first year,
| cheesebot.
|
| https://web.archive.org/web/20180719050236/http://webdocs.cs...
| bingaling wrote:
| reminds me of phase space plots of weak tcp isn rng
|
| https://lcamtuf.coredump.cx/oldtcp/tcpseq.html
|
| https://lcamtuf.coredump.cx/newtcp/
| leijurv wrote:
| 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
| chc4 wrote:
| 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
| squigz wrote:
| > some sort of black magic
|
| > which I can almost pretend to understand if I squint
|
| This is me and all cryptography :D
| dzogchen wrote:
| 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 wrote:
| 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.
| OsrsNeedsf2P wrote:
| To 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
| CERNoholic wrote:
| The video looks very much like a particle collider's detector
| output.
| lxe wrote:
| The video on this is amazing:
| https://www.youtube.com/watch?v=maMpMOnIJDE. I had no idea how
| sophisticated the community was.
___________________________________________________________________
(page generated 2024-04-18 23:00 UTC)