MeOwl ECC - Crypto
Points: 50 | Difficulty: Beginner | Flag: 0xfun{n0n_c4n0n1c4l_l1f7s_r_c00l}
Solved by: Smothy @ 0xN1umb
what we got
ECC challenge with a sussy hint:
"Smart's attack is broken on my curve, so I'm safe"
lmao ok buddy. We get chall.py and output.txt with curve params:
- Curve:
y² = x³ + 19 (mod p) - Points P (generator) and Q (public key)
- AES+DES encrypted flag
The goal is find d where Q = d*P then decrypt.
the solve
So the hint literally says "Smart's attack" which is like... the most famous attack on anomalous curves. Anomalous = when curve order equals p exactly.
Checked with SageMath:
E = EllipticCurve(GF(p), [0, 19])
order = E.order()
print(order == p) # True lolbruh. The curve IS anomalous. "broken" my ass
Smart's attack works by lifting points to p-adic numbers (Qp) where discrete log becomes easy. Basically turns a hard problem into division.
def SmartAttack(P, Q, p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0,p)*p for t in E.a_invariants()])
P_Qp = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_qp in P_Qp:
if GF(p)(P_qp.xy()[1]) == P.xy()[1]:
break
Q_Qp = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_qp in Q_Qp:
if GF(p)(Q_qp.xy()[1]) == Q.xy()[1]:
break
p_times_P = p * P_qp
p_times_Q = p * Q_qp
phi_P = -(p_times_P.xy()[0] / p_times_P.xy()[1])
phi_Q = -(p_times_Q.xy()[0] / p_times_Q.xy()[1])
return ZZ(phi_Q / phi_P) % p
d = SmartAttack(P, Q, p)
# d = 797362141196384868007066615792142575269512834174354422840008233995912822094171106431346799Got d, now just reverse the encryption (DES decrypt → AES decrypt):
k = long_to_bytes(d)
aes_key = hashlib.sha256(k + b"MeOwl::AES").digest()[:16]
des_key = hashlib.sha256(k + b"MeOwl::DES").digest()[:8]
c1 = DES.new(des_key, DES.MODE_CBC, iv=des_iv).decrypt(ciphertext)
c1 = unpad(c1, 8)
flag = AES.new(aes_key, AES.MODE_CBC, iv=aes_iv).decrypt(c1)
flag = unpad(flag, 16)flag
0xfun{n0n_c4n0n1c4l_l1f7s_r_c00l}
ngl the flag makes sense now - "non canonical lifts" is literally what Smart's attack uses. The p-adic lift is the non-canonical part. cute
smothy out ✌️