Home cakectf 2023
Post
Cancel

cakectf 2023

Posted Sep 30, 2023 Updated Mar 22, 2024
By
10 min read

cakectf 2023

BunkyoWesternsに入れてもらったのでチームでやってました。

色々名言が生まれたので楽しかったです。

後買ってきたケーキをみんなで食べましたまる。

kanon on X: “cakectf終わったのでケーキ食べます https://t.co/Kj9xOJZACy” / X (twitter.com)

simple signature 88 solve

chall

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

import os
import sys
from hashlib import sha512
from Crypto.Util.number import getRandomRange, getStrongPrime, inverse, GCD
import signal


flag = os.environ.get("FLAG", "neko{cat_does_not_eat_cake}")

p = getStrongPrime(512)
g = 2
p = 11551622313922707550008678743003601832188036792175262302397935776595208393670456612224185992217183071863853189220628487330346803009314560368938395241129573

def keygen():
    while True:
        x = getRandomRange(2, p-1)
        y = getRandomRange(2, p-1)
        w = getRandomRange(2, p-1)
        v = w * y % (p-1)
        if GCD(v, p-1) != 1:
            continue
        u = (w * x - 1) * inverse(v, p-1) % (p-1)
        return (x, y, u), (w, v)


def sign(m, key):
    x, y, u = key
    r = getRandomRange(2, p-1)

    return pow(g, x*m + r*y, p), pow(g, u*m + r, p)


def verify(m, sig, key):
    w, v = key
    s, t = sig

    return pow(g, m, p) == pow(s, w, p) * pow(t, -v, p) % p


def h(m):
    return int(sha512(m.encode()).hexdigest(), 16)


if __name__ == '__main__':
    magic_word = "cake_does_not_eat_cat"
    skey, vkey = keygen()

    print(f"p = {p}")
    print(f"g = {g}")
    print(f"vkey = {vkey}")

    signal.alarm(1000)

    while True:
        choice = input("[S]ign, [V]erify: ").strip()
        if choice == "S":
            message = input("message: ").strip()
            assert message != magic_word

            sig = sign(h(message), skey)
            print(f"(s, t) = {sig}")

        elif choice == "V":
            message = input("message: ").strip()
            s = int(input("s: ").strip())
            t = int(input("t: ").strip())

            assert 2 <= s < p
            assert 2 <= t < p

            if not verify(h(message), (s, t), vkey):
                print("invalid signature")
                continue

            print("verified")
            if message == magic_word:
                print(f"flag = {flag}")
                sys.exit(0)

        else:
            break

solve

基本的に、公開鍵と秘密鍵は何か数学的な関連性が必要であるから解けないわけで、今回は$x,u$が公開鍵にしか使われていないため、なんでもおｋとなる

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

from pwn import *
from Crypto.Util.number import getRandomRange, getStrongPrime, inverse, GCD
from hashlib import sha512

io = remote("crypto.2023.cakectf.com" ,10444)
# io = process(["python3","server.py"])
p = int(io.recvline().decode().split("= ")[1])
g = int(io.recvline().decode().split("= ")[1])
w,v = eval(io.recvline().decode().split("= ")[1])
y = (v * pow(w,-1,p-1))%(p-1)
x = getRandomRange(2, p-1)
magic_word = "cake_does_not_eat_cat"
u = ((w * x - 1) * inverse(v, p-1)) % (p-1)



def h(m):
    return int(sha512(m.encode()).hexdigest(), 16)

def sign(m, key):
    x, y, u = key
    r = getRandomRange(2, p-1)

    return pow(g, x*m + r*y, p), pow(g, u*m + r, p)
def verify(m, sig, key):
    w, v = key
    s, t = sig
    print(pow(g, m, p) , pow(s, w, p) * pow(t, -v, p) % p)
    return pow(g, m, p) == pow(s, w, p) * pow(t, -v, p) % p

# sig = sign(h("message"),  (x, y, u), )
# print( verify(h("message"), sig, (w, v)))
# exit()

s,t = sign(h(magic_word), (x, y, u))
io.sendlineafter(b": ",b"V")
io.sendlineafter(b": ",b"cake_does_not_eat_cat")
io.sendlineafter(b": ",str(s).encode())
io.sendlineafter(b": ",str(t).encode())
io.interactive()
# io.sendlineafter(b": ",str(t).encode())
# CakeCTF{does_yoshiking_eat_cake_or_cat?}

janken vs yoshiking 2 43 solve

chall

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
66
67
68
69
70
71
72
73

import random
import signal
import os

HANDNAMES = {
    1: "Rock",
    2: "Scissors",
    3: "Paper"
}

def commit(M, m):
    while True:
        r = random.randint(2, 2**256)
        if r % 3 + 1 == m:
            break
    return M**r, r


signal.alarm(1000)

flag = os.environ.get("FLAG", "neko{old_yoshiking_never_die,simply_fade_away}")
p = 1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111
M = random_matrix(GF(p), 5)
print("[yoshiking]: Hello! Let's play Janken(RPS)")
print("[yoshiking]: Here is p: {}, and M: {}".format(p, M.list()))

round = 0
wins = 0
while True:
    round += 1
    print("[system]: ROUND {}".format(round))

    yoshiking_hand = random.randint(1, 3)
    C, r = commit(M, yoshiking_hand)
    print("[yoshiking]: my commitment is={}".format(C.list()))

    hand = input("[system]: your hand(1-3): ")
    print("")
    try:
        hand = int(hand)
        if not (1 <= hand <= 3):
            raise ValueError()
    except ValueError:
        print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(")
        exit()

    print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand]))
    print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand]))
    result = (yoshiking_hand - hand + 3) % 3
    if result == 0:
        print("[yoshiking]: Draw, draw, draw!!!")
        print("[yoshiking]: I'm only respect to win!")
        print("[system]: you can check that yoshiking doesn't cheat")
        print("[system]: here's the secret value: {}".format(r))
        exit()
    elif result == 1:
        print("[yoshiking]: Yo! You win!!! Ho!")
        wins += 1
        print("[system]: wins: {}".format(wins))

        if wins >= 100:
            break
    elif result == 2:
        print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!")
        print("[yoshiking]: You, good loser!")
        print("[system]: you can check that yoshiking doesn't cheat")
        print("[system]: here's the secret value: {}".format(r))
        exit()

print("[yoshiking]: Wow! You are the king of roshambo!")
print("[yoshiking]: suge- flag ageru")
print(flag)

solve

matrixでのDDH仮定みたいなものを判定しろってことみたいです。ただ今回は弱めで$M^t = Y$での$t$が3で割ったあまりがいくつになるかですね。

pがb-smoothなので固有値計算してdlpに持ち込もうとしたけど、固有値がなくどうしたものかと思っていたら、前に自作したもので絶対値に落としてdlpができることを思い出し(一部失敗するかもしれないが)やってみたら解けた。

solve

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

from pwn import *
from tqdm import tqdm
p = 1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111

# io = process(["sage","server.sage"])
io = remote("crypto.2023.cakectf.com" ,"10555")
io.recvline()
M = eval(io.recvline().decode().split(": ")[-1])
M = matrix(GF(p),[[M[i+k*5] for i in range(5)] for k in range(5)])

Mdet = GF(p)(M.det())

for i in tqdm(range(100)):
    io.recvuntil(b"[system]: R")
    io.recvline()
    yoshi = eval(io.recvline().decode().split("=")[1])
    yoshi = matrix(GF(p),[[yoshi[i+k*5] for i in range(5)] for k in range(5)])
    
    yoshi_det = yoshi.det()

    nad = discrete_log(GF(p)(yoshi_det), Mdet)    

    if int((nad)%3)+1==1:
        io.sendlineafter(b": ",str(int(3)).encode())
    if int((nad)%3)+1==2:
        io.sendlineafter(b": ",str(int(1)).encode())
    if int((nad)%3)+1==3:
        io.sendlineafter(b": ",str(int(2)).encode())
    
io.interactive()    
        
# CakeCTF{though_yoshiking_may_die_janken_will_never_perish}

ding-dong-ting-ping 17 solve

chall

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

import os
from base64 import b64decode, b64encode
from hashlib import md5
from datetime import datetime
from Crypto.Cipher import AES

FLAG = os.environ.get("FLAG", "neko{cat_does_not_eat_cake}")
PREFIX = os.environ.get("PREFIX", "cakecakecakecake1").encode()

KEY = os.urandom(16)
IV = os.urandom(16)

aes = AES.new(KEY, AES.MODE_ECB)

xor = lambda a, b: bytes([x^y for x, y in zip(a, b)])

def pad(data: bytes):
    l = 16 - len(data) % 16
    return data + bytes([l]*l)

def unpad(data: bytes):
    return data[:-data[-1]]

def encrypt(plain: bytes):
    plain = pad(plain)
    blocks = [plain[i:i+16] for i in range(0, len(plain), 16)]
    ciphers = [IV]
    for block in blocks:
        block = xor(block, md5(ciphers[-1]).digest())
        ciphers.append(aes.encrypt(block))
    return b"".join(ciphers)

def decrypt(cipher: bytes):
    blocks = [cipher[i:i+16] for i in range(0, len(cipher), 16)]
    h = md5(blocks[0]).digest() # IV
    plains = []
    for block in blocks[1:]:
        plains.append(xor(aes.decrypt(block), h))
        h = md5(block).digest()
    return unpad(b"".join(plains))    

def register():
    username = b64decode(input("username(base64): ").strip())
    if b"root" in username:
        print("Cannot register as root user!")
    else:
        cookie = b"|".join([PREFIX, b"user="+username, str(datetime.now()).encode()])
        cookie = encrypt(cookie)
        cookie = b64encode(cookie)
        print("your cookie =>", cookie.decode())
    return

def login():
    cookie = input("cookie: ").strip()
    cookie = decrypt(b64decode(cookie))
    data = cookie.split(b"|")
    if (data[0] == PREFIX) and data[1].startswith(b"user="):
        username = data[1].split(b"=")[1]
        time = data[2]
    else:
        print("Authentication unsuccessful...")
        return
    print(f"Hi, {username.decode()}! [registered at {time.decode()}]")
    if username != b"root":
        print("You're not the root user...")
    else:
        print("Ding-Dong, Ding-Dong, Welcome, root. The ultimate authority has logged in.")
        print("This is for you => ", FLAG)
    return

while True:
    print("===== MENU =====")
    choice = int(input("[1]register [2]login: ").strip())
    if choice == 1:
        register()
    elif choice == 2:
        login()
    else:
        print("Invalid choice")
    print()

solve

AES-CBCのxor演算にmd5を用いてるもので、エラーを吐かない限りいくらでもoracleは使える。

さらに、timeの部分はcheckされてないことからうまく復元されればなんでも表示してくれる。けど、使わなかった…orz

方針として任意の暗号文を暗号化してくれるoracleを構成し、そこから暗号文を組みたてるという作業をおこなえばおｋ

問題としては、prefixの長さによってメンドサが変わるが今回は運よく、17文字？だったので1文字をブルートフォースして求めればいいことになる。

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

import os
from base64 import b64decode, b64encode
from hashlib import md5
from datetime import datetime
from Crypto.Cipher import AES
from tqdm import tqdm
from pwn import *
from itertools import product
Print = str
context.log_level = "debug"


def encrypt(io,m):
    io.sendlineafter(b": ",b"1" )
    io.sendlineafter(b": ",b64encode(m))
    return b64decode(io.recvline(None).split(b"=> ")[1])

def decrypt(io,m):
    io.sendlineafter(b": ",b"2" )
    io.sendlineafter(b": ",b64encode(m))
    return io.recvline(None).decode()

def ecb_oracle(io,m):
    user = b"A"*9 + b"A"*16
    ret = encrypt(io,user)
    b = md5(ret[3*16:4*16]).digest()
    ret = encrypt(io,user + xor(b,m))
    return ret[4*16:5*16]
    


io = remote("crypto.2023.cakectf.com" ,"11111")
# io = process(["python3","server.py"])

enc_PREFIX = encrypt(io,b"1")[:2*16]
ret = encrypt(io,b"AAAAAAAAA")[2*16:3*16]
for i in range(256):
    if ret == ecb_oracle(io,xor(bytes([i]) + b"|user=AAAAAAAAA", md5(enc_PREFIX[-16:]).digest())):
        print(i)
        break
else:
    print("NOT found")
    exit()

pad = b"\x01"*16
body1 = bytes([i])+b"|user=root|1234"
body1 = ecb_oracle(io,xor(body1, md5(enc_PREFIX[-16:]).digest()))
body2 = ecb_oracle(io,xor(pad, md5(body1).digest()))


aim = enc_PREFIX + body1+ body2
print(decrypt(io,aim))
io.interactive()
# CakeCTF{dongdingdongding-dingdong-dongdingdong-ding}
writeup
writeup
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents