[BtSCTF 2023] Writeup

유독 crypto에서 솔버가 적었던 ctf였다.

1. Break PSI (26 solves)

chall

from Crypto.Hash import SHA256
from Crypto.Util.number import long_to_bytes
import random

FLAG = open("flag", "r")

A = []
B = []
Ahash = []
Bhash = []
Ainv = {}
Binv = {}

limit = 32
setSize = 17
reps = 8


def intersection(A, B):
    return [v for v in A if v in B]


def F(x):
    h = SHA256.new(data=long_to_bytes(x))
    return h.digest().hex()


def hash_list(l):
    h = SHA256.new(data=bytes(str(l), "utf-8"))
    return h.digest()


def is_valid(Asi, Bsi):
    if Asi == [] or Bsi == []:
        return 0
    if hash_list(Asi) != hash_list(Bsi):
        return 0

    cnt = {}
    for a in Asi:
        if Ainv[a] in cnt:
            cnt[Ainv[a]] += 1
        else:
            cnt[Ainv[a]] = 1
    for v in cnt.values():
        if v != reps + 1:
            return 0

    cnt = {}
    for b in Bsi:
        if Binv[b] in cnt:
            cnt[Binv[b]] += 1
        else:
            cnt[Binv[b]] = 1
    for v in cnt.values():
        if v != reps + 1:
            return 0

    return 1


for i in range(420):
    A = random.sample(range(limit), setSize)
    B = random.sample(range(limit), setSize)
    Ahash = []
    Bhash = []
    Ainv = {}
    Binv = {}

    for i in range(setSize):
        for j in range(1, reps + 1):
            A.append(A[i] + limit * j)
            B.append(B[i] + limit * j)

    for a in A:
        h = F(a)
        Ahash.append(h)
        Ainv[h] = a % limit

    for b in B:
        h = F(b)
        Bhash.append(h)
        Binv[h] = b % limit

    print("Alice:", Ahash)
    print("Bob:", Bhash)

    Asi = input("Send PSI to Alice: ").split()
    Bsi = input("Send PSI to Bob: ").split()

    if is_valid(Asi, Bsi):
        if intersection(Ahash, Bhash) == Asi and intersection(Ahash, Bhash) == Bsi:
            print("Honesty is not a way to solve this challenge")
            exit()
    else:
        print("Cheater!")
        exit()

print("You got me! Here is your flag:", FLAG.read())

-0~32 범위의 random int 17개씩 선택 (초기값)

-선택한 random int에 32*i (1≤i≤8)을 더한 수를 추가

-각각의 수를 hash한 암호의 value를 초기값으로 설정 (Ainv, Binv)

-Alice와 Bob에게 PSI 전송 → is_valid 검증(hash암호문에 해당하는 초기값이 9개씩 있어야함) → 동시에 교집합인지 확인 → 420번

exploit strategy

Alice와 Bob이 동시에 갖는 숫자 s선택

→ 초기값이 s인 숫자의 암호문 9개 각각 선택

→ send

exploit code

from Crypto.Util.number import *
from Crypto.Hash import SHA256
from pwn import *

def F(x):
    h = SHA256.new(data=long_to_bytes(x))
    return h.digest().hex()

def lnum(li):
    res = []
    for i in range(len(li)):
        j = 0
        while(1):
            if li[i] == F(j):
                res.append(j)
                break
            j+=1
    return res

p = remote("crypto-breakpsi.ch.bts.wh.edu.pl", 1337)

for _ in range(420):
    print(f"now : {_}")
    p.recvuntil(b"Alice: ")
    Alice = eval(p.recvline().strip())
    p.recvuntil(b"Bob: ")
    Bob = eval(p.recvline().strip())

    bobnum = lnum(Bob)
    alicenum = lnum(Alice)

    x = 0
    while(1):
        if alicenum[x] in bobnum:
            s = alicenum[x]
            break
        x += 1

    sendalice = []
    for i in alicenum:
        if (i-s)%32==0:
            sendalice.append(Alice[alicenum.index(i)])

    sendbob = []
    for i in bobnum:
        if (i-s)%32==0:
            sendbob.append(Bob[bobnum.index(i)])

    sa = ""
    for i in sendalice:
        sa += i + " "
    sb = ""
    for i in sendbob:
        sb += i + " "


    p.recvuntil(b"Alice: ")
    p.sendline(f"{sa}")
    p.recvuntil(b"Bob: ")
    p.sendline(f"{sb}")

p.interactive()

BtSCTF{4lWAys_sHuff1e_PSI_seTs}

2. Textbook (5 solves)

chall

from Crypto.Util.number import getPrime, GCD, getRandomRange
from collections import namedtuple


with open('flag', 'r') as f:
    flag = f.read()

public = namedtuple('public', 'n g')
secret = namedtuple('secret', 'n phi mu')
sig = namedtuple('sig', 's1 s2')

b = 1024
p = getPrime(b)
q = getPrime(b)

assert p != q

n = p * q
phi = (p - 1) * (q - 1)
g = n + 1
mu = pow(phi, -1, n)

pk = public(n, g)
sk = secret(n, phi, mu)

# mask for additional security!!!
mask = getRandomRange(2 ** (n.bit_length() * 2 - 2), (2 ** (n.bit_length() * 2 - 1)))

def h(s: bytes) -> int:
    return int.from_bytes(s, 'big', signed=True)

def int_to_bytes(n: int) -> bytes:
    return n.to_bytes(n.bit_length() // 8 + 1, 'big', signed=True)

def encrypt(m: bytes, pk: public) -> bytes:
    n, g = pk
    r = getRandomRange(1, n)
    assert GCD(r, n) == 1
    mh = h(m)
    c = (pow(g, mh, n ** 2) * pow(r, n, n ** 2)) % (n ** 2)

    return pow(c, mask, n ** 2)

def sign(m: bytes, sk: secret) -> sig:
    n, phi, mi = sk
    mh = (h(m) * mask) % (n ** 2)
    d = pow(mh, phi, n ** 2)
    e = (d - 1) // n

    s1 = (e * mi) % n
    n_inv = pow(n, -1, phi)
    s2 = pow(mh * pow(g, -s1, n), n_inv, n)
    
    return sig(s1, s2)

def verify(m: bytes, sig: sig, pk: public) -> bool:
    s1, s2 = sig
    n, g = pk
    mh = (h(m) * mask) % (n ** 2)
    
    m_prim = pow(g, s1, n ** 2) * pow(s2, n, n ** 2) % (n ** 2)
    return m_prim == mh

if __name__=="__main__":
    flag_enc = encrypt(flag.encode(), pk)
    flag_enc = int_to_bytes(flag_enc)
    print("Hello to my signing service ^^\n")
    print("My public key:")
    print("n =", pk.n)
    print("g =", pk.g)
    print("\nHere, have flag. It's encrypted and masked anyways, so who cares.\n")
    print("flag =", (flag_enc.hex()), "\n")


    while True:
        print("What do you want to do?")
        print("[1] Sign something", "[2] Verify signature", "[3] Exit", sep="\n")

        function = input(">")

        if function == "1":
            message = bytes.fromhex(input("Give me something to sign!\n(hex)>"))
            signature = sign(message, sk)
            print(f"s1 = {signature.s1}\ns2 = {signature.s2}")
        if function == "2":
            message = bytes.fromhex(input("Message to verify\n(hex)>"))
            print("Signature:")
            signature = sig(int(input("s1:\n(int)>")), int(input("s2:\n(int)>")))
            if verify(message, signature, pk):
                print("verified!")
            else:
                print("not verified!")
        if function == "3":
            exit()

Paillier cryptosystem를 모르는 상태에서 푸느라 문제 코드를 분석하는 데에 1시간이 넘게 걸렸다. (알았으면 달랐을까..?) 8분 차이로 퍼블을 놓쳐서 아쉽다..

key point : $g = n + 1$ → $g^x ≡ nx+1 \ (mod \ n)$

exploit strategy

function = 1 에서 0 send

→ phi = inverse(n-s1, n)

→ mask leak using vertify formula (m = 1이면 mh = mask)

→ flag

인텐인지는 잘 모르겠다..

exploit code

from Crypto.Util.number import *
from pwn import *

p = remote("crypto-textbook.ch.bts.wh.edu.pl", 1337)

for _ in range(3):
    p.recvline()

p.recvuntil(b"n = ")
n = int(p.recvline())
g = n + 1
p.recvuntil(b"flag = ")
enc_flag = int(p.recvline(), 16)

#0 send -> phi leak     phi = inverse(n-s1, n)
p.sendline(b"1")
p.recvuntil(b"(hex)>")
p.sendline(b"00")
p.recvuntil(b"s1 = ")
s1 = int(p.recvline())

mi = (-s1) % n
phi = inverse(mi, n)
n_inv = pow(n, -1, phi)

#mask leak
#1 send -> m = 1
p.sendline(b"1")
p.sendline(b"01")
p.recvuntil(b"s1 = ")
ss1 = int(p.recvline())
p.recvuntil(b"s2 = ")
ss2 = int(p.recvline())

mask = pow(g, ss1, n ** 2) * pow(ss2, n, n ** 2) % (n ** 2)

left = pow(enc_flag, phi, n**2)
k = (left - 1)//n
print(long_to_bytes(k*inverse(mask, n)*inverse(phi, n) % n).decode())

p.interactive()

BtSCTF{wh4t_d0_y0u_m34n_1ts_h0m0m0rph1c}

3. Textbook2 (2 solves)

chall

from Crypto.Util.number import getPrime, GCD, getRandomRange
from collections import namedtuple


with open('flag', 'r') as f:
    flag = f.read()

public = namedtuple('public', 'n g')
secret = namedtuple('secret', 'n phi mu')
sig = namedtuple('sig', 's1 s2')

b = 1024
p = getPrime(b)
q = getPrime(b)

assert p != q

n = p * q
phi = (p - 1) * (q - 1)
g = n + 1
mu = pow(phi, -1, n)

pk = public(n, g)
sk = secret(n, phi, mu)

# masks for additional security!!!
mask1 = getRandomRange(2 ** (n.bit_length() * 2 - 2), (2 ** (n.bit_length() * 2 - 1)))
mask2 = getRandomRange(2 ** (n.bit_length() * 2 - 2), (2 ** (n.bit_length() * 2 - 1)))

def h(s: bytes) -> int:
    return int.from_bytes(s, 'big', signed=True)

def int_to_bytes(n: int) -> bytes:
    return n.to_bytes(n.bit_length() // 8 + 1, 'big', signed=True)

def encrypt(m: bytes, pk: public) -> bytes:
    n, g = pk
    r = getRandomRange(1, n)
    assert GCD(r, n) == 1
    mh = h(m)
    c = (pow(g, mh, n ** 2) * pow(r, n, n ** 2)) % (n ** 2)

    return pow(c, mask1, n ** 2)

def sign(m: bytes, sk: secret) -> sig:
    n, phi, mu = sk
    mh = (h(m) * mask2) % (n ** 2)
    d = pow(mh, phi, n ** 2)
    e = (d - 1) // n

    s1 = (e * mu) % n
    n_inv = pow(n, -1, phi)
    s2 = pow(mh * pow(g, -s1, n), n_inv, n)
    
    return sig(s1, s2)

def verify(m: bytes, sig: sig, pk: public) -> bool:
    s1, s2 = sig
    n, g = pk
    mh = (h(m) * mask2) % (n ** 2)
    
    m_prim = pow(g, s1, n ** 2) * pow(s2, n, n ** 2) % (n ** 2)
    return m_prim == mh

if __name__=="__main__":
    flag_enc = encrypt(flag.encode(), pk)
    flag_enc = int_to_bytes(flag_enc)
    print("Hello to my signing service. You don't need any keys, all is handled by me ^^\n")
    #print("My public key:")
    #print("n =", pk.n)
    #print("g =", pk.g)
    print("\nHere, have flag. It's encrypted and masked anyways, so who cares.\n")
    print("flag =", (flag_enc.hex()), "\n")


    while True:
        print("What do you want to do?")
        print("[1] Sign something", "[2] Verify signature", "[3] Encrypt something", "[4] Exit", sep="\n")

        function = input(">")

        if function == "1":
            message = bytes.fromhex(input("Give me something to sign!\n(hex)>"))
            signature = sign(message, sk)
            print(f"s1 = {signature.s1}\ns2 = {signature.s2}")
        if function == "2":
            message = bytes.fromhex(input("Message to verify\n(hex)>"))
            print("Signature:")
            signature = sig(int(input("s1:\n(int)>")), int(input("s2:\n(int)>")))
            if verify(message, signature, pk):
                print("verified!")
            else:
                print("not verified!")
        if function == "3":
            message = bytes.fromhex(input("Message to encrypt\n(hex)>"))
            ciphertext = encrypt(message, pk)
            print("c =", int_to_bytes(ciphertext).hex())
        if function == "4":
            exit()

textbook과 달라진 점 :

-encrypt할 때의 mask, sign과 vertify할 때의 mask가 다르다. (mask1, mask2)

-n을 주지 않는다.

-원하는 평문을 encrypt할 수 있는 메뉴가 생겼다. ([3] Encrypt something)

exploit strategy

우선 n을 leak해야 한다. (여기에 가장 시간을 많이 썼다.)

idea : 메뉴1에 1, -1을 보내면 s1은 동일하고, n_inv가 홀수이니 s2의 부호만 반대일 것이다. (합이 n일 것이다.)

위의 방식대로 n leak

→ phi, mask2는 textbook과 동일하게 leak

→ 메뉴3에 1 send

→ mask1 leak

→ flag

exploit code

from Crypto.Util.number import *
from pwn import *

p = remote("crypto-textbook-2.ch.bts.wh.edu.pl", 1337)


p.recvuntil(b"flag = ")
enc_flag = int(p.recvline(), 16)

#n leak
#1 send
p.sendline(b"1")
p.sendline(b"01")
p.recvuntil(b"s1 = ")
s1 = int(p.recvline())
p.recvuntil(b"s2 = ")
s2 = int(p.recvline())

#-1 send
p.sendline(b"1")
p.sendline(b"ff")
p.recvuntil(b"s1 = ")
ss1 = int(p.recvline())
p.recvuntil(b"s2 = ")
ss2 = int(p.recvline())

n = s2 + ss2
g = n + 1

#0 send -> phi leak     phi = inverse(n-s1, n)
p.sendline(b"1")
p.recvuntil(b"(hex)>")
p.sendline(b"00")
p.recvuntil(b"s1 = ")
s1 = int(p.recvline())

mi = (-s1) % n
phi = inverse(mi, n)
n_inv = pow(n, -1, phi)

#mask2 leak
#1 send -> m = 1
p.sendline(b"1")
p.sendline(b"01")
p.recvuntil(b"s1 = ")
ss1 = int(p.recvline())
p.recvuntil(b"s2 = ")
ss2 = int(p.recvline())

mask2 = pow(g, ss1, n ** 2) * pow(ss2, n, n ** 2) % (n ** 2)

#mask1 leak
p.sendline(b"3")
p.sendline(b"01")
p.recvuntil(b"c = ")
enc = int(p.recvline(), 16)

c = pow(enc, phi, n**2)
mask1 = ((c-1)//n)*inverse(phi, n) % n

c_flag = pow(enc_flag, phi, n**2)
flag = ((c_flag-1)//n)*inverse(mask1, n)*inverse(phi, n) % n
print(long_to_bytes(flag).decode())

p.interactive()

BtSCTF{p4i11i3r_15_pr3tty_c001_4nd_fun_huh}

*2, 3번 문제는 cryptohack의 Roll your Own과 원리가 유사하다.

*Paillier cryptosystem를 더 공부하자.