LostKey

Explanation

The provided code mixes elliptic curve operations with AES encryption. The goal is to figure out how the secret flag was encrypted and how we can recover it.

The script works as follows:

1. An elliptic curve class EC is defined with some unusual parameters. It has:
   • A point addition function add
   • A point multiplication function mul (scalar multiply)
2. A base point G is given explicitly with fixed x and y.
3. A secret scalar n (smaller than 3.8e25, so it’s relatively small compared to the large prime field) is used to compute Gn = n * G.
4. The encrypt function then takes this secret integer n and uses it to derive an AES key:
   • It converts n into a string
   • Hashes it with SHA1
   • Truncates to 16 bytes
   • Uses that as the AES key in CBC mode
5. Finally, it encrypts the flag with that key and outputs the ciphertext and IV.

The challenge output looks something like this:

G = coord(<x>, <y>)
Gn = <some big x coordinate>
Ciphertext: <hex>
IV: <hex>

What’s Going On

• G is the generator.
• n is the secret scalar.
• The public value is Gn (but they only reveal the x-coordinate).
• The AES key is derived directly from the integer n.

So the “hard problem” here is supposed to be: given G and Gn, find n. That’s basically the Elliptic Curve Discrete Logarithm Problem (ECDLP). Normally, this is very hard.

Why It’s Broken

The code includes an assertion:

assert(n < 38685626227668133590597631)

That number is about 2^85. In other words, n is at most 85 bits long. That’s tiny in cryptographic terms.

This makes the discrete log problem completely solvable with a brute-force or baby-step giant-step algorithm, because the search space is only about 2^85 (feasible with optimized algorithms and enough compute).

Exploitation Strategy

1. From the challenge output, we know G and the x-coordinate of Gn. We need to recover n.
2. Use a discrete log algorithm (baby-step giant-step, Pollard’s Rho for ECDLP, or even direct brute-force if n is small enough) to solve for n.
3. Once we have n, we derive the AES key exactly like the script:
   • Convert n to string
   • Hash with SHA1
   • Take the first 16 bytes
4. Decrypt the ciphertext with AES-CBC using that key and the given IV.
5. The plaintext will be the flag.