Abnormal Ellipse

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: ecdh_shared_secret_recovery, padic_lifting, smart_attack, sssa_attack

Summary

Walkthrough of the CUSTOM Crypto Abnormal Ellipse. Task: ECDH key exchange on custom elliptic curve with AES-CBC encryption. Solution: Curve is anomalous (order = p), solved ECDLP via Smart's attack using p-adic lifting to recover private key and decr

Description

Some reason people are using these weird ellipses to do their encryption. But aren't quadratic curves completely broken. Anyways, I caught the data that was being sent along with how they are doing the encryption.

Given: generate.sage (SageMath encryption script implementing ECDH + AES-CBC) and data.txt (public ECDH parameters G, PA, PB, plus AES ciphertext and IV).

The challenge uses a custom elliptic curve over a 256-bit prime field for ECDH key exchange, then encrypts the flag with AES-CBC using the shared secret. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

1. Curve parameters:

   • p = 57896044618658103051097247842201434560310253892815534401457040244646854264811
   • a = 57896044618658103051097247842201434560310253892815534336455328262589759096811
   • b = 6378745995050415640528904257536000

2. Critical observation: The curve is anomalous - its order equals the prime p:

    sage read-only • copy allowed Copy
   E.order() == p  # True!

3. Vulnerability: On anomalous curves, the Elliptic Curve Discrete Logarithm Problem (ECDLP) is trivially solvable in polynomial time using Smart's attack (also called SSSA attack). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

4. The hint: The title "Abnormal Ellipse" directly references "anomalous" curves. The description mentioning "quadratic curves completely broken" also hints at this weakness.

Solution

Step 1: Verify the curve is anomalous

 sage read-only • copy allowed Copy
p = 57896044618658103051097247842201434560310253892815534401457040244646854264811
a = 57896044618658103051097247842201434560310253892815534336455328262589759096811
b = 6378745995050415640528904257536000

E = EllipticCurve(GF(p), [a, b])
print(f"Curve order: {E.order()}")
print(f"Is anomalous: {E.order() == p}")  # True

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step 2: Smart's Attack (SSSA Attack)

Smart's attack exploits the anomalous property by lifting the curve and points from GF(p) to the p-adic numbers Qp, then using the p-adic logarithm to solve the DLP:

 sage read-only • copy allowed Copy
#!/usr/bin/env sage
"""
Smart's attack for anomalous curves.
Solves ECDLP: find k such that Q = k*P when curve order equals p.
"""

def smart_attack(P, Q, p):
    E = P.curve()
    
    # Lift the curve to Qp (p-adic numbers with precision 2)
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0, p)*p for t in E.a_invariants()])
    
    # Lift point P to Qp
    P_Qp = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_lift in P_Qp:
        if GF(p)(P_lift.xy()[1]) == P.xy()[1]:
            break
    
    # Lift point Q to Qp
    Q_Qp = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_lift in Q_Qp:
        if GF(p)(Q_lift.xy()[1]) == Q.xy()[1]:
            break
    
    # Compute p * P_lift and p * Q_lift
    p_adic_P = p * P_lift
    p_adic_Q = p * Q_lift
    
    # Extract coordinates
    x_P, y_P = p_adic_P.xy()
    x_Q, y_Q = p_adic_Q.xy()
    
    # Compute the p-adic logarithm: phi = -x/y
    phi_P = -(x_P / y_P)
    phi_Q = -(x_Q / y_Q)
    
    # The discrete log is the ratio
    k = phi_Q / phi_P
    
    return ZZ(k)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Recover private key dA
dA = smart_attack(G, PA, p)
# dA = 5302515257459728333067206555460709176819601641952986275899160992587299740102

Step 3: Recover shared secret and decrypt

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

# After recovering dA via Smart's attack
dA = 5302515257459728333067206555460709176819601641952986275899160992587299740102

# Compute shared secret: s = x-coordinate of (dA * PB)
shared_point = point_mul(dA, PB, a, p)
s = shared_point[0]
# s = 46862424626771023060842312162194505004189661568357160582950231202292115713415
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Derive AES key
s_bytes = s.to_bytes((s.bit_length() + 7) // 8, 'big')
key = sha256(s_bytes).digest()

# Decrypt
ciphertext = bytes.fromhex("e31e0e638110d1e5c39764af90ac6194c1f9eaabd396703371dc2e6bb2932a18d824d86175ab071943cba7c093ccc6c6")
iv = bytes.fromhex("478876e42be078dceb3aee3a6a8f260f")

cipher = AES.new(key, AES.MODE_CBC, iv=iv)
plaintext = unpad(cipher.decrypt(ciphertext), 16)
print(plaintext.decode())
# gigem{REDACTED}

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering ecdh_shared_secret_recovery, padic_lifting, smart_attack, sssa_attack was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-03-21 • CUSTOM • Abnormal Ellipse • Difficulty: Medium