[n1ctf 2023] e2W@rmup, e2D1p, e20k

좋은 퀄리티의 문제들이 많았지만 시험기간 이슈로 ctf에 집중하지 못했다. 어려운 문제로 구성되어 있고, 앞으로 이런 문제들을 혼자 풀 정도의 실력을 가지는 것을 목표로 하면 좋을 것 같다.

1. e2W@rmup

유일하게 스스로 해결한 문제이다. (warmup에 LLL이..?)

chall (sage)

import hashlib
import ecdsa
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from secret import flag

def gen():
    curve = ecdsa.NIST256p.generator
    order = curve.order()
    d = randint(1, order-1)
    while d.bit_length() != 256:
        d = randint(1, order-1)
    pubkey = ecdsa.ecdsa.Public_key(curve, curve * d)
    privkey = ecdsa.ecdsa.Private_key(pubkey, d)
    return pubkey, privkey, d

def nonce_gen(msg, d):
    msg_bin = bin(msg)[2:].zfill(256)
    d_bin = bin(d)[2:].zfill(256)
    nonce = int(msg_bin[:128] + d_bin[:128], 2)
    return nonce

def sign(msg, privkey, d):
    msg_hash = bytes_to_long(hashlib.sha256(msg).digest())
    nonce = nonce_gen(msg_hash, d)
    sig = privkey.sign(msg_hash, nonce)
    s, r = sig.s, sig.r
    return s, r

pk, sk, d = gen()
msg = b'welcome to n1ctf2023!'
s, r = sign(msg, sk, d)
print(f's = {s}')
print(f'r = {r}')

m = pad(flag, 16)
aes = AES.new(long_to_bytes(d), mode=AES.MODE_ECB)
cipher = aes.encrypt(m)
print(f'cipher = {cipher}')

secp256r1 curve의 ECDSA에서 nonce 256bit 중 상위 128bit가 주어진 상황이다.
바로 식으로 보자.

여기서 $d$ 를 $(2^{128}a + b)$ 로 나타내면

위와 같이 되므로 LLL을 사용할 수 있다.

exploit code (sage)

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import *

msg = b'welcome to n1ctf2023!'
s = 98064531907276862129345013436610988187051831712632166876574510656675679745081
r = 9821122129422509893435671316433203251343263825232865092134497361752993786340
cipher = b'\xf3#\xff\x17\xdf\xbb\xc0\xc6v\x1bg\xc7\x8a6\xf2\xdf~\x12\xd8]\xc5\x02Ot\x99\x9f\xf7\xf3\x98\xbc\x045\x08\xfb\xce1@e\xbcg[I\xd1\xbf\xf8\xea\n-'
msg_hash = bytes_to_long(hashlib.sha256(msg).digest())

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
E = EllipticCurve(GF(p), [-3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b])
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
order = G.order()

x = 2^128*r - s
y = r
z = msg_hash - s*2^128*(msg_hash//(2^128))

M = matrix([
    [x, 1, 0, 0],
    [y, 0, 1, 0],
    [z, 0, 0, 2^125],
    [order, 0, 0, 0]
])
M[:, 0] *= 2^500
M = M.LLL()

for r in M.rows():
    if abs(r[-1]) == 2^125 and r[1]*r[2] > 0:
        a = abs(r[1])
        b = abs(r[2])

d = a*2^128 + b
print(AES.new(long_to_bytes(d), mode=AES.MODE_ECB).decrypt(cipher).decode())

n1ctf{Wow!__You_bre4k_my_s1gn_chal1enge!!___}

2. e2D1p

이 문제부터가 n1ctf의 본론이라고 할 수 있다.

chall

from Crypto.Util.number import *
import os
FLAG = os.environ.get('FLAG', b'n1ctf{XXXXFAKE_FLAGXXXX}')
assert FLAG[:6] == b'n1ctf{' and FLAG[-1:] == b'}'
FLAG = FLAG[6:-1]


def keygen(nbits):
    while True:
        q = getPrime(nbits)
        if isPrime(2*q+1):
            if pow(0x10001, q, 2*q+1) == 1:
                return 2*q+1

def encrypt(key, message, mask):
    return pow(0x10001, message^mask, key)


p = keygen(512)
flag = bytes_to_long(FLAG)
messages = [getRandomNBitInteger(flag.bit_length()) for i in range(200)]
enc = [encrypt(p, message, flag) for message in messages]

print(f'message = {messages}')
print(f'enc = {enc}')

$m$과 $c ≡ e^{m ⊕ flag} \ (mod \ p)$가 각각 200개가 주어졌다.

leak p

우선 $p$를 구해야 한다. $m, flag$의 $i$번째 비트를 각각 $m_i, f_i$ 라고 하면 $m ⊕ flag$ 의 $i$번째 비트는 $m_i + f_i(-1)^{m_i}2^i$ 가 된다. 또한, $m_i$는 0 또는 1이므로 $(-1)^{m_i} = 1 - 2m_i$ 이다. $f_i$를 모르는 상태이므로, 모든 $m$의 $(-1)^{m_i}$ 합이 0이 되도록 LLL을 사용한다면 $f_i$가 소거되어 $p$의 배수를 구할 수 있다.

mul = 2^1024
M = [[(1-2*int(i))*mul for i in bin(j)[2:].zfill(160)] for j in message]
M = matrix(M).augment(matrix.identity(len(message)))
M = M.LLL()
#print(M[0][:200])
xx = product([ZZ(y) ^ x for x, y in zip(M[0][-200:], enc)])
yy = product([ZZ(y) ^ x for x, y in zip(M[1][-200:], enc)])
p= gcd(xx.numer() - xx.denom(), yy.numer() - yy.denom())
print(p)
#25070940894294854944213724808057610995878580501834029791436842569011975159898869595617649716256078890953233822913946718277574163417715224718477846001735447

당연하게도 M.LLL()의 160번째까지의 column값이 모두 0임을 확인할 수 있다.



$m_i ⊕ f_i$ 는 $m_i=0$일 때, $f_i$이고, $m_i=1$일 때, $1-f_i$가 된다. 따라서 다음의 식이 성립한다.

따라서, 각각의 $m$의 이진수로 구성된 200x159크기의 matrix $M$과 곱해져서 벡터 $(1, 0, 0, ..., 0)$가 되는 벡터 $u$를 구한다면, $flag$의 가장 상위 비트를 leak할 수 있고, 나머지 비트들도 마찬가지이다. 이를 식으로 보자.

라고 했을 때,

시간상의 이유로 적당히 $flag$의 한 글자씩(8비트) leak하였다.

exploit code

from Crypto.Util.number import *
from output import *
from tqdm import trange

q = (p-1)//2

for i in range(len(enc)):
    enc[i] = enc[i]*pow(0x10001, -message[i], p)%p

flag = ""
M = [[((-1)^int(i)) for i in bin(j)[2:].zfill(159)] for j in message]
M = matrix(GF(q), M).T
for i in trange(20):
    if i == 0:
        v = vector(GF(q), [1]*7 + [0]*152)
    else:
        v = vector(GF(q), [0]*8*(i-1) + [0]*7 + [1]*8 + [0]*(159-7-8*i))
    #Mu = v
    u = M.solve_right(v)

    m = 1
    for j in range(len(u)):
        m *= pow(enc[j], u[j], p)
        m %= p
    
    for k in range(256):
        if pow(0x10001, k*2^(152-8*i), p) == m:
            flag += chr(k)
            break

print("n1ctf{" + flag + "}")

n1ctf{s0o0_ezzz_dLLLp%$#@!}

3. e20k

chall (sage)

#!/usr/bin/sage
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
import signal
import random
import os
FLAG = os.environ.get('FLAG', 'n1ctf{XXXXFAKE_FLAGXXXX}')

class ECPrng:
    def __init__(self):
        self.N = self.keygen()
        self.E = EllipticCurve(Zmod(self.N), [3, 7])
        self.bias = random.randint(1, 2^128)
        self.state = None
        print(f"N = {self.N}")
        
    def keygen(self):
        P = getPrime(256)
        while True:
            q = getPrime(256)
            if is_prime(2*q-1):
                Q = 2*q^2-q
                return P*Q
    
    def setState(self, x0, y0):
        self.state = self.E(x0, y0)
    
    def next(self):
        self.state = 4*self.state
        return int(self.state.xy()[0])+self.bias

def v2l(v):
    tp = []
    for item in v:
        tp.append(item.list())
    return tp

def Sample(eta, num, signal=0):
    if signal:
        random.seed(prng.next())
    s = []
    for _ in range(num):
        if random.random() < eta:
            s.append(1)
        else:
            s.append(0)
    return Rq(s)

class P:
    def __init__(self, A, s, t):
        self.A = A
        self.s = s
        self.t = t
        self.y = None
    
    def generateCommit(self, Verifier):
        self.y = vector(Rq, [Sample(0.3, N, 1) for _ in range(m)])
        w = self.A * self.y
        Verifier.w = w
        print(f"w = {w.list()}")
        
    def generateProof(self, Verifier, c):
        z = self.s*c + self.y
        print(f"z = {v2l(z)}")
        Verifier.verifyProof(z)

class V:
    def __init__(self, A, t):
        self.A = A
        self.t = t
        self.w = None
        self.c = None
        
    def challenge(self, Prover):
        self.c = Sample(0.3, N)
        print(f"c = {self.c.list()}")
        Prover.generateProof(self, self.c)
        
    def verifyProof(self, z):
        if self.A*z == self.t*self.c + self.w:
            return True
        return False

def Protocol(A, secret, t):
    prover = P(A, secret, t)
    verifier = V(A, t)
    prover.generateCommit(verifier)
    verifier.challenge(prover)

if __name__ == "__main__":
    try:
        signal.alarm(120)
        print("ECPRNG init ...")
        prng = ECPrng()
        x0, y0 = input("PLZ SET PRNG SEED > ").split(',')
        prng.setState(int(x0), int(y0))
        N, q, m = (256, 4197821, 15)
        PRq.<a> = PolynomialRing(Zmod(q))
        Rq = PRq.quotient(a^N + 1, 'x')
        A = vector(Rq, [Rq.random_element() for _ in range(m)])
        secret = vector(Rq, [Sample(0.3, N) for _ in range(m)])
        t = A*secret
        print(f"A = {v2l(A)}")
        print(f"t = {t.list()}")
        Protocol(A, secret, t)
        cipher = AES.new(md5(str(secret).encode()).digest(), mode=AES.MODE_ECB)
        print(f"ct = {cipher.encrypt(pad(FLAG.encode(), 16)).hex()}")
    except:
        print("error!")

$N = p(2q^2-q)$ 인 $N$이 주어지고, $N$을 모듈러로 하는 타원 곡선의 한 점을 입력해야 한다. 그 뒤, 특정한 protocol을 거쳐 secret을 암호화한 결과를 보여준다.

leak n

큰 소수들의 곱으로 이루어진 $N$을 모듈러로 하는 타원곡선 위의 한 점을 알아내기 위해서는 반드시 $N$을 소인수분해 해야 한다. 여기서 또 imginary ctf에 나왔던 sus문제와 유사하게 풀 수 있다. $2N$은 $p * 2q * (2q-1)$ 이므로 $order$가 $(2q-1)^2-1$ 인 $ax + b$ 꼴의 방정식을 $2n$제곱하면 확률적으로 일차항의 계수가 $2q-1$의 배수가 됨을 기대할 수 있다.

R = PolynomialRing(Zmod(n), "x")
while True:
    qr = R.quotient_ring(R.random_element(2))
    res = gcd(int(list(qr.random_element() ^ (2*n))[1]), n)
    if res > 2:
        q = (res+1)//2
        Q = (2*q-1)*q
        P = n//Q
        assert P*Q == n
        break

여기까지는 혼자 했지만, 그 뒤의 과정은 못했다..

이 뒤의 과정은 크게 유의미한 것 같지 않아서 그냥 넘어가겠다.(+사실 다시 보기 귀찮음.)