Blessed — HackTheBox

Description

"In their quest for materials and information, the crew finds themselves facing an unexpected challenge in a city governed by automated robots programmed to shoot non-registered residents on sight. Undeterred, they employ their hacking prowess to infiltrate the city's central control hub, where the robotic overlords oversee the administration of law and order"

A complex three-part cryptographic challenge combining:

1. BLS signatures with aggregation (vulnerable to rogue key attack)
2. EC-LCG (Elliptic Curve Linear Congruential Generator) PRNG with truncated outputs
3. Custom Zero-Knowledge Proof with predictable challenge bits

Goal: Call unveil_secrets with an aggregated BLS signature from ALL verified robots.

Analysis

Server Architecture

The server implements a SuperComputer class managing robots with BLS key pairs:

• 4 robots are pre-created at startup (already verified)
• Available commands: create, join, verify, list, unveil_secrets, exit
• Communication is JSON-based: send {"cmd": "...", ...}, receive JSON response
• To get the flag, ALL robots must be verified and provide an aggregated signature on b'unveil_secrets'

Vulnerability 1: BLS Rogue Key Attack

The server uses FastAggregateVerify without proper proof-of-possession (PoP). This is a classic vulnerability in BLS signature aggregation.

The Attack:

If we know the aggregate of all existing public keys sum(Pk_i), we can craft a malicious public key:

Pk' = sk * G1 - sum(Pk_i)

Where sk is a secret key we control (e.g., sk = 1337).

When all public keys are aggregated:

Pk_agg = sum(Pk_i) + Pk' = sum(Pk_i) + sk*G1 - sum(Pk_i) = sk * G1

Now bls.Sign(1337, b'unveil_secrets') passes FastAggregateVerify against the aggregated public key!

Vulnerability 2: EC-LCG PRNG Weakness

The PRNG uses P-256 curve with the recurrence:

W_{n+1} = W_n + G

The outputs are truncated: only x >> 32 and y >> 32 are revealed as robot IDs. Each create/join call consumes one PRNG output (two values: truncated x and y).

The Attack:

Given 6 consecutive truncated outputs (from 6 robot IDs = 3 full EC points), we recover the full coordinates using LLL lattice reduction.

We set up 7 polynomial equations over GF(p) with 6 unknowns (a1, b1, a2, b2, a3, b3 — the missing 32-bit parts):

1. 3 curve equations (each point must lie on P-256):

   (v_i + b_i)^2 = (u_i + a_i)^3 + a*(u_i + a_i) + b
   

2. 2 X-addition constraints (P_{i+1} = P_i + G, using the addition formula):

   (x_i + x_{i+1} + Gx) * (x_{i+1} - x_i)^2 = (y_{i+1} + y_i)^2
   

   This comes from the EC addition formula: lambda = (y_G - y_i) / (x_G - x_i), then x_{i+1} = lambda^2 - x_i - x_G, rearranged to eliminate the denominator.

3. 2 Y-addition constraints:

   (Gy - y_i) * (x_{i+1} - x_i) = (y_{i+1} + y_i) * (x_i - Gx)
   

Key insight: These are polynomial equations with small unknowns (< 2^32) relative to the modulus p (~2^256). We linearize by treating each monomial as a separate variable using Sage's Sequence.coefficients_monomials(), then build a lattice and apply LLL.

Lattice construction:

A = [I_7 * p | coeff_matrix]
    [0       | I_monomials ]
A[-1,-1] = 2^256
L = A^T.LLL()

The last row of L contains the small unknowns (a1, b1, a2, b2, a3, b3).

Vulnerability 3: ZKP Bypass

The ZKP verification runs 64 rounds. Each round, the server uses next(self.rand) & 1 to choose the challenge bit. The PRNG is the same EC-LCG — each next() call advances the state and outputs one coordinate component.

After cracking the EC-LCG state from step 2, we know the current point W_n. During verification, each next() call produces one coordinate (alternating x and y from successive points). The challenge bit is (coordinate >> 32) & 1.

ZKP Protocol per round:

• We send commitment C (a BLS12-381 G1 point)
• Server picks bit from PRNG:
  • If bit = 1: Server asks for x where C = x * G1 → we must know the discrete log
  • If bit = 0: Server asks for sk_x where C = sk_x * G1 - Pk' → we must know sk + x

By predicting the bit, we prepare the correct response:

• For bit = 1: choose random x, send C = x*G1, reveal x
• For bit = 0: choose random sk_x, send C = sk_x*G1 - Pk', reveal sk_x

Solution

Attack Flow

1. create → get sk, pk, robot_id (5th robot, PRNG output #4)
2. list → get all 5 robot IDs (outputs #0–#4) and public keys
3. Craft rogue key: Pk' = 1337*G1 - sum(Pks)
4. join with rogue pk → get 6th robot ID (output #5)
5. Crack EC-LCG from 6 outputs via LLL → recover W_3 (the 3rd full point)
6. verify → cheat ZKP using predicted PRNG bits
7. unveil_secrets with bls.Sign(1337, b'unveil_secrets') → flag

Full Working Solve Script

#!/usr/bin/env python3
"""
Blessed — HackTheBox Crypto Challenge
BLS Rogue Key Attack + EC-LCG Cracking via LLL + ZKP Bypass

Run: sage -python solve.py HOST:PORT
Requires: SageMath, py-ecc, pwntools
"""

import json

from functools import reduce
from pwn import os, process, sys, remote

from py_ecc.bls.ciphersuites import G2ProofOfPossession as bls
from py_ecc.bls.g2_primitives import G1_to_pubkey, pubkey_to_G1
from py_ecc.bls.point_compression import decompress_G1
from py_ecc.bls.typing import G1Compressed

from py_ecc.optimized_bls12_381.optimized_curve import add, G1, multiply, neg, normalize, Z1

from sage.all import EllipticCurve, GF, identity_matrix, PolynomialRing, Sequence, zero_matrix, ZZ


def get_process():
    if len(sys.argv) == 1:
        return process(['python3', 'crypto_blessed/challenge.py'], level='DEBUG')

    host, port = sys.argv[1].split(':')
    return remote(host, port)


def sr(data):
    io.sendlineafter(b'> ', json.dumps(data).encode())
    return json.loads(io.recvline().decode())


# ============================================================
# P-256 curve setup for EC-LCG
# ============================================================
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
K = GF(p)
a = K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc)
b = K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b)
E = EllipticCurve(K, (a, b))
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
      0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
E.set_order(0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 * 0x1)


def crack_ec_lcg(values):
    """
    Recover full EC-LCG state from 6 truncated outputs.
    
    values: list of 6 integers, each is (coordinate >> 32) << 32
            i.e., the known high bits of alternating x,y coordinates
            [u1, v1, u2, v2, u3, v3] where u_i = x_i & ~0xFFFFFFFF, v_i = y_i & ~0xFFFFFFFF
    
    Returns: the last recovered EC point W3
    """
    assert len(values) == 6
    u1, v1, u2, v2, u3, v3 = values

    # 6 unknowns: the missing low 32 bits of each coordinate
    a1, b1, a2, b2, a3, b3 = PolynomialRing(K, 'a1, b1, a2, b2, a3, b3').gens()

    # Full coordinates: x_i = u_i + a_i, y_i = v_i + b_i

    # 3 curve equations: y_i^2 = x_i^3 + a*x_i + b
    ec1 = (v1 + b1) ** 2 - (u1 + a1) ** 3 - a * (u1 + a1) - b
    ec2 = (v2 + b2) ** 2 - (u2 + a2) ** 3 - a * (u2 + a2) - b
    ec3 = (v3 + b3) ** 2 - (u3 + a3) ** 3 - a * (u3 + a3) - b

    # 2 X-addition constraints: (x_i + x_{i+1} + Gx)(x_{i+1} - x_i)^2 = (y_{i+1} + y_i)^2
    ec4 = ((u1 + a1) + (u2 + a2) + G.x()) * ((u2 + a2) - (u1 + a1)) ** 2 - ((v2 + b2) + (v1 + b1)) ** 2
    ec5 = ((u2 + a2) + (u3 + a3) + G.x()) * ((u3 + a3) - (u2 + a2)) ** 2 - ((v3 + b3) + (v2 + b2)) ** 2

    # 2 Y-addition constraints: (Gy - y_i)(x_{i+1} - x_i) = (y_{i+1} + y_i)(x_i - Gx)
    ec6 = (G.y() - (v1 + b1)) * ((u2 + a2) - (u1 + a1)) - ((v2 + b2) + (v1 + b1)) * ((u1 + a1) - G.x())
    ec7 = (G.y() - (v2 + b2)) * ((u3 + a3) - (u2 + a2)) - ((v3 + b3) + (v2 + b2)) * ((u2 + a2) - G.x())

    # Linearize: treat each monomial as a separate variable
    A, v = Sequence([ec1, ec2, ec3, ec4, ec5, ec6, ec7]).coefficients_monomials(sparse=False)
    A = A.change_ring(ZZ)

    # Build lattice:
    # Top-left: 7x7 identity * p (to reduce mod p)
    # Top-right: coefficient matrix A (7 x num_monomials)
    # Bottom-left: zeros
    # Bottom-right: identity for monomial variables
    A = (identity_matrix(7) * p).augment(A)
    A = A.stack(zero_matrix(len(v), 7).augment(identity_matrix(len(v))))
    A[-1, -1] = 2 ** 256  # Scale constant term to be large

    L = A.T.LLL()

    # The last row should contain our small solution
    assert L[-1][-1] == 2 ** 256
    a1, b1, a2, b2, a3, b3 = L[-1][-7:-1]

    # Verify recovered points lie on the curve
    W1 = E(u1 + a1, v1 + b1)
    W2 = E(u2 + a2, v2 + b2)
    W3 = E(u3 + a3, v3 + b3)

    # Verify addition chain
    assert W2 == W1 + G
    assert W3 == W2 + G

    return W3


# ============================================================
# Main exploit
# ============================================================
io = get_process()

# Step 1: Create a robot (5th robot, PRNG output #4)
res = sr({'cmd': 'create'})
sk = int(res.get('sk'), 16)
robot_id = int(res.get('robot_id'), 16)

# Step 2: List all robots to get IDs and public keys
cmd = 'list'
sig = bls.Sign(sk, cmd.encode())
res = sr({'cmd': cmd, 'robot_id': hex(robot_id), 'sig': sig.hex()})

ids, Pks = [], []
for r in res:
    ids.append(int(r.get('robot_id'), 16))
    Pks.append(decompress_G1(G1Compressed(int(r.get('pk'), 16))))

# Step 3: Craft rogue public key
# Choose sk = 1337, compute Pk' = 1337*G1 - sum(all_Pks)
sk = 1337
cmd = 'unveil_secrets'
pk = bls.SkToPk(sk)
sig = bls.Sign(sk, cmd.encode())
Pk = pubkey_to_G1(pk)

Pk_prime = add(Pk, neg(reduce(add, Pks, Z1)))
pk_prime = G1_to_pubkey(Pk_prime)

# Verify: sum(Pks) + Pk' = sk * G1
assert normalize(add(reduce(add, Pks), Pk_prime)) == normalize(Pk)
io.success('Forged rogue key!')

# Step 4: Join with rogue public key (6th robot, PRNG output #5)
res = sr({'cmd': 'join', 'pk': pk_prime.hex()})
robot_id = int(res.get('robot_id'), 16)
ids.append(robot_id)
assert len(ids) == 6

# Step 5: Crack EC-LCG from 6 truncated outputs
# Robot IDs are (x >> 32) and (y >> 32) interleaved
# Shift left by 32 to get the known high bits
Wn = crack_ec_lcg([i << 32 for i in ids])
io.success('Cracked EC-LCG!')

# Step 6: Cheat ZKP verification
prog = io.progress('Cheating ZKP')
sr({'cmd': 'verify', 'robot_id': hex(robot_id)})

# ZKP has 64 rounds. Each round consumes one PRNG output (one coordinate).
# The PRNG advances: each next() yields one coordinate from the current/next point.
# 64 rounds = 64 next() calls = 32 points worth of coordinates (x,y pairs).
for _ in range(64 // 2):
    Wn += G  # Advance EC-LCG state

    for c in Wn.xy():  # Process x then y coordinate
        challenge_bit = (int(c) >> 32) & 1

        if challenge_bit:
            # Server will ask for x where C = x * G1
            x = int(os.urandom(16).hex(), 16)
            C = multiply(G1, x)
            io.sendlineafter(b'Take a random value x and send me C = x * G1 (hex): ',
                           bytes(G1_to_pubkey(C)).hex().encode())
            io.sendlineafter(b'Give me x (hex): ', hex(x).encode())
        else:
            # Server will ask for (sk + x) where C = sk_x * G1 - Pk'
            sk_x = int(os.urandom(16).hex(), 16)
            C = add(multiply(G1, sk_x), neg(Pk_prime))
            io.sendlineafter(b'Take a random value x and send me C = x * G1 (hex): ',
                           bytes(G1_to_pubkey(C)).hex().encode())
            io.sendlineafter(b'Give me (sk + x) (hex): ', hex(sk_x).encode())

prog.success()

# Step 7: Get flag with forged aggregated signature
res = sr({'cmd': cmd, 'sig': sig.hex()})
sr({'cmd': 'exit'})
io.success(res.get('flag'))

Execution

# Requires SageMath + py-ecc + pwntools
sage -python solve.py HOST:PORT

# Or locally:
sage -python solve.py

Key Learnings

1. BLS aggregation without proof-of-possession enables rogue key attacks — Always require PoP to prevent an attacker from crafting Pk' = sk*G1 - sum(Pks) which collapses the aggregate to a known key.

2. Truncated EC-LCG outputs can be recovered via linearization + LLL when unknowns are small (~32 bits) relative to the modulus (~256 bits). The ratio of unknown bits to modulus bits determines feasibility.

3. The key trick for the lattice: use Sage's Sequence.coefficients_monomials() to automatically linearize polynomial equations, treating each monomial (like a1*b2, a1^2, etc.) as a separate variable. This converts nonlinear polynomial equations into a linear system suitable for LLL.

4. Addition formula constraints: The equations use (x_{i+1} - x_i) form (not (x_i - Gx)) because we express P_{i+1} = P_i + G using the chord between P_i and G. The denominator is cleared by multiplying both sides, yielding polynomial (not rational) equations.

5. ZKP security requires truly unpredictable challenges — a crackable PRNG completely defeats the soundness property. With predicted bits, we can always prepare the "easy" response for each round.

6. PRNG output consumption pattern matters — understanding exactly when and how the PRNG is called (alternating x/y coordinates, one call per ZKP round) is critical for synchronizing the prediction.

References

• 7Rocky's writeup
• Full solve script (7Rocky)
• BLS12-381 For The Rest Of Us
• BLS Signature Aggregation and Rogue Key Attacks
• py_ecc Library