[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 : 480 points
Date : 2024-04-17 17:42 UTC (2 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.
| zzzzzzzzzz10 wrote:
| You 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 wrote:
| RNG 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 wrote:
| 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).
| pclmulqdq wrote:
| 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.
| kbolino wrote:
| 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.
| Retr0id wrote:
| 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.
| kibwen wrote:
| _> 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.
| kbolino wrote:
| 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.
| Retr0id wrote:
| chacha12, a construction that's been around in one form
| or another since the '00s, runs at well under 1 cycle per
| byte on good hardware and still plenty fast on "bad"
| hardware https://bench.cr.yp.to/results-stream.html (iiuc
| just using SIMD, no special acceleration)
|
| But it doesn't really matter what things were like when
| the code was first written, it's about how it could be
| fixed in the present.
| kbolino wrote:
| Video games do not generate large streams of data, they
| generate individual values on demand. Your link says, to
| generate 8 bytes, chacha12 on modern hardware needs 24-45
| cpb. That's 192-360 cycles to generate enough bits for a
| pseudorandom double-precision floating-point number.
| Xoshiro256+ [1], a relatively high-quality generator for
| this purpose, can do it with 11 single-cycle ALU ops. So
| unoptimized xoshiro256+ should be 17 times faster than
| optimized chacha12 on the best hardware. This is a
| classic latency vs. throughput issue.
|
| Now, maybe you could optimize the use of a CSPRNG here by
| filling large buffer(s) and sampling values from them.
| Some warm-up time could go a long way. However, I fear
| that you would run into one or more of the following
| problems:
|
| - stop-the-world pause to refill the buffer (e.g. single
| buffer, no threading)
|
| - synchronization delays from mutex locks (e.g. ring
| buffer refilled from a background thread)
|
| - high memory usage (e.g. rotating pool of buffers,
| atomically swapped)
|
| Needless to say, none of these solutions is anywhere near
| as simple to implement as a non-cryptographic PRNG.
|
| Now let's consider determinism. Video games generally use
| a lot of differently seeded instances of the same PRNG
| algorithm to provide random numbers in different parts of
| the simulation. Since each part may demand random numbers
| at different rates, it's hard to replace several
| independent PRNGs with a single PRNG without compromising
| determinism. In the 4096 bytes necessary to run one
| instance of chacha12 at its maximum efficiency, you can
| fit 128 instances of xoshiro256+ or 512 instances of
| splitmix64 [2].
|
| [1] = https://prng.di.unimi.it/xoshiro256plus.c
|
| [2] = https://github.com/svaarala/duktape/blob/master/mis
| c/splitmi...
| pclmulqdq wrote:
| There are CSPRNG constructions based on AES that would
| probably be appropriate, but they are still a huge
| performance hit. PCG, Xorshift, Xoshiro, and the like are
| all about 50x faster than the fastest CSPRNGs in
| sustained throughput, and also have smaller state and
| much less spinup time.
| Retr0id wrote:
| Generating random numbers into a refillable buffer is the
| standard for high-performance RNG, whether you're doing
| CSPRNG or not (it's how V8 uses xorshift, for example).
| "stop the world" is not a problem when the time to refill
| the buffer is still measured in nanoseconds.
|
| There's nothing stopping you from having multiple CSPRNG
| instances, with deterministic seeds, if that's a design
| requirement.
| pclmulqdq wrote:
| 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.
| marshray wrote:
| 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.
| Filligree wrote:
| "Random" means something closer to "contains maximal
| information"...
| armb wrote:
| 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.
| ryanisnan wrote:
| Indeed! I love seeing how the seemingly innocuous decisions by
| Mojang devs are being abused here, so freaking cool.
| 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.
| zzzzzzzzzz10 wrote:
| You 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 wrote:
| Yeah, I'm good just not hanging out in the same place as
| people like that
| bee_rider wrote:
| Hypothetically 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 wrote:
| or just use discord
| 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.
| bee_rider wrote:
| That's what I think is interesting about it, it looks like
| (from the outside at least; for all I know it could be super
| boring to play) a new system on top of the old one that
| obviates some of the old mechanics by ramming them to
| infinity/zero, but other mechanics emerge as a result.
|
| What's the difference between a weak and strong location?
|
| I could imagine funny evolutions over time, just a random
| thought, if everyone is running a "glass cannon with lots of
| 1-hit protection" build, then I guess if players had to pick
| between fast/little attacks and big/slow ones, they'd favor
| the former. If everyone is walking around with little attacks
| just intended to trigger the 1-hit protections on their
| fellow glass cannons, then actually using the in-game armor
| system might turn those one hits into two-hits, making it
| relevant again. If the systems were properly tuned, (it could
| be exponentially difficult to gather 1-hit protections and
| extra lives, so turning those 1-hits into 2-hits could be
| really valuable), mechanics could be saved from obsolescence
| in interesting ways.
|
| I'm not describing Minecraft at this point, just spitballing.
| It would be interesting to see a game designed with this
| evolution of "things being broken" taken into account,
| though. I guess that's what Magic the Gathering is, hahaha.
| hatsunearu wrote:
| > What's the difference between a weak and strong location?
|
| IIRC ender crystals can only be placed on bedrock, and a
| lot of PVP happens on the bombed-out terrain that goes all
| the way to bedrock.
|
| The weak terrain in the bedrock are locations where it
| requires multiple jumps to get out of, iirc
| gu5 wrote:
| Adding on to this, explosions deal significantly more
| damage if your whole player is exposed - so one block
| holes where the bottom half of the player hitbox is
| covered by bedrock on all sides are usually marked by
| hacked clients
| 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.
| hot_gril wrote:
| The problem is, the optimal hacks usually don't make the game
| fun. It becomes a war of attrition.
| chii wrote:
| > don't make the game fun
|
| the fun is no longer the game in an anarchy server. It's in
| beating other play's strategies - which actually makes it
| quite close to a real war in the physical world.
|
| For example, the 2b2t minecraft wars between factions
| involve logistics, misinformation and intelligence (such as
| spies, fakes etc). It's no longer just minecraft. But
| that's what makes it fun and interesting.
| hot_gril wrote:
| Yeah but that's not fun, that's tedious work 99% of the
| time that culminates in some rare fun.
| orbital-decay wrote:
| _> tedious work 99% of the time that culminates in some
| rare fun_
|
| Welcome to the multiplayer gaming, especially games like
| Minecraft or ARK.
| hot_gril wrote:
| Online games without hacks are usually fun the whole
| time, even Minecraft SMP. Lots of people play those
| casually.
| dontupvoteme wrote:
| This happened in PvE situations too -- Everquest always had
| people, especially guilds, running ShowEQ/MacroEQ to read mob
| locations off of the wire/from memory. Often could be used in
| non-unethical ways[1]
|
| Sometimes you got funny situations like top guilds cheesing
| new raid content in their race to finish it first, leading
| the devs to go "cmon bro, you only played yourself" and then
| patching it immediately after, but almost never taking any
| loot away or banning anyone.
|
| Also funny is the common situation where you don't want to
| _admit_ to everyone in your guild that you have at least one
| person running it, but you can kind of figure it out and it
| becomes an open secret.
|
| 1 - These are the days where you might have to clear down a
| dungeon 4 hours to see if a mob is up, or, even worse, to see
| if it's camped or not. Alternatively (or as a cover) people
| just parked alts but you get the idea. Also, come to think of
| it, Diablo had this too with maphacks and grabit and such
| hot_gril wrote:
| 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).
| vitiral wrote:
| In those cases the bugs are more like advanced fighting
| moves. I don't think item dup or insta-kill bugs would be
| allowed, even if they did exist.
| hot_gril wrote:
| Surprisingly none of those bugs have been found, but yeah
| they'd be banned. The weirdest thing people actually use is
| the yoyo glitch, which allows Ness to hit a player with a
| powerful move from anywhere on the map, but it's hard
| enough to execute that it's not OP.
| dontupvoteme wrote:
| >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?
| 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 :)
| dzdt wrote:
| Thanks for the deep dive. Yes fun to follow.
| konstantinua00 wrote:
| so parallel universes lost to rewriting history
|
| amazing
| 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!
| reactordev wrote:
| So what you're saying is, if you can't beat em, join em? /s
|
| I'm actually a bit relieved they have you on the team.
| Considering what they (Google) know about us all.
| tomrod wrote:
| This makes me happy to see.
| sleepingreset wrote:
| you're a wizard bro. hell yea
| shthed wrote:
| Can you share the source to Nostradamus?
| le-mark wrote:
| Or a write up on the algorithm used? How did knowledge of
| the prngs of the impact the impl?
| teekert wrote:
| You pulled a Kobayashi Maru when you got the chance. I bow to
| thee.
| spacebacon wrote:
| 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.
| romanows wrote:
| DJs have timecoded vinyl records that do something like
| this, even allowing the DJ to scratch the mp3 that is being
| played.
| joshu wrote:
| I submitted the optimally bad entrant the first year,
| cheesebot.
|
| https://web.archive.org/web/20180719050236/http://webdocs.cs...
| BarryMilo wrote:
| I can't believe they didn't say anything about your solution!
| How did it work?
| rhaps0dy wrote:
| Nice! How does Cheesebot work and why did it lose?
| eru wrote:
| 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.)
| alickz wrote:
| I'm surprised they don't use some form of hardware based RNG.
| I assume there's many good reasons
|
| https://en.wikipedia.org/wiki/Hardware_random_number_generat.
| ..
| eru wrote:
| They wanted to show that they didn't cheat.
|
| In general, you can pick a random seed at the start of the
| day, commit to it somewhere (eg publish a hash of it on the
| bitcoin blockchain, or just on your website), then use that
| seed in a cryptographically secure PRNG on your website all
| day, and at the end of the day you publish the seed you
| already committed to.
|
| This way people can check that you didn't cheat, but can't
| guess their opponents cards either.
| eru wrote:
| (The above was simplified. In a game of poker, you also
| want to make sure that when hands get folded, that no one
| learns what the cards were.)
| thenewnewguy wrote:
| Wouldn't the most obvious method of cheating be the site
| owner peeking at other player's hands and/or the deck?
| Which this doesn't (and cannot) prevent?
|
| I guess I'm not sure what publicizing their PRNG is meant
| to prove. It shows they didn't cheat via a very specific
| type of cheating but there are several other potential
| cheating vectors.
| logtempo wrote:
| https://www.random.org/
| mikegreenberg wrote:
| Or, if you don't want to trust the source,
| https://drand.love/
| Elucalidavah wrote:
| > don't use some form of hardware based RNG
|
| I've always wondered: why aren't ADCs (e.g. mic input) and
| temperature sensors considered a good source of entropy,
| particularly if the lower bits are taken?
| bagels wrote:
| So, it was using a pseudorandom generator?
| 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
| tptacek wrote:
| 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...
| pbsd wrote:
| Personally I think 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 wrote:
| There is also some Rng manipulation to make blocks always drop
| the maximum, explained here:
|
| https://youtu.be/ZcdN1wCJPqM?t=390
| 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
| nottorp wrote:
| Fully 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 wrote:
| 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.
| lupusreal wrote:
| 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.
| hot_gril wrote:
| Maybe, but back in high school, it was very hard to find
| those. Especially with things advertised as "vanilla" or
| "semi-vanilla" actually having tons of crap installed.
| permo-w wrote:
| if so, you'd be making a poor argument
| immibis wrote:
| I assure you Notch did not mean to make a game of RNG reverse
| engineering.
| 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.
| ajcp wrote:
| The narration in this video is so over-the-top you'd think they
| were talking about Stuxnet or something. I love it.
| leijurv wrote:
| Yes, absolutely :) that's why we went to FitMC to make the
| video, he always delivers.
| ro_bit wrote:
| Between 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 wrote:
| 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
| er4hn wrote:
| 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.
| niederman wrote:
| Even better, this style of RNG cracking has even been done _in-
| game_ :
|
| https://youtu.be/FPmQ0rnJjNc?si=tTFObcfZ-ILanL_A
| danielwmayer wrote:
| 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 wrote:
| I'm just a regular SWE! Infosec or algorithmic trading - maybe
| someday.
| tptacek wrote:
| This is you? You're fully qualified.
| sdwvit wrote:
| 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.
| lawrenceyan wrote:
| What level of compute would you need realistically to start doing
| things like this irl instead of in Minecraft I wonder?
| moritonal wrote:
| 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.
| smithcoin wrote:
| 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 wrote:
| 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 :)
| skitter wrote:
| 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
___________________________________________________________________
(page generated 2024-04-19 23:02 UTC)