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]
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.
Serato is digital pretend scratching. Might as well use a DJ controller. Real scratching requires a proper tt and skill like Mix Master Mike. Hell, I have 2 Pioneer DL-5 and a Pioneer DJM-600, but these tts aren't good for scratching because of their straight arms, they're good for gapless playback. https://youtu.be/58Y--XTIRZ8
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.
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, 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 :)
The whole is better than the sum of the parts. You have nostradamus which predicts the future, fork bot which plays all playable presents, and the psychic friends network which rewrites the past. All under the watchful eye of the matrix.
There's something beautiful here and you honestly couldn't make it up.
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.
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.
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?
If you just want any old entropy, and don't care about proving to someone else that your entropy is good, these are acceptable. But it's honestly really easy to get entropy on that grate, and thanks to modern cryptographically secure PRNG, you don't need a lot of 'real' entropy. You can stretch it out forever.
If you want/need to be able to argue to a third party that your entropy was good, you can spend a bit more.
How do you convince anyone that your mic input was actual real mic input, and not just a sequence of bits you made up to be convenient for you?
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
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:
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.
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.
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.
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.
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.
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.
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.
> 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.
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.
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.
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].
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.
I ran a microbenchmark with Go 1.22, which ships with both ChaCha8 (a little faster than ChaCha12) and PCG (a little slower than xoshiro256+). On my M1 Mac, I'm seeing 2.3 ns/uint64 for PCG and 4.5 ns/uint64 for ChaCha8. Assuming 3.2 GHz clock speed, that puts them at about 1 and 2 cpb respectively. With a floating-point conversion in the mix, they ran at 4.0 and 4.5 (!) ns/float64 respectively. That's far better than I would have thought.
So yes, a good, slightly buffered (internal state seems to be 300 bytes) implementation of a (quasi-?)CSPRNG is pretty damn close to a decent quality non-cryptographic PRNG and likely fast enough for most video games on most hardware. Though, very few people write games in Go.
That's not quite a correct benchmark if I'm understanding what you benchmarked. Xoshiro and PCG need a chain of serial ops to generate a number, but not a lot of parallelism, letting the core do other stuff while it is working. ChaCha needs a lot of parallelism, and you are essentially saturating that core running it.
The builtin benchmarking tool in Go runs with parallelism set to 2x the number of cores. That should make evident any code that scales poorly. It is a tunable parameter though; I can try 4x cores etc.
I also ran it on x86 (AMD Ryzen 5600X) and got similar results; everything ran faster on a 4.6 GHz chip, but ChaCha8 stayed around 2 cpb while PCG improved a little to about 0.7 cpb.
I do have a ~10-year-old Celeron NUC laying around that I could use to test older/lower-end hardware. I can also publish the (admittedly very simple) program I'm using.
It's also worth noting that cpb is still a measure of average throughput not variance or latency and while Go's buffered ChaCha8 implementation amortizes to 2 cpb, when the 32-element buffer exhausts, generating a new number is much more expensive than the previous 31 numbers. I wouldn't say the performance is good enough for every use case.
Ok, I was able to figure out a few more things. First of all, the benchmark runner does not necessarily exploit the parallelism of GOMAXPROCS out of the box. Second, GOMAXPROCS seems to default to 1x logical cores; I last ran it on a machine where logical cores = 2x physical cores. I adjusted the benchmark code to use RunParallel and adjusted the parallelism of each run.
Testing on Celeron J3455 @ 1.5 GHz (4 physical and logical cores) gave me PCG at 1.2 cpb and ChaCha8 at 2.6 cpb with cpu=1, but PCG stayed relatively constant across cpu=1,2,4,8 (worst was 1.8 cpb) while ChaCha8 slowed to 6.5 cpb at cpu=2 and 7.5 cpb at cpu=4 and cpu=8.
Back on my M1 Mac (8 logical and physical? cores), both ChaCha8 and PCG generally got better with more cores. ChaCha8 got down to 0.76 cpb at cpu=4 (then regressed a bit at cpu=8) while PCG got down to 0.26 cpb at cpu=8.
I don't think any of these results rule ChaCha8 out completely, though again I'm looking from the perspective of video games, which generally monopolize a machine while running.
The important question to benchmark for small buffer sizes isn't actually cycles per byte, it's micro-ops per byte. You are sort of getting there by adding threads, but if you want to measure micro-ops per byte by measuring cycles per byte, your benchmarking code should run a number of parallel implementations of the generator on each thread (and stick to 1 thread per physical core, too). Each generator will have a "roof" where more generators per thread doesn't cost any more in terms of cycles/byte. I am assuming that for PCG, that roof is around 4-ish on an old CPU, and may be as high as 6 or 8 on your macbook, while the roof for ChaCha will be close to 1.
ChaCha exploits instruction-level parallelism to get speed. PCG doesn't - it has a chain of instructions that must be executed sequentially. That means that when the PCG generator executes, it leaves gaps in the instruction stream that can be filled with other instructions for the game. That means a slowdown in the game that is more significant than what your benchmark suggests.
I'm going to do this and write blog about it (although I don't have a macbook), so we may be able to compare results.
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.
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.
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.
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.
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
> 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.
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
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.
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).
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.
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.
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.
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.
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.
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.
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
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):
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 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.
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
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.
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.
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.
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!
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.
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 :)
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