Twisted Entanglement — HackTheBox

Challenge Description

"In our company, we use Elliptic Curve Cryptography to encrypt our internal communications. Fearing the consequences that the rise of quantum computing will bring, we decided to implement a new key exchange scheme. While researching Quantum Cryptography, we came across a strange concept called entanglement and decided to incorporate it into our server."

We are given a server with two menu options:

1. an elliptic-curve scalar multiplication service,
2. a “quantum” key exchange stage that returns an encrypted flag.

The exploit is a true two-stage chain:

1. recover the server's private key from the broken ECC implementation,
2. use that private key to predict the quantum bases, recover the AES key, and decrypt the flag.

Source Analysis

The relevant code is in twisted_entanglement/server.py and twisted_entanglement/util.py.

Stage 1: ECC oracle

server.py exposes this behavior:

point = parseUserPoint(user_point)
public_key = multiply(private_key, point, E)

The curve parameters are secp256k1-style:

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
a = 0
b = 7

However, util.py implements point addition and doubling using only a and p:

def add(P, Q, a, m):
    ...
    if (P[0] == Q[0] and P[1] == Q[1]):
        S = ((3 * (pow(P[0], 2)) + a) * eea(2 * P[1], m)[1]) % m
    else:
        S = ((Q[1] - P[1]) * eea((Q[0] - P[0]) % m, m)[1]) % m

The implementation never checks whether a user-supplied point lies on the intended curve y^2 = x^3 + 7 (mod p), and it never uses b = 7 in the group law.

So the bug is not a weakness in secp256k1 itself. The actual issue is:

• missing point validation,
• arithmetic that ignores b,
• attacker-controlled scalar multiplication on invalid points.

That is exactly an invalid-curve vulnerability.

Stage 2: quantum key exchange

generateKeys() reseeds Python's PRNG every time with the same private_key:

def generateKeys(basis, private_key):
    seed(private_key)

For each of 256 rounds it:

• generates the server basis from randint(0, 1),
• prepares two entangled qubits,
• measures the server qubit in the random server basis,
• measures the user qubit in the attacker-supplied basis.

The server key is hashed with SHA-256 and used as the AES-ECB key:

q_server_key = bitsToHash(q_server_key)
cipher = AES.new(key, AES.MODE_ECB)

Vulnerability Explanation

1) Why the ECC bug is exploitable

For short Weierstrass curves, the point-addition formulas depend on a, but not explicitly on b. That is normal only if all points are guaranteed to lie on the same valid curve.

Here the server accepts arbitrary coordinates and still runs the formulas. Because there is no membership check, we can submit points from a different curve that shares the same a = 0.

This is the invalid-curve attack surface.

2) Why the singular curve trick works

The strongest choice is the singular cubic:

y^2 = x^3

Take a nonzero point (x, y) on this curve. Since y^2 = x^3, we can write points in a rational parameter t with the map:

\phi(P) = -x / y \pmod p

For this singular curve, the chord-and-tangent law induced by the server formulas corresponds to ordinary multiplication of that parameter:

\phi(P + Q) = \phi(P) + \phi(Q)

So scalar multiplication becomes:

\phi(dP) = d \cdot \phi(P)

If we choose

P = (1, -1 \bmod p)

then P lies on y^2 = x^3 and

\phi(P) = -1 / (-1) = 1

Therefore, for the server response Q = dP:

\phi(Q) = d

and we recover the secret scalar directly as:

d = -Q_x / Q_y \pmod p

This is why one oracle query is enough.

Mathematical Reasoning in Practice

The local exploit uses:

ATTACK_POINT = [1, P - 1]

def phi(point):
    x, y = point
    return (-x * pow(y, -1, P)) % P

The returned point from option 1 is Q = private_key * ATTACK_POINT, so phi(Q) gives the private key immediately.

The live exploit recovered:

3262827136301000405966

which also satisfies the server-side bound private_key < 8748541127929402731638.

Quantum Stage Analysis

The qubit preparation sequence is:

ns.qubits.operate(q1, ns.X)
ns.qubits.operate(q1, ns.H)
ns.qubits.operate(q2, ns.X)
ns.qubits.combine_qubits([q1, q2])
ns.qubits.operate([q1, q2], ns.CX)

This prepares the Bell state:

|\Psi^-\rangle = (|01\rangle - |10\rangle)/\sqrt{2}

This state has perfect anti-correlation when both qubits are measured in the same basis:

• in the standard Z basis,
• in the Hadamard X basis as well.

So the quantum stage is not a probabilistic brute force. Once the private key is known, the attack is deterministic:

1. reproduce the server's 256 random basis choices by reseeding Python random with the recovered private key,
2. submit exactly that basis string,
3. when both sides use the same basis, the returned user bits are the inverse of the server bits,
4. invert the returned bits to recover the server bitstring,
5. hash those 256 bits with SHA-256 to derive the AES key,
6. decrypt the AES-ECB ciphertext.

Because the server reseeds with the same private key on every query, the basis sequence is fully predictable.

Exploit Steps

Step 1: Recover the private key

Send the singular-curve point:

(1, -1 mod p)

The server returns Q = dP. Compute:

d = -Q_x / Q_y \pmod p

Recovered live key:

3262827136301000405966

Step 2: Predict the server basis sequence

solve.py reproduces the sequence with:

def predict_basis(private_key):
    rnd = random.Random(private_key)
    return "".join("Z" if rnd.randint(0, 1) else "X" for _ in range(256))

Step 3: Recover the server quantum bits

Submit the exact predicted basis string to option 2.

The server returns a hex string representing the user measurement bits. Convert that hex to 256 bits and invert each bit, since same-basis measurements on |Psi^-> are anti-correlated.

Step 4: Derive the AES key and decrypt

Hash the recovered 256 server bits with SHA-256, then decrypt the ciphertext with AES-ECB.

solve.py Summary

The local exploit script is solve.py.

It works as follows:

1. defines the singular attack point [1, p-1],
2. queries option 1 and computes phi(Q) to recover the private key,
3. reproduces the server basis sequence with Python's random.Random(private_key),
4. queries option 2 using that exact basis string,
5. converts the returned hex to bits, flips every bit, and hashes the result with SHA-256,
6. decrypts the AES-ECB ciphertext and prints the flag.

The same script also contains a MockOracle self-test path, which was used locally to validate the full exploit chain without the real secret file.

Result

The exploit succeeded locally against the mock oracle and remotely against the live target. The final flag was:

HTB{REDACTED}

Final Flag

HTB{REDACTED}