Buckeye CTF

Hashbrown

...
def aes(block: bytes, key: bytes) -> bytes:
    assert len(block) == len(key) == 16
    return AES.new(key, AES.MODE_ECB).encrypt(block)


def pad(data):
    padding_length = 16 - len(data) % 16
    return data + b"_" * padding_length


def hash(data: bytes):
    data = pad(data)
    state = bytes.fromhex("f7c51cbd3ca7fe29277ff750e762eb19")

    for i in range(0, len(data), 16):
        block = data[i : i + 16]
        state = aes(block, state)

    return state


def sign(message, secret):
    return hash(secret + message)

...

From the code, we can see that it uses the last state to encrypt the next block. To get the flag, we must send a message containing $french fry$ and its signature. Therefore, I use a length extension attack to achieve this.

def aes(block: bytes, key: bytes) -> bytes:
    assert len(block) == len(key) == 16
    return AES.new(key, AES.MODE_ECB).encrypt(block)


def pad(data):
    padding_length = 16 - len(data) % 16
    return data + b"_" * padding_length


def hash(data: bytes, state):
    # data = pad(data)
    # state = bytes.fromhex("f7c51cbd3ca7fe29277ff750e762eb19")
    # state = bytes.fromhex(state)
    for i in range(0, len(data), 16):
        block = data[i : i + 16]
        state = aes(block, state)

    return state


def sign(message, secret):
    return hash(secret + message)

# context.log_level = "debug"
# io = process(["python", "hashbrown.py"])
io = remote("challs.pwnoh.io", 13419)

io.recvuntil(b"Recipe for hashbrowns:\n")
msg = io.recvline().decode()

io.recvuntil(b"Signature:\n")
hsh = bytes.fromhex(io.recvline().decode())

msg = pad(b'1'*16 + my_message)
len_m = len(msg)
new_msg = pad(msg + b"french fry")[len_m:]
new_hsh = hash(new_msg, hsh)

send_m = msg[16:] + b"french fry"
io.sendlineafter(b"Give me recipe for french fry? (as hex)", send_m.hex())
io.sendlineafter(b"Give me your signiature?", new_hsh.hex())
io.interactive()

zkwarmup

from math import gcd
import random
import time
# from flag import flag

flag = b"bctf{?????????????????}"
class Verifier:
    def __init__(self, y, n):
        self.y = y
        self.n = n
        self.previous_ss = set()
        self.previous_zs = set()

    def flip_coin(self) -> int:
        return random.randrange(2)

    def verify(self, s, z, b) -> bool:
        if s in self.previous_ss :
            print("Bad: repeated s")
            return False
        if z in self.previous_zs:
            print("Bad: repeated r")
            return False
        self.previous_ss.add(s)
        self.previous_zs.add(z)

        n = self.n
        y = self.y
        if s == 0:
            print("Bad: s = 0")
            return False
        if gcd(s, n) != 1:
            print("Bad: gcd(s, n) != 1")
            return False
        return pow(z, 2, n) == (s * pow(y, 1 - b)) % n


def main():
    print("Welcome to zkwarmup!")

    # p = getPrime(1024)
    # q = getPrime(1024)
    # n = p * q
    n = 19261756194530262169516227535327268535825703622469356233861243450409596218324982327819027354327762272541787979307084854543427241827543331732057807638293377995167826046761991463655794445629511818504788588146049602678202660790161211079215140614149179394809442098536009911202757117559092796991732111808588753074002377241720729762405118846289128192452140379045358673985940236403266552967867241351260376075804662700969038717732248036975281084947926661161892037413944872628410488986135370175176475239647256670545733839891394321932103696968961386864456665963903759123610214930997530883831800104920546270573046968308379346633
    print(f"n = {n}")

    random.seed(int(time.time()))
    x = random.randrange(1, n)
    y = pow(x, 2, n)
    print(f"y = {y}")

    print("Can you prove that you know sqrt(y) without revealing it to the verifier?")
    verifier = Verifier(y, n)
    n_rounds = 128
    for i in range(n_rounds):
        s = int(input("Provide s: ")) % n
        b = verifier.flip_coin()
        print(f"b = {b}")

        z = int(input("Provide z: ")) % n
        if verifier.verify(s, z, b):
            print(f"Verification passed! {n_rounds - i - 1} rounds remaining")
        else:
            print("Verification failed!")
            return

    print("You've convinced the verifier you know sqrt(y)!")
    print(flag)


if __name__ == "__main__":
    main()

• The random seed uses $int(time.time())$ means when we connect to server we can also get the seed $\to$ $x$
• The verify server give the $b$ so we can choose $s = x^{2*i}$ and $z = x^{i}$ or $x^{i} * x$ depend on the $b$

io = remote('challs.pwnoh.io', 13421)
io.recvuntil(b"y = ")
y = eval(io.recvline().decode())

for i in range(-10, 10):
    random.seed(int(time.time())+i)
    n = 19261756194530262169516227535327268535825703622469356233861243450409596218324982327819027354327762272541787979307084854543427241827543331732057807638293377995167826046761991463655794445629511818504788588146049602678202660790161211079215140614149179394809442098536009911202757117559092796991732111808588753074002377241720729762405118846289128192452140379045358673985940236403266552967867241351260376075804662700969038717732248036975281084947926661161892037413944872628410488986135370175176475239647256670545733839891394321932103696968961386864456665963903759123610214930997530883831800104920546270573046968308379346633
    x = random.randrange(1, n)
    if y == pow(x, 2, n):
        break
    
assert y == pow(x, 2, n)

previous_ss = []
previous_zs = []

for i in range(2, 300):
    a = pow(x, 2*i, n)
    b = (pow(x, i, n))%n
    if a in previous_ss or b in previous_zs:
        continue
    previous_ss.append(a)
    previous_zs.append(b)
previous_s_send = set()
previous_z_send = set()

for s, z in zip(previous_ss[2:], previous_zs[2:]):
    if s in previous_s_send or z in previous_z_send:
        continue
    io.sendlineafter(b"Provide s: ", str(s).encode())
    io.recvuntil(b"b = ")
    b = eval(io.recvline().decode())
    if b == 1:
        z_send = z%n
        assert pow(z_send, 2, n) == (s * pow(y, 1 - b)) % n
    else:
        z_send = (z*x)%n
        assert pow(z_send, 2, n) == (s * pow(y, 1 - b)) % n
    previous_s_send.add(s)
    previous_z_send.add(z_send)
    io.sendlineafter(b"Provide z: ", str(z_send).encode())

io.interactive()