Go back

SEKAICTF 2023 writeup

Suggest changes

Cuối tuần vừa rồi (25/8 - 27/8) đã diễn ra giải SEKAICTF 2023, mình đã đánh cho team m1cr0$oft 0ff1c3 và kết thúc giải ở vị trí thứ 27.

Giải này là một trong các giải yêu thích của mình, cơ mà lần này mình thi hơi choked nên chỉ solve được vài câu ppc và 1 câu crypto.

TL;DR

Graph and PPC everywhere

Table of contents

Open Table of contents

cryptoGRAPHy1

Graphs have gained an increasing amount of attention in the world of Cryptography. They are used to model many real-world problems ranging from social media to traffic routing networks. Designing a secure Graph Encryption Scheme (GES) is important as querying plaintext graph database can leak sensitive information about the users.

In this challenge I have implemented a novel GES. Please help me verify if the cryptosystem works.

Author: sahuang

❖ Note lib.zip remains unchanged in this series. The flag for this challenge will be used to access the next one when unlocked.

nc chals.sekai.team 3001

Attachments:

from . import GES
from . import utils
import networkx as nx
import random

from SECRET import flag, decrypt

NODE_COUNT = 130
EDGE_COUNT = 260
SECURITY_PARAMETER = 16

def gen_random_graph(node_count: int, edge_count: int) -> nx.Graph:
    nodes = [i for i in range(1, node_count + 1)]
    edges = []
    while len(edges) <  edge_count:
        u, v = random.choices(nodes, k=2)
        if u != v and (u, v) not in edges and (v, u) not in edges:
            edges.append([u, v])
    return utils.generate_graph(edges)

if __name__ == '__main__':
    try:
        print("[+] Generating random graph...")
        G = gen_random_graph(NODE_COUNT, EDGE_COUNT)
        myGES = GES.GESClass(cores=4, encrypted_db={})
        key = myGES.keyGen(SECURITY_PARAMETER)
        print(f"[*] Key: {key.hex()}")

        print("[+] Encrypting graph...")
        enc_db = myGES.encryptGraph(key, G)

        print("[!] Answer 50 queries to get the flag. In each query, input the shortest path \
              decrypted from response. It will be a string of space-separated nodes from \
              source to destination, e.g. '1 2 3 4'.")
        for q in range(50):
            while True:
                u, v = random.choices(list(G.nodes), k=2)
                if nx.has_path(G, u, v):
                    break
            print(f"[+] Query {q+1}/50: {u} {v}")
            token = myGES.tokenGen(key, (u, v))
            _, resp = myGES.search(token, enc_db)
            print(f"[*] Response: {resp.hex()}")

            ans = input("> Original query: ").strip()
            if ans != decrypt(u, v, resp, key):
                print("[!] Wrong answer!")
                exit()
        print(f"[+] Flag: {flag}")
    except:
        exit()

Nhận xét:

Script:

from pwn import *
from tqdm import tqdm
import utils


host, port = "chals.sekai.team", 3001
r = remote(host, port)#process(["python", "test.py"])


r.recvuntil(b"Key: ")
key = bytes.fromhex(r.recvline().rstrip().decode())
print(f"Given key: {key.hex()}")

key_SKE, key_DES = key[:16], key[16:]

for i in tqdm(range(50)):
    r.recvuntil(f"Query {i+1}/50: ".encode())
    u, v = r.recvline().rstrip().decode().split(" ")
    u = int(u)
    v = int(v)
    print(f"Given nodes: {u}, {v}")
    path = [u]
    r.recvuntil(b"Response: ")
    resp = bytes.fromhex(r.recvline().rstrip().decode())
    block = [resp[i:i+32] for i in range(0, len(resp), 32)]
    for i in block:
        next_vertex, root = eval(utils.SymmetricDecrypt(key_SKE, i).decode())
        path.append(next_vertex)
    #print(path)
    data = " ".join([str(i) for i in path])
    print(f"Recovering path successfully:\n{data}")

    r.sendlineafter(b"> Original query: ", data.encode())

r.interactive()
#SEKAI{GES_15_34sy_2_br34k_kn@w1ng_th3_k3y}

-> Flag: SEKAI{GES_15_34sy_2_br34k_kn@w1ng_th3_k3y}

cryptoGRAPHy2

I am wondering what can be leaked in my GES. Let me know if you can recover the graph structure in an Honest-But-Curious setting.

Author: sahuang

❖ Note lib.zip remains unchanged in this series. The flag for this challenge will be used to access the next one when unlocked.

nc chals.sekai.team 3062

Attachments:

import GES, utils
import networkx as nx
import random

from SECRET import flag, get_SDSP_node_degrees

'''
get_SDSP_node_degrees(G, dest) returns the node degrees in the single-destination shortest path (SDSP) tree, sorted in ascending order.
For example, if G has 5 nodes with edges (1,2),(1,3),(2,3),(2,5),(4,5) and dest=1, returns "1 1 2 2 2".
[+] Original:       [+] SDSP:
1--2--5--4          1--2--5--4
| /                 |
3                   3
'''
# Another example for sanity check
TestGraph = utils.generate_graph([[1, 2], [1, 4], [1, 6], [6, 5], [6, 7], [4, 7], [2, 5]])
assert get_SDSP_node_degrees(TestGraph, 1) == '1 1 1 2 2 3'

NODE_COUNT = 130
EDGE_PROB = 0.031
SECURITY_PARAMETER = 32

def gen_random_graph() -> nx.Graph:
    return nx.fast_gnp_random_graph(n=NODE_COUNT, p=EDGE_PROB)

if __name__ == '__main__':
    try:
        print("[!] Pass 10 challenges to get the flag:")
        for q in range(10):
            print(f"[+] Challenge {q+1}/10. Generating random graph...")
            while True:
                G = gen_random_graph()
                if nx.is_connected(G):
                    break
            myGES = GES.GESClass(cores=4, encrypted_db={})
            key = myGES.keyGen(SECURITY_PARAMETER)

            print("[+] Encrypting graph...")
            enc_db = myGES.encryptGraph(key, G)

            dest = random.choice(list(G.nodes()))
            print(f"[*] Destination: {dest}")

            attempts = NODE_COUNT
            while attempts > 0:
                attempts -= 1
                query = input("> Query u,v: ").strip()
                try:
                    u, v = map(int, query.split(','))
                    assert u in G.nodes() and v in G.nodes() and u != v
                except:
                    print("[!] Invalid query!")
                    break
                token = myGES.tokenGen(key, (u, v)) 
                print(f"[*] Token: {token.hex()}")
                print(f"[*] Query Response: {tok.hex() + resp.hex()}")

            ans = input("> Answer: ").strip()
            if ans != get_SDSP_node_degrees(G, dest):
                print("[!] Wrong answer!")
                exit()
        print(f"[+] Flag: {flag}")
    except:
        exit()

Nhận xét:

Script:

from pwn import *
from tqdm import tqdm

host, port = "chals.sekai.team", 3062

r = remote(host, port)




flag = b"SEKAI{GES_15_34sy_2_br34k_kn@w1ng_th3_k3y}"
r.sendlineafter(b"Flag for cryptoGRAPHy 1: ", flag)

for i in range(10):
    print(f"Attempts {i+1}/10")
    r.recvuntil(b"Destination: ")
    dest = int(r.recvline().rstrip())
    print("Given dest:", dest)
    res = []
    print("Querying phase")
    for i in tqdm(range(130)):
        #print(f"Querrying on node {i}, {dest}")
        if i == dest: continue
        r.sendlineafter(b"> Query u,v: ", f"{i},{dest}".encode())
        r.recvuntil(b"[*] Token: ")
        token = r.recvline().rstrip().decode()
        r.recvuntil(b"Query Response: ")
        data = r.recvline().rstrip().decode()
        tok, resp = data[:len(data)//2], data[len(data)//2:]
        res.append(token+tok)

    r.sendlineafter(b"> Query u,v: ", f"{i},{dest}".encode()) #for the last

    
    
    res.sort(key = len)
    data = []

    root = res[0][-64:]
    deg_root = 0
    for i in range(len(res)):
        if root == res[i][64:64+64]:
            deg_root+=1
    res = [i[:-64] for i in res]
    data.append(deg_root)


    cnt = 0
    while True:
        if len(res) == 0: break
        cur = res[0][-64:]
        deg = 0
        for i in range(1, len(res)):
            if cur == res[i][64:64+64]:
                deg+=1
                res[i] = res[i][:-64]

        res = res[1:]
        for i in range(len(res)):
            if res[i][-64:] == cur:
                res[i] = res[i][:-64]
        data.append(deg+1)
        cnt+=1

    
    
    data = " ".join(str(i) for i in sorted(data))
    print(f"Recover path successfully :\n{data}")
        
    
    r.sendlineafter(b"> Answer: ", data.encode())

    print("~"*40)

r.interactive()
#SEKAI{3ff1c13nt_GES_4_Shortest-Path-Queries-_-}

Giải thích:

-> Flag: SEKAI{3ff1c13nt_GES_4_Shortest-Path-Queries-_-}

Suggest changes
Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
WannaW1n WickedCrown 2023 writeup
Next Post
corCTF 2023 writeup