Scarlet CTF Coloring Heist

 

크립토 문제인데, 자연스럽게 서버와 상호작용 하며 ZKP 오라클을 이용해 coloring 정보를 점진적으로 북구하는 암호학 문제라고 생각해서, 초기에는 서버에 접근해서 

query -> 전체 commits를 제공해주고 
edge로 해당 edge에 대한 proof를 반환해서 값을 얻었다.

실제로 계속 수동으로 정보수집한 흔적들

그렇게 해서, salt / color 일부를 수집 했고, 이를 기반으로 coloring을 역추적 할 계획이었지만, 세션당 PoW 1회 query 1회 edge 1회 이후 추가 edge proof 수집이 불가능 하기 때문에, 수동으로 5개정도의 데이터만 추출해 봤는데, 이게 추출하면서, 이상한 점을 느낀게 추출을 할 때 마다 바뀌는 값이었다. 그래서 위의 흔적들은 쓸모 없는 노력이 되어버렸다.

 

따라서, 이 coloring이 graph.txt를 실제 서버에다가 입력해서 proof 값을 얻어 풀이해라 라는 문제가 아닌, 

graph.txt를 올바르게 3-coloring을 하면, 문제가 풀이 되겠다 라고 생각해서 graph.txt를 3-coloring(DSATUR 휴리스틱)해서 페이로드를 만들면 된다.

import json, random, heapq

GRAPH_PATH = "graph.txt"
OUT_PATH = "payload.json"
RESTARTS = 30

def read_graph(path):
    edges, max_node = [], -1
    with open(path, "r", encoding="utf-8") as f:
        for line in f:
            if not line.strip(): continue
            u, v = map(int, line.split())
            if u == v: raise ValueError(f"self-loop at {u}")
            edges.append((u, v))
            max_node = max(max_node, u, v)
    n = max_node + 1
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return n, edges, adj

def dsatur_3color(n, adj, seed=0):
    rng = random.Random(seed)
    color, deg = [-1]*n, [len(adj[i]) for i in range(n)]
    satmask, satcnt, ver = [0]*n, [0]*n, [0]*n
    heap = []

    def push(v):
        ver[v] += 1
        heapq.heappush(heap, (-satcnt[v], -deg[v], rng.random(), v, ver[v]))

    for v in range(n): push(v)
    uncolored = n

    while uncolored:
        while True:
            if not heap: return None
            _, _, _, v, vv = heapq.heappop(heap)
            if vv == ver[v] and color[v] == -1: break
        used = 0
        for nb in adj[v]:
            if color[nb] != -1: used |= (1 << color[nb])
        chosen = next((c for c in (0,1,2) if not (used & (1<<c))), -1)
        if chosen == -1: return None
        color[v], uncolored = chosen, uncolored-1
        bit = 1 << chosen
        for nb in adj[v]:
            if color[nb] == -1:
                new = satmask[nb] | bit
                if new != satmask[nb]:
                    satmask[nb] = new
                    satcnt[nb] = ((new&1)!=0)+((new&2)!=0)+((new&4)!=0)
                    push(nb)
    return color

def verify(edges, coloring):
    for u, v in edges:
        if coloring[u] == coloring[v]:
            return False, (u, v, coloring[u])
    return True, None

def main():
    n, edges, adj = read_graph(GRAPH_PATH)
    print(f"[+] loaded graph: n={n}, m={len(edges)}")
    sol = None
    for r in range(RESTARTS):
        seed = 1337 + r
        sol = dsatur_3color(n, adj, seed)
        if not sol:
            print(f"[-] restart {r+1}/{RESTARTS}: coloring failed")
            continue
        ok, info = verify(edges, sol)
        if not ok:
            print(f"[-] restart {r+1}/{RESTARTS}: verification failed at {info}")
            sol = None
            continue
        print(f"[+] success with seed={seed}")
        break
    if not sol:
        raise SystemExit("[-] Could not 3-color the graph.")
    payload = {"option": "guess", "coloring": sol}
    with open(OUT_PATH, "w", encoding="utf-8") as f:
        json.dump(payload, f)
    print(f"[+] wrote {OUT_PATH}")

if __name__ == "__main__":
    main()

 

python3 solve.py를 하면 자동으로 payload.json을 만들어주는데, 해당 내용을 복사해서 서버에 제출하면 FLAG가 출력된다.

 

따라서 RUSEC{t0uhou_fum0_b4urs4k_orz0city_fn1x9fk3mdj1} 가 최종 정답이 된다.