Curvy Wurvy - Crypto

Points: Hard | Flag: BCCTF{NOW_7h0s3_4r3_s0m3_curv35} | Solved by: Smothy @ 0xN1umb

what we got

Ed25519 signing server with a custom linear KDF. The server lets you sign arbitrary data with arbitrary UIDs, verify signatures, and gives you a FLAG_UID + flag_sig to work with.

def KDF(uid):
    user_key = MASTER_KEY * uid % p  # p = subgroup order L
    return user_key

So the key derivation is literally MK * uid mod L. thats... not great. every key is a linear function of the master key. if we can figure out MK, we get every key including the flag key.

the solve

step 1: torsion oracle (3-bit leakage)

Ed25519 has cofactor 8, meaning there are order-8 torsion points on the curve. we precompute T8 (a torsion point of order 8) and its multiples.

when we send sign(T8.y, uid) to the server, it computes key * T8 = (key mod 8) * T8. from the y-coordinate of the result, we can determine key mod 8 (up to a sign ambiguity {j, 8-j}).

# precompute torsion table
T8 = compute_T8()
jT8, y_to_j = precompute_jT8(T8)
# y=1       -> key%8 = 0
# y=p-1     -> key%8 = 4
# y=T8.y    -> key%8 in {1,7}
# y=2T8.y   -> key%8 in {2,6}
# y=3T8.y   -> key%8 in {3,5}

3 bits per query. not a lot for a 252-bit secret lol

step 2: why lattice fails

first thing we tried (ngl spent way too long on this): standard Hidden Number Problem lattice attack. build the HNP lattice, BKZ reduce, Babai CVP.

always got 186-bit error. turns out theres a structural short vector (uid_0, uid_1, ..., uid_{n-1}, 8) in the lattice with norm ~2^64 (since UIDs are ~63 bits). this vector exists because 8 * T_i = uid_i (mod L). the CVP distance (~2^251) is 2^186 times the shortest vector. babai cant handle that.

also tried: BKZ with block sizes 10-50, dimensions 85-400, exact babai with python Fraction arithmetic, kannan embedding, projected lattices. all same 186-bit error. boneh-venkatesan theorem says you need ~sqrt(log q) ≈ 16 bits of leakage per query, we only have 3. rip lattice.

step 3: the breakthrough - adaptive interval narrowing

key realization: we can choose our own UIDs (the server accepts any uid for option 2). and the KDF is MK * uid mod L.

for uid = k: key_k = MK * k mod L, and q_k = floor(k * MK / L) is the integer quotient. from key_k mod 8 and MK mod 8, we can determine q_k mod 8. for small k (<=8), q_k < 8 so its fully determined.

the constraint from q_k is: MK in [q_k * L/k, (q_k+1) * L/k). intersecting constraints from multiple k values narrows the interval.

the trick: instead of using consecutive UIDs 1,2,3,...,300 (which only narrows ~14 bits bc most UIDs are redundant), choose UIDs adaptively. after each step, pick the smallest k where the constraint boundary falls inside our current interval, giving us a ~50% cut.

def find_best_k(lo, hi, L):
    width = hi - lo
    k_min = L // width + 1
    # find k near k_min that gives a boundary closest to the middle
    ...

UIDs grow exponentially: ~28, ~56, ~112, ~224, ..., up to ~L. each doubles the denominator. ~300 queries, boom, 252-bit MK recovered.

step 4: flag recovery

with MK recovered:

flag_key = MK * FLAG_UID % L
inv_key = pow(flag_key, -1, L)
Q = (recover_x(flag_sig), flag_sig)  # point from signature
P = inv_key * Q                       # inverse scalar mult
FLAG = P.y.to_bytes(32, 'big')

had to try both MK and L - MK (x-coordinate sign issue), but second one worked.

the numbers

• 317 server queries total
• 183 seconds runtime
• MK = 4747627684408952554495055884313346755842726269957015465592140336813957778804 (252 bits)
• MK mod 8 = 4 (unambiguous from torsion, got lucky there)

flag

BCCTF{NOW_7h0s3_4r3_s0m3_curv35}

smothy out ✌️