InterKosenCTF 2020 Crypto 분야 Write-Ups (?)

참가팀들 중 2번째로 올솔브를 찍어서 해피엔딩으로 끝냈다. 나는 Crypto 문제를 맡았고 결과적으로 5문제를 풀었다.

Ciphertexts

from Crypto.Util.number import *
import gmpy2
from flag import flag
 
p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n1 = p * q
n2 = p * q * r
 
e1 = getPrime(20)
e2 = int(gmpy2.next_prime(e1))
 
m = bytes_to_long(flag)
c1 = pow(m, e1, n1)
c2 = pow(m, e2, n2)
 
print("n1 = {}".format(n1))
print("n2 = {}".format(n2))
print("e1 = {}".format(e1))
print("e2 = {}".format(e2))
print()
print("c1 = {}".format(c1))
print("c2 = {}".format(c2))
 
'''
n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223
n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749
e1 = 745699
e2 = 745709
c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818
c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546
'''

$n_1, n_2$를 알고 있으니 $r$을 얻을 수 있다. $m^{e_2} \pmod{r}$도 알고 있으니 여기서 $m \pmod{r}$을 알 수 있다.

또한, $m^{e_1} \pmod{n_1}$과 $m^{e_2} \pmod{n_1}$을 알고 있으니, $e_1d_1 + e_2d_2 = 1$인 $d_1, d_2$를 찾아서 $m \pmod{n_1}$도 구할 수 있다. 

이제 중국인의 나머지 정리로 두 정보를 합치면 flag를 얻는다. 수식 잘 가지고 노는 문제 :)

 

r = n2 // n1
d = inverse(e2, r - 1)
mr = pow(c2, d, r)
d1 = inverse(e1, e2)
d2 = (e1 * d1 - 1) // e2
mn1 = pow(c1, d1, n1) * inverse(pow(c2, d2, n1), n1) % n1
u, v = CRT(mn1, n1, mr, r)
print(long_to_bytes(u))

No Pressure

from Crypto.Cipher import ARC4
from hashlib import sha256
from base64 import b64encode
import zlib
import os
 
flag = open("./flag.txt", "rb").read()
 
nonce = os.urandom(32)
while True:
    m = input("message: ")
    arc4 = ARC4.new(sha256(nonce + m.encode()).digest())
    c = arc4.encrypt(zlib.compress(flag + m.encode()))
    print("encrypted! :", b64encode(c).decode())

사실 거의 비슷한 문제가 CryptoHack에 있어서 풀이를 쓰기가 조금 애매하긴 하다 ㅋㅋ

문제 이름에서도 나오듯이 compression이 적용되었다는 것을 활용하는 문제이다. 

대충 직관적으로 넣어준 메시지와 flag의 공통 prefix가 크다면 압축이 더 많이 되어 ciphertext의 길이가 작다는 것이다.

flag가 'KosenCTF{' 으로 시작된다는 것은 알고 있으니, 여기에 문자를 하나씩 추가해보며 작은 ciphertext를 찾는 것을 반복하면 된다.

HOST = "misc.kosenctf.com"
PORT = 10002
 
conn = pwnlib.tubes.remote.remote(HOST, PORT)
 
solution = "KosenCTF{"
chars = [chr(x) for x in range(32, 128)]
dumb = ';'
 
while True:
    p = (solution + dumb) * 5
    r = conn.send(str.encode(p + "\n"))
    res = conn.recvline()
    res = res[22:-1]
    res = base64.b64decode(res)
    res = len(res)
    ## print(res)
    for c in chars:
        ntry = (solution + c) * 5
        r = conn.send(str.encode(ntry + "\n"))
        r = conn.recvline()
        r = r[22:-1]
        r = base64.b64decode(r)
        r = len(r)
        ## print(r)
        if r < res:
            res = r
            solution += c
            print(solution)
            if c == "}":
                print(solution)
                exit()
            break

BitCrypto

from Crypto.Util.number import *
from secret import flag
 
def legendre_symbol(x, p):
    a = pow(x, (p-1) // 2, p)
    if a == 0:
        return 0
    elif a == 1:
        return 1
    else:
        return -1
 
def key_gen(bits):
    p = getPrime(bits)
    q = getPrime(bits)
    n = p * q
 
    while True:
        z = getRandomRange(2, n)
        a, b = legendre_symbol(z, p), legendre_symbol(z, q)
        if a == -1 and b == -1:
            break
 
    return (n, z), (p, q)
 
def enc(pubkey, m):
    n, z = pubkey
    bits = [int(b) for b in "{:b}".format(m)]
 
    c = []
    for b in bits:
        while True:
            x = getRandomRange(2, n)
            if GCD(x, n) == 1:
                break
        c.append( ((z**b) * (x**2)) % n )
    return c
 
def dec(privkey, c):
    p, q = privkey
    m = ""
    for b in c:
        if legendre_symbol(b, p) == 1 and legendre_symbol(b, q) == 1:
            m += "0"
        else:
            m += "1"
    return int(m, 2)
 
def main():
    pubkey, privkey = key_gen(256)
 
    keyword = "yoshiking, give me ur flag"
    m = input("your query: ")
    if any([c in keyword for c in m]):
        print("yoshiking: forbidden!")
        exit()
 
    if len(m) > 8:
        print("yoshiking: too long!")
        exit()
 
    c = enc(pubkey, bytes_to_long(m.encode()))
    print("token to order yoshiking: ", c)
 
    c = [int(x) for x in input("your token: ")[1:-1].split(",")]
    if len(c) != len(set(c)):
        print("yoshiking: invalid!")
        exit()
 
    if any([x < 0 for x in c]):
        print("yoshiking: wow good unintended-solution!")
        exit()
 
    m = long_to_bytes(dec(privkey, c))
    if m == keyword.encode():
        print("yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~")
        print(flag)
    else:
        print(m)
        print("yoshiking: ...?")
 
 
if __name__ == '__main__':
    main()
 

뭔가 길게 생겼는데 코드부터 대충 해석해보자.

• KeyGen: 소수 $p, q$를 고르고 $n = pq$라 한자. $z$는 $p, q$ 모두에 대해 이차비잉여이다.
• 이 과정에서 public key는 $n, z$이며, private key는 $p, q$이다.
• Encryption: 메시지를 이진법으로 쓰고 $0$을 위해서는 이차잉여, $1$을 위해서는 이차비잉여를 추가한다.
• Decryption: 르장드르 기호를 직접 계산하여 주어진 값에서 $0$, $1$을 복원한다.
• 목표: 플래그 내놓으라는 저 문장이 복호화 결과가 되도록하는 암호문을 만들라는 것이다.
• 단, 암호문의 각 정수는 모두 서로 달라야 하며, 음수면 안된다.
• 쿼리를 날릴 수도 있는데 문제를 날로 먹을 수는 없고 쿼리의 길이에도 제한이 있다.

이러면 문제가 풀렸다. 사실 encryption을 못하는 이유는 그냥 우리가 $n$도 모르고 $z$도 몰라서다.

그런데 애초에 $n, z$을 몰라도 $\pmod{n}$에 대한 이차잉여/비이차잉여를 만드는 것은 쉽다. 

• 이차잉여: 그냥 제곱수를 하나 보내주면 된다.
• 비이차잉여: 정수 하나를 잡고 비이차잉여라고 기도하자. 이 값에 제곱수를 곱하면 된다.
• 비이차잉여를 뽑을 확률은 든든하게 높으니까 별로 기도하지 않아도 된다.

HOST = "crypto.kosenctf.com"
PORT = 13003
 
conn = pwnlib.tubes.remote.remote(HOST, PORT)
conn.send("@\n")
print(conn.recvline())
print(bytes_to_long("yoshiking, give me ur flag".encode()))
 
z = 195139091440424100361889710829481093024970143303085039083610471
c = bin(z)[2:]
c = str(c)
 
q = 2
res = ""
for t in c:
    if t == '0':
        q += 1
        res += str(q*q) + ","
    if t == '1':
        q += 1
        res += str(2*q*q) + ","
 
res = res[:-1]
print(res)
conn.send(res + "\n")
 
print(conn.recvline())
print(conn.recvline())

PadRSA

import os
import signal
from binascii import unhexlify, hexlify
from Crypto.Util.number import *
from flag import flag
 
r = os.urandom(8)
nonce = 1
 
p = getPrime(256)
q = getPrime(256)
n = p * q
es = set()
 
def pad(x: bytes) -> bytes:
    global r, nonce
    y = long_to_bytes(r[0] | nonce) + x + r
 
    nonce += 1
    r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
    return y
 
def encrypt(m: bytes, e: int) -> bytes:
    m_ = bytes_to_long(pad(m))
    return long_to_bytes(pow(m_, e, n))
 
MENU = """
1. Encrypt the flag
2. Encrypt your message
3. EXIT
"""
 
signal.alarm(30)
print("n: {}".format(n))
 
while True:
    print(MENU)
    choice = input("> ")
    if choice not in ["1", "2"]:
        break
 
    e = int(input("e: "))
    if not(3 <= e <= 65537):
        print("[-] invalid e")
        break
 
    if e in es:
        print("[-] e already used")
        break
 
    if choice == "1":
        m = flag
    if choice == "2":
        m = unhexlify(input("m: "))
 
    c = encrypt(m, e)
    print("c: {}".format(hexlify(c).decode()))
 
    es.add(e)

뭔가 패딩이 있고 정신이 나갈 것 같다. 우선 주어진 코드부터 분석해보자.

• $e$를 고른 뒤, flag의 ciphertext를 얻거나 임의의 메시지에 대한 ciphertext를 얻을 수 있다.
• 하지만 한 번 사용한 $e$의 값은 다시 사용할 수가 없다.
• 랜덤한 패딩처럼 생긴 뭔가를 쓰는데 사실 nonce의 값을 대놓고 알려줬다.
• nonce 값을 안다는 것은 $r$을 구하기만 하면 그 뒤의 $r$ 값을 싹 다 구할 수 있다는 것이다.
• $r$이 8 바이트인데 8 비트라고 생각해서 브루트포스하면 되는 줄 알았다 ㅋㅋ

$r$을 구해보자. 사실 $r$이 64 비트라는 점은 꽤 치명적인데, $r^3 < n$을 강제하기 때문이다.

그러니까 사실 빈 메시지와 $e=3$을 보내고 암호화 하라고 부탁하면 얘가 알아서 $r$을 갖다 바친다.

이제 $r$을 알았으니 문제를 풀 수 있다. $e=4, 5, 6, 7$에 대해서 flag의 암호문을 달라고 하자.

우리는 각 암호화 과정에서 사용된 $r, nonce$의 값을 전부 알고 있다. 그러니 우리가 얻은 정보는 사실상 $$ ( (r[0]|nonce) \cdot 2^{l(x) + 64} + 2^{64} \cdot x + r)^e \equiv c \pmod{n}$$ 형태로 쓸 수 있다. 여기서 $l(x)$는 flag의 길이이며, $x$는 flag 자체이다. 이는 결국 $x$가 여러 차수 낮은 $\mathbb{Z}_n$ 위의 다항식의 공통근임을 의미한다.

그러니 저 다항식들의 GCD를 구하면 된다. $l(x)$의 값을 모르지만 이 정도는 brute-force가 가능하다.

Sage에서 $\mathbb{Z}_n$ 위 다항식의 GCD를 지원하지 않는 것 같은데, 그냥 직접 구현하면 된다.

예전에 쓴 RSA 논문리딩에서 언급했듯이, 유클리드 호제법 과정이 망한다면 그때 $n$의 약수를 하나 얻을 수 있고, 이 경우에는 문제가 바로 풀린다.

첫 부분은 Python으로, 두 번째 부분은 Sage로 작성하였다.

pwntools를 살면서 처음 써봐서 통신 부분 코드가 지나치게 더럽고, 그래서 여기서는 생략했다.

Part 1 : $r$ 값 복원하고 $e=4,5,6,7$에 대한 flag의 ciphertext 얻기

아래 코드에서 kthp는 그냥 이분탐색으로 $k$th root를 구하는 코드이다.

n = 13213917004013074941883923518155352500136040759518468945870343732851737037017858345555718553480688185605981252067134741952110065084206701357744511961587797
rg = 0x0ae26226b16dfc3ca101a1b750f38d0f131fff3c93f04a1222586f
r = kthp(rg, 3)
r = long_to_bytes(r)
r = r[1:]
nonce = 1
 
print("For c4")
nonce += 1
r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
 
print(r[0] | nonce)
print(bytes_to_long(r))
 
print("For c5")
nonce += 1
r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
 
print(r[0] | nonce)
print(bytes_to_long(r))
 
print("For c6")
nonce += 1
r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
 
print(r[0] | nonce)
print(bytes_to_long(r))
 
print("For c7")
nonce += 1
r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1))
 
print(r[0] | nonce)
print(bytes_to_long(r))
 
c4 = 0x8043b337fd500f49ff23589ac40d6208d1ba5e8b6af341da6c63d4dc4af8944930cd5812076686450967c0b36a52b66e25a632d9b1780ca0195be15f81c7efe7
c5 = 0x13d464f1f4d139c78e8bbf20eaf9b7693a931e65649db09f259ffc9a17674d72187fb10b10ad3db629c0dcb7048cf9b836972320b0018edae6c0604bf9911a59
c6 = 0x0a7c1297094b925b4dcb42b001c2cfa9b0524939b4bb13048fb8e3778238e28b93c59b010ee2e45c7d7d25da69824a729141caf8c613e6dae1a8c08e153e5ae9
c7 = 0x5ee21f49be33499cce3a157a1ad55d3df5bce4ad99e90f8f91929c2a7a1a8f56a99bf69789137276eaac3294fd4b91fc1ee857eeb3544cd0c4f95be49ab3abd7

Part 2: 다항식 GCD를 통해서 공통근 도출 (혹시 싶어서 $2^{64} \cdot x$를 변수로 잡았다)

def GCD(f, g, n):
    g = g % f
    if g == 0:
        return f
    t = g.lc()
    if gcd(t, n) != 1:
        print(t)
        exit()
    tt = inverse_mod(Integer(t), n)
    g = g * tt
    return GCD(g, f, n)
 
n = 13213917004013074941883923518155352500136040759518468945870343732851737037017858345555718553480688185605981252067134741952110065084206701357744511961587797
K = Zmod(n)
P.<x> = PolynomialRing(K, implementation='NTL')
t4 = 179
b4 = 12905559065630283676
t5 = 103
b5 = 7364374057551015739
t6 = 204
b6 = 14728748115102031474
t7 = 157
b7 = 11010752156494511329
 
c4 = 0x8043b337fd500f49ff23589ac40d6208d1ba5e8b6af341da6c63d4dc4af8944930cd5812076686450967c0b36a52b66e25a632d9b1780ca0195be15f81c7efe7
c5 = 0x13d464f1f4d139c78e8bbf20eaf9b7693a931e65649db09f259ffc9a17674d72187fb10b10ad3db629c0dcb7048cf9b836972320b0018edae6c0604bf9911a59
c6 = 0x0a7c1297094b925b4dcb42b001c2cfa9b0524939b4bb13048fb8e3778238e28b93c59b010ee2e45c7d7d25da69824a729141caf8c613e6dae1a8c08e153e5ae9
c7 = 0x5ee21f49be33499cce3a157a1ad55d3df5bce4ad99e90f8f91929c2a7a1a8f56a99bf69789137276eaac3294fd4b91fc1ee857eeb3544cd0c4f95be49ab3abd7
 
for i in range(2, 200):
    f4 = (b4 + x + 2^(8*i) * t4)^4 - c4
    f5 = (b5 + x + 2^(8*i) * t5)^5 - c5
    f6 = (b6 + x + 2^(8*i) * t6)^6 - c6
    f7 = (b7 + x + 2^(8*i) * t7)^7 - c7
    f5 = GCD(f4, f5, n)
    f6 = GCD(f5, f6, n)
    f7 = GCD(f6, f7, n)
    if f7.degree() >= 1:
        print(f7)
    
## x + 13213917004013074941883923518155157707200933836201561801562186284370121597148945566062799149031981069879277394219016188339927598569756720133104910406574165
  

Part 3: 마무리 및 flag 도출

res = n - 13213917004013074941883923518155157707200933836201561801562186284370121597148945566062799149031981069879277394219016188339927598569756720133104910406574165
tt = (res * inverse(2 ** 64, n)) % n
print(long_to_bytes(tt))

Ochazuke

from Crypto.Util.number import bytes_to_long
from binascii import unhexlify
from hashlib import sha1
import re
 
EC = EllipticCurve(
    GF(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff),
    [-3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b]
)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 # EC.order()
Zn = Zmod(n)
G = EC((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
        0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))
 
def sign(private_key, message):
    z = Zn(bytes_to_long(message))
    k = Zn(ZZ(sha1(message).hexdigest(), 16)) * private_key
    assert k != 0
    K = ZZ(k) * G
    r = Zn(K[0])
    assert r != 0
    s = (z + r * private_key) / k
    assert s != 0
    return (r, s)
 
def verify(public_key, message, signature):
    r, s = signature[0], signature[1]
    if r == 0 or s == 0:
        return False
    z = Zn(bytes_to_long(message))
    u1, u2 = z / s, r / s
    K = ZZ(u1) * G + ZZ(u2) * public_key
    if K == 0:
        return False
    return Zn(K[0]) == r
 
if __name__=="__main__":
    from secret import flag, d
    public_key = ZZ(d) * G
    print("public key:", public_key)
    
    your_msg = unhexlify(input("your message(hex): "))
    if len(your_msg) < 10 or b"ochazuke" in your_msg:
        print("byebye")
        exit()
    your_sig = sign(d, your_msg)
    print("your signature:", your_sig)
 
    sig = input("please give me ochazuke's signature: ")
    r, s = map(Zn, re.compile("\((\d+), (\d+)\)").findall(sig)[0])
    if verify(public_key, b"ochazuke", (r, s)):
        print("thx!", flag)
    else:
        print("it's not ochazuke :(")
 

일단 생긴 것으로 보아 ECDSA 문제인 것 같고, 요구하는 것은 주어진 메시지에 대한 서명이다.

곡선 자체가 이상한 것 같지도 않고 $G$도 제대로 된 generator 임을 확인할 수 있었다.

그러니 우선 저 ECDSA처럼 생긴 서명 및 verify 과정을 한 번 살펴보자고 생각했다.

일단 sign 과정에서 랜덤성이 정확히 0mg 추가되었고 verify 과정에서 해싱 과정이 하나도 없으니 뭔가 벌써 망했다.

적당한 조건을 만족하는 메시지를 서명 받을 수 있으니, 메시지와 서명의 쌍 하나를 가지고 생각해보자.

sign 알고리즘을 보고, 우리가 여기서 $m, r, s$를 안다고 가정하자. 

$z$는 단순히 bytes_to_long을 때린 결과이므로 계산할 수 있다.

$k$는 계산할 수는 없으나, 계산할 수 있는 값 $kt$가 있어 $k = kt \cdot pvk$로 쓸 수 있다. ($pvk$는 비밀키)

이제 $s = (z + r \cdot pvk) / k$라는 식을 보면, 이는 $pvk$에 대한 일차방정식이다. 

그러니 $pvk$를 도출할 수 있고, 이제 서명을 알아서 잘 하면 된다.

HOST = "crypto.kosenctf.com"
PORT = 13005
 
conn = pwnlib.tubes.remote.remote(HOST, PORT)
print(conn.recvline())
conn.send("ffffffffffffffffffff\n")
print(conn.recvline())
 
## (98664527284046924431103876265370791373438293020179316375883642857046660842422 : 51449822108608164116773906593599196539335313713052966364410874461652593273305 : 1)
 
msg = binascii.unhexlify("ffffffffffffffffffff")
r = 98909165505886332260977490746820914928283581853841477470132641900339514121815
s = 86962637426480431206806090924202825437488410614468755585865520420765819501712
 
z = bytes_to_long(msg)
kt = int(sha1(msg).hexdigest(), 16)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
 
## s = (z + r * pvk) / (kt * pvk)
## s * kt * pvk == z + r * pvk
 
pvk = z * inverse(s * kt - r, n) % n
 
print(pvk)
print(bytes_to_long(b'ochazuke'))
 
fr = 98165594340872803797719590291390519389514915039788511532783877037454671871717
fs = 115665584943357876566217145953115265124053121527908701836053048195862894185539
 
mys = "(" + str(fr)  + ", " + str(fs) + ")"
conn.send(mys + "\n")
print(conn.recvline())

sage에서 서명하는 부분은 자명하므로 따로 첨부하지 않았다.