Codegate CTF Preliminaries 2024 - Babylogin (crypto)
This challenge is based on a typical invalid curve attack. The login handler has the following snippet:
// pw is user password (bytes)
Gx := new(big.Int).SetBytes(pw[:32])
Gy := new(big.Int).SetBytes(pw[32:64])
ct, hmac_in := pw[64:length-32], pw[length-32:]
key1, key2 := KDF(Gx, Gy, SERVER_SECRET_KEY)
hmac := hmac.New(sha256.New, key2)
hmac.Write(pw[:length-32])
tag := hmac.Sum(nil)
if subtle.ConstantTimeCompare(tag, hmac_in) != 1 {
fmt.Println("Unauthorized")
return
}
...
func KDF(Gx, Gy *big.Int, serverPriv []byte) ([]byte, []byte) {
xx, yy := elliptic.P256().ScalarMult(Gx, Gy, serverPriv)
key := pad(xx.Bytes(), 32)
return key[:16], key[16:32]
}
We can see that KDF simply multiplies user-given point $G$ by the secret scalar (key - which we need to find in order to get the flag).
Invalid curve/point attack
Turns out the used version of Go in the challenge is not checking that the given point is on the expected curve (NIST's P-256 curve). Further investigation suggests that the library is using optimized Jacobian arithmetic relying on the curve's $a_4$ coefficient being equal to 3: $y^2 = x^3 - 3x + a_6$. This arithmetic is independent of the other coefficient $a_6$.
Therefore, we can send points $(G_x, G_y)$ being on other curves with arbitrary $a_6 = G_y^2 - G_x^3 + 3G_x$. To reiterate, the arithmetic formulas used in Go are independent of the coefficient $a_6$, but the point's order does depend on it. This allows us to send points of low order, for which we can guess the secret key. The hmac check routine can be used to test our guesses. After recovering the secret modulo many small orders, we can recover the full secret using the CRT. To sum up, we have the following process:
- (Precomputation) find coefficients $a_6$ for which the curve $y^2 = x^3 - 3x + a_6$ has points of low order. Record those points and orders.
- For each low point order $d$, send $d-1$ guesses to the server. The server confirms the right guess yielding the remainder of the secret scalar modulo $d$.
- Recover the full secret using CRT.
Sign problem
Unfortunately, the approach above does not apply directly to the challenge. The problem is that the KDF only depends on the $x$-coordinate of the output. Therefore, in step 2, both $s \mod{d}$ and $-s \mod{d}$ will be confirmed by the server (where $s$ is the secret scalar). Having two candidate per modulo seems to create a problem. After discussions at the Codegate's discord server after the competition, it turned out that there are at least 4 valid solutions to this problem! I briefly mention all of them.
Method 1: Bruteforce
The most straightforward method is to bruteforce all the signs. This suggests to use bigger moduli to reduce their number. For the 256-bit secret scalar, using moduli around 2000 leads to about 24 bits to bruteforce, which is doable online (as was needed in the challenge). Here, we would need to recover slightly more than 256 bit in total to be able to distinguish correct sign guesses (the secret scalar should be less than 256 bits).
Method 2: CRT-LLL (suggested by Joseph)
Since CRT is linear in the remainders and we are looking for the shortest CRT output, it is natural to apply LLL to solve this problem. In order to ensure effectiveness of LLL, we still need to recover quite more bits (350 or more) before applying the method. I provide Joseph's snippet for completeness:
x_size = 256
x = getrandbits(x_size)
Ps = Primes()[50:100]
Ks = [(1 - 2*getrandbits(1)) * x % p for p in Ps]
N = prod(Ps)
b = N.bit_length()
print(b)
l = len(Ps)
Qs = [N // p for p in Ps]
T = [int(pow(Qs[i], -1, Ps[i])) * Qs[i] for i in range(l)]
KT = [k * T[i] for i, k in enumerate(Ks)]
M = Matrix([[N] + [0] * l])
M = M.stack(Matrix.column([KT]).augment(identity_matrix(l)))
Q = diagonal_matrix([2**(b - x_size)] + [2**(b-1)] * l)
M = (M * Q).LLL() / Q
print(M[0])
print(x)
427 (-12416205178812424764995462935419370761012095661412835501811553587457119088316, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1) 12416205178812424764995462935419370761012095661412835501811553587457119088316
Method 3: CRT of the square (suggested by rbtree, also radix security GSM report)
A very elegant approach is to eliminate the signs by squaring the secret and the remainders. Indeed, the remainder of the squared secret is the same as the squared remainder of the secret: $$ x^2 \mod{d} = (x\mod{d})^2 \mod{d}. $$
However, one has to recover double number of bits (512), since the squared secret has double size.
Method 4: Adding an extra shared factor to all moduli
Another approach is to connect the sign information across the different moduli using another small chosen modulus, e.g. 3. Indeed, if we recover the solution modulo $d_1,d_2,\ldots,d_n$ each up to sign, there are $2^n$ CRT candidates. However, if we recover the solution modulo $3d_1,3d_2,\ldots,3d_n$ each up to sign, we can "align" the signs by checking that they all match modulo 3. Then, we only end up with 2 candidates (since we still don't know the actual sign modulo 3).
Example: recover $x = \pm3 \mod{11}$, $x = \pm 5 \mod{17}$ (4 candidates mod $11\cdot 17$). Then recover $x = \pm14 \mod{33}$ and $x = \pm22 \mod{54}$. Now, $x$ must have same remainder modulo 3 in both cases. Since $14 \mod{3} = 2$ and $22\mod{3}= 1$ they must have opposing signs. So we get two candidates $(14, -22)$ and $(-14, 22)$, modulo 33 and 54 respectively, leading to only 2 solutions modulo $11\cdot17\cdot3$ instead of original 4. This generalizes to $n$ moduli, reducing the $2^n$ initial solutions to just $2$ in just $n$ queries.
The overall approach does not work if the secret is divisible by 3, but then we can either restart the attack or use another small prime. Otherwise, after recovering the secret modulo $d_i$ (up to sign), we can extend the guess to modulo $3d_i$ in one query (just test the remainder modulo 3 : 1 or -1).
Thus, this method seems to have minimal query complexity (comparable to Method 1 - we only need enough to distinguish the right guess, but here we only have 2 guesses instead of $2^{24}$ or so).
I used this method to solve the challenge, so I describe some optimizations and implementation details in sections below.
Mining Elliptic Curves for Invalid Point attacks (with orders of the form 3d)
We need points of order $3d$ for small prime $d$ (say, below 5000). Modulo 3 will be used to determine the sign modulo $d$. This is because we can only recover the remainder up to a sign: every $d$ introduces a factor of 2 into total number of candidates. However, recovering the remainder modulo $3d$ allows to link all $d$'s together since they have to agree on the remainder mod 3. This is possible only when the secret is not divisible by 3 (in this case we simply abort and restart the attack with new secret).
Furthermore, Go uses formulas in jacobian coordinates for the $a_4$-coefficient fixed to -3 (NIST's choice). So, we only have to find such curves with a point of order $3d$ for any $d$ useful for us.
We can use a few optimizations:
- We can quickly check if a curve has 3-torsion by finding roots of its 3rd division polynomial (which has degree 4). Then we can try to lift them to actually get an order-3 point defined over our field $\mathbb{F}_p$.
- The heaviest cost is computing the order of the curve (it seems unavoidable - factoring many low-degree division polynomials would definitely be slower). However, computing an order of a point would trigger factorization of the order - which can be slow. So we avoid this:
- Avoid factoring the order for small factors: do trial division instead for the chosen bound.
- If a curve's order over $\mathbb{F}_p$ is divisible by prime $d$ - then it must have a point of order $d$. We can easily get such point by sampling random points and multiplying them by curve's order divided by $d$. This may fail if the curve has full $d$-torsion, so we skip orders that are divisible by $d^2$ (negligible fraction).
- To get an order-$pd$ point, we simply add an order-$p$ and an order-$d$ point! It is easy to see that the sum has order $pd$, since $p,d$ are coprime.
from sage.all import *
# NIST p256 prime
Fp = GF(2**256 - 2**224 + 2**192 + 2**96-1)
p = 3 # connecting prime
BOUND = 5000 # prime moduli bound
curves = {}
for B in (range(256+1)):
try:
EC = EllipticCurve(Fp, [Fp(-3), Fp(B)])
except ArithmeticError:
continue
# quick check for p-torsion
# and get an order-p point
pxs = EC.division_polynomial(p).roots()
for px, _ in pxs:
try:
Gp = EC.lift_x(px)
break
except ValueError:
continue
else:
continue
# slowest part
o = EC.order()
assert o % p == 0
for d in primes(5, BOUND):
# avoid order d^2 to simplify getting order-d point
if d in curves or o % d or not (o % d**2):
continue
# get an order-d point
while True:
Gd = EC.random_element() * (o // d)
if Gd:
break
# add points to get an order-pd point
V = Gd + Gp
assert V and V * d and V * p and not V * p * d
curves[d] = V
print("a6=%d" % B, "prime order", d, ": current bits total", RR(log(prod(curves), 2)))
save(curves, "curves3")
a6=3 prime order 7 : current bits total 2.80735492205760 a6=3 prime order 13 : current bits total 6.50779464019870 a6=3 prime order 37 : current bits total 11.7172480058276 a6=3 prime order 97 : current bits total 18.3171608480148 a6=3 prime order 113 : current bits total 25.1373398104300 a6=5 prime order 2447 : current bits total 36.3941381965094 a6=8 prime order 5 : current bits total 38.7160662913967 a6=8 prime order 179 : current bits total 46.1998820686610 a6=10 prime order 17 : current bits total 50.2873449099113 a6=10 prime order 251 : current bits total 58.2588884638621 a6=12 prime order 389 : current bits total 66.8625148088483 a6=14 prime order 491 : current bits total 75.8020940231630 a6=14 prime order 3109 : current bits total 87.4043289245040 a6=15 prime order 421 : current bits total 96.1220053475704 a6=15 prime order 823 : current bits total 105.806753967992 a6=15 prime order 1871 : current bits total 116.676347811233 a6=19 prime order 11 : current bits total 120.135779429870 a6=19 prime order 829 : current bits total 129.831007721366 a6=21 prime order 433 : current bits total 138.589230936093 a6=25 prime order 541 : current bits total 147.668715719919 a6=25 prime order 977 : current bits total 157.600930471888 a6=36 prime order 131 : current bits total 164.634353473425 a6=36 prime order 673 : current bits total 174.028816168036 a6=39 prime order 19 : current bits total 178.276743681479 a6=39 prime order 2473 : current bits total 189.548790205869 a6=40 prime order 349 : current bits total 197.995873432079 a6=41 prime order 73 : current bits total 204.185697990959 a6=42 prime order 229 : current bits total 212.024901779056 a6=42 prime order 1373 : current bits total 222.448017689203 a6=43 prime order 31 : current bits total 227.402213999590 a6=43 prime order 1481 : current bits total 237.934569924879 a6=48 prime order 59 : current bits total 243.817212974240 a6=49 prime order 47 : current bits total 249.371801825918 a6=49 prime order 1579 : current bits total 259.996597281778 a6=54 prime order 2659 : current bits total 271.373265343636 a6=61 prime order 607 : current bits total 280.618818049892 a6=61 prime order 4003 : current bits total 292.585683950279 a6=62 prime order 61 : current bits total 298.516421287842 a6=62 prime order 1867 : current bits total 309.382927500068 a6=71 prime order 197 : current bits total 317.004979319525 a6=71 prime order 3319 : current bits total 328.701512233603 a6=72 prime order 29 : current bits total 333.559493228730 a6=76 prime order 67 : current bits total 339.625582419188 a6=86 prime order 1429 : current bits total 350.106372620284 a6=87 prime order 293 : current bits total 358.301129474706 a6=95 prime order 41 : current bits total 363.658681479324 a6=103 prime order 397 : current bits total 372.291676676467 a6=118 prime order 53 : current bits total 378.019597131031 a6=120 prime order 877 : current bits total 387.796030163475 a6=127 prime order 23 : current bits total 392.319592119532 a6=127 prime order 107 : current bits total 399.061059105933 a6=132 prime order 127 : current bits total 406.049743792706 a6=132 prime order 241 : current bits total 413.962633128936 a6=141 prime order 263 : current bits total 422.001552118228 a6=148 prime order 677 : current bits total 431.404564141803 a6=156 prime order 167 : current bits total 438.788268434277 a6=157 prime order 43 : current bits total 444.214533188979 a6=157 prime order 467 : current bits total 453.081811928689 a6=157 prime order 743 : current bits total 462.619030329227 a6=165 prime order 2851 : current bits total 474.096282653165 a6=168 prime order 2017 : current bits total 485.074278021778 a6=172 prime order 79 : current bits total 491.378058769955 a6=175 prime order 83 : current bits total 497.753098201302 a6=175 prime order 157 : current bits total 505.047718950194 a6=175 prime order 1427 : current bits total 515.526488569670 a6=180 prime order 313 : current bits total 523.816507416602 a6=180 prime order 1021 : current bits total 533.812274567480 a6=183 prime order 1091 : current bits total 543.903709953804 a6=183 prime order 1831 : current bits total 554.742126029601 a6=186 prime order 239 : current bits total 562.642992837582 a6=190 prime order 191 : current bits total 570.220421665618 a6=205 prime order 149 : current bits total 577.439590186080 a6=207 prime order 89 : current bits total 583.915323617046 a6=213 prime order 2441 : current bits total 595.168580196827 a6=215 prime order 307 : current bits total 603.430675042197 a6=218 prime order 733 : current bits total 612.948344430331 a6=219 prime order 2969 : current bits total 624.484105808318 a6=219 prime order 3889 : current bits total 636.409289327752 a6=221 prime order 3089 : current bits total 648.002213483380 a6=235 prime order 211 : current bits total 655.723312672087 a6=241 prime order 853 : current bits total 665.459714603405 a6=246 prime order 173 : current bits total 672.894342831042 a6=252 prime order 1741 : current bits total 683.660043318693
print(sorted(curves))
[5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 73, 79, 83, 89, 97, 107, 113, 127, 131, 149, 157, 167, 173, 179, 191, 197, 211, 229, 239, 241, 251, 263, 293, 307, 313, 349, 389, 397, 421, 433, 467, 491, 541, 607, 673, 677, 733, 743, 823, 829, 853, 877, 977, 1021, 1091, 1373, 1427, 1429, 1481, 1579, 1741, 1831, 1867, 1871, 2017, 2441, 2447, 2473, 2659, 2851, 2969, 3089, 3109, 3319, 3889, 4003]
Finishing the challenge
There are two more issues present in the challenge:
- For points of small order, the implementation on the server often returns an empty KDF output. Probably it happens during internal double-and-add computations when a point at infinity is computed (even if the final result is not zero). This is easy to test by 1 query per a modulus, and ignore such moduli.
- The secret scalar in the challenge is 33 bytes but Go reduces it by the curve's order before the multiplication (which is 256 bits). After recovering the 256-bit scalar part using the invalid curve attack, we have to bruteforce the missing byte by doing around 256 queries to the flag page.
Overall, after a lengthy process, we recover the flag.
Implementation
Here we define API to work with the server.
import json, base64, hashlib
def reset_cache():
global QS, CACHE
CACHE = False
QS = []
def reset():
global sock
sock = Sock("127.0.0.1 3124")
print(sock.readline())
reset_cache()
def reset2():
global sock
sock = Sock("43.202.3.171 8081")
sock.read_until("> ")
pref = sock.read_line().strip()
for i in tqdm(range(2**24 * 100)):
s = pref + b"%d" % i
if hashlib.sha256(s).digest()[-3:] == b"\x00\x00\x00":
break
else:
raise
sock.send_line(str(i))
print(sock.readline())
reset_cache()
CACHE = False
QS = []
def query(Path, **kwargs):
kwargs["Path"] = Path
if CACHE:
QS.append(json.dumps(kwargs))
return
sock.sendline(json.dumps(kwargs))
return sock.readline()
def queryGET(Path, **kwargs):
return query(Path, method="GET", **kwargs)
def queryPOST(Path, **kwargs):
return query(Path, method="POST", **kwargs)
def register(Uid):
ret = queryPOST("/register.html", Uid=Uid)
ret = ret.strip().split(b" : ")[1]
return base64.b64decode(ret)
def login(Uid, Pw):
ret1 = queryPOST("/login.html", Uid=Uid, Password=base64.b64encode(Pw).decode())
if CACHE:
return
if b"Hello " in ret1:
ret2 = sock.readline()
ret = ret2.strip().split(b" : ")[1]
return ret1, ret
else:
return ret1, None
We can easily bypass the admin check by using weak separation of uid and role. Registering a username ADMIN_admin
leads to the string ADMIN_admin_GUEST
but the login code only checks the first two tokens after splitting with _
, so we end up with ADMIN
user and admin
role:
reset()
user = "ADMIN_admin"
pw = register(user)
# 32 32 16 32
# Gx Gy pad(uid+role) hmac
len(pw), pw
msg, sess = login("ADMIN", pw)
msg
b'webAPI for my "Baby Login" system\n'
b'> Hello ADMIN! You are logged in as admin!!\n'
This is not very helpful in general, since we really need to recover the server's secret elliptic scalar in order to get the flag.
Secret Remainder Test Oracle
The following code tests whether a given guess for the secret scalar value is correct, modulo the order of the given point. The idea is to login with credentials derived from the guess. Note that Go's ECC has an annoying behaviour that hitting an infinity point during any step in scalar multiplication leads to returned infinity point. We test this case specially in a separate query to avoid useless bruteforcing of the remainder.
import hmac, hashlib
from Crypto.Cipher import AES
def try_point(G, i):
x, y = G.xy()
pay = b"ADMIN_admin_XXX\x01"
if i == 0:
key1 = b"\x00" * 16
key2 = b""
else:
xx = (G*i).xy()[0]
key1 = Bin(xx, 256).bytes[:16]
key2 = Bin(xx, 256).bytes[16:32]
C = AES.new(key1, mode=AES.MODE_ECB)
ct = C.encrypt(pay)
pw = b""
pw += Bin(x, 256).bytes
pw += Bin(y, 256).bytes
pw += ct
tag = hmac.new(key=key2, msg=pw, digestmod=hashlib.sha256).digest()
pw += tag
ret_sess = login("ADMIN", pw)
if CACHE:
return
# True: success
return bool(ret_sess[1])
Now, we load precomputed curves and points of orders $3d$ for small primes $d > 3$.
curves = load("curves3")
print(sorted(curves))
[5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 73, 79, 83, 89, 97, 107, 113, 127, 131, 149, 157, 167, 173, 179, 191, 197, 211, 229, 239, 241, 251, 263, 293, 307, 313, 349, 389, 397, 421, 433, 467, 491, 541, 607, 673, 677, 733, 743, 823, 829, 853, 877, 977, 1021, 1091, 1373, 1427, 1429, 1481, 1579, 1741, 1831, 1867, 1871, 2017, 2441, 2447, 2473, 2659, 2851, 2969, 3089, 3109, 3319, 3889, 4003]
Here is the main loop of the attack. For enough different primes $d$, we try to recover the remainder of the secret modulo $d$. First, we check if an empty output is returned by Go's scalar multiplication (see above). Then, we bruteforce the remainder (in batched communication). Finally, for the first successful $d$ we also check if the secret is divisible by 3, by testing remainder $d$ modulo $3d$. If it is, we restart the attack with another secret.
Note that the remainders are only recovered up to sign, because the server only uses the $x$-coordinate of the result. We will specify this in the next step.
# reset() # local
reset2() # challenge
import time
known_d = {} # known mod d
t0 = time.time()
n_done = 0
n_d = 0
mod = 1
p = 3 # connecting prime
for d, V in sorted(curves.items(), reverse=False):
if d < 200:
# eats latency instead of throughput
continue
if n_done:
print("d", d, "avg query time %.5f" % ((time.time() - t0) / n_done), "avg d time %.5f" % ((time.time() - t0) / n_d))
n_done += 1
n_d += 1
# order-d point, matches zero-key?
# then its triggering zero during scalar mult
# => useless
if try_point(V * p, 0):
print("skip")
continue
# send in batches to overcome long network latency
CACHE = True
QS = []
for i in range(1, d//2+1):
try_point(V * p, i) # order-d point
sock.sendline("\n".join(QS))
CACHE = False
QS = []
# detect the right remainder
ans = None
for i in range(1, d//2+1):
n_done += 1
ret1 = sock.readline()
if b"Hello" in ret1:
ans = i
sock.readline()
assert ans
# try if SECRET % p = 0
# then it's useless and we need to restart
if len(known_d) == 1 and try_point(V, crt([ans, 0], [d, p])):
print("\n\nBAD p detected:", p, "\n\n")
raise RuntimeError("fail")
continue
known_d[d] = ans
mod *= d
print("got solution!", ans, "%", d, "cur log %.1f" % RR(log(mod, 2)))
if mod > 2**264:
break
1%|█▊ | 16063707/1677721600 [00:20<35:53, 771546.56it/s]
b'webAPI for my "Baby Login" system\n' skip d 229 avg query time 0.68933 avg d time 0.68935 got solution! 33 % 229 cur log 7.8 d 239 avg query time 0.01771 avg d time 1.02692 skip d 241 avg query time 0.02328 avg d time 0.90789 got solution! 116 % 241 cur log 15.8 d 251 avg query time 0.01706 avg d time 1.01500 got solution! 125 % 251 cur log 23.7 d 263 avg query time 0.01601 avg d time 1.16566 skip d 293 avg query time 0.01933 avg d time 1.17595 got solution! 48 % 293 cur log 31.9 d 307 avg query time 0.01819 avg d time 1.33063 got solution! 50 % 307 cur log 40.2 d 313 avg query time 0.01605 avg d time 1.33583 skip d 349 avg query time 0.01703 avg d time 1.26190 got solution! 169 % 349 cur log 48.6 d 389 avg query time 0.01507 avg d time 1.26895 got solution! 164 % 389 cur log 57.2 d 397 avg query time 0.01441 avg d time 1.35842 got solution! 34 % 397 cur log 65.9 d 421 avg query time 0.01360 avg d time 1.40033 got solution! 122 % 421 cur log 74.6 d 433 avg query time 0.01316 avg d time 1.46445 got solution! 167 % 433 cur log 83.3 d 467 avg query time 0.01280 avg d time 1.52097 got solution! 174 % 467 cur log 92.2 d 491 avg query time 0.01224 avg d time 1.54914 got solution! 58 % 491 cur log 101.1 d 541 avg query time 0.01193 avg d time 1.59804 got solution! 42 % 541 cur log 110.2 d 607 avg query time 0.01179 avg d time 1.67535 got solution! 284 % 607 cur log 119.5 d 673 avg query time 0.01285 avg d time 1.94072 got solution! 193 % 673 cur log 128.9 d 677 avg query time 0.01243 avg d time 1.99954 got solution! 128 % 677 cur log 138.3 d 733 avg query time 0.01209 avg d time 2.05277 skip d 743 avg query time 0.01237 avg d time 2.00089 got solution! 282 % 743 cur log 147.8 d 823 avg query time 0.01212 avg d time 2.07560 got solution! 311 % 823 cur log 157.5 d 829 avg query time 0.01146 avg d time 2.08351 skip d 853 avg query time 0.01166 avg d time 2.03054 skip d 877 avg query time 0.01185 avg d time 1.98206 got solution! 253 % 877 cur log 167.3 d 977 avg query time 0.01137 avg d time 2.02024 skip d 1021 avg query time 0.01154 avg d time 1.97564 got solution! 315 % 1021 cur log 177.3 d 1091 avg query time 0.01087 avg d time 1.99283 got solution! 397 % 1091 cur log 187.4 d 1373 avg query time 0.01033 avg d time 2.02296 skip d 1427 avg query time 0.01046 avg d time 1.98099 got solution! 647 % 1427 cur log 197.8 d 1429 avg query time 0.00985 avg d time 2.03119 got solution! 179 % 1429 cur log 208.3 d 1481 avg query time 0.00948 avg d time 2.10553 got solution! 562 % 1481 cur log 218.8 d 1579 avg query time 0.00892 avg d time 2.12234 got solution! 233 % 1579 cur log 229.5 d 1741 avg query time 0.00847 avg d time 2.15324 got solution! 394 % 1741 cur log 240.2 d 1831 avg query time 0.00811 avg d time 2.20308 got solution! 659 % 1831 cur log 251.1 d 1867 avg query time 0.00768 avg d time 2.22393 got solution! 197 % 1867 cur log 261.9 d 1871 avg query time 0.00736 avg d time 2.26087 got solution! 478 % 1871 cur log 272.8
Now, we can figure out the signs by aligning them all modulo 3. For this, we check for the remainder agreeing with remainder modulo d and nonzero modulo 3. Since there are only two options (1 and 2 mod 3), we need just 1 query per $d$. Here we use the fact that we have a poing of order $3d$, as requested from the mining procedure.
This has some quantum vibe, like we entangle each mod $d$ with mod 3, and this forces them all to be properly aligned in their sign (while independently, the signs could be arbitrary).
known_dp = {}
p = 3
for d, rem in tqdm(known_d.items()):
V = curves[d]
# assert try_point(V * p, rem)
# i = crt([rem, 0], [d, p])
# assert not try_point(V, i)
i = crt([rem, 1], [d, p])
if try_point(V, i):
known_dp[d*p] = i
else:
i = crt([rem, 2], [d, p])
# assert try_point(V, i)
# align all remainders to same value mod p (==1 mod 3)
known_dp[d*p] = d*p-i
100%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 29/29 [00:17<00:00, 1.63it/s]
We are still left with unknown sign, since we actually don't know the remainder modulo 3. But there are only two candidates overall, and furthermore we can use the fact that the secret is small (256 bits) for testing.
Finally, the server's secret is 33 bytes, but Go (by NIST's recommendation) reduces the scalars modulo the order first. So the remainder we recovered must be below the NIST's curve order. Unfortunately, this means that the most significant byte is simply truncated, but we can still recover it by bruteforce.
# prepare session for bruteforcing the missing byte of the secret
user = "ADMIN_admin"
pw = register(user)
msg, sess = login("ADMIN", pw)
print(msg)
for sign in (-1, 1):
sol = crt(
[rem*sign for mod, rem in known_dp.items()],
[mod for mod, rem in known_dp.items()]
)
if sol < 2**256:
print("sol", sol)
p256order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
num = 2**264//p256order + 1
# could also be batched
# but not really needed
for j in tqdm(range(num)):
test = sol + p256order * j
if test >= 2**264:
break
s = queryPOST("/flag.html", Session=sess.decode(), Secret=base64.b64encode(Bin(test, 256+8).bytes).decode())
if b"Unauthorized" not in s:
print(j, s)
print("Finished..")
b'> Hello ADMIN! You are logged in as admin!!\n' sol 87840242453665073672332009209469007863532939365154747365694665936706803117204
2%|████▋ | 6/257 [00:03<02:37, 1.60it/s]
5 b'> Here is your flag : codegate2024{46fe42789e18b21539f1c7615bf0c1ef9bf7d10b5385e6c60535db78de37dacf9dad64a65f910ef1c82182a94a47805e3402e9}\n' 6 b'\n'
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏| 256/257 [01:43<00:00, 2.48it/s]
Finished..