N1CTF 2022 Writeups

發表於 分類於

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

Crypto

ezdlp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)

這題會先用 ，其中 是個 smooth number，然後隨便生成些 之後給你 的值，然後它並沒給你 的值。

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

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

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

1
echo 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441 | ecm -pm1 33554432 4294967296

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

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
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

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
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 得到 。

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

把第一條改寫可以得到:

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

所以可知 是 的倍數，RSA 其實也只需要知道 就能算出一個能用的 private key 了，所以只要有 我們就能解決這題。

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

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

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

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

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

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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)

這題會隨機生成 和 得到一條橢圓曲線 ，之後取上面一點 之後給你 的 y 座標。其中的 固定是 flag，一共會重複七次所以有七組 。

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

因為有七個，所以可以拿到七組 和 ，之後利用 CRT 可以得到另一個 在 的情況下以 為根，所以用 coppersmith 就能得到 flag。 ()

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

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
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}