N1CTF 2022 Writeups

發表於 2022-11-07

分類於 CTF

這次在隊伍 隨便啦 解了些 Crypto 方面的題目，因為蠻有趣的所以簡單紀錄一下做法。

Crypto

ezdlp

from Crypto.Util.number import *
from math import prod
from secret import flag

def keygen(pbits,kbits,k):
    p = getPrime(pbits)
    x = [getPrime(kbits + 1) for i in range(k)]
    y = prod(x)
    while 1:
        r = getPrime(pbits - kbits * k)
        q = 2 * y * r + 1
        if isPrime(q):
            return p*q, (p, q, r, x)

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

key = keygen(512, 24, 20)
flag = bytes_to_long(flag)
messages = [getPrime(flag.bit_length()) for i in range(47)] + [flag]
enc = [encrypt(key[0], message) for message in messages]

print(messages[:-1])
print(enc)

這題會先用 $n=pq$ ，其中 $q-1$ 是個 smooth number，然後隨便生成些 $m_i$ 之後給你 $y_i \equiv 65537^{m_i} \pmod{n}$ 的值，然後它並沒給你 $n$ 的值。

首先是要還原 $n$ ，這部分對我來說其實很簡單，因為我不久前才給 ImaginaryCTF 出了個 No modulus，裡面用的概念完全相同，都是用 LLL + gcd 去得到 $n$ XDD。

之後得到 $n$ 之後就是分解 $n$ ，第一眼會覺得 $q-1$ 是 $2^{25}$ smooth 的，但實際上因為 $512-24 \times 20 = 32$ ，所以還會多出一個 $32$ bits 的 factor。而就是這個多出來的 factor 讓我原本寫好的 pollard p-1 跑不出來，變得要去找所有的 $32$ bits prime 才行，但這個在我用 Python 寫的腳本要花上十個小時左右...。(我這邊的方法類似 wiki 上說的 Two-stage variant，取 $B_1=2^{25}, B_2=2^{32}$ )

後來查了些資料才知道說有個叫 gmp-ecm 的神奇 command line 工具有實作 p-1, p+1, ecm，並且支援許多自訂的設定，所以稍微研究了一下之後可以生出這條指令:

echo 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441 | ecm -pm1 33554432 4294967296

然後他很神奇的就在大概 15 秒內就吐出了 prime factor，所以之後只要在 $\mathbf{F}_q$ 下解 DLP 就能得到 flag 了。

from Crypto.Util.number import *
import ast

with open('output.txt') as f:
    msgs = ast.literal_eval(f.readline())
    enc = ast.literal_eval(f.readline())

M = matrix(ZZ, msgs).T.augment(matrix.identity(len(msgs)))
M[:,0] *= 2^1024
M = M.LLL()
print(M[0])
print(M[1])
aa = product([ZZ(x)^y for x,y in zip(enc, M[0][1:])])
bb = product([ZZ(x)^y for x,y in zip(enc, M[1][1:])])
n = gcd(aa.numer() - aa.denom(), bb.numer() - bb.denom())
print(n)

# echo 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441 | ecm -pm1 33554432 4294967296

n = 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441
q = 12980311456459934558628309999285260982188754011593109633858685687007370476504059552729490523256867881534711749584157463076269599380216374688443704196597025947
p = n // q

m = GF(q)(enc[-1]).log(0x10001)
flag = long_to_bytes(int(m))
print(flag)

brand_new_checkin

from Crypto.Util.number import *
from random import getrandbits
from secret import flag

def keygen():
    p = getPrime(512)
    q = getPrime(512)

    n = p * q
    phi = (p-1)*(q-1)

    while True:
        a = getrandbits(1024)
        b = phi + 1 - a

        s = getrandbits(1024)
        t = -s*a * inverse(b, phi) % phi

        if GCD(b, phi) == 1:
            break
    return (s, t, n), (a, b, n)


def enc(m, k):
    s, t, n = k
    r = getrandbits(1024)

    return m * pow(r, s, n) % n, m * pow(r, t, n) % n


pubkey, privkey = keygen()

flag = pow(bytes_to_long(flag), 0x10001, pubkey[2])

c = []
for m in long_to_bytes(flag):
    c1, c2 = enc(m, pubkey)
    c.append((c1, c2))

print(pubkey)
print(c)

這題是基於 CakeCTF 2022 - brand_new_crypto 改的，主要差異在於它在 byte by byte 加密前會先用一般的 RSA 先把 flag 加密過一遍，再來是它取 random 的地方改為使用 Python random 的 getrandbits，且固定使用 1024 bits。

前面的部分就直接用元題的解法來做就好，主要的難點還是在怎麼解 RSA 的部分。因為它 random 的改動所以可以很明顯的看出是要想辦法去回推 MT19937 得到 $a$ 。

首先是可以假想有 $a$ 的情況我們可以做什麼，所以先從 keygen 列出兩條等式:

\begin{aligned} a+b &= \varphi(n)+1 \\ as+bt &\equiv 0 \pmod{\varphi(n)} \end{aligned}

把第一條改寫可以得到:

\begin{aligned} a+b &= 1 \pmod{\varphi(n)} \\ as+bt &\equiv 0 \pmod{\varphi(n)} \end{aligned}

這裡面我們唯一不知道的是 $b$ ，所以自然會想把 $b$ 拿掉，所以第一式乘上 $t$ 之後和第二式相減可得:

at-as \equiv t \pmod{\varphi(n)}

所以可知 $at-as-t$ 是 $\varphi(n)$ 的倍數，RSA 其實也只需要知道 $\varphi(n)$ 就能算出一個能用的 private key $d$ 了，所以只要有 $a$ 我們就能解決這題。

再來是要恢復 random，從 enc 的部分可以知道當 $m$ 已知時可得 $r^s$ 和 $r^t$ ，而這題因為 $\gcd(s,t)=1$ 所以用 common modulus attack 就能獲得 $r$ 。因為每個 $r$ 是 1024 bits，而且這題又提供的大量的 sample 所以直接隨便找個 MT19937 的破解工具來用應該就行了。

......我最初確實是這麼想的，但是實際上在獲得 $r$ 之後遇到的許多困難，才發現說 $r<n$ 並不是一定成立的，而前面的 common modulus attack 得到的其實是 $r \mod{n}$ ，而做些實驗可以方法 $r \mod{n}$ 可能是 $r, r-n, r-2n$ 三者之一。

因為破解 MT19937 需要 624 個 32 bits 的輸出，而 $1024 \div 32 = 32$ ，所以至少要 20 個 $r$ 才夠 ( $20 \times 32 > 624$ )，但是每個 $r$ 都有三種可能，所以一共需要 $3^{20}$ 的 brute force，計算量以 CTF 來說有點太大因此不太可行。

我後來寫了個函數 (solve script 的 try_xx) 會嘗試還原 MT19937 後生成一些輸出，然後和真正的 $r \mod{n}$ 比較看看有多少的 bits 是相同的，然後經過一些實驗發現有些 xx (猜測的輸入)可以得出較高的正確率，所以有機會能利用一些比較好的爆破方法把原本的 3^20 的搜尋空間壓縮。

而我這邊具體使用的方法是一個類似基因演算法 (Genetic Algorithm) 的方法，詳情請見 code，不過這個方法確實是有效幫我破解 MT19937 的，所以後來就隨便將它 reverse 回去之後直接暴力找 $a$ ，然後用前面的方法算出 private key 之後就有 flag 了。

from Crypto.Util.number import *
import ast
from sage.all import xgcd, gcd, matrix, ZZ
import gmpy2


def pow(a, b, c):
    return int(gmpy2.powmod(a, b, c))


with open("output.txt") as f:
    s, t, n = ast.literal_eval(f.readline())
    c = ast.literal_eval(f.readline())


def inverse(x, y):
    return pow(x, -1, y)

# decrypt
flagct = []
for (c1, c2) in c:
    for m in range(1, 256):
        if c1 == c2 == 0:
            flagct.append(0)
            break
        rs = c1 * inverse(m, n) % n
        rt = c2 * inverse(m, n) % n
        if pow(rs, t, n) == pow(rt, s, n):
            flagct.append(m)
            break
    else:
        raise ValueError("???")
    print(bytes(flagct))

# flagct = list(
#     b'\x08EZg\xbf\xa0\xeb\x9d\x81\x01\xa8\x96m\x97\x08I(\xed\xb5iQE\xdb\xf5\x8c\xbdcr!\xe6\xc9\xac\x0c\x16K\xa0\x0fr\xecM\x04\xe6\x87\x0f}9\x94\xcfa\x16\x87\x8f4\xcd\xcb\xa4\x0eq\xc3Q\x16\x928&\xe2\x18C\xafN\x87\xcc\x18\xc2D\x9d\x06\xbd"\xe7\xe8\xb7\x12\xb0\xb8CC\x9aM\xff\x12\x00\x05,\xeeopYC)mI\xb7\x81\xb6\x13\x0e\x8a\xc0\xd7\xd3\xd2\xa9\xe5vg.\xa4\xf3\xaa\x10f\x9c\xa4nS=O\xe9'
# )

# recover r
g, x, y = xgcd(s, t)
assert g == 1
assert x * s + y * t == 1
rrr = []
for m, (c1, c2) in zip(flagct, c):
    try:
        im = inverse(m, n)
        rs = im * c1 % n
        rt = im * c2 % n
        r = pow(rs, x, n) * pow(rt, y, n) % n
        rrr.append(r)
    except:
        break
print(len(rrr))

import sys

sys.path.append("./MT19937-Symbolic-Execution-and-Solver/source")
from MT19937 import MT19937, MT19937_symbolic
from XorSolver import XorSolver
import random

from functools import lru_cache


@lru_cache(maxsize=None)
def split1024(r):
    x = []
    for _ in range(1024 // 32):
        x.append(r & 0xFFFFFFFF)
        r >>= 32
    return x


def clone(rng):
    return MT19937(state=rng.state[:])


def grb1024(rng):
    ss = 0
    for i in range(1024 // 32):
        ss |= rng() << (i * 32)
    return ss



def randgen(n, prob=0.3, prob2=0.05):
    ar = []
    for _ in range(n):
        r = random.random()
        if r < prob2:
            ar.append(2)
        elif r < prob:
            ar.append(1)
        else:
            ar.append(0)
    return ar


def compare(x, y):
    cnt = 0
    for a, b in zip(f"{x:01024b}", f"{y:01024b}"):
        cnt += a == b
    return cnt


def try_xx(xx, n_cmp, return_rng=False):
    # xx: a list of 0, 1, 2
    rtmp = [r + x * n for r, x in zip(rr, xx)]
    data = []
    for r in rtmp:
        data += split1024(r)
    try:
        rng_clone = MT19937(state_from_data=(data, 32))
        # print("gj", xx)
        cr = clone(rng_clone)
        tot = 0
        for j in range(n_cmp):
            lhs = grb1024(cr) % n
            rhs = rrr[baseidx + j]
            cond = lhs == rhs
            cp = compare(lhs, rhs)
            tot += cp
            # print(j, cond, cp)
        # print(tot)
        if return_rng:
            return rng_clone
        return tot
    except Exception as ex:
        # import traceback
        # traceback.print_exc()
        pass


def mutate(xx):
    xx = list(xx)
    v = random.randint(0, 2)
    xx[random.randrange(len(xx))] = v
    return xx


baseidx = 0  # choose a starting index to start searching
rr = rrr[baseidx : baseidx + 20]
xx = [0] * 20
tot = 0
n_cmp = 40
# a shitty searching algorithm inspired by genetic algorithm
# try_xx is some sort of a fitness function
while tot < n_cmp * 1024:
    mut = [mutate(xx) for _ in range(10)] + [randgen(len(xx)) for _ in range(10)]
    res = [(ret, mx) for mx in mut if (ret := try_xx(mx, n_cmp)) is not None]
    res.sort(key=lambda x: x[0], reverse=True)
    # for r, mx in res:
    #     print(r, mx)
    if len(res) >= 1:
        tot, mx = res[0]
        print(tot, mx)
        xx = mx

rng_clone = try_xx(xx, n_cmp, return_rng=True)

# do some santiy check
cr = clone(rng_clone)
print(grb1024(cr) % n, rrr[baseidx])
cr = clone(rng_clone)
print([cr() for _ in range(1024 // 32)], split1024(rrr[baseidx] + xx[0] * n))

rng = clone(rng_clone)
rng.reverse_states(512 * (1024 // 32))
for i in range(512):
    ss = grb1024(rng)
    if s == ss:
        print("good")
        print(hex(s))
        print(hex(ss))
        a = prv
        print(hex(a))
        phik = s * a - t * a + t
        d = inverse(0x10001, phik)
        cc = bytes_to_long(bytes(flagct))
        m = pow(cc, d, n)
        print(long_to_bytes(m))
    prv = ss
# n1ctf{5255840f-9140-4479-950f-a3c03fe7f4cd}

babyecc

from Crypto.Util.number import *
from secret import flag

m = Integer(int.from_bytes(flag, 'big'))

for _ in range(7):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    while 1:
        try:
            a = randint(0,n)
            b = randint(0,n)
            Ep = EllipticCurve(GF(p), [a,b])
            Gp = Ep.lift_x(m) * 2
            Eq = EllipticCurve(GF(q), [a,b])
            Gq = Eq.lift_x(m) * 2
            y = crt([int(Gp[1]),int(Gq[1])],[p,q])
            break
        except Exception as err:
            pass
    print(n, a, b, y)

這題會隨機生成 $n=pq$ 和 $a,b$ 得到一條橢圓曲線 $E: y^2 \equiv x^3+ax+b \pmod{n}$ ，之後取上面一點 $P=(m,?)$ 之後給你 $2P$ 的 y 座標。其中的 $m$ 固定是 flag，一共會重複七次所以有七組 $n,a,b,y$ 。

方法也很簡單，就對每組設 $P$ 的座標為未知數，然後用橢圓曲線的定義可以得到第一條等式，再來用 doubling formula 和它給的 $y$ 又能得到另一條等式，然後用 resultant 把未知的 $P$ 的 y 座標給消除後能得到一個 12 次的多項式 $f_i(x)$ 以 $m$ 為根。

因為有七個，所以可以拿到七組 $f_i(x)$ 和 $n_i$ ，之後利用 CRT 可以得到另一個 $f(x)$ 在 $\mod{N}$ 的情況下以 $m$ 為根，所以用 coppersmith 就能得到 flag。 ( $N=\prod_{i=1}^{7} n_i$ )

CRT 部分可以參考 CakeCTF 2021 - Party Ticket，這題和那題的概念很接近，可以當作是擴展是 hastad broadcast attack

from Crypto.Util.number import *

with open("output.txt") as f:
    ar = []
    for line in f:
        n, a, b, y = map(ZZ, line.strip().split(" "))
        ar.append((n, a, b, y))


def double(x, y, a, b):
    s = (3 * x ^ 2 + a) / (2 * y)
    xr = s ^ 2 - 2 * x
    yr = y + s * (xr - x)
    return xr, yr


P.<mx, my> = QQ[]
eqs = []
for n, a, b, y in ar:
    eq1 = my ^ 2 - (mx ^ 3 + a * mx + b)
    _, yy = double(mx, my, a, b)
    eq2 = (yy - y).numerator()
    f = eq1.sylvester_matrix(eq2, my).det().univariate_polynomial()
    eqs.append(f)

ns = [n for n, a, b, y in ar]
Ti = [crt([1 if nn == n else 0 for nn in ns], ns) for n in ns]

N = product(ns)
ff = sum([f * ti for f, ti in zip(eqs, Ti)])
ff = ff.change_ring(Zmod(N)).monic()
set_verbose(1)
rs = ff.small_roots(epsilon=0.03)
print(rs)
m = int(rs[0])
print(long_to_bytes(m))
# n1ctf{7140f171-5fb5-484d-92f4-9f7ba02c33d0}

Crypto#

ezdlp#

brand_new_checkin#

babyecc#

Crypto

ezdlp

brand_new_checkin

babyecc