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:

1. (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.
2. 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$.
3. 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:

1. 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$.
2. 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:

1. 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.
2. 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..