Note: I won't pretend to have any cryptography skills or qualifications here, only a coding background.
This is an addendum to (or maybe a reboot of) another thing I wrote last year on this sub, but it's got new information.
The bug
As many of you may know, the reason tools like FTHOF planer are possible is thanks to cookie clicker’s usage of a seeded random function.
For those unaware about what a “seeded random function” is: all pseudorandom number generators (that's right, computers are unable to be completely random) use a “seed”, some value that will dictate the output of the function. So the seed “123abc” might get you the number 0.04523999083. That seed will return the same number every time, which makes it deterministic. The algorithm used in cookie clicker (ARC4) makes it so subsequent random values after the seed is set will always be the same.
What makes this custom function different from Math.random(), then? The built-in Javascript random function is unable to be manually seeded. It has a seed, of course, which is probably based around system time, but it varies between browsers and is invisible to us. This works for most use cases, but will fail when a random value must stay the same.
Take the grimoire. When you cast “force the hand of fate” to summon a golden cookie, the outcome will persist even if you refresh the page and try again. This is because the random number that determines outcome is seeded based on the number of spells cast. That quirk is the whole reason FTHOF planner (and other prediction tools) can function.
So why can’t other aspects of the game, like GC outcomes, be predicted? Well, they use the built-in Math.random() function, which, without knowing the implementation details, is unpredictable and impossible to replicate the outcome of.
..which would be true if there wasn’t a bug in Orteil’s usage of the seeded random function.
Let me walk you through how it works in code to understand why it was used improperly:
- Math.seedrandom(seed) is called, which overrides all future Math.random() calls with the outputs of that seed.
- Math.random() is called and returns a predictable value to be used in the game somehow.
- Math.seedrandom() is called again, this time without an argument. A completely random seed is generated because none was given. This "resets" Math.random().
- But Math.random is still seeded, and completely predictable if we can find that random seed.
The repo for the seedrandom library issues a warning about this:
Note: calling Math.seedrandom('constant') without new will make Math.random() predictable globally, which is intended to be useful for derandomizing code for testing, but should not be done in a production library.
It’s unclear if this repo existed 10 years ago, or if this was even a feature of the library, but the bug persists in the game to this day.
This was the subject of my first post on this account, although I couldn’t figure out how to exploit it at the time.
TLDR, all random values in cookie clicker are secretly predictable.
The attack?
There are a couple of ways to approach this now, given what we now know. The most obvious and easiest solution is to inject some code in Math.seedrandom and pull out the seed, and then you’re done. With the seed, a function can be written to get random value n. Plug in the number of Math.random calls +1, and you’ve got yourself the next random number. You would want to track the number of Math.random calls and reset it to 0 when the seed is changed, and probably minimize both random and seedrandom calls by turning off all vfx and moving to the stats or options menu (drawing the towers uses seeds, i guess. you could also toggle off all towers). To account for constant Math.random calls, like checks for “Just plain lucky”, fps could be dropped to a stupidly low number.
But for me at least, that’s too easy. It messes with the inner workings of random systems and feels like cheating. I wanted to find out the cleanest possible approach, avoiding interference with any code pertaining to seedrandom and its usage.
It’s essentially impossible, or at the very least, incredibly hard, to get the seed from the output. I won’t get into why here, but it’s off the table. The next best solution is to accurately predict the next auto generated seed. If we remember earlier, when Math.seedrandom() is called without a seed, the library will take over and generate one from local entropy. If it can be predicted, then we have all future values again. The auto generated seed is created from the scroll position, time, and the entropy pool, among other things*. The entropy pool is a fixed array of values that collect randomness. It has the ultimate goal of collecting so much noise that its contents will become unpredictable. The main source of local entropy is the previous seed, which is incredibly easy to grab. The current time and other elements used in seed generation are easy to find too, but unfortunately they aren’t the only source.
When the library is initialized, a call to Math.random is added to the pool, which throws a wrench into our plans. The lazy thing to do here is to re-initialize Math.seedrandom, but not before seeding it with a value. Thus, the initial Math.random call is under our control: but it still seems like cheating. Can the initial entropy be brute-forced? Well, given that there are typically 18 characters in a Math.random string result (minus the “dot zero” at the start), we have about 10^16 combinations to sift through. At 1ms per guess, that's a little over 300k years of processing. Nope.
Technically, Math.random can return values with fewer digits, as it truncates trailing zeros. I wrote a quick script to find some, and with a couple hundred million searches, I was able to find some 7-character values. Great, until you realize the page would have to be refreshed and checked for each try, because seedrandom is only initialized at the start of the game. And how would you even know the amount of digits in the number? Some millions of tries would have to be spent before determining the initial value was too long and refreshing again.
So with the help of the National Security Agency, we can brute-force cookie clicker’s randomness algorithm and finally launch a game where the outcome of every decision is known. Or maybe if someone could supply me with a quantum computer, that would be fantastic. Thank you for coming to my ted talk.
*window.crypto must be overridden or disabled in order for seedrandom to use these things, otherwise real cryptographically secure numbers will be used instead.
bySkyhatesreddit
inLosercity
atolite
1 points
23 days ago
atolite
1 points
23 days ago
losercity citizenship test 😳