Writeup by shd33 for Abyssal Odds

Table of contents

TLDR: Use Z3 to predict the output of Math.random based on previous outputs (CSP nonce, CSRF token and box ID). Then, find a key for each collectible and catch them all.

Analysis of the challenge

The website allows users to collect ocean-themed virtual items. To do so, they have to buy boxes and open them. However, we can only open eight boxes and the odds of getting all eight collectibles out of luck seem abyssal.

For this challenge, we have access to the source code. By looking into it, we find out that the content of a box is determined by a key sent by the user in the POST request, as well as the current timestamp and a random number associated with the box (box.seed).

Here is the full function:

function _openBox(box: LootBox, key: number) {
  const ts = Math.floor(Date.now() / 1000);
  switch (true) {
    case key === box.seed:
      return 1;
    case Math.abs(key - ts) < 60:
      return 2;
    case box.seed % key === 0:
      return 3;
    case Math.cos(key) * 0 !== 0:
      return 4;
    case key && (box.seed * key) % 1337 === 0:
      return 5;
    case key && (box.seed | key) === (box.seed | 0):
      return 6;
    case !(key < 0) && box.seed / key < 0:
      return 7;
    default:
      return 0;
  }
}

The whole difficulty lies in the fact that we don’t know the box seed, but only the box id. A comment in middleware/0-patch.ts gives us a hint that the pseudo-random generator used to generate the box seed might be broken (the so-called “patch” doesn’t fix anything). Upon closer inspection, we find out that indeed, the box seed is generated by the randomNumber function defined in utils/random.ts, which itself relies on the JS function Math.random which is not cryptographically secure.

Predicting randomness

The Math.random function in NodeJS relies on an algorithm called xorshift128+. At its name indicates, this pseudo-random generator works by applying XOR and shift operations on a 128 bit register. However, xorshift128+ is not cryptographically secure and one can find patterns in its outputs. This allows us to predict the outputs of Math.random based on what it has outputted before. A way to do this is to use a constraint solver such as Z3. The process is detailed in this blogpost I found.

In our case, we find out that Math.random is called several times in the following order:

the session_id cookie is generated with randomHex, which calls Math.random twice
the CSP nonce is generated with randomHex
the csrf_token cookie is generated with randomHex
the box.id variable is generated with randomHex
the box.seed variable is generated with randomNumber, which calls Math.random once.

We need to keep the same session_id cookie during the session, but the CSRF token can be regenerated every time. The CSP nonce, CSRF token and box ID can all be accessed from the /buy webpage. We can use them to guess box.seed using the method mentioned above.

Finding the key

Once we know the box seed, there are only two tricky keys to find:

Math.cos(key) * 0 !== 0 is true when key = Infinity, as Math.cos(Infinity) is NaN.
!(key < 0) && box.seed / key < 0 is true when key = -0.0. Indeed, negative zero is part of the IEEE Standard for Floating-Point Arithmetic and division by zero evaluates to infinity in JS.

Full script

import z3
import struct
import math
import time
import requests
from bs4 import BeautifulSoup


#########################################################################################
# Break the xorshift128+ pseudo-random generator used in NodeJS/V8 using the z3 solver. #
# Reference: https://github.com/IvanLudvig/google-rng-hack/tree/master                  #
#########################################################################################
def xs128p(state0, state1):
    s1 = state0
    s0 = state1
    s1 ^= s1 << 23
    s1 ^= z3.LShR(s1, 17)
    s1 ^= s0
    s1 ^= z3.LShR(s0, 26)
    return s0, s1

def to_double(state0):
    bits = (state0 >> 12) | 0x3FF0000000000000
    return struct.unpack('d', struct.pack('<Q', bits))[0] - 1

def from_double(val):
    return struct.unpack('<Q', struct.pack('d', val + 1))[0] & 0x3FFFFFFFFFFFFFFF

def normalize(val, vmin, vmax):
    return (val - vmin) / (vmax - vmin + 1)

def break_xorshift128(points, vmin, vmax):
    solver = z3.Solver()
    state0, state1 = z3.BitVecs("state0 state1", 64)

    points = points[::-1]  # Math.random() outputs are cached in reverse order
    for point in points:
        state0, state1 = xs128p(state0, state1)
        calc = z3.LShR(state0, 12)

        # make up for the Math.floor() with an inequality
        lower = from_double(normalize(point, vmin, vmax))
        upper = from_double(normalize(point + 1, vmin, vmax))
        upper_exp = (upper >> 52) & 0x7FF  # check for an edge case
        lower = lower & 0x000FFFFFFFFFFFFF
        upper = upper & 0x000FFFFFFFFFFFFF

        solver.add(z3.And(lower <= calc, z3.Or(calc <= upper, upper_exp == 1024)))

    # get the results
    if solver.check() == z3.sat:
        model = solver.model()
        state = {}
        for d in model.decls():
            state[d.name()] = model[d]
        state0 = state["state0"].as_long()
        state1 = state["state1"].as_long()

        next_value = math.floor(to_double(state0) * (vmax - vmin + 1)) + vmin
        return next_value
    else:
        print("[!] failed")


########################
# Solve the challenge! #
########################
def buy_box(session, buy_url):
    response = session.post(buy_url)
    soup = BeautifulSoup(response.text, "html.parser")
    csp_nonce = soup.find('script')['nonce']
    csrf_token = soup.find(attrs={'name': 'csrf_token'})['value']
    box_id = soup.find(attrs={'name': 'boxId'})['value']
    return csp_nonce, csrf_token, box_id

def open_box(session, open_url, csrf_token, key, box_id):
    open_data = {
        "csrf_token": csrf_token,
        "key": key,
        "boxId": box_id,
        "action": "open"
    }
    response = session.post(open_url, json=open_data)

    # check that we found the collectible
    soup = BeautifulSoup(response.text, "html.parser")
    collectible = soup.find(class_="name").string
    print("[!] Found", collectible)

def pair_from_randomhex(s):
    """ Recover the pair of random numbers used in randomHex() """
    return int(s[:8], 16), int(s[8:], 16)

def find_key(collectible, box_seed):
    """ Find the correct key for a given seed to get the desired collectible """
    ts = math.floor(time.time())
    match collectible:
        case 1:  # key === box.seed
            return box_seed
        case 2:  # Math.abs(key - ts) < 60
            return ts
        case 3:  # box.seed % key === 0
            return 1
        case 4:  # Math.cos(key) * 0 !== 0
            return 10**1000  # Math.cos(Infinity) is NaN
        case 5:  # key && (box.seed * key) % 1337 === 0
            return 1337
        case 6:  # key && (box.seed | key) === (box.seed | 0)
            return 1 << int(math.log(box_seed, 2))  # the most significant bit of box.seed
        case 7:  # !(key < 0) && box.seed / key < 0
            return -0.0  # negative zero is part of IEEE 754 
        case 0:
          return 0  # a key of 0 will likely fall back on the default


session = requests.Session()  # to keep track of the session cookie
base_domain = "http://localhost:8000"
buy_url = base_domain + "/buy"
open_url = base_domain + "/open"
collection_url = base_domain + "/collection"
vmin = 0  # the minimum value yielded by randomNumber()
vmax = 0xfffffffe  # the maximum value yielded by randomNumber()

# Gotta catch 'em all!
for c in range(8):
    csp_nonce, csrf_token, box_id = buy_box(session, buy_url)
    points = [
        *pair_from_randomhex(csp_nonce),
        *pair_from_randomhex(csrf_token),
        *pair_from_randomhex(box_id),
    ]
    box_seed = break_xorshift128(points, vmin, vmax)  # the box seed is the next "random" number
    key = find_key(c, box_seed)
    open_box(session, open_url, csrf_token, key, box_id)
    session.cookies.pop('csrf_token', None)  # remove the CSRF cookie so that a new one will be generated

# Get the flag :)
response = session.get(collection_url)
soup = BeautifulSoup(response.text, "html.parser")
flag = soup.find(class_="text-amber-600").string
print("[!] Flag:", flag)