ParadigmCTF2023-Oven

2023-11-02
Tags: wp.
Categories: write up.

Oven

某日，blockchain大哥发来一道题，当时有要事在身没什么时间来做，只好在这之后来看看题复现一下

Analysis

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
#!/usr/bin/env python3
from Crypto.Util.number import *
import random
import os
import hashlib

FLAG = os.getenv("FLAG", "PCTF{flag}").encode("utf8")
FLAG = bytes_to_long(FLAG[5:-1])
assert FLAG.bit_length() < 384

BITS = 1024


def xor(a, b):
    return bytes([i ^ j for i, j in zip(a, b)])


# This doesn't really matter right???
def custom_hash(n):
    state = b"\x00" * 16
    for i in range(len(n) // 16):
        state = xor(state, n[i : i + 16])

    for _ in range(5):
        state = hashlib.md5(state).digest()
        state = hashlib.sha1(state).digest()
        state = hashlib.sha256(state).digest()
        state = hashlib.sha512(state).digest() + hashlib.sha256(state).digest()

    value = bytes_to_long(state)

    return value


def fiat_shamir():
    p = getPrime(BITS)
    g = 2
    y = pow(g, FLAG, p)

    v = random.randint(2, 2**512)

    t = pow(g, v, p)
    c = custom_hash(long_to_bytes(g) + long_to_bytes(y) + long_to_bytes(t))
    r = (v - c * FLAG) % (p - 1)

    assert t == (pow(g, r, p) * pow(y, c, p)) % p

    return (t, r), (p, g, y)


while True:
    resp = input("[1] Get a random signature\n[2] Exit\nChoice: ")
    if "1" in resp:
        print()
        (t, r), (p, g, y) = fiat_shamir()
        print(f"t = {t}\nr = {r}")
        print()
        print(f"p = {p}\ng = {g}\ny = {y}")
        print()
    elif "2" in resp:
        print("Bye!")
        exit()

task是fiat-shamir heuristic的python实现，具体方案如下：

image-20231102150110279

图片截自维基百科

在def custom_hash(n)上有一句注释“This doesn't really matter right???”，本以为是出题人的此地无银，结果真是 “doesn't really matter” hhh。

注意到在Peggy生成这一步，，有着线性关系，且都没有超过。可以构造一个lattice，用多组已知的来恢复

对lattice使用LLL可得flag

exp

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
# https://github.com/chainlight-io/publications/blob/main/ctf-writeups/paradigm2023/oven
from pwn import *
from Crypto.Util.number import *
from tqdm import trange

conn = remote("oven.challenges.paradigm.xyz", "1337")

def get_arg(v):
    conn.recvuntil(f'{v} = '.encode())
    return int(conn.recvline().strip().decode())

def parse():
    t = get_arg('t')
    r = get_arg('r')
    p = get_arg('p')
    g = get_arg('g')
    y = get_arg('y')

    return t, r, p, g, y

def custom_hash(n):
    state = b"\x00" * 16
    for i in range(len(n) // 16):
        state = xor(state, n[i : i + 16])

    for _ in range(5):
        state = hashlib.md5(state).digest()
        state = hashlib.sha1(state).digest()
        state = hashlib.sha256(state).digest()
        state = hashlib.sha512(state).digest() + hashlib.sha256(state).digest()

    value = bytes_to_long(state)

    return value

arr = []

for _ in trange(20):
    conn.sendlineafter(b'Choice: ', b'1')
    t, r, p, g, y = parse()

    c = custom_hash(long_to_bytes(g) + long_to_bytes(y) + long_to_bytes(t))

    arr.append((c, r, p))


mat = []

mat.append([ -it[0] for it in arr ] + [1, 0])

for i in range(20):
    row = [0] * i + [ arr[i][2] - 1 ] + [0] * (20 - i) + [0]
    mat.append(row)

mat.append([ -it[1] for it in arr ] + [0, 2^512])

mat = Matrix(mat)

res = mat.LLL()

for row in res:
    t = int(row[-2])
    if t < 0:
        t = -t
    print(long_to_bytes(t))

网上找的大哥的exp在构造lattice时用的是和，这里的正负对恢复flag没有影响，无非就是多个由负转正的过程

Flag：pctf{F1at_shAm1R_HNP_g0_Cr4ZyyYy_m0rE_1iK3_f4T_Sh4mIr}