GoogleCTF2023 Writeup

Misc

Crypto

LEAST COMMON GENOMINATOR?

Web

UNDER-CONSTRUCTION

NPC

A friend handed me this map and told me that it will lead me to the flag.
It is confusing me and I don’t know how to read it, can you help me out?

Attachment

使用Graphviz工具将hint.dot转换为图片,得到下图

dot -Tjpg  hint.dot -o hint.jpg

分析代码:

从USACONST.TXT中随机选择N个单词生成密码,使用passphrase.encrypt(secret, password)对flag加密
对于password中的每个字母,创建一个带有唯一ID的节点,并添加到图中
按照password的顺序,对密码中相邻的两个字符创建一条边
向图中随机添加int(len(password) ** 1.3)条边
随机打乱图中节点和边的顺序
随机交换一些节点的起点和终点,由于random() % 2只有在random函数返回值为0时才为False,我们假定图中每条边的起点和终点都被交换了一遍
将节点和边的信息写入到hint.dot文件中

我是思路是:

遍历words_list中的单词,从每个节点出发,使用DFS判断是否可以在图中找到,这样过滤后得到30个单词,即密码一定由该30个单词中的某几个单词组成
枚举密码中所用的单词个数N
使用组合数从这30个单词选择N个单词
判断所选的N个单词组成的字符集和hint.dot中的字符集是否一致
对N个单词进行全排列,并尝试解密 (为了提高效率,这里还用到了多进程)

当N=5时,得到passwordstandardwatersigngivenchosen和flag.

代码

import concurrent.futures
import itertools
import re
from collections import Counterfrom pyrage import passphrasefrom encrypt import get_word_listclass Node:def __init__(self, letter):self.letter = letterself.adjacent = []def __str__(self) -> str:return f"{self.letter} -> {[x.letter for x in self.adjacent]}"__repr__ = __str__def build_nodes():pattern = r"\s+(\d+)\s+\[label=(\w+)\];"pattern2 = r"\s+(\d+)\s+--\s+(\d+);$"nodes = dict()with open("hint.dot", "r") as f:for line in f:if "label" in linematch = re.match(pattern, line)node_id = match.group(1)letter = match.group(2)nodes[node_id] = Node(letter)elif "--" in line:match = re.match(pattern2, line)start = match.group(1)end = match.group(2)# nodes[start].adjacent.append(nodes[end])nodes[end].adjacent.append(nodes[start])return nodesvisited = set()def dfs(node, index, word):if index == len(word):return Trueif node.letter != word[index]:return Falsevisited.add(node)for adj in node.adjacent:if adj not in visited:if dfs(adj, index + 1, word):return Truevisited.remove(node)return Falsedef check(password):with open("secret.age", "rb") as f:enc = f.read()try:print("[FLAG] is ", passphrase.decrypt(enc, password))print("Password is ", password)except Exception as e:passdef filter_words(nodes):ans = set()for word in get_word_list():visited.clear()for node in nodes.values():if dfs(node, 0, word):ans.add(word)breakprint("ans:", len(ans), ans)return ansdef main():nodes = build_nodes()letters = sorted([node.letter for node in nodes.values()])ans = filter_words(nodes)for num in range(1, len(ans) + 1):print(f"Num is {num}")for comb in itertools.combinations(ans, num):  # 组合if sorted("".join(comb)) == letters:passwords = ["".join(perm) for perm in itertools.permutations(comb, len(comb))]with concurrent.futures.ProcessPoolExecutor(max_workers=8) as executor:executor.map(check, passwords)if __name__ == "__main__":main()

flag: CTF{S3vEn_bR1dg35_0f_K0eN1g5BeRg}

参考:

concurrent.futures — 启动并行任务 – Python 3.11.4 文档

LEAST COMMON GENOMINATOR?

Someone used this program to send me an encrypted message but I can’t read it! It uses something called an LCG, do you know what it is? I dumped the first six consecutive values generated from it but what do I do with it?!

Attachment

generate.py

from secret import config
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrimeclass LCG:lcg_m = config.mlcg_c = config.clcg_n = config.ndef __init__(self, lcg_s):self.state = lcg_sdef next(self):self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_nreturn self.stateif __name__ == '__main__':assert 4096 % config.it == 0assert config.it == 8assert 4096 % config.bits == 0assert config.bits == 512# Find prime value of specified bits a specified amount of timesseed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635lcg = LCG(seed)primes_arr = []dump = Trueitems = 0dump_file = open("dump.txt", "w")primes_n = 1while True:for i in range(config.it):while True:prime_candidate = lcg.next()if dump:dump_file.write(str(prime_candidate) + '\n')items += 1if items == 6:dump = Falsedump_file.close()if not isPrime(prime_candidate):continueelif prime_candidate.bit_length() != config.bits:continueelse:primes_n *= prime_candidateprimes_arr.append(prime_candidate)break# Check bit lengthif primes_n.bit_length() > 4096:print("bit length", primes_n.bit_length())primes_arr.clear()primes_n = 1continueelse:break# Create public key 'n'n = 1for j in primes_arr:n *= jprint("[+] Public Key: ", n)print("[+] size: ", n.bit_length(), "bits")# Calculate totient 'Phi(n)'phi = 1for k in primes_arr:phi *= (k - 1)# Calculate private key 'd'd = pow(config.e, -1, phi)# Generate Flagassert config.flag.startswith(b"CTF{")assert config.flag.endswith(b"}")enc_flag = bytes_to_long(config.flag)assert enc_flag < n# Encrypt Flag_enc = pow(enc_flag, config.e, n)with open ("flag.txt", "wb") as flag_file:flag_file.write(_enc.to_bytes(n.bit_length(), "little"))# Export RSA Keyrsa = RSA.construct((n, config.e))with open ("public.pem", "w") as pub_file:pub_file.write(rsa.exportKey().decode())

分析可知:

flag是使用RSA加密的,已知公🔑 文件,即n,e
使用LCG线性同余生成器生成素数
已知LCG的种子和前6个连续生成的数字
config.it = 8
config.bits = 256

LCG是伪随机数生成器和流密码的一种,递推公式是 𝑋𝑛+1=(𝑎𝑋𝑛+𝑐) 𝑚𝑜𝑑 𝑚

已知初值和随后LCG连续生成的6个值,未知增量、乘数和模数.

我们可以通过攻击得到这三个值,然后模拟原算法通过LCG得到8个素数后,进一步计算n的欧拉函数并求逆元得到d,解密即可.

题解:

import math
from functools import reduceimport gmpy2from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrime, long_to_bytesdump_file = open("dump.txt")
output_values = [int(x) for x in dump_file.readlines()]  # 已知的 LCG 输出值def crack_unknown_increment(states, modulus, multiplier):"""已知：a,m,s0,s1求c"""increment = (states[1] - states[0] * multiplier) % modulusreturn modulus, multiplier, incrementdef crack_unknown_multiplier(states, modulus):"""已知：m,s0,s1,s2求a"""multiplier = ((states[2] - states[1]) * gmpy2.invert(states[1] - states[0], modulus) % modulus)  # 注意这里求逆元return crack_unknown_increment(states, modulus, multiplier)def crack_unknown_modulus(states):"""已知：s0-s6求a,c,m"""diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]zeroes = [t2 * t0 - t1 * t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]modulus = abs(reduce(math.gcd, zeroes))return crack_unknown_multiplier(states, modulus)class LCG:def __init__(self, lcg_m, lcg_c, lcg_n, lcg_s):self.state = lcg_sself.lcg_m = lcg_mself.lcg_c = lcg_cself.lcg_n = lcg_ndef next(self):self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_nreturn self.statem, a, c = crack_unknown_modulus(output_values)
seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
lcg = LCG(a, c, m, seed)
print(a, c, m)
primes_n = 1
primes_arr = []
for i in range(8):while True:prime_candidate = lcg.next()if not isPrime(prime_candidate):continueelif prime_candidate.bit_length() != 512:continueelse:primes_n *= prime_candidateprimes_arr.append(prime_candidate)breakprint(list(primes_arr))phi = 1
for k in primes_arr:phi *= k - 1key = RSA.importKey(open("public.pem", "r").read())
n = key.n
e = key.e
d = gmpy2.invert(e, phi)enc = open("flag.txt", "rb").read()flag = pow(int.from_bytes(enc, "little"), d, n)
print(long_to_bytes(flag))

flag: CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}

参考:

攻击线性同余生成器(LCG) | 码农网
LCG(线性同余生成器)_lcg线性同余_WustHandy的博客-CSDN博客

UNDER-CONSTRUCTION

We were building a web app but the new CEO wants it remade in php.

Attachment
https://under-construction-web.2023.ctfcompetition.com
https://under-construction-php-web.2023.ctfcompetition.com

题目提供了Flask和PHP两个站点,用户可以在Flask站点进行注册,注册的账号可以同时用于登录Flask和PHP两个站点.

分析代码:

Flask会将HTTP请求原始查询参数转发到PHP应用程序中完成用户注册.

# File: /flask/authorized_routes.py
@authorized.route('/signup', methods=['POST'])
def signup_post():raw_request = request.get_data()...requests.post(f"http://{PHP_HOST}:1337/account_migrator.php", headers={"token": TOKEN, "content-type": request.headers.get("content-type")}, data=raw_request)return redirect(url_for('authorized.login'))

只有gold级别的用户,在PHP站点登录后才可以看到FLAG

# File: /php/index.php
function getResponse()
{...$response = "Login successful. Welcome " . htmlspecialchars($username) . ".";if ($tier === "gold") {$response .= " " . getenv("FLAG");}return $response;
}

Flask会对查询参数进行校验,防止创建高权限的用户.

# File: /flask/authorized_routes.py
@authorized.route('/signup', methods=['POST'])
def signup_post():...tier = models.Tier(request.form.get('tier'))if(tier == models.Tier.GOLD):flash('GOLD tier only allowed for the CEO')return redirect(url_for('authorized.signup'))...

HTTP查询参数中存在重复的key时,在Flask和PHP有不同的行为,flask会取第一个值,而PHP会取最后一个值.

因此我们可以构造如下命令,以此绕过Flask对查询参数的校验,并在PHP中注册高权限用户.

curl

curl -X POST https://under-construction-web.2023.ctfcompetition.com/signup -d "username=admin&password=admin&tier=blue&tier=gold"

然后用上述的用户名和密码去PHP站点登录即可.

flag: CTF{ff79e2741f21abd77dc48f17bab64c3d}